Collision-Aware Evolutionary Algorithm for Multi-Agent Coverage Path Planning
Xiuwen MA, Ting Huang, Weili Liu, Yue‐Jiao Gong · 2024
Multi-agent coverage path planning (MACPP) aims to find the shortest paths for agents to collaboratively accomplish an area coverage task. Most current MACPP studies focus on introducing various area decomposition methods to decouple the MACPP problem into individual single-agent path planning problem. However, these methods often neglect the collisions among agents in the planning process, which may result in agent crashes. In this paper, we introduce a collision-aware evolutionary algorithm to provide a collision-free path set for agents. The proposed algorithm adopts the trapezoidal decomposition to divide the region into convex areas and evenly assigns these areas to agents. Based on the decomposed areas, we propose an interarea visiting order planning method for agents. Within each area, we implement intra-area coverage path planning for each agent. Furthermore, we incorporate collision detection between agents and adjust the paths of conflict agents to prevent collisions. Finally, we conduct experiments with three state-of-the-art approaches in four different environments to verify that the proposed algorithm can effectively complete the task and avoid the collision risk.