D* Lite
Pathfinding incrementale che ripara a basso costo un percorso quando la mappa cambia, invece di ricominciare la ricerca da zero.
Un robot che esplora un terreno ignoto scopre gli ostacoli solo quando li raggiunge. D* Lite cerca a ritroso a partire dall'obiettivo e conserva i costi dell'albero di ricerca; quando un arco diventa all'improvviso più costoso (una porta si rivela chiusa) vengono aggiornati soltanto i nodi la cui distanza dall'obiettivo cambia davvero. Il resto del lavoro precedente viene riutilizzato, il che è molto più veloce che rieseguire A* a ogni mutamento del mondo.
Lo pubblicarono Sven Koenig e Maxim Likhachev nel 2002, come riscrittura più pulita del D* di Anthony Stentz (1994), costruita sul loro Lifelong Planning A*. Alcune varianti hanno guidato robot reali sul campo; l'uso canonico è un agente che pianifica in modo ottimistico e ripianifica ogni volta che i sensori smentiscono la mappa.