Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schrödinger Bridges
2026-05-11 • Machine Learning
Machine LearningMultiagent SystemsRobotics
AI summaryⓘ
The authors study how to efficiently plan routes for multiple robots moving to different targets without knowing which robot goes where. They show this problem can be transformed into a special mathematical setup called multi-marginal optimal transport (MMOT), which simplifies to a manageable linear program under certain conditions. To handle larger problems, they use a probabilistic method called Schrödinger bridges that allows for approximate, easier solutions while still producing nearly optimal paths. Their experiments show that these methods work well and scale to bigger robot groups.
multi-agent path findingmulti-marginal optimal transportlinear programmingMarkov processtotally unimodular matrixSchrödinger bridgeentropic regularizationSinkhorn algorithmprobabilistic modelingcombinatorial optimization
Authors
Usman A. Khan, Joseph W. Durham
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.