対象は、地図探索、コンピュータゲーム、ロボティクスなど、状態空間全体は比較的小さい一方で、任意の開始状態から任意の目標状態への最適経路を極めて短時間で求めたい問題である。通常の組合せ問題ほど巨大でなくても、リアルタイム用途では単純なヒューリスティクスによる相対的な高速性では不十分な場合がある。本研究は解の品質を犠牲にする近似探索ではなく、メモリを使って探索を高速化しながら最適解を維持する方向を扱う。供給された抜粋は、MAPFやMAPD、複数エージェント間の衝突制約を対象としているとは述べていない。
本研究の新規性は、元の状態空間における一部の状態対の真の距離を保存し、それを任意の状態対に対する許容的なヒューリスティックへ変換する一般的な枠組みを導入した点にある。二つの表形式手法として、基準状態までの距離差を使う差分ヒューリスティクスと、状態を代表する正準状態を使う正準ヒューリスティクスを示す。さらに、正準状態の配置、複数の参照状態の利用、既存ヒューリスティクスとの最大値の利用など、推定値を改善する方法を検討する。従来のパターンデータベースが一般には特定のパターンや目標構造に依存するのに対し、任意の開始状態と目標状態を扱える点を、両者を統合する一般的な利点として位置づけている。
状態空間をグラフとみなし、全状態対の最短距離を保存すれば完全なヒューリスティックになるが、計算時間は最大で状態数の三乗、記憶量は状態数の二乗に達する。差分ヒューリスティクスでは、少数の基準状態から各状態までの真の距離を保存し、二状態について基準状態への距離の差の絶対値を計算して下界を得る。正準ヒューリスティクスでは、各状態を近い正準状態へ対応付け、正準状態間の距離と各状態から対応する正準状態までの距離を組み合わせて推定する。複数の基準または正準状態から得た値、既存ヒューリスティック、追加の検索情報を組み合わせ、実験では既存ヒューリスティックと正準ヒューリスティクスの最大値を使う。正準状態はランダムにも、配置アルゴリズムにも、領域固有の規則にもとづいて配置でき、局所的な正準近傍の形状を考慮すると推定値を改善できる。
実験は経路探索、作動ロボットアーム、8パズルを扱い、供給された抜粋では経路探索とロボットアームでA*を使い、8パズルでは別の探索設定を使ったと記載されている。経路探索では、幅2の廊下を持つ迷路と、16×16の部屋をランダムに開いた扉で接続したマップを使い、公開マップを利用した。詳細な比較では、状態数206,720の512×512の部屋マップ上で、解の長さが256～512の640問題を平均し、正準状態数を0から125まで変化させた。報告された値では、全状態対データ、オクタイル距離、差分ヒューリスティクス、正準ヒューリスティクスを、ヒューリスティック値、展開ノード数、時間、メモリ量などで比較している。供給された抜粋だけでは、ロボットアームの具体的なデータ、全ベースラインの名称、8パズルで使った探索アルゴリズムの詳細は確定できない。
結果は、少数の真距離情報でも探索量を大幅に減らせることを示す一方、完全な全対距離データにはなお理論上の精度上限があることを示している。正準状態の数と位置は性能とメモリのトレードオフを決め、領域の構造を反映した配置が、ランダムな配置より有利になり得る。パターンデータベースと異なり任意の目標状態に使える一般性があるが、状態空間全体がメモリに収まるという仮定が基本的な制約である。結論では、最良の正準状態数と配置、ヒューリスティックやパラメータの選択指針は未解決であり、応用開発者への理論的ガイダンスが今後必要だとされる。さらに、より小さな抽象空間で得た解を元の空間で利用する可能性にも触れているが、この方向の詳細な実験は抜粋に示されていない。
従来のヒューリスティック探索では、より大きな問題を解くことが重視される一方、地図型領域では比較的小さな問題をリアルタイムに解く速度が重要になる。パターンデータベースはメモリを使って許容的ヒューリスティクスを自動構築する代表的手法だが、一般には保存したパターンや目標状態への依存がある。全状態対の最短距離を保存すれば最適な推定値を得られるが、現実的でない記憶量と前処理時間を要する。
任意の開始状態と目標状態に対して、最適解を保ったまま探索時間を短縮することが問題である。状態数をNとすると、全対最短距離データは記憶量が状態数の二乗規模となり、前処理は最大で状態数の三乗規模になる。したがって、限られたメモリで全対情報に近い推定精度を得る必要がある。
差分ヒューリスティクスは、基準状態からの距離の差の絶対値を利用する。正準ヒューリスティクスは、状態を正準状態へ割り当て、正準状態間の距離と局所距離を使って状態対を三角測量する。供給された本文ではヒューリスティクスが許容的であると述べられているが、その証明は紙幅の都合で省略されている。別の参照情報による追加検索によって状態の位置を三角測量し、推定値を改善できる。
部屋マップの詳細実験では、512×512マップに206,720状態があり、640個の問題を平均した。全対データの最適ヒューリスティック値は384.59で、完全データには210億のヒューリスティックエントリが必要と見積もられた。8パズルでは状態数181,440、31,125問題、平均最適経路長21.84手を用い、通常の差分・正準設定と、空白が中央にある状態を正準状態にした設定を比較した。
部屋マップでは、オクタイル距離の平均展開数21,686に対し、正準状態10個で3,440、125個で760まで減少した。125個の設定は、完全な全対情報に必要なメモリの約1000分の1で29倍の展開削減を達成し、時間では最大13倍の削減が報告されている。8パズルでは、特別な正準状態20,160個と深さ3の設定により、平均69ノード展開となり、マンハッタン距離より40倍良いと報告された。全体の要約として、従来ヒューリスティクスに対する探索速度6～14倍向上が示されている。
真距離ヒューリスティクスは、部分的な状態間距離を再利用して、任意の開始・目標状態に対する探索を高速化する。全対最短距離の大部分の利点を、はるかに少ないメモリで得られることが、複数領域の実験で示された。これは最適解を維持したリアルタイム経路探索におけるメモリ活用の有効性を示す。
基本的な議論は、完全な状態空間がメモリに収まる場合を仮定している。正準状態の最適な数と配置は未解決であり、配置に関する改善余地がある。抜粋では、ロボットアーム実験の数値、8パズルの詳細な探索方式、すべての比較条件は示されていないため、それらについては判断できない。
本研究は、検索時に計算する情報だけでなく、オフラインに蓄積した真距離を探索性能へ変換する設計を明確にする。特に、全対距離表が非現実的な領域でも、少数の参照状態で展開数を大幅に減らせる可能性を定量的に示した点が重要である。複数エージェント探索への直接的な評価は供給資料にないが、状態空間と許容的推定値を扱う設計原理として読むことはできる。
任意の開始・目標状態を持つ最適経路探索、リアルタイム地図探索、ゲームやロボットの状態空間探索に関心がある読者に向いている。パターンデータベース、ランドマーク距離、メモリと探索量のトレードオフを比較したい研究者にも有用である。MAPFやMAPDの具体的なアルゴリズム、衝突回避、複数エージェントの実験結果を求める読者には、この抜粋だけでは不十分である。