MG-MAPFでは、複数のエージェントが単位長の辺を持つ無向グラフ上を移動し、それぞれにあらかじめ割り当てられた複数のゴールを任意の順序で少なくとも一度訪問する。各時刻にエージェントは現在の頂点で待機するか、隣接頂点へ移動できる。同じ時刻に同じ頂点に滞在すること、また同じ時刻に同じ辺を移動することが衝突となる。全エージェントのゴール訪問完了までの時間の総和を最小化する。
第一に、ゴール頂点訪問順序の探索と単一エージェント経路探索を分離するDVS型手法は、MG-MAPFで常に最適解を返せないことをケーススタディと実験で示す。第二に、ゴールの安全区間訪問順序の探索と単一エージェント経路探索を分離するMGCBSを提案する。第三に、任意の始点と開始時刻から各ゴール安全区間までの最短経路を保持して再利用するTime-Interval-Space Forestを導入する。論文はさらに、MGCBSの最適性と完全性を理論的に示している。
MGCBSは、CBSを拡張した高位探索と、A*に基づく低位探索からなる二層ソルバである。高位ソルバは制約木を管理し、最小コストのノードを選び、衝突を検出すると、衝突に対応する制約を追加した子ノードを生成する。制約を追加されたエージェントについて、低位ソルバはその制約下で全ゴールを訪問する最良の安全区間訪問順序と経路を求める。TIS Forestはエージェントごとに構築され、各TIS Treeは特定のゴール安全区間に対応し、始点頂点と始点時刻からその安全区間への最短経路と長さを提供する。
評価は4近傍グリッドマップ上で行われ、MAPFベンチマークから小・中・大規模の3マップが選ばれた。各エージェント数について開始点とゴールをランダムに生成し、異なるエージェントの開始点は重ならないようにした。比較対象は、DVS型の従来SOTAであるHCBS、TIS Forestを除いたMGCBS、提案手法MGCBS、そして最適アルゴリズムとして扱われるCBSとA*の組合せである。効率について平均実行時間と成功率を、解の質について最適基準とのコスト差、最大相対誤差、平均相対誤差を用いた。提示された抜粋には、全条件の実行時間や全インスタンスの詳細値は含まれていない。
DVSではゴール頂点の訪問順序を探索するが、論文のケーススタディは、この分離ではMG-MAPFの最適性を保証できないことを示す。DSSはゴールを時間的な安全区間と結び付けて扱い、MGCBSの低位探索にその情報を取り込む。TIS Forestは複数の始点・時刻から同じ安全区間への問い合わせを共有できる一方、制約が変わると関連する木の再構築が必要になる。実験は提案手法の有効性を支持するが、抜粋だけでは実環境、非グリッド地図、異なる衝突モデル、メモリ使用量、スケーリング限界については確立されていない。
MAPFは、複数エージェントの開始地点から目標地点までの衝突のない経路を計画する問題であり、航空機牽引車両、ビデオゲーム、交通管理などへの応用がある。MG-MAPFは、各エージェントが単一のゴールではなく、割り当てられた複数のゴールを訪問するよう拡張した問題である。関連問題にはMAPD、先行制約付きMAPF、ゴール割当を含む同時マルチゴール順序付け問題などがあるが、論文はそれらの設定がMG-MAPFと異なり、手法を直接適用できないと説明する。既存のMG-MAPF手法としてHCBSとSMT-HCBSが挙げられ、HCBSはヒューリスティックを利用するため通常はSMT-HCBSより速い一方、最適性と効率に改善余地があると位置付けられる。
入力は、単位長の辺を持つ無向グラフ、複数エージェント、各エージェントの開始頂点、複数の割り当てゴールである。各エージェントは待機または隣接頂点への移動を行い、すべてのゴールを少なくとも一度訪問した後はゴール頂点の一つに留まる。頂点衝突と辺衝突を避けつつ、各経路のゴール訪問完了までの時間の総和を最小化する。訪問順序は任意であり、時間的な衝突回避と同時に決める必要がある。
TIS Forestは、エージェントごとに複数のTIS Treeから構成され、各木は特定のゴール安全区間に対応する。木は、時間・区間・空間に関する状態から安全区間へ至る最短経路を逆向きに保持する。論文の説明では、これは逆向きDijkstra法に基づき、同じTIS状態内の状態をまとめて逆向きの辺に沿って展開する。ゴール到達時刻が事前に分からないため、通常のSIPPに類似した構築機構をそのまま使えない点も設計上の特徴である。
効率実験では、MAPFベンチマークのmaze-32-32-4、lak303d、orz900dという3つの4近傍グリッドマップを用いた。各マップとテスト対象のエージェント数の組について100インスタンスを生成し、実行時間が60秒を超えたケースは失敗として扱い、実行時間を60秒に設定した。HCBS、TIS ForestなしのMGCBS、MGCBSを比較し、平均実行時間と成功率を測定した。最適性実験ではCBS+A*とコストを比較し、コストが異なるインスタンス数、最大相対誤差、平均相対誤差を調べた。
論文は、MGCBSが評価した成功インスタンスで一貫して最適解を得たと報告している。HCBSでは最適経路との差が生じるインスタンスがあり、最大相対誤差は17%を超えたとされる。効率について、MGCBSは従来SOTAに対して最大7倍の高速化を達成した。提示された抜粋には、すべてのマップとエージェント数における平均実行時間の具体値は含まれていない。
MG-MAPFでは、ゴール頂点訪問順序と単一エージェント経路を分離するだけでは最適性を保証できない。MGCBSは安全区間訪問順序を探索し、CBS型の衝突解消とA*型の低位探索を組み合わせる。TIS Forestは安全区間への最短経路問い合わせを再利用し、最適性を保ちながら効率化する。提示された実験結果は、従来のDVS型手法より高い最適性と実行効率を示している。
論文の抜粋は、主に4近傍グリッドと単位長辺を持つグラフ、総コスト最小化を対象としており、他の地図構造や目的関数への一般性は示していない。TIS Forestの構築・再構築に必要なメモリ量と、制約やエージェント数が増えた場合の詳細な計算量は、提示情報からは分からない。実験はランダム生成された開始点とゴールを使うため、特定の構造を持つ実運用シナリオでの失敗モードは評価されていない。将来課題として明示された具体的な拡張計画は、提示された抜粋からは確定できない。
この研究は、MG-MAPFで訪問順序決定と経路計画を単純に分離する設計が、効率だけでなく最適性にも影響することを明確にする。安全区間を探索対象にすることで、ゴール訪問順序と時間的な衝突回避を同じ低位計画に結び付ける。理論的な最適性・完全性と、TIS Forestによる最短経路情報の再利用を組み合わせた点は、複数ゴールを持つエージェント群の厳密計画に有用である。
複数の作業地点を持つロボット群で、衝突のない経路と総コストの最適性を研究する人に適している。CBS、MAPFの安全区間、A*、単一エージェント経路探索の再利用に関心がある読者にも向く。実時間運用、非グリッド環境、確率的な移動、メモリ制約を主題とする読者は、これらが提示された抜粋で十分評価されていない点に注意すべきである。