An Optimization Variant of Multi-Robot Path Planning Is Intractable
DOI:
https://doi.org/10.1609/aaai.v24i1.7767Keywords:
graph pebbling, multi-robot, path planning, complexity, motion puzzleAbstract
An optimization variant of a problem of path planning for multiple robots is addressed in this work. The task is to find spatial-temporal path for each robot of a group of robots such that each robot can reach its destination by navigating through these paths. In the optimization variant of the problem, there is an additional requirement that the makespan of the solution must be as small as possible. A proof of the claim that optimal path planning for multiple robots is NP‑complete is sketched in this short paper.
Downloads
Published
2010-07-04
How to Cite
Surynek, P. (2010). An Optimization Variant of Multi-Robot Path Planning Is Intractable. Proceedings of the AAAI Conference on Artificial Intelligence, 24(1), 1261-1263. https://doi.org/10.1609/aaai.v24i1.7767
Issue
Section
Short Papers