Structure and Intractability of Optimal Multi-Robot Path Planning on Graphs

By Jingjin Yu, Steven M. LaValle. AAAI Conference on Artificial Intelligence, 2013

495 citations recorded by the source corpus.

In this paper, we study the structure and computational complexity of optimal multi-robot path planning problems on graphs. Our results encompass three formulations of the discrete multi-robot path planning problem, including a variant that allows synchronous rotations of robots along fully occupied, disjoint cycles on the graph. Allowing rotation of robots provides a more natural model for multi-robot path planning because robots can communicate.Our optimality objectives are to minimize the total arrival time, the makespan (last arrival time), and the total distance. On the structure side, we show that, in general, these objectives demonstrate a pairwise Pareto optimal structure and cannot be simultaneously optimized. On the computational complexity side, we extend previous work and show that, regardless of the underlying multi-robot path planning problem, these objectives are all intractable to compute. In particular, our NP-hardness proof for the time optimal versions, based on a minimal and direct reduction from the 3-satisfiability problem, shows that these problems remain NP-hard even when there are only two groups of robots (i.e. robots within each group are interchangeable).

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/01d090ac9cd0ddc7da673e12acb157431260afbc

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Alejandro Ribeiro
2. Sven Koenig
3. Nathan R Sturtevant
4. Peter James Stuckey
5. Amanda Prorok
6. Qingbiao Li
7. Ariel Felner
8. Maxim Likhachev

In Computer Vision and Pattern Recognition

1. Sven Koenig
2. Jiaoyang Li
3. Hang Ma
4. Amanda Prorok
5. Qingbiao Li
6. Max Barer
7. Roni Stern
8. Ariel Felner

In Industrial and Manufacturing Engineering

1. Peter James Stuckey

Citations in the corpus

• Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem (2014, background): “Solving MAPF optimally (i.e., finding a conflict-free so-lution of minimal cost) is NP-Complete (Yu and LaValle 2013b).”
• Conflict-based search for optimal multi-agent pathfinding (2012, background): “In addition, these algorithms are usually highly efficient only on small problem instances On large problem instances the translation process from an MAPF instance to the required problem has a very large, yet polynomial, overhead which makes these approaches inefficient.”
• Graph Neural Networks for Decentralized Multi-Robot Path Planning (2019, background): “Indeed, solving for optimality is NP-hard [11], and although significant progress has been made towards alleviating the computational load [12], [13], these approaches still scale poorly in environments with a high number of potential path conflicts.”
• Searching with Consistent Prioritization for Multi-Agent Path Finding (2018, background): “MAPF is NP-hard to solve optimally (Yu and LaValle 2013b; Ma et al. 2016b).”