Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schrödinger Bridges
For multi-robot coordination, this work provides a theoretically grounded, scalable method for optimal anonymous MAPF, addressing a key bottleneck in path planning.
The paper casts anonymous multi-agent path finding (MAPF) as a multi-marginal optimal transport (MMOT) problem, showing it reduces to a polynomial-size linear program (LP) that yields integral, non-overlapping transports. It further introduces a Schrödinger bridge formulation for scalability, achieving near-optimal solutions with reduced complexity.
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 consequently, 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.