# Mixed Integer Programming for Time-Optimal Multi-Robot Coverage Path Planning with Efficient Heuristics

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 42 references that are in the map.
- First posted on arXiv 30 Jun 2023.

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

- [UAV Coverage Path Planning under Varying Power Constraints using Deep Reinforcement Learning](https://mlsanity.com/paper/2003.02609/) (2020)
- [A Comprehensive Survey on the Multiple Travelling Salesman Problem: Applications, Approaches and Taxonomy](https://mlsanity.com/paper/2102.12772/) (2021)
- [Optimal Multi-Robot Path Planning on Graphs: Complete Algorithms and Effective Heuristics](https://mlsanity.com/paper/1507.03290/) (2015)
- [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)
- [A Mixed-Integer Linear Programming Formulation for Human Multi-Robot Task Allocation](https://mlsanity.com/paper/2106.06772/) (2021)
- [Learning to Coordinate for a Worker-Station Multi-robot System in Planar Coverage Tasks](https://mlsanity.com/paper/2208.02993/) (2022)
- [Integer Programming as a General Solution Methodology for Path-Based Optimization in Robotics: Principles, Best Practices, and Applications](https://mlsanity.com/paper/1902.02652/) (2019)
- [Spatial and Temporal Splitting Heuristics for Multi-Robot Motion Planning](https://mlsanity.com/paper/2103.14111/) (2021)
- [TMSTC*: A Turn-minimizing Algorithm For Multi-robot Coverage Path Planning](https://mlsanity.com/paper/2212.02231/) (2022)

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

- [Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction](https://mlsanity.com/paper/2411.01707/) (2024)
- [Large-Scale Multi-Robot Coverage Path Planning via Local Search](https://mlsanity.com/paper/2312.10797/) (2023)
- [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)

We investigate time-optimal Multi-Robot Coverage Path Planning (MCPP) for both unweighted and weighted terrains, which aims to minimize the coverage time, defined as the maximum travel time of all robots. Specifically, we focus on a reduction from MCPP to Min-Max Rooted Tree Cover (MMRTC). For the first time, we propose a Mixed Integer Programming (MIP) model to optimally solve MMRTC, resulting in an MCPP solution with a coverage time that is provably at most four times the optimal. Moreover, we propose two suboptimal yet effective heuristics that reduce the number of variables in the MIP model, thus improving its efficiency for large-scale MCPP instances. We show that both heuristics result in reduced-size MIP models that remain complete (i.e., guaranteed to find a solution if one exists) for all MMRTC instances. Additionally, we explore the use of model optimization warm-startup to further improve the efficiency of both the original MIP model and the reduced-size MIP models. We validate the effectiveness of our MIP-based MCPP planner through experiments that compare it with two state-of-the-art MCPP planners on various instances, demonstrating a reduction in the coverage time by an average of 27.65% and 23.24% over them, respectively.