SpecializedSource checked

D* Lite

Repairs shortest paths efficiently when edge costs change during navigation.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pathfinding
Difficulty: Advanced
Family: Incremental Pathfinding
Tier: Specialized
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 6
Code example: Ready
Visualization: Ready

Overview

D* Lite reuses previous search work by maintaining one-step lookahead values and updating only affected parts of the graph.

Core Concepts

incremental searchrhs valuepriority repairchanging edge costs

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(E log V)

Average

O(E log V) per repair in worst case

Worst

O(E log V)

Space

O(V)

When to Use

Use when a path must be updated repeatedly as map costs are discovered or changed.
Use when robot navigation is a central requirement.

When Not to Use

Avoid when the map is static and a single A* search is simpler.
Avoid when edge costs or movement rules do not match the algorithm's assumptions.

What It Does

Tracks current and lookahead costs
Prioritizes inconsistent nodes
Repairs paths after cost changes

Use Cases

Robot navigation
Unknown terrain exploration
Dynamic obstacle replanning

Inputs

Graph or grid
Start and goal
Changing edge costs

Outputs

Current best path
Updated cost estimates

Key Formulas (1)

Local consistency

rhs(u) = min(cost(u, v) + g(v)) over successors v

rhs(u) = min(cost(u, v) + g(v)) over successors v

Stores the one-step lookahead value used to decide whether a node needs repair.

Pseudocode

1.Initialize goal costs and priority queue
2.Compute the shortest path to the current start
3.Move along the current path
4.When edge costs change, update affected nodes
5.Repair inconsistent priorities before continuing

Canonical Example

Input: start = S, goal = G, one edge becomes blocked
Output: path = repaired route around blocked edge
Explanation: Only nodes affected by the cost change need priority updates.

Implementation Notes

Keep g and rhs values separate; they are equal only when a node is locally consistent.
Store predecessor links so paths can be reconstructed after distances are computed.
Keep a tiny example with expected output beside the implementation.

Common Pitfalls

Incorrect priority keys can make stale nodes appear valid.
Mixing heuristic, movement cost, and tie-breaking rules can produce surprising routes.
Not defining boundary, empty, or degenerate inputs before implementation.

Interactive Mechanism Walkthrough

2D Grid Wavefront & Trajectory

Show a path being repaired locally after an obstacle appears.

Step 1 of 5: Initialize goal costs and priority queue

pathfinding

Notes

D* Lite is useful when the agent discovers map changes while moving; focused-search variants should be treated as separate techniques unless explicitly supported.