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.

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