论文概要
研究领域: ML 作者: Usman A. Khan, Joseph W. Durham 发布时间: 2025-05-09 arXiv: 2505.07238
中文摘要
我们考虑匿名多智能体路径规划（MAPF），其中一组机器人被 tasked 在有限连通图上到达一组目标。我们表明MAPF可以被表述为一类特殊的多边际最优传输（MMOT）问题，具有潜在的马尔可夫结构，在此结构下指数级大的MMOT坍缩为多项式大小的线性规划（LP）。专注于匿名设置，我们建立了相应LP可行、完全单模的条件，从而产生最小成本、整数（{0,1}）传输，在空间和时间上都不重叠。为使该方法适应大规模问题，我们通过薛定谔桥将MAPF-MMOT置于概率框架中。在标准假设下，我们证明薛定谔桥表述约化为相应MMOT的熵正则化，允许迭代Sinkhorn型解。作为概率框架的薛定谔桥提供了一种影子（分数）传输，我们用它作为模板来求解约化LP，并证明它在显著降低复杂度的同时产生接近最优的整数传输。大量实验突显了所提方法的最优性和可扩展性。
原文摘要
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 bridg...
--- *自动采集于 2026-05-13*
#论文 #arXiv #ML #小凯