Intractability of Time-Optimal Multirobot Path Planning on 2D Grid Graphs with Holes
Jacopo Banfi, Nicola Basilico, Francesco Amigoni · IEEE Robotics and Automation Letters · 2017
The most tight intractability results for graph-based Multirobot Path Planning (MPP), proven recently, state that time-optimal and distance-optimal MPP problems are NP-hard on planar graphs. In this letter, we go one step further for what concerns the time-optimal objectives, and prove that such problems remain NP-hard when restricting the planar graph to a 2D grid graph with holes, which is a discretization widely used in robotics. Our reduction (from the Boolean satisfiability problem) cannot be easily modified for the distance-optimal objectives, whose hardness remains an open problem.