対象は、グリッド上を移動する複数エージェントに対して、衝突のない経路を計画するMAPFである。入力は直交近傍をもつ4連結グリッド地図と、固有の始点・目標をもつエージェント集合である。時間は離散化され、各エージェントは隣接セルへの移動またはその場での待機を行う。目的は、すべてのエージェントが目標に到達し、目標到達後は他のエージェントのために移動せず、個別経路コストの総和を最小化することである。
主要な新規性は、CBSのヒューリスティックとバイパスを、2エージェントの関係から3エージェント以上の相互作用へ拡張した点にある。著者らは、現在のCBSノードにおいて、各エージェントのコスト最小経路を組み合わせても衝突を避けられない集合を競合クラスタとして動的に検出する。クラスタの存在から、現在ノードのコストより少なくとも1高い解が必要だという下界を導く。さらに、一部のエージェントの経路を同じコストの別経路に置き換え、競合数を減らすクラスタ対応バイパスを提案する。
基礎となるCBSは、各エージェントを個別に経路計画し、衝突が見つかると制約木の子ノードを生成して再計画する。提案手法は、WDGによる既存のペアワイズ・ヒューリスティックを計算した後、競合状態グラフから関与度の高いエージェントを選び、他のエージェントとのMDD間でmutex伝播を行う。MDDは、制約を満たすコスト最小経路が各時刻に訪れ得る頂点を表し、異なるMDDの同じレベルにあるmutex頂点は、その組合せでは個別最適経路を同時に実現できないことを示す。選択したエージェントのMDDから互換性のないノードを除去し、競合クラスタまたはバイパスを見つける。クラスタが見つかればヒューリスティック値を増やし、バイパスが見つかれば経路と競合状態グラフを更新して、同じコストで競合を減らす。
評価では、最先端のCBS変種であるWDGと、WDGにクラスタ・ヒューリスティックとバイパスを加えたWDG+CHBPを比較した。加えて、クラスタ・ヒューリスティックだけのWDG+CHと、提案バイパスだけのWDG+BPも調べた。ベンチマークは、ランダム障害物地図、空の地図、倉庫地図、ビデオゲーム地図の4種類で、各設定にはランダムな始点・目標の集合と、短距離・長距離を均等に含む集合がある。各インスタンスを1分実行し、実行時間、CBS競合木のノード展開、制限時間内に解けたかどうかを報告した。抜粋は実験環境と設定を示しているが、各手法の正確な数値、全グラフの値、統計的ばらつきは確定させていない。
提案法の利点は、ペアごとには見えにくい相互排他をクラスタとしてまとめ、CBSの高位探索をより早く枝刈りできる点である。クラスタ検出とバイパスを同時に行うため、単に下界を強くするだけでなく、同じコストの経路変更によって後続の衝突も減らせる。代償として、MDDとmutex伝播を含むヒューリスティック計算はWDGより高価であり、抜粋では平均計算時間がWDGの2倍を超えないとされるが、詳細な条件別数値は示されていない。再利用可能なmutex伝播は、伝播情報の一部しか得られない可能性がある一方、キャッシュによってほぼ常に高速化したと報告されている。将来課題として、より複雑なクラスタの捕捉、WDGの整数計画への統合、クラスタ内の全衝突を効率的に解消する方法が挙げられる。
MAPFの最適解探索は、さまざまな目的関数のもとでNP困難であり、倉庫自動化、ドローン群制御、コンピュータゲームのチーム移動などに応用される。CBSは、エージェントを個別に経路計画してから衝突を解消する、最適MAPFの代表的なベストファースト探索である。近年のCBSの改良は、対称性処理、複雑な許容ヒューリスティック、バイパスを組み合わせてきたが、数十エージェント程度でもタイムアウトが起こり得る。
従来の高性能CBS改良は、主としてエージェントのペア間の衝突や依存関係を扱っていた。ペアごとの推論では、あるエージェントの代替経路が別のエージェントと衝突するような、多数エージェントにまたがる不可避性を十分に表せない場合がある。本論文の問題設定は、これらの相互作用を利用して、最適性を保ちながらCBSの探索量を削減することである。
競合クラスタは、現在ノードの制約下で、クラスタ内のエージェントにコスト最小で衝突のない経路割当が存在しない集合として定義される。クラスタが存在すれば、そのノードから得られる衝突回避解の個別コスト総和は、現在ノードのコストより少なくとも1大きい。提案法はWDGのペアワイズ下界にクラスタ数を加え、さらに経路置換によるクラスタ対応バイパスを利用する。
4つの4連結グリッド地図で、エージェント数を地図ごとに変化させたインスタンスを評価した。各地図設定には25インスタンスからなる2種類の集合があり、すべてのアルゴリズムをC++で実装して1分の制限時間で実行した。比較対象はWDG、WDG+CH、WDG+BP、WDG+CHBPであり、WDGには既存の依存グラフ・ヒューリスティック、対称性推論、競合優先付け、バイパスが含まれる。
抜粋された結論では、WDG+CHBPが解けるインスタンス数を増やし、実行時間と競合木ノード展開を削減したと報告されている。改善は特に密な地図で顕著であり、タイムアウトしたインスタンスでも下界の最小値を大きく押し上げた。正確な改善率、地図別の平均値、手法間の有意差は、 supplied excerpt には確立されていない。
3エージェント以上を同時に扱う競合クラスタ推論は、ペアワイズ推論だけに依存するCBSを改善する有効な方向として示された。クラスタ・ヒューリスティックとバイパスを組み合わせることで、強い下界と少ない高位探索を両立する。論文は、特に大規模または密なMAPFで、多数エージェントの相互作用を明示的に扱う価値を示している。
抜粋は、すべての実験結果の数値、メモリ使用量、クラスタ検出の詳細な計算量を提示していないため、改善の大きさやスケーリング特性を完全には判断できない。評価は4種類のグリッド地図と1分の制限時間に基づくため、他の地図構造、目的関数、制限時間で同じ傾向になるかは確定していない。3エージェント・ヒューリスティックを扱う既存研究との直接比較は、MAPFのコスト定義を変更する必要があるとして行われていない。再利用mutex伝播は情報を弱める可能性があり、より複雑なクラスタの解消も未解決である。
本研究の意義は、MAPFのボトルネックが個別の衝突だけでなく、複数エージェントの同時の不可避な干渉にもあることを、CBSの探索機構に組み込んだ点にある。これは、密集した倉庫や狭い通路のように、局所的な選択が多数のエージェントへ波及する環境で特に有用である。最適性を維持するCBSの枠内で、下界強化とコスト同値の経路変更を統合したことも実用上重要である。
最適MAPF、CBS、MDD、mutex伝播、依存グラフ・ヒューリスティックに関心のある研究者に適している。特に、ペアワイズ推論の限界、密な地図での高位探索、ヒューリスティック計算コストと探索削減のトレードオフを調べたい読者に推奨される。