マルチエージェント経路計画（MAPF）は、複数のエージェントを現在の状態から目標状態へ移動させ、任意の時刻にエージェントの形状が重ならない経路を求める問題である。古典的 MAPF では、通常、二次元グリッド上の点エージェントと単位時間の移動を扱う。これに対して連続時間 MAPF は、非平面でもよい重み付きグラフ、正の実数または有理数の移動時間、待機を表す自己ループ辺、辺の走行中に生じる衝突を扱う。求める解は競合を含まない実行可能解であり、一般にメイクスパンまたはフロータイムの最小化も目的となる。
中心的な貢献は、CBS に時間相対重複枝刈り（TRDP）を導入することである。TRDP は、絶対時刻が異なっていても、将来の経路生成に関して同じ意味を持つ状態を時間相対的な重複として検出し、別々の有用な状態として展開することを防ぐ。著者らは、TRDP が最適な実行可能解を排除せず、TRDP を備えた CBS が、インスタンスが可解かどうかにかかわらず停止することを理論的に示す。さらに、エージェント密度の高い設定向けのバイパス手続きを示し、通常は実行時間への影響が小さく、場合によっては性能が向上することを報告する。
通常の CBS は、各ノードにエージェントごとの経路を格納した競合木を探索する。根では他のエージェントの経路を考慮せずに個別経路を計画し、経路間の衝突が見つかると、関係するエージェントの一つに制約を追加して再計画し、後続ノードを生成する。TRDP は、個別経路または複数エージェントの経路に、時間のずれを許せば以前の状態と同じ将来の振る舞いを持つループがあるかを調べる。このようなループは、ループ部分を除去または回避しても同じ目標へ到達でき、最適経路として残す必要がないため、対応する重複状態の展開を枝刈りできる。密な環境では重複が大きな多分岐を生む可能性があるので、ループを避け、経路コストを増やさず、追加の衝突も生じさせない代替経路が見つかる場合には、バイパスによって分岐を省略する。
評価では、4、8、16、32 近傍のグリッド領域における MAPF ベンチマーク全体で、TRDP なしの CBS と TRDP 付き CBS を比較している。4 近傍は古典的 MAPF、より高い接続性の領域は提示された証拠では MAPF Q として扱われる。各問題についてエージェント数を2から始め、30秒以内に解けなくなるまで1体ずつ増やし、実行時間、制限時間内に解けたエージェント数、競合木の大きさ、TRD の発生回数、重複検出に要した時間の割合を記録した。手作りの解なしインスタンスと高密度の例も調べているが、抜粋だけでは、すべての実験条件や全インスタンスの完全な結果を確定できない。
理論結果は、可解インスタンスで解を返すだけでは完全性として不十分であり、解なしインスタンスでも有限時間で停止する必要があるという CBS の長年の問題を扱う。論文の仮定の下では、TRDP によって関連する探索空間が有限になり、外部のタイムアウトや並列の緩和手続きに頼らず、失敗を報告して停止できる。通常のベンチマークでは TRD がまれで、単一エージェントのループがなければ検査も早期終了するため、追加コストは小さいとされる。一方、幅の狭い通路などエージェント密度の高い環境では多くの TRD が生じ、大きな多分岐により計算量が増える可能性がある。バイパスはこのトレードオフを緩和するが、提示された抜粋は、すべてのスケーリング問題を解消することや、あらゆる連続時間モデル、エージェント形状、他のソルバーでの性能を示してはいない。
CBS は MAPF の代表的な最適・非結合型手法である。多エージェント A* のような結合型手法が全エージェントの状態を一つの共同状態空間にまとめるのに対し、CBS は個別経路と衝突から生成される制約を組み合わせて探索する。ほかの非結合型最適手法にも、解が存在しない場合に停止しない問題があると論文は述べている。完全性には、解が存在するときに有限時間で解を返すことと、解が存在しないときに有限時間でその事実を報告することの二つがある。
本論文の中心問題は、完全性のうち後者である。有限の地図でも時間を状態に含めると、エージェントが同じ場所で永久に待てるため状態空間は無限になり得る。CBS は時間のずれだけが異なる同等の状態を繰り返し生成し、解のないインスタンスで有限停止を保証できない場合がある。連続時間 MAPF では、大きなエージェント形状や交差する辺によって古典的な点エージェントにはない衝突が生じるため、基礎グラフだけの解析で可解性を判断することもできない。
TRDP は、絶対時刻の完全一致ではなく、時間をずらしたときの相対的な将来の振る舞いを重複判定に用いる。後の状態が前の状態と同じ関連情報を持つなら、ループを続ける経路は、その部分を除いても同じ目標へ到達でき、最適解として必要ではない。理論的議論は、ループが劣った経路であること、TRD 制約が最適な実行可能解を遮らないこと、重複除去後の競合木に有限上限があることを示す。したがって、別個の可解性判定器を要求せずに、古典的および連続時間の領域を対象にできる。
論文は、約3万2千件のベンチマーク実験と、数百万個の競合木ノードの生成を報告している。テストしたグリッド領域全体で遭遇した TRD は29件で、通常のグリッドベンチマークのうち TRDP ロジックが発動した問題は0.01％未満だった。TRD は、通路幅1の小さな迷路のように、利用可能な空間に対してエージェント密度が高い問題で最も多く観測された。手作りの解なし問題と高密度の例についても、停止性、競合木の大きさ、実行時間を調べているが、抜粋は全ての生成手順や比較条件を示していない。
提示された解なしの場所交換例では、TRDP 付き CBS は高レベル展開を5回行った後に停止した。ベンチマーク全体では、重複検出が大半の問題で実行時間に有意なコストを加えず、検出処理の割合も一般に小さいと報告されている。選択された高密度の例では、通常の CBS より浅い競合木で解を発見したり、競合木の大きさを減らしたりする場合があった。したがって証拠は停止性と場合によっては性能向上を支持するが、全問題での高速化や全数値比較までは示していない。
TRDP は、時間的にずれた重複状態が探索を無限に引き延ばすことを防ぎ、CBS を本質的に完全にする。理論解析によれば、枝刈りは最適性を保ち、解の有無にかかわらず有限停止を保証する。実験では標準ベンチマークでの発動頻度が低く通常の負担は小さい一方、高密度の設定では重複除去とバイパスによる改善が得られる場合がある。
論文の主目的は、CBS を大幅に大規模化することではなく、完全性に関する理論的な抜け穴を埋めることである。標準 MAPF ベンチマークには解なしインスタンスが含まれておらず、領域によってはそのような問題自体がまれで手作りされることも、停止性の利点を通常のベンチマークで測りにくくする。高密度の環境では TRD が多くなり、大きな多分岐が発生するため、TRDP のコストが常に無視できるわけではない。提示された抜粋だけでは、すべての連続時間意味論、エージェント形状、他の MAPF アルゴリズム、評価外の実運用負荷での挙動は確立されていない。
解のない要求に対して永遠に走り続ける最適プランナーは、実際の協調システムで安全に利用しにくい。TRDP は別個のタイムアウトや並列緩和手続きに依存せず、CBS の探索内部でこの失敗モードを扱う。最適解の保持、完全性の証明、低いと報告されたオーバーヘッドを組み合わせるため、信頼性の高い MAPF および連続時間 MAPF ソルバーの設計に意義がある。
CBS、MAPF の完全性、解なしインスタンス、連続時間の衝突判定、探索における重複検出を研究する読者に適している。特に、最適性を保った有限停止保証を求めるソルバー設計者や、狭い通路と高いエージェント密度を扱う研究者に有用である。大規模なスループットを主目的とする読者は、本論文をまず完全性の貢献として読み、広範なスケーリング結論を得る前に完全な実験結果を確認すべきである。