CoMAEA: A Collision-Avoiding Multi-Agent Evolutionary Algorithm for Coverage Path Planning
提出了一种新的避碰多智能体覆盖路径规划问题，并设计了进化算法，通过梯形分解和时空避碰机制生成无碰撞路径，平均路径长度减少15.9%，覆盖重叠减少58.1%。
Efficient and safe path planning for multiple autonomous agents, such as unmanned aerial vehicles (UAVs), is essential in many real-world applications. The objective is to coordinate these agents to cover a target area with minimal cost. However, most existing multi-agent coverage path planning (MACPP) methods rely on purely spatial planning and neglect spatio-temporal interactions among agents, which often result in unsafe paths and a high risk of inter-agent collisions during execution. To address this challenge, we propose a new problem formulation, termed collision-aware MACPP (CaMACPP), which incorporates both spatial coverage efficiency and collision avoidance. To solve this problem, we introduce an efficient multi-agent evolutionary algorithm to minimize costs while avoiding collisions. The algorithm first introduces a trapezoidal decomposition strategy to partition complex environments into convex subareas. Then, a cooperative evolutionary algorithm is designed to optimize the inter-area visiting orders for multiple agents and the intra-area coverage modes assigned to each agent. Next, a spatio-temporal collision avoidance mechanism is incorporated to detect and resolve conflicts between agent paths. The proposed algorithm is extensively evaluated against the state-of-the-art MACPP methods to demonstrate its effectiveness in generating collision-free paths with minimal total cost. The results show that it achieves zero collisions in all tested scenarios, reduces the average path length by 15.9%, and decreases coverage overlap by 58.1%.