Multi-agent pathfinding

Multi-agent pathfinding (MAPF) is the problem of finding collision-free paths for multiple agents moving simultaneously in a shared environment. Unlike single-agent pathfinding, where the only constraint is the environment itself, MAPF must account for inter-agent collisions — spatial conflicts where two agents attempt to occupy the same location at the same time, or cross each other's paths.

The problem is computationally hard. Finding optimal solutions — minimizing the sum of path lengths or the makespan (time until all agents reach their goals) — is NP-hard for many formulations. Even finding feasible solutions can be difficult when agents are densely packed and their goals require them to pass through each other's starting positions, a situation known as the parking problem or deadlock.

Common approaches include decoupled methods, which plan paths for each agent independently and then resolve conflicts through priority assignments or reservation tables; coupled methods, which search the joint state space of all agents (treating the multi-agent system as a single high-dimensional agent); and hybrid methods, which combine aspects of both. The A* algorithm has been extended to MAPF in the form of Conflict-Based Search (CBS), which plans independently and then iteratively resolves conflicts by adding constraints.

Multi-agent pathfinding is not merely a robotics problem. It models traffic flow in cities, packet routing in networks, coordination in warehouse automation, and crowd simulation in games. In each domain, the challenge is the same: individual optimality (each agent wants the shortest path) conflicts with collective feasibility (the paths must not collide). MAPF is the formalization of this tension, and its solutions are instances of mechanism design — the engineering of coordination structures that align individual behavior with collective constraints.