Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schrödinger Bridges

We consider anonymous multi-agent path finding (MAPF) where a set of robots is tasked to travel to a set of targets on a finite, connected graph. We show that MAPF can be cast as a special class of multi-marginal optimal transport (MMOT) problems with an underlying Markovian structure, under which the exponentially large MMOT collapses to a linear program (LP) polynomial in size. Focusing on the anonymous setting, we establish conditions under which the corresponding LP is feasible, totally unimodular, and yields min-cost, integral~$(\{0,1\})$ transports that do not overlap in both space and time. To adapt the approach to large-scale problems, we cast the MAPF-MMOT in a probabilistic framework via Schrödinger bridges. Under standard assumptions, we show that the Schrödinger bridge formulation reduces to an entropic regularization of the corresponding MMOT that admits an iterative Sinkhorn-type solution. The Schrödinger bridge, being a probabilistic framework, provides a shadow (fractional) transport that we use as a template to solve a reduced LP and demonstrate that it results in near-optimal, integral transports at a significant reduction in complexity. Extensive experiments highlight the optimality and scalability of the proposed approaches.

When many robots need to reach different targets in a shared space without collisions, finding the best routes is extremely difficult because the number of possible plans grows exponentially with more robots and longer routes. We show that by viewing this as a transport problem, that is, moving mass from starting locations to destinations, a certain mathematical structure emerges that naturally guarantees optimal, collision-free paths, without the expensive trial-and-error search that existing methods require. This makes the problem solvable in a fraction of the time. For even larger problems, we introduce a probabilistic relaxation that produces a "shadow", which is a blurry picture of where robots are likely to travel. This shadow can be computed extremely fast. We then focus only on the darkest corridors of this shadow and solve a smaller, simpler problem restricted to these corridors. This two-step approach scales highly favorably with problem size (almost linearly) while staying within 10% of the optimal solution, enabling coordination of over a thousand robots in under a minute.