Introduction

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.

Try It

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.

<!-- D* Lite incremental replanning demo -->
<div class="toolbar">
  <span class="legend-item"><span class="swatch start"></span> Start</span>
  <span class="legend-item"><span class="swatch goal"></span> Goal</span>
  <span class="legend-item"><span class="swatch path"></span> Path</span>
  <span class="legend-item"><span class="swatch updated"></span> Updated cells</span>
  <span class="legend-item"><span class="swatch wall"></span> Wall</span>
</div>
<div id="grid" class="grid" role="grid" aria-label="Pathfinding grid — click cells to toggle walls"></div>
<div id="status" class="status"></div>
<div class="btns">
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* Layout and color palette */
* { 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; }
/* Grid cells */
.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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* Grid dimensions and fixed endpoints */
const ROWS = 9, COLS = 12;
const START = [0, 0], GOAL = [ROWS - 1, COLS - 1];
const INF = 1e9;

/* Algorithm state — g values and flash set */
const walls = new Set();
let g = [], rhs = [];
let flashCells = new Set();

/* Coordinate helpers */
const key = (r, c) => r * COLS + c;
const valid = (r, c) => r >= 0 && r < ROWS && c >= 0 && c < COLS;
const isWall = (r, c) => walls.has(key(r, c));
const isStart = (r, c) => r === START[0] && c === START[1];
const isGoal  = (r, c) => r === GOAL[0]  && c === GOAL[1];

/* 4-connected neighbors (no diagonals, no walls) */
function neighbors(r, c) {
  const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
  return dirs.map(([dr, dc]) => [r + dr, c + dc])
             .filter(([nr, nc]) => valid(nr, nc) && !isWall(nr, nc));
}

/* Full backward Dijkstra from goal — used on first load and reset */
/* Sets g[r][c] = shortest distance from (r,c) to GOAL ignoring walls at start. */
function fullDijkstra() {
  g = Array.from({ length: ROWS }, () => new Array(COLS).fill(INF));
  rhs = Array.from({ length: ROWS }, () => new Array(COLS).fill(INF));
  const [gr, gc] = GOAL;
  g[gr][gc] = 0;
  /* Simple array-based min-heap (small grid, sufficient for demo) */
  const heap = [[0, gr, gc]];
  while (heap.length) {
    heap.sort((a, b) => a[0] - b[0]);
    const [dist, r, c] = heap.shift();
    if (dist > g[r][c]) continue;
    for (const [nr, nc] of neighbors(r, c)) {
      const nd = g[r][c] + 1;
      if (nd < g[nr][nc]) { g[nr][nc] = nd; heap.push([nd, nr, nc]); }
    }
  }
}

/* Incremental update — the core D* Lite idea */
/* Propagates cost changes outward from the affected edge, touching only inconsistent vertices. */
function incrementalUpdate(changedEdges) {
  flashCells.clear();
  /* Seed the queue with directly affected cells */
  const queue = [];
  for (const [r, c] of changedEdges) {
    if (isWall(r, c)) {
      /* Cell became a wall — its cost is now infinity */
      if (g[r][c] < INF) { g[r][c] = INF; flashCells.add(key(r, c)); queue.push([r, c]); }
    } else {
      /* Wall removed — recompute cost from neighbors */
      const best = isGoal(r, c) ? 0 : Math.min(...neighbors(r, c).map(([nr, nc]) => g[nr][nc] + 1));
      if (best < g[r][c]) { g[r][c] = best; flashCells.add(key(r, c)); queue.push([r, c]); }
    }
  }
  /* Propagate cost decreases (relaxation, like Dijkstra) */
  const visited = new Set();
  while (queue.length) {
    queue.sort((a, b) => g[a[0]][a[1]] - g[b[0]][b[1]]);
    const [r, c] = queue.shift();
    const k2 = key(r, c);
    if (visited.has(k2)) continue;
    visited.add(k2);
    for (const [nr, nc] of neighbors(r, c)) {
      const nd = g[r][c] + 1;
      if (nd < g[nr][nc]) {
        g[nr][nc] = nd;
        flashCells.add(key(nr, nc));
        queue.push([nr, nc]);
      }
    }
    /* Propagate cost increases (raises) to neighbors that depended on this cell */
    for (const [nr, nc] of [[r-1,c],[r+1,c],[r,c-1],[r,c+1]]) {
      if (!valid(nr,nc) || visited.has(key(nr,nc))) continue;
      const old = g[nr][nc];
      const best2 = isGoal(nr,nc) ? 0 : Math.min(...neighbors(nr,nc).map(([a,b]) => g[a][b]+1));
      if (isWall(nr,nc)) continue;
      if (best2 !== old) {
        g[nr][nc] = isFinite(best2) ? best2 : INF;
        flashCells.add(key(nr,nc));
        if (!visited.has(key(nr,nc))) queue.push([nr,nc]);
      }
    }
  }
}

