要旨: 多エージェント経路探索（MAPF）では、共有グラフ上で複数のエージェントが衝突のない軌跡を必要とし、多くの場合、総コスト（SOC）を最小化することを目的とします。多くの最適解および上界付き準最適解のソルバは、時間展開モデルと中央集権的な競合解決に依存しており、大規模または密なインスタンスでのスケーラビリティを制限します。そこで本研究では、幾何学的計画と実行時の競合解決を分離するハイブリッド優先順位フレームワークを提案します。第1段階では、幾何学的競合プリエンプション（GCP）により、元のグラフ上でA*を用いてエージェントを逐次的に計画し、優先度の高い経路が使用する頂点へ入る遷移のコストを膨張させます。これにより、明示的な時間推論を行わずに空間的な迂回を促します。第2段階では、分散型ローカルコントローラ（DLC）が、頂点ごとのFIFO認可キューを用いて幾何学的経路を実行し、頂点と辺のスワップによる競合を回避する必要がある場合にのみ待機アクションを挿入します。最大1000エージェントまでの標準ベンチマークマップに対する実験では、この手法が経験的にほぼ線形の実行時間傾向でスケールし、幾何学的な実行可能性の仮定を満たすインスタンスにおいて100%の成功率を達成することが示されました。ボトルネックが多いマップでは、GCPが同期に起因する待機を減らし、しばしばボトルネックが多いマップでSOCを改善します
スケーラブルなマルチエージェント経路探索における幾何学的計画と実行の分離
arXiv cs.RO / 2026/3/31
💬 オピニオンIdeas & Deep AnalysisModels & Research
要点
- 本論文は、総コスト（sum-of-costs）目的関数を扱うマルチエージェント経路探索（MAPF）に取り組み、一般的な時間拡張型や集中型の競合解決アプローチが、大規模あるいは密なグラフ上でのスケーラビリティを阻害し得ることを指摘している。
- 幾何学的計画と実行を分離する2段階のハイブリッドフレームワークを提案する。Geometric Conflict Preemption（GCP）は、コスト増大（cost inflation）を用いて空間的な迂回を促すために、元のグラフ上でA*を実行する。
- 実行においては、Decentralized Local Controller（DLC）が計画された幾何学的経路を、頂点ごとのFIFO認可キューを用いて分散的に走らせ、頂点競合および辺のスワップ競合を防ぐ必要がある場合にのみ待機アクションを追加する。
- 最大1000体のエージェントを扱うベンチマーク地図での実験により、実行時間がほぼ線形にスケールすること、また幾何学的実現可能性の仮定を満たすインスタンスで100%の成功率が得られることが報告される。
- ボトルネックが多い地図では、GCPが同期に起因する待ち時間を減らすのに役立ち、時間推論や集中型調整により強く依存する手法と比べて総コストを改善できる可能性が示される。
