ExtendedSource checked

D* Search

Repairs paths for a moving agent as new obstacle or cost information appears.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pathfinding
Difficulty: Advanced
Family: Incremental Heuristic Search
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 3
Code example: Ready
Visualization: Ready
Aliases: Dynamic A*

Overview

D* search plans backward from the goal and updates affected costs when the agent discovers changes, making it useful for robotics in partly known maps.

Core Concepts

incremental replanningcost repairbackward searchmoving start

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(E log V)

Average

O(k log V)

Worst

O(E log V)

Space

O(V)

When to Use

Use when route planning needs incremental replanning.
Use when the input matches the assumptions behind incremental Heuristic Search.

When Not to Use

Avoid when edge costs or movement rules change faster than the search can update them.
Avoid when a simpler algorithm gives the required result with less setup.

What It Does

Repairs paths for a moving agent as new obstacle or cost information appears
Uses incremental replanning and cost repair to guide the work.
Produces path.

Use Cases

Route planning
Game navigation
Robotics motion planning

Inputs

Search graph or state space
Start state
Goal state or target set

Outputs

Path
Distance estimate
Search frontier state

Key Formulas (1)

Path repair key

key(v) = min(g(v), rhs(v)) + h(start, v)

key(v) = min(g(v), rhs(v)) + h(start, v)

Prioritizes inconsistent states by repaired path estimate.

Pseudocode

1.Prepare the inputs and state needed for D* Search.
2.Apply the incremental replanning step while the stopping condition has not been met.
3.Update intermediate state and discard invalid candidates.
4.Return path.

Canonical Example

Input: D* Search input with a small representative case
Output: Path
Explanation: D* Search applies incremental replanning to produce path.

Implementation Notes

Store predecessor information separately from distance or priority values.
Keep the incremental replanning step separate enough to test independently.

Common Pitfalls

Using a heuristic or preprocessed data that does not match the actual cost model breaks path quality.
Forgetting to check edge cases can make D* Search look correct on only ideal inputs.

Interactive Mechanism Walkthrough

2D Grid Wavefront & Trajectory

Show the frontier, settled nodes, and the final path over the search space.

Step 1 of 4: Prepare the inputs and state needed for D* Search.

pathfinding-mechanism

Notes

D* Search operates in O(k log V) time and O(V) space within the Incremental Heuristic Search family. Key governing relation: key(v) = min(g(v), rhs(v)) + h(start, v). Often compared with D* Lite and Lifelong Planning A*.