対象は、グラフ上で複数のラベル付きエージェントを、それぞれの開始位置から目標位置へ衝突なく移動させるMAPFである。各時刻にエージェントは隣接頂点へ移動するか待機でき、同一頂点の同時占有は禁止される。また、隣接する2頂点を2体のエージェントが反対方向に同時通過することも禁止される。目的は、全エージェントが目標へ到達する行動列のうち、総コストが最小のものを求めることである。通常の移動と待機のコストは1であるが、目標位置での待機は0として扱われ、そこで待機してから移動する場合には待機回数が後続移動のコストに反映される。
第一の貢献は、EPEA*をMAPFへ適用する方法を詳しく示したことである。EPEA*は、最適解のコストを超える評価値を持つ余分なノードを生成しないよう、問題領域の知識を利用する。第二に、EPEA*の枠組みを一般化し、その上にPDBヒューリスティックを利用できるようにした。著者らは、MAPFにPDBを適用した例として当時初めての報告だと述べている。第三に、Standleyの演算子分解と、部分展開に基づく基本部分展開を組み合わせた新しい最適探索法を提案した。
通常のA*では、ノードの評価値はこれまでのコストとヒューリスティック値の和で決まるが、EPEA*は静的な評価値とオープンリストに保存する値を区別する。ノードを展開するとき、すべての組合せを一度に生成するのではなく、適切な増分コストを持つ後続だけを順次生成し、それ以外を避けることでオープンリストを小さく保つ。複数エージェントの複合操作については、各エージェントの操作が評価値をどれだけ増加させるかを組み合わせ、必要な増分を満たす組合せを再帰的に列挙する。PDBは、衝突に頻繁に関与するエージェント群について構築すると有効だが、そのような群は事前には分からないため、独立性検出（ID）がエージェントをグループ化した後にペアワイズPDBを構築する。さらに、基本部分展開を演算子分解に重ね、標準ノードの先行ノードが持つ保存値に等しい評価値の中間ノードだけを残すBPEODA*を定義する。
実験では、障害物のない4近傍8×8グリッド上で、エージェント数を変えた事例が比較された。比較対象には通常のA*、演算子分解A*（ODA*）、基本部分展開A*（BPEA*）、演算子分解と基本部分展開の組合せ（BPEODA*）、EPEA*、およびEPEA*にPDBを加えた手法が含まれる。評価は、割り当てられた時間とメモリの範囲内で解けるか、実行時間、探索ノード数、およびPDB構築コストを中心に行われた。抜粋には、全インスタンスの構成、各手法の正確な実行時間、ノード数、使用したヒューリスティックの詳細は確立されていない。
報告された結果では、簡単な事例を除きA*とBPEA*は、1事例あたり2分・2ギガバイトという割当資源内で解けなかった。ODA*はA*より高速で、BPEA*もA*より高速だったが、BPEA*は不要なノードを生成してから刈り込むオーバーヘッドを負うと説明されている。BPEODA*はオープンリストを大幅に小さくできるため、A*とODA*を大きく上回り、EPEA*はこれらすべてより高速だった。難しい事例ではPDBがEPEA*をさらに平均で最大約3倍改善した一方、易しい事例ではPDB構築時間のため、ノード数では最良でも時間では最良でなかった。PDBの構築時間はインスタンス依存であり、複数事例間で償却できないため、性能向上と前処理コストのトレードオフがある。
MAPFの最適解を求めることは、複数エージェントの相互作用によって単一エージェント探索より難しくなるため、近年大きな関心を集めている。先行研究では、演算子分解や部分展開など、A*を拡張する複数の方向が提案されていた。本稿は、そうしたA*バリアントを同一のMAPF設定で整理し、探索ノードの生成を抑える技術に焦点を当てる。
入力はグラフと、開始頂点・目標頂点を持つ複数のラベル付きエージェントである。エージェントは移動または待機を行うが、頂点衝突と反対方向の辺通過衝突を避けなければならない。待機と移動の通常コストは1で、目標上の待機は0であり、そこから再び移動する場合のコスト規則も定義される。求めるのは、すべてのエージェントが目標へ到達する最小コストの行動列である。
EPEA*では、通常の評価値とオープンリストに保存された評価値を分離し、現在必要な評価値を持つ後続だけを展開する。複合エージェントの操作による評価値増分を組み合わせるため、必要な合計増分を満たす組合せを再帰的に探索する。PDBは衝突に関係するエージェント群に対して構築され、IDによるグループ化を利用して構築対象を決める。BPEODA*は、演算子分解で生じる中間ノードに部分展開の条件を適用する。
実験の明示的な環境は、障害物のない4近傍8×8グリッドで、エージェント数を変化させたものである。通常のA*、ODA*、BPEA*、BPEODA*、EPEA*、EPEA*とPDBの組合せが比較された。各インスタンスには2分と2ギガバイトの資源上限が設定されたと報告されているが、抜粋は他のデータセットや反復条件を示していない。
A*とBPEA*は、最も簡単な事例を除いて資源上限内に解けなかったと報告されている。ODA*はA*より速く、BPEODA*は小さいオープンリストによってA*とODA*を大きく上回った。EPEA*は比較されたバリアントの中でさらに高速で、難しい事例ではPDB追加により平均で最大約3倍改善した。易しい事例では、EPEA*+PDBはノード数では最良だったが、PDB構築時間を含む実行時間では最良とは限らなかった。
本稿は、MAPFの最適探索において、余分なノードの生成を避ける部分展開が重要であることを示している。EPEA*は、提示された実験条件では既存の比較手法より高速だった。PDBは難しい事例で有効だが、インスタンス依存の構築費用がある。著者らは、先行する技術についてさらに重要な知見を完全版で提示したいとしている。
提示された証拠は論文の中間部を省略しており、EPEA*の完全なデータ構造、増分計算、衝突処理の実装詳細は確立されていない。実験結果も一つのグリッド設定についての要約であり、他の地図、障害物密度、エージェント配置、評価値の正確な表は示されていない。PDBの構築方法はIDに依存し、衝突の多いエージェントを事前に特定できないことが制約になる。したがって、報告された優位性がすべてのMAPF分布や目的関数に一般化することは、抜粋だけからは判断できない。
この研究は、最適MAPF探索で計算時間だけでなく、どのノードを生成しないかが重要であることを明確にする。EPEA*、PDB、ID、演算子分解の組合せは、探索空間の構造を利用してオープンリスト操作とノード展開を抑える設計例を与える。特に、PDBの有効性と構築コストを同時に示す点は、強いヒューリスティックを導入する際の実用的な判断材料になる。
最適MAPF、A*の部分展開、演算子分解、PDBヒューリスティックの関係を短く把握したい研究者に適している。大規模な実運用システムの評価や、非最適MAPF、確率的環境、異なるコストモデルの研究者は、抜粋に含まれない追加評価が必要である。