An Optimization Variant of Multi-Robot Path Planning Is Intractable

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 𝑁𝑃-complete is sketched in this short paper.

Authors

• Pavel Surynek Czech Technical University in Prague

Keywords

No keywords are indexed for this paper.