D* Lite
Inkrementell vägsökning som räknar om en väg billigt när kartan ändras, i stället för att söka om från början.
En robot som utforskar okänd terräng upptäcker hinder först när den kommer fram till dem. D* Lite söker bakåt från målet och sparar sökträdets kostnader; när en kant plötsligt blir dyrare — en dörr visade sig stängd — uppdateras bara de noder vars avstånd till målet faktiskt påverkas. Resten av det tidigare arbetet återanvänds, vilket är drastiskt snabbare än att köra A* på nytt varje gång världen rör sig.
Sven Koenig och Maxim Likhachev publicerade den 2002 som en enklare omskrivning av Anthony Stentz D* (1994), byggd ovanpå deras Lifelong Planning A*. Varianter har styrt riktiga fältrobotar; den klassiska tillämpningen är en agent som planerar optimistiskt och replanerar varje gång sensorerna motsäger kartan.