D* Lite

Imagine a self-driving robot moving from a start to a goal. Before it sets off, it computes the shortest path on a known map using something like Dijkstra's algorithm. But the world is rarely static: a door slams shut, a crate slides into the corridor, a sensor picks up a wall that wasn't on the original map.

The naive response is to throw away the old path and run the full planner again from scratch. On a large map with many obstacles, that can be expensive — and the robot keeps encountering new surprises as it moves.

D Lite* (Dynamic A* Lite), introduced by Sven Koenig and Maxim Likhachev in 2002, solves this elegantly. Instead of replanning from scratch, it repairs only the part of the path that the change actually damaged. The key insight: when a single edge cost changes, most of the old shortest-path tree is still correct. D* Lite propagates corrections backward from the goal, touching only the vertices whose optimal costs changed.

The result is an algorithm that is provably no slower than rerunning Dijkstra from scratch, and in practice far faster — because most of the old plan survives intact.

The grid below shows a path from S (start, top-left) to G (goal, bottom-right). The blue cells are the current shortest path, computed with a backward Dijkstra from G.

Click any white cell to toggle a wall. When a new wall appears, only the cells whose shortest-path costs actually changed are recomputed — those are highlighted briefly in yellow. Compare that to what a full restart would touch: every cell on the map.

<!-- {{c_intro}} -->
<div class="toolbar">
  <span class="legend-item"><span class="swatch start"></span> {{label_start}}</span>
  <span class="legend-item"><span class="swatch goal"></span> {{label_goal}}</span>
  <span class="legend-item"><span class="swatch path"></span> {{label_path}}</span>
  <span class="legend-item"><span class="swatch updated"></span> {{label_updated}}</span>
  <span class="legend-item"><span class="swatch wall"></span> {{label_wall}}</span>
</div>
<div id="grid" class="grid" role="grid" aria-label="{{grid_aria}}"></div>
<div id="status" class="status"></div>
<div class="btns">
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_layout}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 4px; }
.toolbar { display: flex; flex-wrap: wrap; gap: .5rem 1rem; font-size: .8rem; margin-bottom: .5rem; }
.legend-item { display: flex; align-items: center; gap: .3rem; }
.swatch { width: 14px; height: 14px; border-radius: 3px; border: 1px solid #aaa; }
.swatch.start   { background: #2a9d8f; }
.swatch.goal    { background: #e76f51; }
.swatch.path    { background: #457b9d; }
.swatch.updated { background: #f4d35e; }
.swatch.wall    { background: #333; }
/* {{c_grid}} */
.grid { display: grid; gap: 2px; user-select: none; margin-bottom: .5rem; }
.cell {
  display: flex; align-items: center; justify-content: center;
  font: 700 11px ui-monospace, monospace;
  border-radius: 3px; cursor: pointer; transition: background .1s;
}
.cell.empty  { background: #e8eef3; }
.cell.wall   { background: #333; color: #555; cursor: pointer; }
.cell.path   { background: #457b9d; color: #fff; }
.cell.start  { background: #2a9d8f; color: #fff; cursor: default; }
.cell.goal   { background: #e76f51; color: #fff; cursor: default; }
.cell.flash  { background: #f4d35e; color: #555; }
.cell:hover.empty { background: #d0d8e0; }
.cell:hover.wall  { background: #555; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.4em; margin-bottom: .4rem; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice how few cells flash when you add a wall far from the current path. The closer the wall is to the path, the more repair is needed — but D* Lite never redoes work that is still valid.

D* Lite inherits its structure from LPA* (Lifelong Planning A*), which in turn generalises Dijkstra. The key data structures are:

• $g(v)$ — the current estimated cost from $v$ to the goal.
• $\mathrm{rhs}(v)$ — a one-step lookahead: the best cost achievable in one move, i.e. $\mathrm{rhs}(v) = \min_{s'} [c(v, s') + g(s')]$ where $c(v, s')$ is the edge cost.
• A vertex is consistent when $g(v) = \mathrm{rhs}(v)$, meaning its estimate is settled.
• Inconsistent vertices — where $g(v) \neq \mathrm{rhs}(v)$ — sit in a priority queue and are processed in order of their key $[\min(g(v), \mathrm{rhs}(v)) + h(v, s_\text{start})]$.

When an edge cost changes, D* Lite marks only the vertices that depended on that edge as inconsistent and re-expands them. If $k$ vertices are affected, the replan costs $O(k \log n)$ — exactly the cost of those expansions, nothing more.

The worst case is a change that invalidates the entire path, but that is also the case where replanning from scratch would cost the same. In all other cases — which dominate in practice — D* Lite is faster.

One subtlety: as the robot moves from start to goal, D* Lite shifts the start node and updates heuristics. A small accumulation factor $k_m$ keeps the keys consistent across moves, ensuring the invariant is maintained without recomputing any heuristic from scratch.

Any agent that navigates an environment it does not fully know in advance benefits from incremental replanning:

• Autonomous robots: NASA's Mars rovers used a variant of D* for terrain navigation, where new sensor readings constantly revise the map.
• Self-driving vehicles: lane closures, pedestrians, and temporary obstacles trigger replanning dozens of times per second; starting from scratch each time would be too slow.
• Video game AI: NPCs must reroute around players, explosions, and moving objects. D* Lite and its relatives allow believable real-time navigation at low CPU cost.
• Network routing: when a link fails, shortest-path routing protocols must update routing tables. Incremental methods propagate only the affected prefixes rather than reconverging the whole network.
• Warehouse robots: fleets of robots share a dynamic map; each new blocked aisle is a small edge-cost change that D* Lite can absorb without a full replan.

The common thread: a lot of prior work stays valid after a small change. D* Lite exploits that observation precisely, making it the algorithm of choice wherever maps change but don't change completely.

D* Lite embodies a simple but powerful idea: past computation is an asset, not a liability. When the world changes a little, the optimal plan changes a little too — and D* Lite finds exactly which part changed and fixes only that.

The algorithm is a clean example of incremental computation: instead of restarting from a blank slate whenever new information arrives, it maintains a data structure that can absorb updates cheaply. The same philosophy appears across computer science, from dynamic shortest paths to incremental compilers to live spreadsheets.

Next time you see a robot smoothly reroute around an obstacle without any visible pause, there is a good chance D* Lite — or one of its descendants — is quietly repairing the path one changed edge at a time.