Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction

In this article, we study multirobot coverage path planning (MCPP) on a four-neighbor 2-D grid <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula>, which aims to compute paths for multiple robots to cover all cells of <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula>. Traditional approaches are limited as they first compute coverage trees on a quadrant coarsened grid <inline-formula><tex-math notation="LaTeX">$\mathcal {H}$</tex-math></inline-formula> and then employ the spanning tree coverage (STC) paradigm to generate paths on <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula>, making them inapplicable to grids with partially obstructed <inline-formula><tex-math notation="LaTeX">$2 \times 2$</tex-math></inline-formula> blocks. To address this limitation, we reformulate the problem directly on <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula>, 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 <inline-formula><tex-math notation="LaTeX">$\mathcal {H}$</tex-math></inline-formula> 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 <inline-formula><tex-math notation="LaTeX">$G$</tex-math></inline-formula>. Unlike prior grid-based MCPP work, our approach also incorporates a versatile postprocessing procedure that applies multiagent path finding (MAPF) techniques to MCPP for the first time, enabling a fusion of these two important fields in multirobot coordination. This procedure effectively resolves inter-robot conflicts and accommodates turning costs by solving an 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 <inline-formula><tex-math notation="LaTeX">$\text{256} \times \text{256}$</tex-math></inline-formula> within minutes of runtime. Validation with physical robots confirms the feasibility of our solutions under real-world conditions.