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

arXiv: https://arxiv.org/abs/2411.01707 · HTML: https://mlsanity.com/paper/2411.01707/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 75 references that are in the map.
- First posted on arXiv 3 Nov 2024.

## Builds on (most cited first, 19 of 19)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks](https://mlsanity.com/paper/1705.10868/) (2017)
- [Lifelong Path Planning with Kinematic Constraints for Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/1812.06355/) (2018)
- [Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering](https://mlsanity.com/paper/2009.05161/) (2020)
- [Multi-Goal Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/2208.01223/) (2022)
- [MSTC*:Multi-robot Coverage Path Planning under Physical Constraints](https://mlsanity.com/paper/2108.04632/) (2021)
- [MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding](https://mlsanity.com/paper/2103.09979/) (2021)
- [Efficient Multi-Robot Coverage of a Known Environment](https://mlsanity.com/paper/1808.02541/) (2018)
- [Graph-Based Multi-Robot Path Finding and Planning](https://mlsanity.com/paper/2206.11319/) (2022)
- [Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding](https://mlsanity.com/paper/2208.01222/) (2022)
- [Mixed Integer Programming for Time-Optimal Multi-Robot Coverage Path Planning with Efficient Heuristics](https://mlsanity.com/paper/2306.17609/) (2023)
- [Learning to Coordinate for a Worker-Station Multi-robot System in Planar Coverage Tasks](https://mlsanity.com/paper/2208.02993/) (2022)
- [Large-Scale Multi-Robot Coverage Path Planning via Local Search](https://mlsanity.com/paper/2312.10797/) (2023)
- [MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem](https://mlsanity.com/paper/2404.19518/) (2024)
- [Optimal Partitioning of Non-Convex Environments for Minimum Turn Coverage Planning](https://mlsanity.com/paper/2109.08185/) (2021)
- [Multi-Robot Connected Fermat Spiral Coverage](https://mlsanity.com/paper/2403.13311/) (2024)
- [Risk-Aware Coverage Path Planning for Lunar Micro-Rovers Leveraging Global and Local Environmental Data](https://mlsanity.com/paper/2404.18721/) (2024)

## Built on by (most cited first, 5 of 5)

- [Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2505.19219/) (2025)
- [GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets](https://mlsanity.com/paper/2511.06471/) (2025)
- [Priority-Aware Multi-Robot Coverage Path Planning](https://mlsanity.com/paper/2601.00580/) (2026)
- [CREST: Constraint-Release Execution for Multi-Robot Warehouse Shelf Rearrangement](https://mlsanity.com/paper/2603.28803/) (2026)
- [Coverage Path Planning: Classical Foundations, Recent Advances, and Future Directions](https://mlsanity.com/paper/2607.10649/) (2026)

## Abstract (arXiv)

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 H and then employ the Spanning Tree Coverage (STC) paradigm to generate paths on G, making them inapplicable to grids with partially obstructed 2x2 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 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 256x256 within minutes of runtime. Validation with physical robots confirms the feasibility of our solutions under real-world conditions.