D* Lite
Przyrostowe wyszukiwanie ścieżki, które tanio naprawia trasę po zmianie mapy, zamiast szukać od zera.
Robot badający nieznany teren odkrywa przeszkody dopiero, gdy do nich dojedzie. D* Lite szuka wstecz, od celu, i zachowuje koszty drzewa poszukiwań; gdy krawędź nagle drożeje — drzwi okazały się zamknięte — aktualizowane są tylko te węzły, których odległość do celu faktycznie się zmieniła. Reszta wcześniejszej pracy jest wykorzystywana ponownie, co jest dramatycznie szybsze niż uruchamianie A* od nowa przy każdej zmianie świata.
Sven Koenig i Maxim Likhachev opublikowali go w 2002 roku jako prostsze przepisanie algorytmu D* Anthony’ego Stentza (1994), zbudowane na ich Lifelong Planning A*. Warianty sterowały prawdziwymi robotami terenowymi; klasyczne zastosowanie to agent, który planuje optymistycznie i planuje na nowo za każdym razem, gdy czujniki przeczą mapie.