The most tight intractability results for graph-based Multirobot Path Planning (MPP), proven recently, state that timeoptimal 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.
Intractability of time-optimal multirobot path planning on 2D grid graphs with holes / J. Banfi, N. Basilico, F. Amigoni. - In: IEEE ROBOTICS AND AUTOMATION LETTERS. - ISSN 2377-3766. - 2:4(2017 Oct), pp. 1941-1947. [10.1109/LRA.2017.2715406]
Intractability of time-optimal multirobot path planning on 2D grid graphs with holes
N. BasilicoSecondo
;
2017
Abstract
The most tight intractability results for graph-based Multirobot Path Planning (MPP), proven recently, state that timeoptimal 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.File | Dimensione | Formato | |
---|---|---|---|
07949109.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
408.63 kB
Formato
Adobe PDF
|
408.63 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.