Navigation & SLAM

D* Lite

D* Lite is an incremental heuristic search algorithm for path planning in unknown or changing environments, introduced by Koenig and Likhachev in 2002 as a simpler reformulation of Stentz's D*. Built on Lifelong Planning A*, it efficiently repairs a previously computed shortest path when edge costs change instead of replanning from scratch. Algorithms in the D* family have been used for rover navigation, including planetary exploration systems.

Why it matters for physical AI

Mobile robots and manipulator bases constantly discover obstacles their maps missed. Incremental replanners like D* Lite keep navigation reactive at real-world update rates, a prerequisite for deploying autonomous platforms outside static, fully mapped facilities.