ArXiv

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

2026-05-11 · 17:52 UTC ·Usman A. Khan, Joseph W. Durham ·1 min read
Authors
Usman A. Khan, Joseph W. Durham
Categories
cs.LG, cs.MA, cs.RO
arXiv
https://arxiv.org/abs/2605.10917v1
PDF
https://arxiv.org/pdf/2605.10917v1

Brief

The paper addresses anonymous MAPF by formulating it as a Markovian MMOT that exactly reduces an exponentially large problem to a polynomial-size LP, with proven feasibility and total unimodularity yielding collision-free integral {0,1} transports. For large-scale instances the authors use a Schrödinger-bridge entropic regularization solved via Sinkhorn iterations to produce fractional templates used in a reduced LP, trading negligible optimality loss for major computational savings; experimental results demonstrate strong optimality and scalability. Accepted to ICML 2026 as a spotlight paper.

Why it matters

Usman A. Khan and Joseph W. Durham (ArXiv 2026-05-11; accepted ICML 2026 spotlight) recast anonymous multi-agent path finding (MAPF) on finite graphs as a Markovian multi-marginal optimal transport (MMOT) problem whose exponentially large MMOT collapses to a linear program (LP) of polynomial size.

Key details

  • They prove the LP is feasible and totally unimodular under stated conditions, yielding min-cost integral {0,1} transports that provably avoid space–time overlaps (no collisions).
  • For scalability, they formulate a Schrödinger bridge (entropic regularization) solved by Sinkhorn-type iterations; the resulting fractional transport guides a reduced LP that produces near-optimal integral solutions with significantly lower complexity, validated by extensive experiments.
Source evidence

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 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.

Comment: Accepted in ICML 2026 as a spotlight paper