An Optimization Variant of Multi-Robot Path Planning is Intractable

Abstract

An optimization variant of a problem of path planning for multiple robots is addressed in this work. A proof of the claim that optimal path planning for multiple robots is NP-complete is sketched in the paper.

Keywords

• Optimization
• Multi-Robot
• Path-Planning
• Intractable