Refined Hardness of Multi-Robot/Agent Motion Planning
Wednesday, December 22nd, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)
Tzvika Geft, Tel Aviv University
Abstract:
In Multi-Robot Motion Planning (MRMP) we aim to plan collision-free motion of
robots from given start to target positions in a common workspace. While the
general problem has been known to be intractable for decades, the reasons
behind its difficulty are still not well-understood. I will present new
complexity results for MRMP and its discrete counterpart, called Multi-Agent
Pathfinding (MAPF), where the robots are modeled as agents on a graph.
First, we study distance-optimal MAPF, i.e., where the objective is minimizing
the total distance travelled. The tightest hardness result for distance-optimal
MAPF so far were for planar graphs. However, MAPF formulations commonly further
restrict the input graph to be a 2D grid, as grids naturally model well-structured
environments such as warehouses. Following this gap, Banfi et al. (2017) posed
the tractability on 2D grids as an open question, which we settle by showing
that this case remains NP-hard. We improve on previous hardness results in the
additional following ways: Our reduction is directly from 3-SAT using simple
gadgets, making it arguably more helpful for identifying the source of
hardness. Secondly, the reduction is the first linear one for the planar case.
This results in the first exponential lower bound for the problem's running
time, based on the Exponential Time Hypothesis.
Next, we turn to monotone MRMP, a natural NP-hard restriction of MRMP where
robots move one by one to their targets. We examine two tractable variants of
the problem that become NP-hard when their formulation is altered slightly.
These sharp changes in the problem's computational complexity shed new light on
its tractability frontier.
Joint work with Dan Halperin.