  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 opposite
directions on those paths. Indeed, such efficiency boosting structures, such as
highways and elevated intersections, are ubiquitous in robotics and
transportation applications.
