# Online Concurrent Multi-Robot Coverage Path Planning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 37 references that are in the map.
- First posted on arXiv 15 Mar 2024.

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

- [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-robot Dubins Coverage with Autonomous Surface Vehicles](https://mlsanity.com/paper/1808.02552/) (2018)
- [Online Exploration and Coverage Planning in Unknown Obstacle-Cluttered Environments](https://mlsanity.com/paper/2006.16460/) (2020)
- [Online Coverage Planning for an Autonomous Weed Mowing Robot with Curvature Constraints](https://mlsanity.com/paper/2111.10462/) (2021)
- [Online On-Demand Multi-Robot Coverage Path Planning](https://mlsanity.com/paper/2303.00047/) (2023)

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

- [Priority-Aware Multi-Robot Coverage Path Planning](https://mlsanity.com/paper/2601.00580/) (2026)
- [Coverage Path Planning: Classical Foundations, Recent Advances, and Future Directions](https://mlsanity.com/paper/2607.10649/) (2026)

## Abstract (arXiv)

Recently, centralized receding horizon online multi-robot coverage path planning algorithms have shown remarkable scalability in thoroughly exploring large, complex, unknown workspaces with many robots. In a horizon, the path planning and the path execution interleave, meaning when the path planning occurs for robots with no paths, the robots with outstanding paths do not execute, and subsequently, when the robots with new or outstanding paths execute to reach respective goals, path planning does not occur for those robots yet to get new paths, leading to wastage of both the robotic and the computation resources. As a remedy, we propose a centralized algorithm that is not horizon-based. It plans paths at any time for a subset of robots with no paths, i.e., who have reached their previously assigned goals, while the rest execute their outstanding paths, thereby enabling concurrent planning and execution. We formally prove that the proposed algorithm ensures complete coverage of an unknown workspace and analyze its time complexity. To demonstrate scalability, we evaluate our algorithm to cover eight large 2D grid benchmark workspaces with up to 512 aerial and ground robots, respectively. A comparison with a state-of-the-art horizon-based algorithm shows its superiority in completing the coverage with up to 1.6x speedup. For validation, we perform ROS + Gazebo simulations in six 2D grid benchmark workspaces with 10 quadcopters and TurtleBots, respectively. We also successfully conducted one outdoor experiment with three quadcopters and one indoor with two TurtleBots.