A Dynamic Cooperative Multi-Agent Online Coverage Path Planning Algorithm

Abstract

This paper proposes a novel approach for finding an optimized solution for the online coverage path planning in unknown environments problem employing cooperative multi robotic agents. The suggested approach lessens the time required for solving the coverage problem by using cooperative multiple robotic agents working together to achieve enhanced complete coverage while sustaining minimum time, and the minimum number of repeated cells and respecting the service time. The distributed multi-agent planning with coordination process is optimized using dynamic programming with a rolling horizon limited look-ahead policy for online capability. In addition to expanding the usual single-agent action tree to hold a multi-agent scheme for possible collision-free sub-trajectories generation con-cerning quality, repetitions count, length per single agent to plan and execute cooperatively for covering a given unknown sur-roundings. Regarding coverage optimization, we utilize a multi-objective optimization genetic based algorithm with uniform cost search for the single-agent coverage sub-trajectory planning. In multi-agent-based systems, communication introduces overhead and have a direct influence on the system's robustness. Hence, we proposed a voting and coalition formation based on the K-means clustering algorithm for minimizing the communication henceforth improving the system's robustness. Simulation results highlight an enhancement regarding speeding up the complete coverage process compared to optimum single-agent approaches while advancing near-optimal utilization and efficiency minimizing repetitions in different unknown environments.