Replanning with D* Lite
A robot in an unknown place plans on what it knows, then finds new obstacles as it goes. Planning again from scratch every time wastes effort. D* Lite keeps the previous search and repairs only the cells affected by the new information, which is why it was used on Mars rovers and many field robots.
Incremental search
D* Lite searches backward from the goal and stores, for every cell, its cost-to-goal \(g\) and a one-step lookahead value \(rhs\):
A cell is consistent when \(g = rhs\). When the robot discovers that some edge costs have changed, only those cells become inconsistent, and the search re-expands just them and whatever their change affects. The robot then follows the cheapest neighbor at each step.
What to notice
Each time the sensor reveals new wall, the path bends around it. The readout compares the cells the incremental repair touched with what a full Dijkstra search from scratch would expand: the repair is usually a small fraction. This page uses the core of D* Lite, the LPA* repair from the goal, without its heuristic, to keep the code short. The full algorithm adds a heuristic to focus the repair even more.