  Multi-Agent Path Finding (MAPF) is a fundamental motion coordination problem
arising in multi-agent systems with a wide range of applications. The problem's
intractability has led to extensive research on improving the scalability of
solvers for it. Since optimal solvers can struggle to scale, a major challenge
that arises is understanding what makes MAPF hard. We tackle this challenge
through a fine-grained complexity analysis of time-optimal MAPF on 2D grids,
thereby closing two gaps and identifying a new tractability frontier. First, we
show that 2-colored MAPF, i.e., where the agents are divided into two teams,
each with its own set of targets, remains NP-hard. Second, for the flowtime
objective (also called sum-of-costs), we show that it remains NP-hard to find a
solution in which agents have an individually optimal cost, which we call an
individually optimal solution. The previously tightest results for these MAPF
variants are for (non-grid) planar graphs. We use a single hardness
construction that replaces, strengthens, and unifies previous proofs. We
believe that it is also simpler than previous proofs for the planar case as it
employs minimal gadgets that enable its full visualization in one figure.
Finally, for the flowtime objective, we establish a tractability frontier based
on the number of directions agents can move in. Namely, we complement our
hardness result, which holds for three directions, with an efficient algorithm
for finding an individually optimal solution if only two directions are
allowed. This result sheds new light on the structure of optimal solutions,
which may help guide algorithm design for the general problem.
