# 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.