Abstract
Multi-robot coverage path planning (MCPP) is a critical task in robotics, aiming to find paths for a fleet of robots to visit every point in a given area while minimizing the total time taken (makespan). Traditional methods based on Spanning Tree Coverage (STC) often rely on coarse grid abstractions that lead to incomplete coverage and suboptimal paths. This paper introduces LS-MCPP, a local search framework that operates on fine-grained decomposed grids. By employing Extended-STC (ESTC) and specialized boundary-editing operators, LS-MCPP significantly improves path quality and computational efficiency, outperforming state-of-the-art baselines by up to 35% in makespan.
Introduction
Coverage Path Planning (CPP) is essential for applications ranging from autonomous vacuuming to large-scale search-and-rescue. In the multi-robot variant (MCPP), the challenge is to partition the workload among robots to minimize the makespan—the time the last robot finishes its task.
Most existing MCPP algorithms utilize the Spanning Tree Coverage (STC) paradigm. STC simplifies the environment by grouping 2x2 "fine" grid cells into "coarse" terrain vertices. A spanning tree is constructed on these coarse vertices, and robots follow paths circumnavigating the tree edges. While computationally efficient, this abstraction has significant drawbacks: it often fails in cluttered environments where 2x2 blocks are partially obstructed, and it ignores a vast search space of potential paths on the fine grid.
The LS-MCPP Framework
LS-MCPP addresses these limitations by performing local search directly on the fine-grained decomposed graph $D$. The framework iteratively refines the assignment of cells to robots to balance the load and shorten paths.
Extended-STC (ESTC)
The core of the path generation is the Extended-STC (ESTC) algorithm. Unlike standard STC, ESTC is designed to handle "incomplete" vertices—coarse blocks where some sub-cells are blocked by obstacles. It uses path-deformation rules and a weight-prioritization scheme to ensure full coverage without unnecessary re-visitation of cells.
Boundary Editing and Local Search
To optimize the makespan, LS-MCPP employs three primary boundary-editing operators:
- Grow: A robot expands its territory into adjacent cells.
- Deduplicate: Redundant path segments (like U-turns) are removed.
- Exchange: Cells are transferred from a robot with a longer path to one with a shorter path.
The algorithm uses a metaheuristic similar to Simulated Annealing to select these operators. It prioritizes "heavy" subgraphs (robots with long paths) for reduction and "light" subgraphs for expansion, effectively balancing the workload across the fleet.
Experimental Results
The authors evaluated LS-MCPP on standard benchmarks and new large-scale instances derived from the Moving AI 2D pathfinding dataset, including maps of Shanghai and New York with over 12,000 vertices.
Key findings include:
- Path Quality: LS-MCPP reduced makespan by up to 35.7% compared to the leading MFC algorithm.
- Efficiency: The local search converges in minutes on maps where optimal Mixed Integer Programming (MIP) solvers would take hours or fail to find a solution.
- Scalability: The method successfully handled scenarios with up to 32 robots on massive grids, demonstrating its viability for real-world large-scale deployments.
Conclusion
LS-MCPP represents a significant step forward in multi-robot coverage. By moving away from coarse grid constraints and utilizing local search with the ESTC engine, it provides a robust and scalable solution for complex, cluttered environments. Future work will explore integrating dynamic collision avoidance and using machine learning to further optimize heuristic selection.
Summary updated