Paper Overview
- Field: Machine Learning
- Authors: Usman A. Khan, Joseph W. Durham
- Published: 2025-05-09
- arXiv: 2505.07238
- MAPF is reformulated as a Markovian multi-marginal optimal transport problem that collapses from exponential to polynomial LP size.
- Feasibility and total unimodularity conditions guarantee min-cost integral ({0,1}) transports with no overlap in space or time.
- Schrödinger bridge formulation reduces to entropy-regularized MMOT, solvable via Sinkhorn-type iterations.
- The fractional Schrödinger bridge transport serves as a template to solve the reduced LP near-optimally with lower complexity.
- Extensive experiments validate both optimality and scalability.
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, admitting 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 integer transports at a significantly reduced complexity. Extensive experiments highlight the optimality and scalability of the proposed methods.