用最优传输方法解决机器人路径规划，既保证最优又可大规模扩展。
Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schrödinger Bridges
- 将路径规划建模为具有马尔可夫结构的多边际最优传输问题，降维成多项式规模线性规划。
- 在匿名设置下确保解为整数且时空无冲突，理论证明可行且最优。
- 引入薛定谔桥框架，通过迭代算法大幅降低计算复杂度，适合大规模场景。
我们研究匿名多智能体路径规划（MAPF），即一组机器人需在有限连通图上前往目标点。本文表明，该问题可转化为一类具有马尔可夫结构的多边际最优传输（MMOT）问题，使原本指数级规模的MMOT退化为规模多项式级别的线性规划（LP）。针对匿名设定，我们建立了该LP可行性、全单模性的条件，从而获得最小代价且不重叠（{0,1}）的时空整数解。为应对大规模问题，我们通过薛定谔桥将其转化为概率框架下的熵正则化形式，导出类似Sinkhorn的迭代求解方法。该框架提供一个分数级运输方案作为模板，用于求解简化后的线性规划，最终获得近似最优的整数解，同时显著降低计算开销。大量实验验证了方法的最优性与可扩展性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。