D* Lite
地図が変わったとき、一から探索し直さずに経路を安く修復するインクリメンタルな経路探索アルゴリズム。
未知の地形を探索するロボットは、障害物に近づいて初めてその存在に気づく。D* Liteはゴールから逆向きに探索し、探索木のコストを保持し続ける。ドアが閉まっていたなどの理由で辺のコストが急に上がっても、ゴールまでの距離が実際に変わるノードだけを更新すればよい。それまでの計算の大半は再利用されるため、世界が変わるたびにA*を最初からやり直すよりはるかに高速である。
2002年にSven KoenigとMaxim Likhachevが発表した。Anthony StentzのD*（1994年）を、自分たちのLifelong Planning A*を土台に書き直した、よりすっきりした版である。派生版は実際のフィールドロボットの誘導にも使われてきた。定番の使い方は、楽観的に計画を立て、センサーが地図と食い違うたびに再計画するエージェントだ。