日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

群制御arXiv:2605.10917

多マージン最適輸送とシュレーディンガー橋による最適かつスケーラブルなMAPF

Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schr\"odinger Bridges

シェア:XThreadsFacebookLINEはてブBluesky

匿名マルチエージェント経路探索を多マージン最適輸送問題として定式化し、線形計画問題に帰着させて最適解を得る手法を提案。さらにシュレーディンガー橋による確率的枠組みで大規模問題へのスケーラビリティを実現した。

詳しい要約

1. どんなもの?

- 匿名のmulti-agent path finding (MAPF) を対象とする研究。 - 有限連結グラフ上でロボット群を目標群へ移動させる問題。 - MAPFをmulti-marginal optimal transport (MMOT) の特殊クラスとして定式化。 - 指数的なMMOTが多項式サイズの線形計画 (LP) に帰着することを示す。 - 大規模問題向けにSchrödinger bridgeによる確率的枠組みを提案。

2. 先行研究と比べてどこがすごい?

- 従来のMAPF手法と比べ、MMOTのMarkovian構造を利用して指数的MMOTを多項式サイズLPに縮約。 - 匿名設定でLPが実行可能かつtotally unimodularとなる条件を確立。 - 時空間で重複しないmin-cost integral ({0,1}) transportが得られることを示す。 - Schrödinger bridgeにより大規模問題でもnear-optimalな解を効率的に求める点が新しい。

3. 技術・手法の肝は?

- MAPFをmulti-marginal optimal transport (MMOT) として定式化。 - 匿名設定でLPの実行可能性とtotally unimodular性を条件付きで証明。 - 大規模化のためSchrödinger bridgeを導入し、MMOTのentropic regularizationに帰着。 - Sinkhorn型の反復解法で解く。 - Schrödinger bridgeのfractional transportをテンプレートとして縮小LPを解き、integral transportを得る。

4. どうやって有効だと検証した?

- 広範な実験により提案手法の最適性とスケーラビリティを検証。 - 具体的な実験設定やベンチマークは要旨からは不明。

5. 議論はある?

- 匿名設定におけるLPの実行可能性とtotally unimodular性の条件を議論。 - Schrödinger bridgeによる確率的枠組みがnear-optimalなintegral transportを与えることを議論。 - 計算複雑性の大幅な削減について言及。 - 限界や課題については要旨からは不明。

6. 次に読むべき論文は?

- 要旨で参照/比較されている研究は明示されていない。 - 関連手法としてmulti-marginal optimal transport (MMOT)、Schrödinger bridge、Sinkhornアルゴリズム、MAPFの既存研究が挙げられる。

※ 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.

関連論文

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  3. 3NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  4. 4GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  5. 5UC BerkeleyとNVIDIAの研究者、AIエージェントでロボット制御コードを仮想環境で改善研究・技術

PR・アフィリエイト広告

MINISFORUM(ミニPC)

MINISFORUM(ミニPC)の公式広告バナーMINISFORUM公式ストアを見る ↗
PR本紙発行元 EmplifAI