日本フィジカルAI新聞

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

群制御arXiv:2603.26684

幾何計画と実行を分離したスケーラブルなマルチエージェント経路探索

Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding

シェア:XThreadsFacebookLINEはてブBluesky

マルチエージェント経路探索において、幾何学的な経路計画と実行時の衝突解決を分離するハイブリッド優先度フレームワークを提案し、最大1000エージェントの大規模問題で高いスケーラビリティと成功率を実証した。

詳しい要約

1. どんなもの?

- 複数エージェントが共有グラフ上で衝突のない経路を計画する Multi-Agent Path Finding (MAPF) の新しいハイブリッド優先度フレームワーク。 - 目的は sum-of-costs (SOC) の最小化。 - 幾何計画と実行時衝突解決を分離する。 - 第1段階の Geometric Conflict Preemption (GCP) では、A* を用いて元のグラフ上で順次計画し、高優先度経路が使用する頂点への遷移コストを膨張させて空間的迂回を促す。 - 第2段階の Decentralized Local Controller (DLC) では、頂点ごとの FIFO 認可キューを用いて幾何経路を実行し、待機行動を挿入して頂点衝突とエッジスワップ衝突を回避する。 - 最大1000エージェントの標準ベンチマークマップで評価。

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

- 従来の最適・有界準最適ソルバは時間拡張モデルと集中型衝突解決に依存し、大規模・高密度インスタンスでのスケーラビリティが制限されていた。 - 提案手法は幾何計画と実行時衝突解決を分離することで、時間推論を明示的に行わずに空間的迂回を促し、スケーラビリティを向上させる。 - 最大1000エージェントでほぼ線形のランタイム傾向を示し、幾何学的実現可能性仮定を満たすインスタンスで100%の成功率を達成。

3. 技術・手法の肝は?

- 第1段階: Geometric Conflict Preemption (GCP) では、A* を元のグラフ上で順次適用し、高優先度経路が使用する頂点に入る遷移のコストを膨張させることで、時間を明示的に考慮せずに空間的迂回を促す。 - 第2段階: Decentralized Local Controller (DLC) では、頂点ごとの FIFO 認可キューを用いて幾何経路を実行し、待機行動を挿入して頂点衝突とエッジスワップ衝突を回避する。 - これにより、集中型の時間拡張モデルを必要とせず、分散的に衝突解決を行う。

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

- 標準ベンチマークマップを用いた実験で、最大1000エージェントのインスタンスを評価。 - 提案手法はほぼ線形のランタイム傾向を示し、幾何学的実現可能性仮定を満たすインスタンスで100%の成功率を達成した。 - 具体的なベンチマーク名や比較手法の詳細は要旨からは不明。

5. 議論はある?

- 提案手法は幾何学的実現可能性仮定を満たすインスタンスで100%の成功率を達成するが、仮定を満たさない場合の挙動や限界については要旨からは不明。 - また、SOC の最適性や有界準最適性に関する理論的保証については言及されていない。 - 大規模インスタンスでのスケーラビリティは示されているが、他の手法との定量的比較は要旨からは不明。

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

- 要旨で参照/比較されている研究は明示されていない。 - 関連手法として、時間拡張モデルを用いた最適・有界準最適 MAPF ソルバ(例: Conflict-Based Search (CBS), MAPF with time-expanded networks)や、優先度ベースの手法(例: Prioritized Planning)が挙げられる。 - また、分散型衝突解決手法(例: Decentralized Local Controller に類似する FIFO ベースのアプローチ)も参考になる。

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

著者: Fernando Salanova, Eduardo Montijano, Cristian Mahulea

分類: cs.MA, cs.RO

原文アブストラクト

Multi-Agent Path Finding (MAPF) requires collision-free trajectories for multiple agents on a shared graph, often with the objective of minimizing the sum-of-costs (SOC). Many optimal and bounded-suboptimal solvers rely on time-expanded models and centralized conflict resolution, which limits scalability in large or dense instances. We propose a hybrid prioritized framework that separates \emph{geometric planning} from \emph{execution-time conflict resolution}. In the first stage, \emph{Geometric Conflict Preemption (GCP)} plans agents sequentially with A* on the original graph while inflating costs for transitions entering vertices used by higher-priority paths, encouraging spatial detours without explicit time reasoning. In the second stage, a \emph{Decentralized Local Controller (DLC)} executes the geometric paths using per-vertex FIFO authorization queues and inserts wait actions to avoid vertex and edge-swap conflicts. Experiments on standard benchmark maps with up to 1000 agents show that the method scales with an near-linear runtime trend and attains a 100\% success rate on instances satisfying the geometric feasibility assumption. Page of the project: https://sites.google.com/unizar.es/multi-agent-path-finding/home

関連論文

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

PR・アフィリエイト広告

FRONTIER(GPU搭載BTOパソコン)

FRONTIER(GPU搭載BTOパソコン)の公式広告バナーFRONTIERでGPU搭載PCを見る ↗
PR本紙発行元 EmplifAI