通常のマルチエージェント経路探索では、共有環境内で各エージェントが始点から指定された目的地まで、他のエージェントと衝突しない経路を求める。本論文のCTS-MAPFでは、各エージェントが最終目的地へ向かう前に、複数の中間タスク位置を訪問しなければならず、タスクをどのエージェントに割り当て、どの順番で訪問するかも決める必要がある。あるエージェントのタスク順序は他のエージェントの計画結果に影響されるため、順序付けは個別ではなく協調的である。目的は、待機を含む移動の総コスト、例えば総時間や総距離を小さくしつつ、衝突、タスク割り当て、訪問順序、最終到達に関する条件を満たすことである。
中心的な貢献は、CTS-MAPFに対するCollaborative Task Sequencing Conflict-Based Search、すなわちCTS-CBSを提案したことである。CTS-CBSは、従来の衝突ベース探索を、タスク順序を含む共同計画へ拡張し、上位層で複数の共同タスク順序に対応する探索森林を構成する。各木は、jTSPの解から得られた共同タスク順序に対応し、下位層ではその順序と衝突制約の下でエージェントごとの経路を生成する。論文は、厳密解を求める設定での完全性と最適性、および有界パラメータを用いる設定での有界劣最適性を理論的に示したと述べる。さらに、CTS-MAPFとMG-MAPFという二つのデータセットを作成し、シミュレーションと実ロボット試験を行った。
CTS-CBSは二層探索として動作する。上位層では、共同タスク順序を一つに固定するのではなく、複数の候補順序に対応する探索木を含む探索森林を優先度付きに扱い、必要に応じて新しい根ノードを生成する。下位層では、各エージェントについて、上位層が指定したタスク列と衝突回避制約を守る単一エージェント経路計画を行い、得られた経路集合のコストを上位探索の評価に使う。衝突が見つかった場合は、衝突に関係する経路の一方または他方を制限する制約へ分岐し、制約下で経路を再計画する。この構造により、タスク順序の変更と経路衝突の解消を相互に考慮できる。実装では下位探索にSIPPが使われているが、論文はA*型アルゴリズムも利用可能だと説明している。
評価では、Moving AIが提供するMAPFベンチマークをCTS-MAPF用に適応した。各マップには50シナリオがあり、各シナリオには約100件のエージェントデータが含まれるため、最初の20件をエージェントデータ、残りの始点をタスクデータとして利用したとされる。実験はC++で実装され、1インスタンスあたり3分の制限時間、Intel Core i7-12700KF、GeForce RTX 3080、32GBメモリ、Linuxという条件で実施された。比較対象には複数の既存手法が含まれ、提示された抜粋で明示されている名称はHCBSとMGCBSである。成功率、実行時間、解の品質を比較し、さらに劣最適性境界を調整するパラメータの影響と実ロボット上の動作も調べた。
MG-MAPF向けのCTS-CBS適応版は、ベースラインに対して成功率が最大20倍、実行時間が最大100倍で、解の品質の犠牲は10%未満だったと報告されている。ただし、これらは提示された抜粋に記された上限値であり、個別マップ、エージェント数、タスク数ごとの詳細値、分散、統計的有意性、全ベースラインの名称は抜粋からは確認できない。劣最適性境界を調整することで品質と効率を交換できる点は、厳密な最適解と高速な実用解の両方を必要とする運用に有用である可能性がある。一方、評価は主として静的な環境と離散的な移動モデルを前提としており、実際のエージェントの運動学的制約、動的環境、継続的に到着するタスクへの対応は今後の課題として残されている。タスク順序探索と衝突解消を統合するため、問題規模が増えた場合の計算量や、タスク・経路の構造による失敗条件についても、提示された抜粋だけでは十分に評価できない。
MAPFは、共有環境内で複数エージェントの衝突しない経路を求める問題であり、ロボット、倉庫、自動運転などへの応用がある。従来の優先順位付き計画、PUSH AND SWAP、Hierarchical Cooperative A*などは導入しやすい一方、一般に完全性や最適性を保証しない。Conflict-Based Searchは、上位層の衝突制約分岐と下位層の単一エージェント計画を組み合わせる、完全かつ最適なMAPF手法として位置付けられている。
CTS-MAPFでは、エージェント集合、無向グラフで表された作業空間、頂点と辺、正の移動コスト、障害物、始点、最終目的地、タスク位置などが与えられる。各エージェントは待機または上下左右への一歩移動を行い、割り当てられたタスクを必要な順序で訪問してから目的地へ到達する。待機によるコストも含めて全体の移動コストを最小化し、衝突やタスクに関する条件を満たす必要がある。
上位層は、jTSPの解に基づく共同タスク順序ごとに探索木を作る。下位層は、固定された順序と衝突制約に対して単一エージェント経路を再計画し、実装上はSIPPが用いられる。劣最適性を許す設定では、新しい根ノードが本当に必要かを確認する機構と、劣最適性境界を制御するパラメータが効率と品質の調整に使われる。
論文はCTS-MAPFとMG-MAPFという二つのデータセットを作成したが、提示された抜粋では両者の完全な生成手順や規模の詳細は示されていない。MAPFベンチマークから各マップ50シナリオを適応し、最初の20件をエージェントデータ、残りの始点をタスクデータとして使った。各インスタンスの制限時間は3分で、既存手法との比較、パラメータの影響調査、実ロボット試験を行った。
MG-MAPF向けのCTS-CBS適応版は、成功率で最大20倍、実行時間で最大100倍、ベースラインを上回ったと報告されている。解の品質の低下は10%未満だったとされる。実ロボットでは、ロボットが指定経路に沿って移動し、手法の実環境への適用可能性を確認した。個々の実験値や全条件別の比較結果は、提供された抜粋には含まれていない。
CTS-CBSは、協調的なタスク順序付けと衝突回避経路計画を一つの探索枠組みに統合する。論文は、厳密設定での完全性・最適性と、境界付き設定での有界劣最適性を理論的に主張している。実験とロボット試験は、特にMG-MAPFでの実用的な成功率と速度の改善を示したとされる。
提示された本文抜粋には、提案手法の計算量、全ベースラインの具体名、詳細なマップ名、各条件の数値、統計的検定が記載されていない。現状の前提は静的環境と離散的な行動を中心としており、動的・生涯型タスク、エージェントの運動学、規模拡大時の挙動は未解決である。成功率や速度の改善はMG-MAPF適応版についての報告であり、あらゆるMAPF設定へ一般化できるとは抜粋だけからは断定できない。
本研究は、タスク割り当てや巡回順序を先に固定してから経路を作るのではなく、両者を衝突制約の下で協調的に探索する視点を提供する。品質と計算時間をパラメータで調整できるため、倉庫や複数ロボット運用で、最適性と応答性の要求が異なる場面に適用できる可能性がある。
MAPF、マルチロボット経路計画、タスク割り当てと経路計画の統合に関心がある研究者に適している。CBSの拡張、共同巡回セールスマン問題、実ロボットでの検証を学びたい読者にも向く。ただし、動的環境、連続制御、厳密なベンチマーク比較を主題とする読者は、本文全体で追加条件を確認すべきである。