Portal de Periódicos da CAPES

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

2017; Institute of Electrical and Electronics Engineers; Volume: 2; Issue: 4 Linguagem: Inglês

10.1109/lra.2017.2715406

2377-3766

Jacopo Banfi, Nicola Basilico, Francesco Amigoni,

Modular Robots and Swarm Intelligence

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.