対象は、共有環境内で複数エージェントが衝突を避けながら、それぞれの始点から目標へ移動する連続時間のマルチエージェント経路探索問題である。古典的MAPFでは時間を離散化するのに対し、MAPF-Rではエージェントの運動、移動時間、待機を連続時間として扱う。論文は、衝突のない計画のうち目的関数を最小化する計画を求める問題としてこの設定を定式化し、主にSOCを最適化する。焦点は、実行可能経路を見つけることだけでなく、厳密探索が理論上の保証を実際に保持するかどうかにある。
第一の貢献は、CCBS型アルゴリズムの分岐規則がすべての有効な解を保持するための十分条件を、制約対の健全性として整理したことである。第二に、その条件を満たす新しい分岐規則を用いるOptimal Continuous-time Conflict-Based Search、すなわちOC-CBSを提案した。第三に、OC-CBSの厳密性と解完全性を理論的に示し、CCBSを基盤とする既存の継続手法へドロップイン置換として適用できることを示した。提示された抜粋は、既存の継続手法をすべて再実装して再評価したことまでは示していない。
CCBSは、衝突を検出すると、競合する二つのエージェントの行動に制約を加えた子ノードへ探索を分岐する。論文の分析では、分岐によって除外される計画集合を調べ、二つの制約集合の組が少なくとも一つの有効解を失わせないことを健全性の基準とする。この基準を満たすOC-CBSの分岐規則と、低い目的値を持つ探索ノードを維持する性質、さらに有限回で停止する性質を組み合わせ、最適性と解完全性を導く。実装では公開CCBS実装を基礎とし、円形エージェント、直線移動、一定速度、有限精度演算を仮定して、二分探索ではなく解析的に衝突区間を計算する。
評価では、公開されているCCBSと、分岐規則だけを変更したOC-CBSを比較した。実験はベンチマーク問題、特定の反例、さらにOC-CBSのパラメータに関するアブレーションで構成され、解品質と実行時間を調べている。エージェントは円形で、辺を直線かつ一定速度で通過し、主な目的関数はSOCである。実験環境は16コアのM4 Maxを搭載した2025年のMac Studio、メモリ64GB、macOS Sequoia 15.3である。提示された抜粋には、ベンチマーク全体の具体的な数値、問題数、平均値、分散、または統計的検定の詳細は含まれていない。
CCBSの実装済み分岐規則は、移動と待機の衝突において有効解を探索から除外し得るため、健全な分岐規則ではない。この欠陥は、CCBSが常に最適解を返すという従来の理論的前提を崩し、CCBS上に構築された継続手法の保証にも影響する。OC-CBSはこの問題を分岐規則の変更によって理論面と実装面の両方で修正するが、計算時間、探索ノード数、異なる幾何形状や環境への一般化について、抜粋から包括的な結論は得られない。パラメータのアブレーション結果も特定のグリッド状道路地図に依存し、他の地図、障害物配置、始点・目標配置、エージェント形状で同じ傾向になるとは限らない。著者らは、分析枠組みを将来の厳密なMAPF-Rソルバーの設計に利用することを展望している。
MAPFは倉庫、工場、ゲーム、交通管理、空港、捜索救難などで現れる、複数エージェントの衝突回避経路計画である。エージェントは単独なら最短経路を選べるが、他のエージェントとの衝突やデッドロックを避ける必要がある。古典的MAPFの最適解探索はNP困難であり、優先順位付けや限定時間窓などの近似的戦略と、CBSなどの厳密手法が研究されてきた。
MAPF-Rでは、環境を頂点と有向辺からなるグラフとして表し、頂点を2次元空間の座標へ対応させる。各移動行動は辺を通過する一つの方法を表し、時間から空間への運動関数、継続時間、始点と終点を持つ。エージェントの計画は時刻付き行動列であり、最後には最終位置で無限に待機する行動を含むため、全エージェントが永久に滞在することまで表現できる。
論文は、解の正しさをサウンドネス、最適解を返す性質を厳密性、可解な問題で探索が解を返して停止する性質を解完全性として区別する。健全な制約対とは、分岐で追加される制約が少なくとも一つの有効な計画を不当に失わせない制約対であり、分岐規則の健全性と同値になるよう整理される。OC-CBSでは、健全な分岐、探索ノードの目的値に関する下界性質、有限停止性を組み合わせて理論保証を得る。
実験対象は、元のCCBS実装と、同じ基盤上で新しい分岐規則を使うOC-CBSである。両手法は、円形エージェントが直線を一定速度で移動する設定で、SOCを中心に比較された。反例では4エージェントの相互作用を扱い、さらにベンチマーク比較と分岐規則のパラメータに関するアブレーションを実施した。抜粋は、ベンチマークの地図数や全試行数を明示していない。
反例では、OC-CBSがCCBSより低いSOC、メイクスパン、計算時間の解を生成したと報告されている。OC-CBSのSOC最適性は理論証明だけでなく、その反例専用に構成したSMTモデルをZ3で解くことでも検証され、約数時間の計算後に確認された。ただし、抜粋にはその反例の正確な目的値や、ベンチマーク全体における具体的な速度差は示されていない。全体としては、OC-CBSはCCBSと実行時間の面で競争力があり、ときにより良い解を得たと結論づけられている。
OC-CBSは、有限精度演算のもとで、可解なMAPF-Rインスタンスに対して最適解を返し、解完全性を満たすソルバーとして提示された。これは、CCBSの誤った正しさの前提を修正し、CCBSに依存する手法の理論的基盤を回復する。さらに、健全性と停止性を分析する枠組みは、将来の連続時間MAPFソルバーを評価・設計するための再利用可能な基盤となる。
評価は公開実装と特定の運動仮定、すなわち円形エージェント、直線移動、一定速度に依存している。パラメータの効果についても、抜粋ではグリッド状道路地図で得られた傾向に一般性はないと注意されている。異なる地図族、障害物、始点・目標配置、エージェント形状での性能や最適性保証の適用範囲を、提示された情報だけから具体的に評価することはできない。
この研究は、広く利用される基準アルゴリズムの最適性保証が実装上の分岐規則によって失われる可能性を明確にした点で重要である。理論的に健全な置換手法を示すことで、連続時間MAPFの比較実験や、その上に構築された継続手法の信頼性を改善する。単なる新アルゴリズムではなく、既存ソルバーを検証するための概念的な基準も提供している。
連続時間MAPF、MAPF-R、CCBS、CBSの正しさや最適性保証を研究する読者に適している。既存のCCBS実装を利用している研究者、分岐規則の健全性を形式的に分析したい研究者、厳密ソルバーの設計原理を学びたい研究者にも有用である。具体的なベンチマーク数値や多様な運動モデルの包括的比較を求める読者は、本文全体の追加情報を確認する必要がある。