  We study the computational complexity of multi-agent path finding (MAPF).
Given a graph $G$ and a set of agents, each having a start and target vertex,
the goal is to find collision-free paths minimizing the total distance
traveled. To better understand the source of difficulty of the problem, we aim
to study the simplest and least constrained graph class for which it remains
hard. To this end, we restrict $G$ to be a 2D grid, which is a ubiquitous
abstraction, as it conveniently allows for modeling well-structured
environments (e.g., warehouses). Previous hardness results considered highly
constrained 2D grids having only one vertex unoccupied by an agent, while the
most restricted hardness result that allowed multiple empty vertices was for
(non-grid) planar graphs. We therefore refine previous results by
simultaneously considering both 2D grids and multiple empty vertices. We show
that even in this case distance-optimal MAPF remains NP-hard, which settles an
open problem posed by Banfi et al. (2017). We present a reduction directly from
3-SAT using simple gadgets, making our proof arguably more informative than
previous work in terms of potential progress towards positive results.
Furthermore, our reduction is the first linear one for the case where $G$ is
planar, appearing nearly four decades after the first related result. This
allows us to go a step further and exploit the Exponential Time Hypothesis
(ETH) to obtain an exponential lower bound for the running time of the problem.
Finally, as a stepping stone towards our main results, we prove the NP-hardness
of the monotone case, in which agents move one by one with no intermediate
stops.
