Scalable Robust Multi-Agent Path Finding (Student Abstract)

Amit Bouzaglo
採択先: Proceedings of the International Symposium on Combinatorial Search 2026 ・ 2026-08-14 ・ source: openalex

原典・ PDF ・ DOI

補充候補採択先 Proceedings of the International Symposium on Combinatorial Search 2026公開日 2026-08-14キーワード一致 2被引用 0関連度 5本文(OA-PDF)読む価値 3/5

kRMAPFという制約下でのスケーラビリティ向上を目指した提案であり、既存手法の拡張として新規性がある。ただし、コストのトレードオフが示されており、関連分野の研究者にとって検討価値がある。

本文取得済み: 本文(OA-PDF)を根拠に要約しています。

Multi-Agent Path FindingMAPF

一言で: 各エージェントに最大k回までの遅延を許容する頑健なマルチエージェント経路探索において、既存の最適解探索手法のスケーラビリティの課題を解決するため、LaCAM*を拡張したkRLaCAM*-CRを提案し、高い成功率を実現した。

どんなもの？

グラフ上の複数のエージェントが、頂点の同時占有やエッジの逆方向通行といった衝突を避けつつ経路を求めるマルチエージェント経路探索（MAPF）を対象とする。各エージェントに最大k回までの待機による遅延が発生することを想定し、時間差がk以内での衝突を防ぐ制約を課すk-Robust MAPF（kRMAPF）を扱う。既存の最適解探索手法であるkRCBSは、エージェント数やkの増加に伴い、解を見つけることが困難になるというスケーラビリティの課題がある。

先行研究と比べてどこがすごい？

既存の最適解探索手法であるkRCBSに対し、anytimeソルバーであるLaCAM*をkRMAPFへ拡張したkRLaCAM*を導入した。さらに、低レベルの探索および構成生成器に渡す候補アクションから、過去kステップの配置と衝突するものを事前に除外するCardinality Reduction（CR）を導入した点が新規性である。

技術や手法のキモはどこ？

kRLaCAM*は、状態空間に各エージェントの現在の位置だけでなく、過去kステップ分の配置を含めることで、kRMAPFにおける最適性を担保する。また、低レベルの探索において、全エージェントが同時に待機することを許可する。改良版のkRLaCAM*-CRでは、低レベルの探索および構成生成器が利用可能なアクションの選択肢を動的に削減する。具体的には、各エージェントの候補アクションのうち、過去kステップの配置と衝突を引き起こすものを事前に検出し、それらを除外した状態で構成を生成する。

どうやって有効だと検証した？

brc202dベンチマークマップを用い、エージェント数を5、10、15、20、25と変化させた条件下で、kRCBSとkRLaCAM*-CRを比較した。90秒の制限時間内における成功率と、解が得られたインスタンスにおける平均コストを評価指標とした。実験の結果、kRLaCAM*-CRはテストしたすべてのkの値において成功率100%を達成したが、kRCBSはエージェント数やkの増加に伴って成功率が低下した。また、エージェント数の増加に伴い、kRLaCAM*-CRの平均コストはkRCBSが達成するコストから乖離していく傾向が見られた。

議論はある？（限界・課題）

kRLaCAM*-CRは、kRCBSと比較して成功率において優れた性能を示す一方で、生成する解の平均コストが高くなるというトレードオフが存在する。エージェント数が増えるほど、提案手法のコストはkRCBSが達成する最適値から離れていく。

セクション別の詳細要約

Introduction and Background

マルチエージェント経路探索（MAPF）は、グラフ上の複数のエージェントに対し、頂点の同時占有やエッジの逆方向通行といった衝突を避ける経路集合を求める問題である。各エージェントが最大k回まで待機による遅延が発生することを想定したk-Robust MAPF（kRMAPF）では、時間差がk以内での衝突を防ぐ制約が課される。本研究では、既存の最適解探索手法であるkRCBSのスケーラビリティの課題に対し、LaCAM*をkRMAPFへ拡張したkRLaCAM*を提案する。kRLaCAM*は、状態空間に過去kステップの配置を含めることで最適性を担保し、低レベルの探索において全エージェントが同時に待機することを許可している。さらに、低レベルの探索および構成生成器に渡す候補アクションから、過去kステップの配置と衝突するものを事前に除外するCardinality Reduction（CR）を導入したkRLaCAM*-CRを提案する。実験の結果、kRLaCAM*-CRはkRCBSを大幅に上回る性能を示し、解のコストを大きく増大させることなく、より多くのエージェントに対してスケーラブルに動作することが確認された。

Experimental Study

MovingAIリポジトリのbrc202dベンチマークマップを用い、エージェント数を5から25まで変化させた条件下で、kRCBSとkRLaCAM*-CRの性能を評価する予備的な実験を行いました。各エージェント数に対して25個のインスタンスをランダムに割り当て、90秒の制限時間内で成功率と、両手法が解いたインスタンスにおける平均コストを測定しています。実験の結果、kの値による顕著な差は見られず、kRLaCAM*-CRはテストしたすべてのkの値において全インスタンスを解いたのに対し、kRCBSはエージェント数やkの増加に伴って解けるインスタンス数が減少しました。両手法ともエージェント数の増加に伴ってコストが増大しますが、エージェント数が増えるほど、kRLaCAM*-CRのコストはkRCBSが達成する最適値から乖離していく傾向が確認されました。

Conclusion

本研究では、頑健なマルチエージェント経路探索（MAPF）の解を求めるために、既存のLaCAM*アルゴリズムを調整したkRLaCAM*を提案した。さらに、低レベルソルバーおよび構成生成器が利用可能な選択肢の集合の濃度を削減することで、kRLaCAM*-CRへと改良を加えた。実験の結果、kRLaCAM*-CRはkRCBSと比較して成功率において上回る性能を示した。一方で、kRLaCAM*-CRが生成する解の平均コストは、kRCBSよりも高くなることが確認された。