/* Greedy path trace from start to goal following decreasing g values */
function tracePath() {
  const path = new Set();
  let [r, c] = START;
  const limit = ROWS * COLS;
  let steps = 0;
  while (!(r === GOAL[0] && c === GOAL[1]) && steps < limit) {
    steps++;
    path.add(key(r, c));
    const nbs = neighbors(r, c);
    if (!nbs.length) break;
    const [nr, nc] = nbs.reduce((best, [a, b]) => g[a][b] < g[best[0]][best[1]] ? [a, b] : best);
    if (g[nr][nc] >= g[r][c]) break;
    [r, c] = [nr, nc];
  }
  if (r === GOAL[0] && c === GOAL[1]) path.add(key(r, c));
  return path;
}

/* Render grid with current state */
function render(path) {
  const grid = document.getElementById('grid');
  grid.style.gridTemplateColumns = `repeat(${COLS}, 30px)`;
  grid.innerHTML = '';
  for (let r = 0; r < ROWS; r++) {
    for (let c = 0; c < COLS; c++) {
      const el = document.createElement('div');
      el.className = 'cell';
      el.style.width = el.style.height = '30px';
      el.dataset.r = r; el.dataset.c = c;
      if (isStart(r, c))        { el.className += ' start'; el.textContent = 'S'; }
      else if (isGoal(r, c))    { el.className += ' goal';  el.textContent = 'G'; }
      else if (isWall(r, c))    { el.className += ' wall'; }
      else if (flashCells.has(key(r, c))) { el.className += ' flash'; }
      else if (path.has(key(r, c)))       { el.className += ' path'; }
      else                      { el.className += ' empty'; }
      grid.appendChild(el);
    }
  }
}

/* Update the status message below the grid */
function updateStatus(updatedCount) {
  const el = document.getElementById('status');
  const [sr, sc] = START;
  const dist = g[sr][sc];
  if (dist >= INF) {
    el.textContent = 'No path exists — goal is unreachable.';
    el.style.color = '#c92f3c';
  } else {
    el.textContent = i18nFmt('Path length: %dist% steps | %updated% cell(s) updated by replan.', { dist, updated: updatedCount });
    el.style.color = '#0a7d33';
  }
}

/* Initial computation */
fullDijkstra();
let currentPath = tracePath();
render(currentPath);
updateStatus(0);

/* Toggle a wall on click and trigger incremental replan */
document.getElementById('grid').addEventListener('click', e => {
  const el = e.target.closest('.cell');
  if (!el) return;
  const r = +el.dataset.r, c = +el.dataset.c;
  if (isStart(r, c) || isGoal(r, c)) return;
  const k2 = key(r, c);
  /* Toggle wall membership */
  if (walls.has(k2)) { walls.delete(k2); } else { walls.add(k2); }
  incrementalUpdate([[r, c]]);
  currentPath = tracePath();
  render(currentPath);
  updateStatus(flashCells.size);
  /* Clear yellow flash after a short delay */
  setTimeout(() => { flashCells.clear(); render(currentPath); updateStatus(flashCells.size); }, 600);
});

document.getElementById('btn-reset').addEventListener('click', () => {
  walls.clear(); flashCells.clear();
  fullDijkstra();
  currentPath = tracePath();
  render(currentPath);
  updateStatus(0);
});
Result
Console

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.

The Real Complexity

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

  • g(v)g(v) — the current estimated cost from vv to the goal.
  • rhs(v)\mathrm{rhs}(v) — a one-step lookahead: the best cost achievable in one move, i.e. rhs(v)=min⁡s′[c(v,s′)+g(s′)]\mathrm{rhs}(v) = \min_{s'} [c(v, s') + g(s')] where c(v,s′)c(v, s') is the edge cost.
  • A vertex is consistent when g(v)=rhs(v)g(v) = \mathrm{rhs}(v), meaning its estimate is settled.
  • Inconsistent vertices — where g(v)≠rhs(v)g(v) \neq \mathrm{rhs}(v) — sit in a priority queue and are processed in order of their key [min⁡(g(v),rhs(v))+h(v,sstart)][\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 kk vertices are affected, the replan costs O(klog⁡n)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 kmk_m keeps the keys consistent across moves, ensuring the invariant is maintained without recomputing any heuristic from scratch.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/d-star-lite/Content licensed under CC BY-NC 4.0.