Skip to content Skip to navigation

Intractability of Optimal Multi-Robot Path Planning on Planar Graphs

Intractability of Optimal Multi-Robot Path Planning on Planar Graphs

Author Name: 

Jingjin Yu

Publication Type: 
Journal Publications
Journal/Volume: 
IEEE Robotics and Automation Letters
Publication Date: 
January, 2016
Abstract: 
We study the computational complexity of optimally solving multi-robot path planning problems on planar graphs. For four common time- and distance-based objectives, we show that the associated path optimization problems for multiple robots are all NP-complete, even when the underlying graph is planar. Establishing the computational intractability of optimal multi-robot path planning problems on planar graphs has important practical implications. In particular, our result suggests the preferred approach toward solving such problems, when the number of robots is large, is to augment the planar environment to reduce the sharing of paths among robots traveling in pposite directions on those paths. Indeed, such efficiency boosting structures, such as highways and elevated intersections, are ubiquitous in robotics and transportation applications.