対象は、重み付きグラフ上で任意の始点から目標状態までの最短経路を求めるヒューリスティック探索問題である。状態集合をV、ピボット集合をPとし、通常のDHは各状態から各ピボットまでの距離を事前計算してルックアップ表に保存する。検索時には、基礎ヒューリスティックとピボットまでの距離から状態間距離の下界を作り、A*探索を導く。提示された抜粋だけでは、提案法のすべての理論的証明や各実験の完全な数値は確認できない。
中心的な新規性は、通常のDHの全距離表ではなく、各状態について一部のピボットへの距離だけを保存する圧縮方式である。CDHは利用可能なメモリ量に合わせてピボット数と状態ごとの保存距離数を柔軟に選べるため、通常DHのようにメモリ量からピボット数が固定されない。圧縮によって欠落した距離情報は、目標からピボットまでの距離に関する上界・下界とBPMXによって補う。さらに、巨大な非圧縮DHを一度作って保存することなく、CDHを直接構築できる点も貢献である。
入力グラフと使用可能メモリが与えられると、まずピボット数を経験的に決定し、Avoid配置戦略でピボットを配置する。その後、各ピボットについて距離を保存する状態集合を作り、各状態の配列内でそのピボットに対応する位置を記録する。各ピボットから幅優先探索を行い、選ばれた状態への距離だけを対応位置に格納する。問題インスタンスごとには、目標から各ピボットまでの距離の境界をBounding手続きで計算し、CDHでヒューリスティック値を生成してA*探索を行う。CDHは状態ごとに異なるピボット集合を使うため不整合になり得るので、実験では展開ノードと直下の子の間だけで値を伝播するBPMX(1)を使用した。
実験は三つの実世界ドメイン、すなわちDragon Age: Originsの八近傍グリッド、北米の道路地図、二次元空間で動くロボットアームで行われた。グリッドではオクタイル距離、道路地図では空気距離を基礎ヒューリスティックとして用い、ロボットアームでは隣接セグメント間の角度を状態とした。比較対象には基礎ヒューリスティックと通常のDHが含まれ、メモリ量、ピボット数、Boundingのパラメータ、解の長さなどを変化させて検索時間を測定した。提示された抜粋からは、全インスタンス数、すべての平均値、実験の反復条件、通常DHとの各ケースの正確な倍率までは確定できない。
CDHの主な利点は、固定したメモリ予算の中で、少数のピボットを全状態に適用する代わりに、より多様なピボットから距離情報を分配できることである。これにより、通常DHに必要なメモリが状態空間の大きさに達しないゲームなどでも、DH型の情報を利用できる。反面、状態ごとに参照できるピボットが異なるためヒューリスティックが不整合となり、BPMXを含む探索時の処理が必要になる。ピボット配置、距離の分配、ピボット数、Boundingの設定は性能に影響し、論文はより高度な分配方法やピボットの優先順位付けを将来課題として挙げている。
メモリベース・ヒューリスティックは、前処理で計算した値をルックアップ表として保持し、探索時に再利用する。パターンデータベースは代表例だが、暗黙的な指数状態空間と適切な抽象化を前提にすることが多い。明示的状態空間では、差分ヒューリスティックが少数のピボットまでの距離から下界を計算する、単純で効果的な表形式ヒューリスティックとして用いられてきた。先行するパターンデータベース圧縮の考え方と、距離表を圧縮したいという問題意識が本研究の背景にある。
通常のDHでは、各状態から全ピボットへの距離、すなわちピボット数と状態数の積に比例する情報を保存する必要がある。利用可能メモリが小さい場合、特に入力グラフ自体を格納するメモリにも満たない場合、通常DHを使えないことがある。単純にピボット数を減らすと、ヒューリスティックの多様性や値の強さが低下し得る。したがって、限られたメモリで有用な距離情報を残す方法が必要になる。
グラフG上の状態aとピボットpの距離d(a,p)を、状態ごとに選択的に保存する。欠落した距離は、目標からピボットまでの距離の上界・下界と、圧縮によって保存された情報を利用して推定する。CDHは許容的であるため、このヒューリスティックを用いたA*探索は最適経路を生成する。ピボットIDを各状態に明示的に保存しない方式では、その識別情報に必要なメモリを半分にでき、各状態についてより多くのピボットへの距離を保存できる可能性があるが、提示抜粋はその方式の全詳細を確定していない。
DAOのost100dマップ、北米の道路地図、3アームおよび4アームのロボット領域が実験対象として示されている。ロボット領域の状態数は、3アームで約1億3400万、4アームで約690億と記述されている。DAOではピボット数と検索時間の関係、Boundingのパラメータ、異なるメモリ量、最適解のホップ数に対する改善傾向を調べた。部屋マップとドロネーグラフでも傾向を確認したが、詳細結果は掲載されていない。
提示された結論では、適度なメモリ、つまり通常DHがほぼ完全なヒューリスティックになるほどではないメモリで、CDHは通常DHに対して検索時間を数倍改善した。入力グラフの格納に必要なメモリより少ない場合でも、CDHは基礎ヒューリスティックに対して数倍の改善を達成したと報告されている。DAOとサンフランシスコ湾岸地域の道路地図では、最適解のホップ数が長いほど基礎ヒューリスティックに対するCDHの改善率が増える傾向が観測された。正確な改善倍率や統計的有意性は、提示された抜粋には記載されていない。
CDHは、通常DHの距離表の一部だけを保存しながら、検索に十分な情報を保つ圧縮方式である。メモリ量を任意に調整でき、非圧縮表を先に作成・保存せずに構築できる。三つの実世界ドメインで、通常DHおよび基礎ヒューリスティックに対する性能上の利点が報告された。著者らは、この考え方がDH以外の表形式距離ヒューリスティックにも適用可能だと述べている。
抜粋には、CDHの完全な数式、Boundingの詳細な定義、ピボット配置と距離分配の全アルゴリズム、実験表の全数値が含まれていない。したがって、どのメモリ量・マップ・インスタンスでどの倍率が得られたかをここから再現することはできない。性能はピボット配置、ハッシュまたは分配方法、キャッシュ効果、基礎ヒューリスティック、グラフ構造に依存する。BPMX(1)は不整合性への対処だが、追加の伝播コストや他の探索設定との比較範囲は抜粋からは確定できない。
本研究は、メモリ制約が厳しい明示的状態空間でも、事前計算型ヒューリスティックを利用可能にする設計を示している。特に、ゲームマップや巨大なロボット状態空間のように、通常DHの最小メモリすら確保できない場合に実用的な意味がある。メモリを単に削るのではなく、ピボットの多様性と状態ごとの情報分布を利用する点が、メモリと探索時間のトレードオフを考える上で重要である。
明示的状態空間、A*、差分ヒューリスティック、パターンデータベース圧縮を研究する読者に適している。限られたメモリで最短経路探索を高速化したいMAPF/MAPD研究者や、ゲーム・道路網・ロボットの探索問題を扱う人にも有用である。CDHの実装詳細や厳密な再現値を必要とする読者は、提示された抜粋だけでなく論文全体を参照すべきである。