対象は、グラフ上で各エージェントに開始位置と個別の目標位置が与えられ、各時刻に移動または待機しながら衝突を避けるMAPFである。衝突には、同じ時刻に同じ頂点を占有する場合と、隣接頂点間を反対向きに同時通過する場合が含まれる。論文が主に最適化する目的関数はsum of costsであり、各エージェントが目標へ到達するまでの時間を合計する。最適解のコストを求める一方、makespanなど別の目的関数もあり得ることが説明されている。
中心的な貢献は、従来の単一エージェント探索を状態空間全体に適用するA*系の定式化とは異なる、二層構造のIncreasing Cost Tree Search（ICTS）である。高レベルでは、各エージェントに割り当てる個別経路コストのベクトルを、最小の個別コストから総和が増える順に探索する。低レベルでは、各コストベクトルに対応する経路が衝突なく組み合わせられるかをMDDに基づいて検査する。さらに、ペア単位の整合性検査やEnhanced Pairwise Pruningなど、低レベル探索を縮小する改良も提示する。論文はICTSの最適性を示すだけでなく、どの条件でA*系が優位になるかという限界も明示する。
ICTの根ノードは、他エージェントを無視した場合の各エージェントの最短経路コストを並べたベクトルである。高レベル探索は、そのベクトルの各成分を増加させる子ノードを生成し、総和の小さいノードから調べるため、最初に実行可能な解を表すノードが見つかった時点でその解は最適になる。低レベルでは、各エージェントについて指定コストちょうどの経路候補を保持するMulti-value Decision Diagram（MDD）を構築し、複数MDDの直積を暗黙的に探索して頂点衝突と辺の交換衝突がない組合せを探す。直積全体をメモリに展開せず、深さ方向の系統的探索として検証する点が重要である。ペアのMDDを先に照合し、どのペアにも両立する経路がなければ高レベルノードを棄却することで、より高価な探索を避ける。
評価は、障害物のない4近傍グリッド、ランダム障害物を含むグリッド、およびSturtevantの経路探索ベンチマークに含まれるゲームマップを用いて行われた。大規模なゲームマップとして、Dragon Age: Origins由来の257×257マップも使用され、グリッドでは各エージェント数について100個のランダムインスタンスを生成したと記載されている。比較対象には、通常のA*、Operator Decompositionを加えたA*、基本ICTS、および複数の枝刈りを加えたICTSが含まれる。主な指標は、生成または訪問したノード数、実行時間、制限時間内に解けたインスタンス数、成功率である。抜粋は全ての実験条件や全表の値を網羅していないため、個別の設定ごとの完全な再現条件はここからは確定できない。
ICTSは、低レベルで検査されるコストベクトルの組合せ数が小さい場合、A*が生成する全体状態の組合せを避けられるため有利になる。反対に、エージェント数が少ないのに相互作用のため個別コストの増加量が非常に大きい場合、ICTSの高レベル木が膨張し、A*の方が大幅に速くなる可能性がある。論文は、ノードあたりの定数オーバーヘッドも比較結果を左右し、ノード数が少ないことが常に実行時間の短縮を意味しないと示す。高密度な小グリッドや、長い廊下で二者が位置交換するような構造はICTSの病理的事例として扱われる。将来課題として、低レベル探索のCSPとしての定式化、問題パラメータの影響の解明、重み付きグラフや抽象的な目標への拡張が挙げられる。
MAPFでは、各エージェントが独立に最短経路を選ぶだけでは、同時占有や交換衝突が発生し得る。従来の最適解法はA*の単一エージェント探索を拡張し、全エージェントの状態を組み合わせた探索を行っていた。論文が説明する他の手法には、最適性や一般グラフでの完全性を保証しない分離型アルゴリズムもある。したがって、最適性を保ちながら組合せ爆発を抑える別の探索分解が動機になる。
入力はグラフ、各エージェントの開始頂点、各エージェントの目標頂点である。エージェントは離散時間に合法な辺を移動するか待機し、頂点衝突と反対向きの辺通過を避けなければならない。求めるのは、全エージェントが目標に到達する実行可能な経路集合のうち、経路長の総和が最小のものである。抜粋では、重み付きグラフや集合として指定される抽象目標は本来の評価対象として確立されていない。
ICTノードはエージェントごとの個別コストを成分とするベクトルで、ノードのコストはその総和である。MDDは、開始位置から指定された深さで目標に到達する全ての候補経路を有向非巡回構造として表し、各時刻の位置候補を保持する。MDDの直積を探索する低レベル検査では、同時刻の位置一致と反対向きの辺通過を禁じる。理論的には、訪問されるICTノードの総和および低レベルで扱う状態の評価値が最適解コストを超えないことが、ICTSの探索効率の根拠として示される。
実験では、8×8の開放グリッド、3×3グリッド、障害物割合の異なる32×32グリッド、さらにゲーム由来の大規模マップが扱われた。グリッド実験では、難しい事例を生成するためのエージェント結合機構が使われた場合と、改良的なID枠組みを使わない場合が区別されている。ゲームマップではIDが有効化された実験が行われ、解けたインスタンスについて平均値が報告された。抜粋だけでは、全マップ名、全エージェント数、各アルゴリズムの実装詳細までは確定できない。
8×8開放グリッドでは、エージェント数が少ない領域でICTSがA*系より少ないノードを生成し、同程度またはやや短い時間で解いたと報告されている。エージェント数が増えると相対的な優位性は変化し、ある範囲ではA*系がノード数と時間の両方でICTSを上回った。別の実験では、強化された枝刈りを持つICTSが基本ICTSより高速で、A*系より大幅に速い場合が示され、8×8グリッドでは「ほぼ三桁のオーダー」と表現されている。DAOマップでも、ICTSやICTS＋強化枝刈りがA*＋ODより速い設定が複数報告される一方、全ての設定で一貫して優位だとは抜粋は示していない。
ICTSは、最適MAPFを個別コストの決定と衝突しない経路集合の検査に分解することで、A*とは異なる最適探索を実現する。最初に見つかる実行可能なICTノードが最適解を表すため、方法の正しさは高レベルのコスト順序と低レベルの完全な検査に基づく。実験は、グラフの形状、エージェント密度、衝突の構造、エージェント数に応じてICTSとA*系の優位性が変わるという理論的説明を支持する。
ICTSの計算量は、個別コストベクトルの探索範囲やMDD直積の大きさに強く依存する。エージェント数が小さくても必要なコスト増分が大きい場合や、密集した環境で衝突が多い場合には、ICTSが極端に遅くなり得る。低レベルのMDD探索は最悪時に大きな状態空間を扱い、ペア検査にも追加コストがある。提示された抜粋は、提案法が全てのMAPF変種、目的関数、グラフクラスで有効だとは確立していない。
本論文の重要性は、最適MAPFの組合せ爆発を、単一の全状態探索だけでなく個別経路コストの構造から扱う視点を示した点にある。MDDによる候補経路の表現は、衝突検査と枝刈りを体系化する基盤になる。さらに、どのアルゴリズムが常に最良とは限らず、問題構造に応じて探索方式を選ぶべきだという実証的な教訓を与える。
最適MAPFの探索分解、MDD、経路コストベクトル、A*との計算量比較に関心がある研究者に適している。特に、最適性保証と実際の性能のトレードオフを、グリッドやゲームマップ上の実験と結び付けて学びたい人に向く。強化枝刈りや後続のICTS系研究の背景を理解する出発点としても有用である。