Abstract
Multi-Agent Path Finding (MAPF) is a fundamental motion coordination problemarising in multi-agent systems with a wide range of applications. The problem'sintractability has led to extensive research on improving the scalability ofsolvers for it. Since optimal solvers can struggle to scale, a major challengethat arises is understanding what makes MAPF hard. We tackle this challengethrough a fine-grained complexity analysis of time-optimal MAPF on 2D grids,thereby closing two gaps and identifying a new tractability frontier. First, weshow 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 flowtimeobjective (also called sum-of-costs), we show that it remains NP-hard to find asolution in which agents have an individually optimal cost, which we call anindividually optimal solution. The previously tightest results for these MAPFvariants are for (non-grid) planar graphs. We use a single hardnessconstruction that replaces, strengthens, and unifies previous proofs. Webelieve that it is also simpler than previous proofs for the planar case as itemploys minimal gadgets that enable its full visualization in one figure.Finally, for the flowtime objective, we establish a tractability frontier basedon the number of directions agents can move in. Namely, we complement ourhardness result, which holds for three directions, with an efficient algorithmfor finding an individually optimal solution if only two directions areallowed. This result sheds new light on the structure of optimal solutions,which may help guide algorithm design for the general problem.