# Optimal Multi-Robot Path Planning on Graphs: Complete Algorithms and Effective Heuristics

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2015.

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

- [Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search](https://mlsanity.com/paper/2103.07116/) (2021)
- [Answer Set Planning: A Survey](https://mlsanity.com/paper/2202.05793/) (2022)
- [Graph-Based Multi-Robot Path Finding and Planning](https://mlsanity.com/paper/2206.11319/) (2022)
- [Coordinated Multi-Agent Pathfinding for Drones and Trucks over Road Networks](https://mlsanity.com/paper/2110.08802/) (2021)
- [Multi-agent Soft Actor-Critic Based Hybrid Motion Planner for Mobile Robots](https://mlsanity.com/paper/2112.06594/) (2021)
- [Mixed Integer Programming for Time-Optimal Multi-Robot Coverage Path Planning with Efficient Heuristics](https://mlsanity.com/paper/2306.17609/) (2023)
- [The Parameterized Complexity of Coordinated Motion Planning](https://mlsanity.com/paper/2312.07144/) (2023)
- [On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles](https://mlsanity.com/paper/2312.10887/) (2023)
- [Simultaneous Task Allocation and Planning for Multi-Robots under Hierarchical Temporal Logic Specifications](https://mlsanity.com/paper/2401.04003/) (2024)
- [Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding](https://mlsanity.com/paper/2404.16379/) (2024)
- [Multi-robot Social-aware Cooperative Planning in Pedestrian Environments Using Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2211.15901/) (2022)
- [Optimally Solving Colored Generalized Sliding-Tile Puzzles: Complexity and Bounds](https://mlsanity.com/paper/2410.14947/) (2024)

## Abstract (arXiv)

We study the problem of optimal multi-robot path planning on graphs MPP over four distinct minimization objectives: the makespan (last arrival time), the maximum (single-robot traveled) distance, the total arrival time, and the total distance. In a related paper, we show that these objectives are distinct and NP-hard to optimize. In this work, we focus on efficiently algorithmic solutions for solving these optimal MPP problems. Toward this goal, we first establish a one-to-one solution mapping between MPP and network-flow. Based on this equivalence and integer linear programming (ILP), we design novel and complete algorithms for optimizing over each of the four objectives. In particular, our exact algorithm for computing optimal makespan solutions is a first such that is capable of solving extremely challenging problems with robot-vertex ratio as high as 100%. Then, we further improve the computational performance of these exact algorithms through the introduction of principled heuristics, at the expense of some optimality loss. The combination of ILP model based algorithms and the heuristics proves to be highly effective, allowing the computation of 1.x-optimal solutions for problems containing hundreds of robots, densely populated in the environment, often in just seconds.