Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schrödinger Bridges (arXiv 2505.07238)

Forum topic · 小凯 · 2026-05-13

Summary

This arXiv paper (2505.07238) by Usman A. Khan and Joseph W. Durham addresses anonymous multi-agent path finding (MAPF), where robots must reach targets on a finite, connected graph without overlapping in space or time. The authors show MAPF can be formulated as a special class of multi-marginal optimal transport (MMOT) problems with an underlying Markovian structure, which collapses an exponentially large MMOT into a polynomial-size linear program (LP). They establish conditions under which this LP is feasible and totally unimodular, yielding minimum-cost integral ({0,1}) transports with no space-time collisions. To scale to large problems, the paper embeds MAPF-MMOT in a probabilistic framework via Schrödinger bridges, proving that under standard assumptions the Schrödinger bridge formulation reduces to an entropy-regularized MMOT solvable with iterative Sinkhorn-type methods. The resulting shadow (fractional) transport serves as a template for solving the reduced LP, producing near-optimal integer transports with significantly lower complexity. Extensive experiments demonstrate the method's optimality and scalability.

Paper Overview

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

Abstract

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. Since the Schrödinger bridge provides a shadow (fractional) transport as a probabilistic framework, we use it as a template to solve the reduced LP, proving that it yields near-optimal integer transports while significantly reducing complexity. Extensive experiments highlight the optimality and scalability of the proposed approach.

Key Contributions

MAPF recast as a Markovian multi-marginal optimal transport problem, reducing exponential complexity to polynomial-size LPs.
Conditions for feasibility and total unimodularity of the LP, guaranteeing collision-free integral ({0,1}) solutions in both space and time.
A Schrödinger bridge probabilistic formulation that reduces to entropy-regularized MMOT, solvable via Sinkhorn-type iterations.
A shadow-transport template for solving the LP with near-optimal integer solutions at reduced computational cost.
Extensive experiments demonstrating optimality and scalability.