Divide Areas based on Area Growing via Wavefront Propagation: a near-optimal multi-robot coverage path planning algorithm for large-scale maps with low computational cost

Abstract Multi-robot coverage path planning (MCPP) is a typical problem in multi-robot applications. Its goal is to decompose and assign coverage tasks, enabling mobile robots to collaboratively perform complete coverage of the map within a short time (referred to as coverage time). The coverage time of MCPP is generally determined by the path lengths of the robots and the number of turns on the paths. Most existing studies focus on only one of the two metrics, and few address the simultaneous optimization of both aspects. In this letter, we propose the Divide Areas based on area Growing via Wavefront Propagation (DAWG) algorithm to solve this problem through a staged co-optimization approach. Specifically, DAWG combines area growing and wavefront propagation to divide the map into equally sized subareas, ensuring equal path lengths. Meanwhile, DAWG incorporates a greedy strategy that reduces computation time by 81% while maintaining turn counts comparable to TMSTC*, a state-of-the-art (SOTA) method that minimizes path turns. Experiments on dozens of large-scale map instances demonstrate that DAWG achieves superior performance in both computation time and path quality compared to existing methods.