Incremental heuristic search とは

インクリメンタルヒューリスティック検索アルゴリズムは、インクリメンタル検索とヒューリスティック検索の両方を組み合わせて、同様の検索問題のシーケンスの検索を高速化します。不完全にしか知られていないドメインや動的に変化するドメインでは重要です。インクリメンタルサーチは、少なくとも1960年代後半から研究されてきました。インクリメンタル検索アルゴリズムは、以前の検索の情報を再利用して、現在の検索を高速化し、検索の問題をゼロから繰り返し繰り返して解決するよりもはるかに早く解決します。同様に、ヒューリスティック検索も少なくとも1960年代後半から研究されてきました。
ヒューリスティック検索アルゴリズムは、しばしばA *に基づいて、目標距離の近似の形で発見的知識を使用して、探索に集中し、未知の探索アルゴリズムよりもはるかに高速に探索問題を解決する。グラフのトポロジ、エッジコスト、開始頂点、またはゴール頂点が時間の経過とともに変化するため、パスを繰り返し検出する必要があるグラフ検索の問題です。
これまで、3つの主なクラスの増分ヒューリスティック探索アルゴリズムが開発されている。
 最初のクラスは、現在の検索が前の検索から逸脱した時点でA *を再開します(例:Fringe Saving A *)。 2番目のクラスは、現在の検索中に前回の検索時のh値(ヒューリスティック、つまり目標との近似距離)を更新して、より情報に基づいたものにします(例:Generalized Adaptive A *)。 3番目のクラスは、現在の検索中の前回の検索時のg値(最初からの距離)を更新し、必要に応じて修正します。これは、A *検索ツリーを以前の検索からA *検索ツリーに変換するものと解釈できます現在の検索(例:生涯計画A *、D *、D * Lite)。
インクリメンタルヒューリスティックサーチアルゴリズムの3つのクラスはすべて、再プランニングの回数によって計画の品質が低下しない点で、類推による計画など、他の再配置アルゴリズムとは異なります。