地図不確実性下のマルチエージェント経路探索に信念認識型MAGICを提案、実行SoCを96.3%のインスタンスで削減
SymboticとMITの研究チームは、初期地図の不確実性を共有信念として扱うBelief-Aware MAPFを定式化し、ガウス信念伝播（GaBP）を用いたオンライン推論フレームワークMAGICを提案した。実験では標準MAPFベンチマーク上で最大800エージェント規模まで、既存手法と比較して96.3%のインスタンスで実行コスト（SoC）を削減した。本論文はプレプリントであり、査読済み会議・論文誌への採録は明記されていない。
固定環境において一部地点の通行可能性が事前に未知である場合に、観測の空間的相関を活用して未観測地点の通行可能性を推論し、マルチエージェント経路探索の実行コストを削減できるか。
実環境では落下物や閉鎖通路などの地図乖離が発生し、事前の地図が不正確になる。従来手法は直接観測に基づく再計画や分岐計画を行うが、空間的相関を利用しないため、1つの観測から近傍の未観測障害を予測できず、後で高コストな迂回が発生する。
MAPF-OUは不確実な障害に対する分岐計画を構築するが、不確実性が増えると計算コストが急増する。MAPF-IMは計画と実行を交互に行い直接観測に応じて再計画するが、空間依存性を利用しない。また、カナダ旅行者問題などの単一エージェント手法は不確実なグラフ上での期待コスト最小化を扱うが、多エージェントの衝突回避に拡張されていない。
MAGICは、ガウス・マルコフ確率場（GMRF）で地点間の空間相関をモデル化し、ガウス信念伝播（GaBP）により各エージェントの観測から共有信念をオンライン更新する。この信念から辺の通行可能性推定値を算出し、各辺について、その辺が通行不能になった場合の迂回距離（detour）を用いた辺コストを構築する。このコストをCBS、EECBS、PBS、PIBT、LaCAMなどの標準MAPFプランナに与え、観測のたびに再計画を実行する。
標準MAPFベンチマーク（empty、random、maze、room、warehouse、city等）で、小規模（n=10）、中規模（n=50）、大規模（n=200）、超大規模（n=800）の4階層で評価した。不確実割合φ=0.30では、楽観的再計画は最適SoC比9.4%増に対しMAGICは3.6%増、MAPF-IMは14.9%増だった。ブロック率ρ=0.30では、MAGIC 2.7%増、楽観的再計画6.7%増、MAPF-IM12.4%増。小・中・大規模層でMAGICはMAPF-IMより96.3%のインスタンスで実行SoCが低く、15の全MAGIC構成で平均SoC比が1を下回った。CBS（n=10）ではSoC比0.966±0.004、PBS（n=10）では0.963±0.006、PBS（n=50）で0.987±0.004、LaCAM（n=200）で0.989±0.001、PIBT+（n=800）で0.995±0.001だった。成功率は一部設定でMAGICが楽観的再計画より低く（例：CBS n=10で88.8%対91.2%、PIBT n=800で55%対79%）、これはGaBP推論と再計画の計算負荷による。事前分布の空間割当を環境生成モデルに整合させた場合、逆に割り当てた場合より実行SoCが3.40%低減し、成功率も88.5%から90.9%に向上した。2台のTurtleBotによる実機デモも実施した。
著者は、Belief-Aware MAPFの拡張として生涯タスクや実行中に通行可能性が変化する環境への適用を将来課題としている。現状のMAGICは計算負荷が高く、GaBP推論と頻繁な再計画により、一部設定で成功率が楽観的再計画より低下する。また、辺コストは局所的な迂回距離の代理であり、将来の実行コストの正確な期待値ではない。事前分布p0が真の環境分布と一致しない場合の頑健性は限定的で、不確実半径R=1の大規模倉庫マップではMAGICが楽観的再計画より劣る結果も報告された。さらに、実機評価は2台のデモンストレーションのみで、コードやデータセットの公開については論文に記載がない。
倉庫自動化を手掛けるSymboticなど、多数の移動ロボットを運用する企業が直接利用可能な枠組みである。既存のMAPFプランナに組み込めるため、現在から1〜3年以内に実システムへ統合できる可能性がある。ただし、実運用には計算資源の確保と、事前分布の設計（環境の空間相関のモデル化）が必要であり、大規模環境でのリアルタイム性を担保するためのGaBP実装最適化が前提となる。また、本論文はプレプリントであり、査読済みの有効性確認はされていない。
この論文はライセンス上、全文を転載できないため、要約と原文へのリンクのみを掲載しています。