D* Algorithm

The core innovation of D* is its ability to incrementally repair a previously computed optimal path when edge costs in the graph change. Instead of discarding all prior work and restarting a search from scratch (like A*), D* reuses the previous search tree and efficiently updates only the states affected by the cost changes. This makes it orders of magnitude faster for repeated replanning in dynamic environments, such as a robot navigating around newly discovered obstacles.

D* maintains two key values for each state (node) in the graph:

• RHS (Right-Hand Side) Value: A one-step lookahead cost, computed as the minimum of the costs to move to a neighbor plus that neighbor's cost-to-goal.
• G (Cost-to-Goal) Value: The current estimated optimal cost from that state to the goal. A state is consistent if G = RHS. D* propagates cost changes by identifying inconsistent states (where G ≠ RHS) and efficiently updating them and their neighbors, using backpointers to track the optimal next step toward the goal. This process continues until the robot's current state is consistent, guaranteeing an optimal path given the updated map.

Unlike forward search algorithms like A* that search from the start to the goal, D* performs a reverse search. It initializes the search from the goal state and propagates cost-to-goal values outward. This orientation is critical for efficiency in mobile robotics:

• The robot only needs to replan from its current position, not from the original start.
• As the robot moves, it follows the backpointers from its current state toward the consistently calculated goal.
• When an obstacle is sensed, cost changes are propagated, but the goal remains fixed, allowing the algorithm to locally repair the path ahead of the robot.

D* uses a priority queue to manage the repair process efficiently. The queue is ordered by a key function (typically a 2-tuple: [min(G, RHS) + heuristic; min(G, RHS)]). This ensures the algorithm:

• Focuses expansion on states most likely to affect the path from the robot's current position to the goal.
• Processes states in an optimal order, similar to A*, but for the repair operation.
• Terminates early once the robot's current state becomes consistent, meaning a new optimal path from its location is known, without necessarily repairing the entire graph.

D* was explicitly designed for partially known or unknown environments, a common scenario in robotics. The algorithm operates in two main phases:

1. Initial Planning: Uses the initially known map (which may have large unknown areas treated as traversable) to compute an initial optimal path.
2. Execution and Repair: As the robot moves and its sensors reveal the true cost of states (e.g., discovering an obstacle), it updates the cost map. D* then incrementally repairs the cost-to-goal values and path. This allows a robot to navigate optimally with respect to what it has observed so far, replanning only when new information invalidates its current plan.

D Lite* is a modern, simplified reinterpretation of D* that is algorithmically equivalent but much easier to implement. Its key features:

• Formalizes D as an incremental version of A**, building directly on the Lifelong Planning A (LPA)** framework.
• Maintains identical logic using RHS values, consistency, and a priority queue.
• Reverses search direction by cleverly modifying the heuristic function, making the code structure nearly identical to A*.
• Becomes the de facto standard in robotics due to its simplicity and proven performance. Most modern implementations referenced as 'D*' are actually D* Lite.

D* is foundational for autonomous robots exploring unmapped environments. The robot plans an initial path based on prior knowledge. As it moves and its sensors (e.g., LIDAR) detect unforeseen obstacles—like a newly closed door or a fallen object—D* incrementally repairs the cost map and updates the optimal path from the robot's current position to the goal. This allows for continuous, real-time navigation without costly complete re-searches, making it ideal for search-and-rescue or planetary rovers.

In dynamic urban settings, D* enables vehicles to react to sudden road changes. When a primary route is blocked by an accident, construction, or a traffic jam, the vehicle's perception system updates the cost graph. D* efficiently propagates cost changes from the blocked edges, recalculating a new optimal route from the vehicle's current node. This is more efficient than A* for frequent, localized changes, providing drivers with near-instantaneous alternate directions.

Game AI uses D* to manage unit pathfinding in dynamically changing battlefields. The map is a grid where costs can change instantly—a bridge is destroyed, a wall is erected, or an area becomes hazardous. For a squad of units, D* allows the AI to minimally adjust the paths of all affected units by repairing the shared graph, preventing computational spikes that would cause lag. This ensures smooth, responsive unit control even during chaotic gameplay.

In automated warehouses, Autonomous Mobile Robots (AMRs) use D* for material transport. The floor plan is known, but dynamic obstacles—like human workers, dropped packages, or other robots—are constant. D* allows each robot to reactively replan its path to its picking station or drop-off point. By focusing computation only on the changed area of the graph, the system maintains high throughput and avoids deadlocks without overloading the central planner.

• A*: Optimal for single, static searches. Must replan from scratch for any change, which is computationally expensive in dynamic settings.
• D*: The original incremental algorithm. Maintains a complex OPEN list to propagate cost changes both forward and backward, optimal for reversing direction if needed (e.g., backing out of a dead-end).
• D Lite*: A modern simplification. Equivalent to Lifelong Planning A* in behavior but often simpler to implement. It is now more commonly used than original D* due to its efficiency and clarity, while solving the same class of dynamic replanning problems.

The efficiency of D* stems from its backpointer repair process. When an edge cost increases (e.g., an obstacle appears), the algorithm raises the cost of the affected node and places it on a priority queue. It then recursively propagates this cost increase to predecessor nodes, updating their costs and backpointers (pointers to the next optimal node) only where necessary. This local propagation avoids re-exploring the entire graph, which is the source of its incremental speed.