インクリメンタルヒューリスティック探索は、グラフが時間とともに変化する場合にグラフ内の経路を見つける問題に対処する、人工知能におけるアルゴリズム群の一つです。環境が変化するたびに完全な解をゼロから再計算するA*などの古典的なヒューリスティック探索法とは異なり、インクリメンタルヒューリスティック探索アルゴリズムは、以前の探索努力から可能な限り多くの情報を再利用します。この再利用により、動的または部分的に既知の環境での計算コストを大幅に削減でき、ロボットナビゲーション、ビデオゲームの経路探索、自動運転車のルーティングなどのアプリケーションで特に価値があります。
核となるアイデアは、ヒューリスティック関数と探索木を維持し、エッジコストの変化や新しい障害物の発見に応じてそれらをインクリメンタルに更新することです。変化が発生すると、アルゴリズムは以前の探索のどの部分がまだ有効で、どの部分を修正する必要があるかを特定し、必要な更新を伝播させます。このアプローチは、静的グラフを想定する古典的なヒューリスティック探索と、ヒューリスティックなしのインクリメンタル探索（経路を再利用する可能性があるが、ヒューリスティックのガイダンスを欠く）の両方とは対照的です。
歴史的発展
インクリメンタルヒューリスティック探索の基礎は、1990年代後半から2000年代初頭に築かれました。最も影響力のあるアルゴリズムであるD Liteは、2002年にSven KoenigとMaxim Likhachevによって導入されました。D Liteは、1994年にAnthony Stentzによって開発された、移動ロボットナビゲーション用に設計された初期のDアルゴリズムに基づいています。D Liteは、元のD*を簡素化しながらその効率を維持し、この分野の標準的な参照となっています。
もう一つの重要なアルゴリズムは、2001年にKoenigとLikhachevによって導入されたLifelong Planning A（LPA）です。LPAは、ヒューリスティックを一貫性に保ちながらエッジコストの変化を処理し、D Liteの基礎を形成します。この分野はその後、Generalized Adaptive A（GAA）やAnytime D*などの変種で拡張され、これらは解の品質と計算時間をトレードオフします。
アルゴリズムの原理
インクリメンタルヒューリスティック探索アルゴリズムは、通常、各ノードに対して2種類の値を維持します：g値（開始点からの既知の最良経路のコスト）とh値（ゴールへのヒューリスティック推定）です。また、ノードが一貫しているかどうか、つまりg値がその前駆ノードの最小値と等しいかどうかも追跡します。エッジコストが変化すると、アルゴリズムは影響を受けるノードのg値を更新し、f = g + hで順序付けられた優先度キューを使用して探索木を通じて変化を伝播させます。
重要な革新は、LPAとD Liteにおける「rhs値」（右辺値）の使用であり、これは前駆ノードのg値とエッジコストの合計の最小値を表します。ノードは、g値がrhs値と等しい場合に局所的に一貫しています。アルゴリズムは、局所的に一貫性のないノードのリストを維持し、それらをキー（min(g, rhs) + h, min(g, rhs)のペア）の順に処理します。これにより、探索の必要な部分のみが再計算されることが保証されます。
ロボティクスとAIにおける応用
インクリメンタルヒューリスティック探索は、未知または変化する環境での経路計画のためにロボティクスで広く使用されています。例えば、建物を探索するロボットは、最初に地図に基づいて経路を計画するかもしれませんが、新しい障害物（例えば、閉じたドア）を発見すると、再起動せずに計画をインクリメンタルに更新できます。これは、計算時間が限られているリアルタイムナビゲーションにとって重要です。
ビデオゲームでは、ノンプレイヤーキャラクター（NPC）が、移動する障害物や変化するゴールを持つ動的な地形をナビゲートする必要があることがよくあります。インクリメンタルヒューリスティック探索により、効率的な再計画が可能になり、ゲームの応答性が向上します。この技術は、配達ルートが交通状況に適応する必要がある物流や、リンクコストが変動するネットワークルーティングにも適用されています。
他の探索方法との比較
古典的なA探索は、静的グラフに対して最適かつ完全ですが、グラフが変化すると以前の作業をすべて破棄するため、動的設定では非効率です。インクリメンタルヒューリスティック探索は、Aの最適性保証を維持しながら、以前の計算を再利用します。ただし、探索木と一貫性情報を保存するために追加のメモリが必要です。
もう一つの関連するアプローチは、任意時点探索であり、良い解を迅速に見つけ、その後時間が許せば改善することを目的としています。Anytime D*などの一部のインクリメンタルアルゴリズムは、両方の特性を組み合わせています：準最適な解を迅速に返し、時間が許せばそれを洗練できます。これは、時間が重要なアプリケーションで特に有用です。
現在の研究と将来の方向性
インクリメンタルヒューリスティック探索の最近の研究は、非常に大きなグラフへのスケーリング、連続状態空間の処理、機械学習との統合に焦点を当てています。例えば、学習ベースのヒューリスティックを使用して初期のh値を改善し、展開数を減らすことができます。また、マルチコアプロセッサ向けのインクリメンタル探索の並列化や、高次元問題向けのRRT*などのサンプリングベースのプランナーとの組み合わせに関する研究もあります。
現代の人工知能システムの文脈では、インクリメンタルヒューリスティック探索は、ウェイモの自動運転車やテスラオートパイロットシステムなどの具現化エージェントにとって依然として重要であり、リアルタイムの再計画が不可欠です。その原理は、探索を学習するための機械学習や深層学習の研究にも影響を与えていますが、古典的なアルゴリズムは保証された最適性の標準として残っています。
関連項目
参考文献
- Koenig, S., & Likhachev, M. (2002). D* Lite. Proceedings of the National Conference on Artificial Intelligence.
- Koenig, S., & Likhachev, M. (2001). Lifelong Planning A*. Artificial Intelligence.
- Stentz, A. (1994). Optimal and Efficient Path Planning for Partially-Known Environments. IEEE International Conference on Robotics and Automation.