Intractability of Time-Optimal Multirobot Path Planning on 2D Grid Graphs with Holes

Jacopo Banfi; Nicola Basilico; Francesco Amigoni

RA-L 201768 citations

Intractability of Time-Optimal Multirobot Path Planning on 2D Grid Graphs with Holes

Jacopo Banfi, Nicola Basilico, Francesco Amigoni

Abstract

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.

BibTeX

@inproceedings{ral2017_intractabilityof,
  title = {Intractability of Time-Optimal Multirobot Path Planning on 2D Grid Graphs with Holes},
  author = {Jacopo Banfi and Nicola Basilico and Francesco Amigoni},
  booktitle = {RA-L 2017},
  year = {2017}
}