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

Forum topic · 小凯 · 2026-05-13

Summary

This arXiv paper (2505.07238, May 2025) by Usman A. Khan and Joseph W. Durham addresses anonymous multi-agent path finding (MAPF), where robots must reach a set of targets on a finite, connected graph. The authors show that MAPF can be cast as a special class of multi-marginal optimal transport (MMOT) problems with an underlying Markovian structure, causing the exponentially large MMOT to collapse into a polynomial-size linear program (LP). For the anonymous setting, they establish conditions under which the LP is feasible and totally unimodular, yielding minimum-cost, integral (0/1) transports with no overlaps in space or time. To scale to large problems, the MAPF-MMOT is placed in a probabilistic framework via Schrödinger bridges; under standard assumptions, this reduces to entropy regularization of the MMOT, solvable with iterative Sinkhorn-type iterations. The Schrödinger bridge provides a shadow (fractional) transport used as a template to solve the reduced LP, producing near-optimal integral transports at significantly lower complexity. Experiments demonstrate both optimality and scalability of the approach.

Paper Overview

Field: Machine Learning / Robotics
Authors: Usman A. Khan, Joseph W. Durham
Published: 2025-05-09
arXiv: 2505.07238

Abstract (translated)

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 entropy-regularized version of the corresponding MMOT, allowing iterative Sinkhorn-type solutions. As a probabilistic framework, the Schrödinger bridge provides a shadow (fractional) transport, which we use as a template to solve the reduced LP, and we prove that it yields near-optimal integral transports with significantly reduced complexity. Extensive experiments highlight the optimality and scalability of the proposed methods.

Key Contributions

1. MAPF as MMOT: MAPF is formulated as a multi-marginal optimal transport problem with Markovian structure, reducing exponential complexity to a polynomial-size LP. 2. Total unimodularity: Conditions are established under which the LP is feasible and totally unimodular, guaranteeing integral (0/1), collision-free solutions in both space and time. 3. Schrödinger bridge scaling: The problem is embedded in a probabilistic framework that reduces to entropy-regularized MMOT, solvable via Sinkhorn-type iterations. 4. Near-optimal integral transports: The fractional (shadow) transport from the Schrödinger bridge serves as a template for the reduced LP, achieving near-optimal integer solutions at lower computational complexity. 5. Empirical validation: Extensive experiments demonstrate optimality and scalability.

---

*Automatically collected on 2026-05-13.*