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

• URL: http://arxiv.org/abs/2605.10917v1
• Date: Mon, 11 May 2026 17:52:15 GMT
• Title: Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schrödinger Bridges
• Abstract summary: We show that MAPF can be cast as a special class of multi-marginal optimal (MMOT) problems with an underlying Markovian structure.<n>To adapt the approach to large-scale problems, we cast the MAPF-MMOT in a probabilistic framework via Schrdinger bridges.
• Score: 1.6042394978941512
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Twisted Schrödinger Bridge Matching [34.126987447337534]
  Diffusion-based Schrdinger bridge models have been proposed to approximate optimal transport dynamics between two prescribed boundary distributions.<n>We introduce Twisted Schrdinger Bridge Matching, a diffusion-based method designed to handle both continuous- and discrete-time potentials.
  arXiv  Detail & Related papers  (2026-07-18T22:30:43Z)
• A Generalized Sinkhorn Algorithm for Mean-Field Schrödinger Bridge [19.922542189921447]
  The mean-field Schrdinger bridge (MFSB) problem concerns designing a minimum-effort controller that guides a diffusion process with nonlocal interaction to reach a given distribution by a fixed deadline.<n>Unlike Schrdinger bridge, the dynamical constraint for MFSB is a population of interacting agents with repulsive controls.<n>We propose a generalization the Hopf-Cole algorithm for MFSB and, on building it, design a Sinkhorn-type algorithm to solve the associated system integro-PDEs.
  arXiv  Detail & Related papers  (2026-04-08T00:04:52Z)
• Schrödinger bridge for generative AI: Soft-constrained formulation and convergence analysis [6.584866740785309]
  We study the so-called soft-constrained Schr"odinger bridge problem (SCSBP)<n>We prove that as the penalty grows, both the controls and value functions converge to those of the classical SBP at a linear rate.<n>These results provide the first quantitative convergence guarantees for soft-constrained bridges.
  arXiv  Detail & Related papers  (2025-10-13T18:29:15Z)
• Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning [56.240199425429445]
  Multi-Robot Motion Planning (MPMP) involves generating trajectories for multiple robots operating in a shared continuous workspace.<n>While discrete multi-agent finding (MAPF) methods are broadly adopted due to their scalability, their coarse discretization trajectory quality.<n>This paper tackles limitations of two approaches by introducing discrete MAPF solvers with constrained generative diffusion models.
  arXiv  Detail & Related papers  (2025-08-27T17:59:36Z)
• Schrödinger Bridge Matching for Tree-Structured Costs and Entropic Wasserstein Barycentres [6.197358216842481]
  Recent advances in flow-based generative modelling have provided scalable methods for computing the Schr"odinger Bridge (SB) between distributions.<n>We present an elegant and practical approach with many favourable properties over the more traditional Iterative Proportional Fitting (IPF) procedure.<n>Our resulting algorithm inherits the many advantages of IMF over IPF approaches in the tree-based setting.
  arXiv  Detail & Related papers  (2025-06-20T17:47:47Z)
• Light and Optimal Schrödinger Bridge Matching [67.93806073192938]
  We propose a novel procedure to learn Schr"odinger Bridges (SB) which we call the textbf Schr"odinger bridge matching. We show that the optimal bridge matching objective coincides with the recently discovered energy-based modeling (EBM) objectives to learn EOT/SB. We develop a light solver (which we call LightSB-M) to implement optimal matching in practice using the mixture parameterization of the Schr"odinger potential.
  arXiv  Detail & Related papers  (2024-02-05T17:17:57Z)
• Generalized Schrödinger Bridge Matching [54.171931505066]
  Generalized Schr"odinger Bridge (GSB) problem setup is prevalent in many scientific areas both within and without machine learning. We propose Generalized Schr"odinger Bridge Matching (GSBM), a new matching algorithm inspired by recent advances. We show that such a generalization can be cast as solving conditional optimal control, for which variational approximations can be used.
  arXiv  Detail & Related papers  (2023-10-03T17:42:11Z)
• Light Schrödinger Bridge [72.88707358656869]
  We develop a lightweight, simulation-free and theoretically justified Schr"odinger Bridges solver. Our light solver resembles the Gaussian mixture model which is widely used for density estimation. Inspired by this similarity, we also prove an important theoretical result showing that our light solver is a universal approximator of SBs.
  arXiv  Detail & Related papers  (2023-10-02T13:06:45Z)
• Implicitly normalized forecaster with clipping for linear and non-linear heavy-tailed multi-armed bandits [85.27420062094086]
  Implicitly Normalized Forecaster (INF) is considered an optimal solution for adversarial multi-armed bandit (MAB) problems. We propose a new version of INF called the Implicitly Normalized Forecaster with clipping (INFclip) for MAB problems with heavy-tailed settings. We demonstrate that INFclip is optimal for linear heavy-tailed MAB problems and works well for non-linear ones.
  arXiv  Detail & Related papers  (2023-05-11T12:00:43Z)
• Markovian Sliced Wasserstein Distances: Beyond Independent Projections [51.80527230603978]
  We introduce a new family of SW distances, named Markovian sliced Wasserstein (MSW) distance, which imposes a first-order Markov structure on projecting directions. We compare distances with previous SW variants in various applications such as flows, color transfer, and deep generative modeling to demonstrate the favorable performance of MSW.
  arXiv  Detail & Related papers  (2023-01-10T01:58:15Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. The object of interest for applications such as generative modeling is the underlying optimal transport map. We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
  arXiv  Detail & Related papers  (2021-12-03T13:45:36Z)
• On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity [11.280177531118206]
  We study the multi-marginal partial optimal transport (POT) problem between $m$ discrete (unbalanced) measures with at most $n$ supports. We first prove that we can obtain two equivalence forms of the multimarginal POT problem in terms of the multimarginal optimal transport problem via novel extensions of cost tensor. We demonstrate that the ApproxMPOT algorithm can approximate the optimal value of multimarginal POT problem with a computational complexity upper bound of the order $tildemathcalO(m3(n+1)m/ var
  arXiv  Detail & Related papers  (2021-08-18T06:46:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.