多マージン最適輸送とシュレーディンガー橋による最適かつスケーラブルなMAPF
Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schr\"odinger Bridges
匿名マルチエージェント経路探索を多マージン最適輸送問題として定式化し、線形計画問題に帰着させて最適解を得る手法を提案。さらにシュレーディンガー橋による確率的枠組みで大規模問題へのスケーラビリティを実現した。
詳しい要約
1. どんなもの?
2. 先行研究と比べてどこがすごい?
3. 技術・手法の肝は?
4. どうやって有効だと検証した?
5. 議論はある?
6. 次に読むべき論文は?
※ AIが要旨から生成した要約です。正確性は原文をご確認ください。
著者: Usman A. Khan, Joseph W. Durham
分類: cs.LG, cs.MA, cs.RO
原文アブストラクト
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\"odinger bridges. Under standard assumptions, we show that the Schr\"odinger bridge formulation reduces to an entropic regularization of the corresponding MMOT that admits an iterative Sinkhorn-type solution. The Schr\"odinger 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.
