Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction
Jingtao Tang, Z. Morley Mao, Hang Ma · IEEE Transactions on Robotics · 2025
We study Multi-Robot Coverage Path Planning (MCPP) on a 4-neighbor 2D grid$G$, which aims to compute paths for multiple robots to cover all cells of$G$. Traditional approaches are limited as they first compute coverage trees on a quadrant coarsened grid$\mathcal {H}$and then employ the Spanning Tree Coverage (STC) paradigm to generate paths on$G$, making them inapplicable to grids with partially obstructed$2 \times 2$blocks. To address this limitation, we reformulate the problem directly on$G$, revolutionizing grid-based MCPP solving and establishing new NP-hardness results. We introduce Extended-STC (ESTC), a novel paradigm that extends STC to ensure complete coverage with bounded suboptimality, even when$\mathcal {H}$includes partially obstructed blocks. Furthermore, we present LS-MCPP, a new algorithmic framework that integrates ESTC with three novel types of neighborhood operators within a local search strategy to optimize coverage paths directly on$G$. Unlike prior grid-based MCPP work, our approach also incorporates a versatile post-processing procedure that applies Multi-Agent Path Finding (MAPF) techniques to MCPP for the first time, enabling a fusion of these two important fields in multi-robot coordination. This procedure effectively resolves inter-robot conflicts and accommodates turning costs by solving a MAPF variant, making our MCPP solutions more practical for real-world applications. Extensive experiments demonstrate that our approach significantly improves solution quality and efficiency, managing up to 100 robots on grids as large as$256 \times 256$within minutes of runtime. Validation with physical robots confirms the feasibility of our solutions under real-world conditions.