Does D* require a perfect initial map?

No. It is designed to incorporate revised information as planning proceeds.

Can a cost change matter even without a complete blockage?

Yes. A passage becoming more expensive can change the preferred route.

Does D* solve every moving-obstacle problem automatically?

No. Updating a spatial graph alone does not necessarily model future obstacle motion or the timing of collisions.

AI Glossary / Graphs and symbolic AI / Advanced

D*

Definition

D*, or Dynamic A*, is an incremental path-planning algorithm that repairs a route when new information changes edge costs in a graph. It reuses earlier search work instead of necessarily computing every revised route from scratch.

What it means

A robot can begin with an incomplete map and discover blocked passages while moving. The best route according to the original map may then be unusable or expensive. D* addresses the repeated planning problem created by those updates.

Its central idea is to retain useful information about routes to the goal and revise the parts affected by changed costs. The robot's current location may also change between updates, so the required answer is a route from where it is now.

“Optimal” must be read against the available graph and cost model. D* cannot know that an undiscovered corridor is blocked. A route that is optimal under the current map does not imply that the entire journey matches the route an all-knowing planner would have chosen at departure.

How it works

Represent navigable states as graph vertices and allowed movements as edges with costs. A cost can reflect distance or another modeled quantity. A blocked movement may be represented by an unavailable or effectively infinite-cost edge.

The original D* approach establishes cost-to-go information by propagating from the goal toward the starting location. As observations reveal changed edge costs, it identifies affected states and propagates corrections until the relevant route information is consistent again.

Some previous values remain useful because the changed edge does not affect their best route. Other changes can propagate widely, especially when an important passage becomes blocked. Incremental repair reduces redundant work when the problem structure allows it; it is not a promise that every update is small.

D* Lite is a related but algorithmically different method introduced by Koenig and Likhachev. It uses ideas from Lifelong Planning A* to provide similar replanning behavior. An implementation should identify the actual algorithm used rather than treating D*, focused D* and D* Lite as interchangeable pseudocode.

Three practical examples

A warehouse robot revises its route after detecting that a normally open aisle is temporarily blocked.
An exploration robot updates travel costs as sensors reveal terrain that was previously unknown.
A simulated game agent reuses route-search information while newly discovered obstacles change its map.

Think of it this way

Think of keeping a route notebook and correcting the entries affected by a road closure. Routes that never use that road may remain valid, while routes depending on it need revision.

The analogy does not mean D* merely draws a small detour around the obstacle. A local observation can require a different global route, and the algorithm's cost updates can reach far beyond the changed location.

Worked example

Repairing the route from the current position

Use an undirected graph with edges S-A cost 2, A-G cost 2, S-B cost 3, B-G cost 3 and A-B cost 2. The goal is G. Initially, the cheapest route from S is S-A-G with total cost 4, compared with S-B-G at cost 6.

After moving from S to A, the robot discovers that A-G is blocked. From its current position A, the route A-B-G costs 2+3=5. Returning through S would cost A-S-B-G=2+3+3=8, so the repaired route uses B directly.

The total journey actually traveled becomes S-A-B-G, costing 2+2+3=7. An all-knowing planner starting at S would have chosen S-B-G at cost 6.

This is not a contradiction of current-map shortest-path planning: the robot already spent 2 reaching A before learning of the blockage. The example illustrates the revised route and the information limitation, rather than a step-by-step trace of D*'s internal queue operations.

Illustrative case study

A fictional facilities company, Rowan Mobility, trials a delivery robot in a building where maintenance barriers change throughout the day. It uses incremental replanning to update routes when a barrier is detected.

The team initially reports only the length of each newly computed route. That hides distance already traveled before a map correction. It adds separate measures for remaining planned cost, total executed distance and time spent replanning.

The engineers also discover that a geometric route can pass too close to a barrier for the robot's actual footprint. They correct the graph construction and local motion constraints. A shortest-path guarantee over the old graph could not compensate for an inaccurate representation of traversable space.

Common misconceptions and mistakes

D* predicts obstacles before they are observed. It responds to the information supplied through the model and sensors.
Incremental repair always touches only nearby vertices. A changed connection can alter routes across a large part of the graph.
D* Lite is simply the original D* with fewer lines of code. It is a distinct algorithm with related behavior.
A shortest graph route guarantees safe physical motion. Geometry, sensing, dynamics and collision avoidance must also be represented or handled appropriately.

Business use

Incremental replanning is relevant when an application repeatedly solves closely related route problems. Evaluate the complete sequence of observations and route updates, rather than one static shortest-path query.

Useful measures include replanning latency, memory use, executed travel cost and behavior when the goal becomes unreachable. Compare with a straightforward repeated-search baseline: retaining search state has overhead, and the benefit depends on update patterns and graph structure. For physical robots, the global path planner is one part of a broader navigation system.

Check your understanding

A robot's completed trip is longer than the route that would have been chosen with perfect advance knowledge. Does that alone prove its D* replanning was incorrect?

Answer: No. Assess each revised route using the robot's current position and information at that time, while separately measuring total journey performance.

Related terms

Lifelong Planning A*
Shortest Paths
Path planning
Incremental search
A* search
D* Lite
shortest path
cost map

Learn next

Recalculate the example after changing B-G from cost 3 to cost 8 instead of blocking A-G. Then distinguish the current optimal remaining route from the total cost already incurred. This prepares you to compare repeated search with incremental repair.

Sources

Anthony Stentz, original D* technical report and institutional abstract: https://publications.ri.cmu.edu/optimal-and-efficient-path-planning-for-unknown-and-dynamic-environments

Koenig and Likhachev, D* Lite, original AAAI paper: https://aaai-25.aaai.org/Papers/AAAI/2002/AAAI02-072.pdf

The route arithmetic and Rowan Mobility case are original teaching examples.

Previous: CYK algorithm Next: D-optimal design

D*