# MSTC*:Multi-robot Coverage Path Planning under Physical Constraints

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Aug 2021.

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

- [Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction](https://mlsanity.com/paper/2411.01707/) (2024)
- [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)
- [Priority-Aware Multi-Robot Coverage Path Planning](https://mlsanity.com/paper/2601.00580/) (2026)
- [Cooperative Informative Sensing for Monitoring Dynamic Indoor Environments via Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2604.23179/) (2026)
- [Coverage Path Planning: Classical Foundations, Recent Advances, and Future Directions](https://mlsanity.com/paper/2607.10649/) (2026)

## Abstract (arXiv)

For large-scale tasks, coverage path planning (CPP) can benefit greatly from multiple robots. In this paper, we present an efficient algorithm MSTC* for multi-robot coverage path planning (mCPP) based on spiral spanning tree coverage (Spiral-STC). Our algorithm incorporates strict physical constraints like terrain traversability and material load capacity. We compare our algorithm against the state-of-the-art in mCPP for regular grid maps and real field terrains in simulation environments. The experimental results show that our method significantly outperforms existing spiral-STC based mCPP methods. Our algorithm can find a set of well-balanced workload distributions for all robots and therefore, achieve the overall minimum time to complete the coverage.