Grid & robotics pathfinding

D* Lite

Re-plan a path fast when the world changes, without starting over.

Interactive demo coming soon — read the theory below

The idea

D* Lite is a pathfinding algorithm for robots moving through a world that keeps changing. It first computes a shortest path, then as the robot discovers new obstacles (edge costs change), it repairs only the affected part of its plan instead of re-searching the whole map from scratch. It works backward from the goal so that when the robot moves and its surroundings shift, most of the earlier computation stays valid and can be reused.

How it works

Start from the goal and estimate, for every cell, how far it is from the goal. Give the goal a cost of zero.
Search outward (goal to start) with A*-style heuristics until the start cell has a settled shortest-path estimate, then follow the cheapest neighbors to walk toward the goal.
For each cell keep two numbers: g (its current best-known cost to the goal) and rhs (a fresh one-step-lookahead estimate based on its best neighbor). When g equals rhs the cell is 'consistent' (settled).
Move the robot one step along the current best path.
If the robot's sensors reveal a changed edge cost (a new wall, or a path that opened up), update the rhs of the cells touching that edge. This may make them inconsistent (g not equal to rhs).
Push only those newly inconsistent cells onto the priority queue, so work is focused near the change.
Re-run the search loop, which pops inconsistent cells in priority order and repairs their g values, rippling corrections outward only as far as needed.
Repeat move-sense-repair until the robot reaches the goal. Because the search is anchored at the goal, the robot's own movement doesn't invalidate the stored estimates.

OPEN, CLOSED & the data structures

["g[s]: best-known cost from cell s to the goal (may be stale until repaired).", "rhs[s]: one-step-lookahead cost = min over neighbors of (cost(s, s') + g[s']); the goal's rhs is 0. A cell is consistent when g[s] == rhs[s].", "A priority queue (open list) of only the locally inconsistent cells, ordered by a two-part key [min(g,rhs)+heuristic+k_m, min(g,rhs)].", "k_m: a running key modifier that lets the algorithm reuse the queue after the robot moves, instead of re-sorting everything.", "The known map / current edge costs, updated as the robot senses its surroundings."]

Pseudocode

function initialize():
    g[all] = rhs[all] = infinity
    rhs[goal] = 0
    k_m = 0
    push goal into U with key(goal)

function key(s):
    return [ min(g[s], rhs[s]) + h(start, s) + k_m,  min(g[s], rhs[s]) ]

function updateVertex(s):
    if s != goal: rhs[s] = min over s' in succ(s) of (cost(s,s') + g[s'])
    remove s from U
    if g[s] != rhs[s]: push s into U with key(s)   # inconsistent -> needs work

function computeShortestPath():
    while topKey(U) < key(start) or rhs[start] != g[start]:
        s = pop lowest-key vertex from U
        if g[s] > rhs[s]: g[s] = rhs[s]            # overconsistent: settle it
        else:             g[s] = infinity; updateVertex(s)  # underconsistent
        for each neighbor s' of s: updateVertex(s')

function main():
    initialize(); computeShortestPath()
    while start != goal:
        start = best neighbor: argmin (cost(start,s') + g[s'])
        move robot to start
        if edge costs changed near robot:
            k_m += h(old_start, start)             # keep old queue reusable
            for each changed edge: updateVertex(affected cells)
            computeShortestPath()

At a glance

Complete?Yes. If a path from start to goal exists in the current known map, D* Lite will find it; if no path exists, the start's cost stays infinite and it correctly reports failure. It handles changing costs without ever missing a reachable goal.

Optimal?Yes, given what the robot currently knows. Each replan produces a shortest path for the present map. It is optimal with respect to known information, not omniscient: it cannot account for obstacles it hasn't sensed yet, so the overall traveled path can be longer than if the robot had known everything up front.

TimePer replan, roughly proportional to the number of cells whose costs actually changed plus their neighborhood (not the whole grid). The initial search is A*-like. The big win is that later replans touch only the affected region, so repeated small changes are far cheaper than repeated full A* searches.

SpaceO(number of cells): it stores g, rhs, and heuristic bookkeeping for cells it has touched, plus the priority queue of currently inconsistent cells. Comparable to A*, with a little extra per-cell state (the rhs value and key modifier).

👍 When to use it

A robot or agent must navigate a partially known or changing map and discovers obstacles as it moves.
You need frequent, fast re-planning and full A*-from-scratch each step is too slow.
The environment changes locally (a door closes, debris appears) rather than the whole map reshuffling at once.
The goal is fixed (or changes rarely) while the agent's position keeps advancing.

⚠️ Watch out for

It searches from the goal to the start, which is backward from ordinary A*; this is what makes robot movement cheap to handle. Don't mix up the direction.
The g == rhs 'consistency' idea is the heart of it: rhs is a fresh estimate, g is the stored one; work happens only where they disagree.
The k_m key modifier exists purely to reuse the old priority queue after the robot moves, avoiding a full re-sort. It's an optimization, not new logic.
It replans optimally only for what is currently known; unsensed obstacles can still force detours later, so the total journey may not be globally shortest.
If almost the entire map changes at once, incremental repair loses its advantage and can cost as much as searching fresh.
It's optimized for a moving start toward a fixed goal; frequently moving the goal is a poorer fit (the original D*/LPA* family assumes the goal stays put).