# Large-Scale Multi-Robot Coverage Path Planning via Local Search

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 23 references that are in the map.
- First posted on arXiv 17 Dec 2023.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [MSTC*:Multi-robot Coverage Path Planning under Physical Constraints](https://mlsanity.com/paper/2108.04632/) (2021)
- [Efficient Multi-Robot Coverage of a Known Environment](https://mlsanity.com/paper/1808.02541/) (2018)
- [Scalable Coverage Path Planning of Multi-Robot Teams for Monitoring Non-Convex Areas](https://mlsanity.com/paper/2103.14709/) (2021)
- [Multi-UAV Coverage Planning with Limited Endurance in Disaster Environment](https://mlsanity.com/paper/2201.10150/) (2022)
- [Mixed Integer Programming for Time-Optimal Multi-Robot Coverage Path Planning with Efficient Heuristics](https://mlsanity.com/paper/2306.17609/) (2023)

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

- [Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction](https://mlsanity.com/paper/2411.01707/) (2024)
- [Multi-Robot Connected Fermat Spiral Coverage](https://mlsanity.com/paper/2403.13311/) (2024)
- [Semantic Map Sharing and Capability-Aware Coverage Planning for AI-Native 6G Robotic Coordination](https://mlsanity.com/paper/2609.37666/) (2026)

## Abstract (arXiv)

We study graph-based Multi-Robot Coverage Path Planning (MCPP) that aims to compute coverage paths for multiple robots to cover all vertices of a given 2D grid terrain graph G. Existing graph-based MCPP algorithms first compute a tree cover on G -- a forest of multiple trees that cover all vertices -- and then employ the Spanning Tree Coverage (STC) paradigm to generate coverage paths on the decomposed graph D of the terrain graph G by circumnavigating the edges of the computed trees, aiming to optimize the makespan (i.e., the maximum coverage path cost among all robots). In this paper, we take a different approach by exploring how to systematically search for good coverage paths directly on D. We introduce a new algorithmic framework, called LS-MCPP, which leverages a local search to operate directly on D. We propose a novel standalone paradigm, Extended-STC (ESTC), that extends STC to achieve complete coverage for MCPP on any decomposed graphs, even those resulting from incomplete terrain graphs. Furthermore, we demonstrate how to integrate ESTC with three novel types of neighborhood operators into our framework to effectively guide its search process. Our extensive experiments demonstrate the effectiveness of LS-MCPP, consistently improving the initial solution returned by two state-of-the-art baseline algorithms that compute suboptimal tree covers on G, with a notable reduction in makespan by up to 35.7% and 30.3%, respectively. Moreover, LS-MCPP consistently matches or surpasses the results of optimal tree cover computation, achieving these outcomes with orders of magnitude faster runtime, thereby showcasing its significant benefits for large-scale real-world coverage tasks.