# Scalable Coverage Path Planning of Multi-Robot Teams for Monitoring Non-Convex Areas

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Mar 2021.

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

- [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)
- [Online Concurrent Multi-Robot Coverage Path Planning](https://mlsanity.com/paper/2403.10460/) (2024)
- [Multi-Robot Connected Fermat Spiral Coverage](https://mlsanity.com/paper/2403.13311/) (2024)
- [Coverage Path Planning: Classical Foundations, Recent Advances, and Future Directions](https://mlsanity.com/paper/2607.10649/) (2026)

## Abstract (arXiv)

This paper presents a novel multi-robot coverage path planning (CPP) algorithm - aka SCoPP - that provides a time-efficient solution, with workload balanced plans for each robot in a multi-robot system, based on their initial states. This algorithm accounts for discontinuities (e.g., no-fly zones) in a specified area of interest, and provides an optimized ordered list of way-points per robot using a discrete, computationally efficient, nearest neighbor path planning algorithm. This algorithm involves five main stages, which include the transformation of the user's input as a set of vertices in geographical coordinates, discretization, load-balanced partitioning, auctioning of conflict cells in a discretized space, and a path planning procedure. To evaluate the effectiveness of the primary algorithm, a multi-unmanned aerial vehicle (UAV) post-flood assessment application is considered, and the performance of the algorithm is tested on three test maps of varying sizes. Additionally, our method is compared with a state-of-the-art method created by Guasella et al. Further analyses on scalability and computational time of SCoPP are conducted. The results show that SCoPP is superior in terms of mission completion time; its computing time is found to be under 2 mins for a large map covered by a 150-robot team, thereby demonstrating its computationally scalability.