D* Lite and Incremental Replanning

In live air routing, weather cells move, restricted airspace opens and closes, and traffic constraints shift while a flight is already underway. Replanning from scratch with A* after every change is wasteful — most of the previous plan is still valid. D Lite* is an incremental search algorithm that reuses prior computation when edge costs change.

D* Lite searches backward from the goal. For every node $s$ it maintains two quantities:

• $g(s)$: the cost-to-goal estimate carried over from the previous search.
• $rhs(s)$: a fresh one-step lookahead based on the latest neighbor information,

$$rhs(s) = \begin{cases} 0, & s = s_{goal}, \\ \min\limits_{s' \in \text{Succ}(s)} \big( c(s,s') + g(s') \big), & \text{otherwise}, \end{cases}$$

where $c(s,s')$ is the edge cost from $s$ to $s'$ and $\text{Succ}(s)$ is the set of successors of $s$. The $g$-values are memory from the last search; the $rhs$-values are the freshly recomputed lookahead.

For example, suppose $s$ has two successors $a$ and $b$ with $c(s,a) = 5$, $c(s,b) = 3$, and current values $g(a) = 8$, $g(b) = 12$. Then

$$rhs(s) = \min(5+8,\ 3+12) = \min(13, 15) = 13.$$