対象は、複数エージェントを指定された始点から目標点へ移動させ、エージェント同士が衝突しない計画集合を求める任意角度MAPFである。古典的な格子MAPFのように移動方向を固定せず、障害物との衝突がない限り、可視な任意の頂点間を直線的に移動できる。エージェントは一定半径の円盤としてモデル化され、頂点で任意の連続時間だけ待機できる。各移動の時間は始点と終点の距離であり、主な目的は全エージェントの目標到着時刻の総和を最小化することである。
第一に、著者らは最適性を保証する任意角度MAPFアルゴリズムとしてAA-CCBSを提示する。これは、連続時間を扱うContinuous Conflict-based Searchを高レベル探索に用い、最適な単一エージェント任意角度探索器TO-AA-SIPPを低レベル探索器として組み合わせる。第二に、任意角度経路探索による大きな分岐数を抑えるため、古典的MAPFのDisjoint SplittingとMulti-Constraintsを任意角度設定へ適応する。さらに、Multi-Constraintsの三つの実装方法を示し、これらの拡張を利用できる有界劣最適版も構成する。
CCBSは各エージェントの計画を個別に作成し、連続時間上で計画間の衝突を検出し、衝突を避ける制約を加えて関係するエージェントを再計画する。AA-CCBSでは低レベル探索にTO-AA-SIPPを用い、障害物を通過しない可視な直線移動と、他エージェントに関する制約のもとで安全な時間区間を考慮する。Multi-Constraintsは一つの衝突を解消するときに複数の制約を追加し、高レベル探索木をより強く枝刈りする。Disjoint Splittingは衝突の解消を互いに分離された制約分岐として扱い、任意角度移動による探索負荷の軽減を図る。有界劣最適版では、高レベルのBest-First SearchをFocal Searchに置き換え、最適解からのコスト超過を指定因子内に制限する。
評価にはC++実装とMovingAIベンチマークの五つのマップ、すなわちempty-16-16、random-32-32-20、maze-32-32-4、den321d、warehouse-10-20-10-2-2を用いた。各マップには25シナリオがあり、各シナリオで2エージェントから開始し、制限時間内に解ける限りエージェント数を増加させた。評価した構成は、バニラAA-CCBS、Multi-Constraintsの三方式、Disjoint Splitting単独、およびDisjoint Splittingと第三のMulti-Constraints方式の組合せである。指標には300秒以内に解けたインスタンス数、異なる時間制限での解決数、高レベル反復回数が含まれる。有界劣最適版では、性能のよかった三構成を同じ問題集合で評価し、最適解に対する解コストの超過を調べた。
結果は、Multi-Constraintsの第一および第二方式がバニラAA-CCBSに対して大きな改善を示さない一方、第三方式、Disjoint Splitting、および両者の組合せが大幅に優れることを示す。非常に短い時間制限では第三方式が適し、より長い制限ではDisjoint Splittingとその組合せが優位であり、インスタンスの難しさや利用可能時間に応じて有効な技法が異なる。第三方式は比較的容易なインスタンスで高レベル反復を減らす傾向があり、Disjoint Splittingはより難しいインスタンスで有効である。少量の劣最適性を許すと解ける問題数が増えるが、抜粋には各因子についての完全なコストデータは示されていない。
古典的MAPFでは、エージェントの移動はあらかじめ定めた疎なグラフ上の遷移に制限され、通常は各移動が一単位時間である。Conflict-Based Searchは代表的な最適MAPF枠組みであり、CCBSは衝突ベースの考え方を連続時間と異なる行動時間へ拡張する。単一エージェントの最適任意角度探索器としてAnyaやTO-AA-SIPPがあり、先行する任意角度MAPF手法には最適性を保証しないものもある。
頂点は計量空間内に配置され、例えば格子セルの中心として表される。エージェントは頂点で任意時間待機でき、二頂点間の直線が障害物に衝突しない場合だけ移動できる。二つの円盤形エージェントの距離が、ある時刻に両者の半径の和未満になる場合、計画は衝突する。求めるのは、全ての計画が相互に衝突せず、エージェントの目標到着時刻の総和が最小となる解である。
AA-CCBSの高レベル探索は離散的な時刻ではなく連続時間の衝突と制約を扱い、低レベル探索はTO-AA-SIPPが担う。待機は必ずしも明示的な行動として列挙されず、ある移動の終了と次の移動の開始の間の時間差で表現できる。移動速度は単位速度で、開始と停止は瞬時と仮定されるため、移動時間は端点間の距離になる。論文は他の目的関数、例えばメイクスパンへの適応も可能だとしているが、提示された評価は主に総コストを扱う。
実験では五種類のMovingAIマップと各マップ25シナリオを使い、エージェント数を段階的に増やした。あるシナリオで300秒以内に解を見つけられない場合、そのシナリオを終えて次へ進んだ。比較対象はバニラAA-CCBS、Multi-Constraintsの三方式、Disjoint Splitting、および第三のMulti-Constraints方式との組合せである。有界劣最適実験では、Disjoint Splitting、第三方式、両者の組合せを同じインスタンスで評価した。
要旨では、提案技法によりバニラのCCBSとTO-AA-SIPPの組合せより30パーセント超多くの問題を解けたと報告されている。時間制限の分析では、第三のMulti-Constraints方式が0.01秒から0.1秒の範囲で最も良く、より長い制限ではDisjoint Splitting系が優位だった。全ての比較手法で解けたインスタンスのうち、第三方式はほぼ半数でDisjoint Splitting系より少ない高レベル反復を必要とし、これは主に容易なインスタンスで見られた。少量の有界劣最適性を許すと、より多くの問題を解けることも報告されている。
AA-CCBSは、任意角度MAPFに最適性保証を与えるCCBSベースの枠組みである。Disjoint SplittingとMulti-Constraintsは、任意角度移動による大きな探索分岐を抑える有効な拡張として示された。有界劣最適版は、解コストと実行時間を制御して交換する手段を提供する。
任意角度移動は移動候補を増やし、CCBSとTO-AA-SIPPの単純な組合せは小さなインスタンスでもスケールしにくい。論文は、有界劣最適な低レベル探索の構成を扱っていない。実験は指定された五マップ、シナリオ、エージェント増加手順、時間制限に基づくため、他の環境やより豊かなロボット運動学への性能の一般化は抜粋から確認できない。将来課題として、より高度なMulti-Constraintsの形成、各段階で考慮する行動集合の選択、任意角度低レベル探索への増分探索の適応が挙げられている。
任意角度移動は固定された4近傍などより短い経路を表現できる一方、マルチエージェント探索の分岐を大きくする。本研究は、連続時間の衝突処理と最適な単一エージェント任意角度探索を、最適なマルチエージェント枠組みに結び付けた点で重要である。さらに、厳密な最適解が高コストな場合に、制御されたコスト保証を保ちながら実行時間を短縮する選択肢を示している。
任意角度MAPF、CCBS、SIPP、CBS拡張、連続時間衝突処理、または有界劣最適探索を研究する読者に適している。特に、高レベル探索の負荷を減らす衝突分割と複数制約の方法を比較したい人に向く。異種エージェント、異なる速度、キノダイナミクスに関心がある読者は関連研究の背景として参照できるが、提示された抜粋だけではそれらの性能は評価できない。