対象は、グラフ上で複数エージェントを衝突なく開始頂点から目標頂点へ移動させるマルチエージェント経路探索（MAPF）である。時間は離散化され、各エージェントは隣接頂点への移動または現在頂点での待機を行う。研究の焦点は、衝突を制約として分岐するCBSの高レベル探索を、より情報量の多い許容的ヒューリスティクスで導くことである。
第一に、従来のCGヒューリスティクスは現在の解にあるカーディナル衝突だけを考慮するため、衝突グラフから得られる許容的情報には限界があることを定理によって分析する。第二に、将来の子ノードで生じる衝突や、エージェント対の経路依存性を利用するDGおよびWDGという二つの許容的ヒューリスティクスを導入する。第三に、WDGがDGを厳密に支配し、DGがCGを厳密に支配する関係を示す。さらに、遅延計算とメモ化を用いて、強いヒューリスティクスの計算オーバーヘッドを抑える。
CBSの各高レベルノードは、エージェントごとの制約、制約を満たすコスト最小経路、経路コストの総和を持つ。CGは、現在解に含まれるカーディナル衝突を辺とする衝突グラフを作り、その最小頂点被覆の大きさを下界として使う。本論文は、両方の子ノードに解がある場合、単一の衝突を解消することによるコスト増分が、衝突グラフから得られる範囲では実質的に1を超えて評価できないことを示す。DGは、あるエージェント対について、制約下のコスト最小経路同士が必ず衝突するかを、二つのMDDを段階的に組み合わせて調べ、依存する対ごとに少なくとも1の増分を数える。WDGは、依存する対を重み付き辺として表し、衝突のない二者の経路コストと現在解の二者コストとの差分を辺の重みにして、重み付き頂点被覆をヒューリスティクスにする。
評価では、4近傍グリッド上でCBS、ICBS、CG・DG・WDGを備えたCBSHを比較している。各マップとエージェント数について、開始頂点と目標頂点をランダムに選んだ50インスタンスを生成し、20×20の空マップ、30%のランダム障害物を持つ密なマップ、障害物密度を変えたマップ、および大きなマップを用いたと記載されている。指標は成功率、展開したCTノード数、実行時間、ルートノードのヒューリスティクス値、展開ノード当たりの計算時間であり、小規模マップでは各ソルバと各インスタンスに1分の制限を設けた。実験はC++で、2.80GHzのIntel Core i7-7700と8GB RAMのラップトップ上で行われた。提供された抜粋には、大規模マップの正確なサイズ、全エージェント数、すべての結果表の数値は含まれていないため、個別の比較を網羅的には確定できない。
CGの弱点は、現在の解で見えているカーディナル衝突だけでは、子孫ノードの解で必ず現れる依存性を捉えられないことである。DGはこの将来の依存性を扱うが、依存性があっても増分を1として数えるため、実際の追加コストが大きい場合には情報を捨てる。WDGは追加コストを重みとして利用するため、より強い下界を得られる一方、MDD構築や二エージェント問題の解法に計算費用がかかる。空マップでは迂回経路が多く、密なマップではエージェント間の結合が強いため、ヒューリスティクスの値の改善とノード削減効果の関係は単純ではない。著者らは、将来課題として非最適CBS、ICTSやMDD-SATなど他のMAPFアルゴリズム、さらに三者以上の依存関係への一般化を挙げている。
MAPFはNP困難であるが、削減型、A*型、専用探索型など多くの最適解法が研究されている。CBSは、低レベルで各エージェントの経路を計算し、高レベルで衝突を制約に分割する二層探索法である。CBSHはCBSの高レベル探索に許容的ヒューリスティクスを導入した先行研究であり、本論文ではその従来手法をCGと呼んでいる。
グラフは無向かつ重みなしで、通常の移動と待機には単位コストがあり、目標到達後の終端待機はコスト0である。頂点衝突は同じ時刻に同じ頂点を占有すること、辺衝突は反対方向に同じ辺を通過することである。求めるのは制約を満たす全エージェントの経路であり、CBSのノードコストは経路コストの総和である。
CGはカーディナル衝突を辺とする衝突グラフの最小頂点被覆を用いる。DGは二エージェントのMDDを組み合わせ、すべての分岐が衝突状態になってこれ以上展開できなくなるかを調べ、依存関係を検出する。WDGでは、二エージェントの衝突回避コストと現在経路コストの差分を非負の値として計算し、正の差分を持つ依存対に重みを与える。高価な評価を必要な時点まで遅らせ、同じ制約集合に対応する依存関係、辺、重み、MDDの計算結果をメモ化することでオーバーヘッドを抑える。
実験はC++で、2.80GHzのIntel Core i7-7700、8GB RAMのラップトップ上で実施された。4近傍グリッドに対し、空の20×20マップ、障害物を含む20×20マップ、障害物密度を変えた設定、大きなマップを扱っている。CBS、ICBS、CG・DG・WDGを使うCBSHを比較し、CBSHには遅延計算などの二つの改善を適用した。大規模マップの正確な構成、全エージェント数、その他の実験パラメータは、提供された抜粋だけでは完全には確定しない。
DGとWDGはCGを厳密に支配し、WDGはDGを厳密に支配すると報告されている。WDGはCGと比べて成功率を大幅に向上させ、展開ノード数と実行時間を最大50分の1にした。メモ化により、グラフの辺と重みの計算時間を90%以上削減したと記載されている。抜粋はすべてのマップとエージェント数に対する具体的な成功率、実行時間、ノード数を提示していない。
ペアワイズな依存関係を考慮することで、CBSの高レベル探索に対してCGより強い許容的下界を与えられる。DGは依存関係の有無を利用し、WDGは依存しているかどうかだけでなく、衝突回避に必要な追加コストの大きさも利用する。実験結果は、計算オーバーヘッドが合理的な範囲にあり、解けるインスタンス数と探索効率が改善することを支持している。
CG、DG、WDGはいずれも主にエージェント対の依存関係を扱うため、三者以上の同時依存を完全には表現しない。密なマップではエージェントが強く結合し、ペアワイズ情報だけではより強い全体下界に近づきにくいと報告されている。WDGの計算はCGより高価で、遅延計算やメモ化が必要になる。提供された抜粋からは、実験結果の統計的ばらつき、他のデータセットでの再現性、非グリッドグラフや実運用環境での性能は確定できない。
CBSの高レベル探索で衝突を解消する際、現在の解にある衝突だけを数えると、将来の制約波及を十分に評価できないことを明確にした。ペアワイズ依存性を許容的下界へ変換する枠組みは、最適性を保ちながら探索量を減らす実用的な設計指針になる。MAPFが倉庫ロボット、クアッドロータ群、ゲームキャラクターなどに利用される中で、成功率と実行時間の改善は実装上重要である。
CBS、ICBS、CBSHの内部動作と許容的ヒューリスティクスを学びたいMAPF研究者に向いている。MDD、衝突グラフ、頂点被覆、エージェント間依存性を組み合わせた探索改善に関心がある読者にも有用である。実験の完全な数値、大規模マップの詳細、グリッド以外の性能を必要とする場合は、提供された抜粋だけでは不十分であり、原論文全体の確認が必要である。