D* Lite
Búsqueda de caminos incremental que repara una ruta de forma barata cuando el mapa cambia, en vez de buscar otra vez desde cero.
Un robot que explora un terreno desconocido solo descubre los obstáculos al llegar a ellos. D* Lite busca hacia atrás desde la meta y conserva los costes del árbol de búsqueda; cuando una arista se encarece de pronto —una puerta resultó estar cerrada— solo se actualizan los nodos cuya distancia a la meta cambia realmente. El resto del trabajo anterior se reutiliza, lo que es mucho más rápido que relanzar A* cada vez que el mundo se mueve.
Sven Koenig y Maxim Likhachev lo publicaron en 2002 como una reescritura más limpia del D* de Anthony Stentz (1994), sobre su Lifelong Planning A*. Algunas variantes han guiado robots de campo reales; el uso canónico es un agente que planifica con optimismo y replanifica cada vez que sus sensores contradicen el mapa.