D* Lite

D* Lite is an incremental algorithm, meaning it reuses information from previous searches to repair the path when the underlying graph changes (e.g., new obstacles are discovered). Instead of replanning from scratch, it efficiently updates only the parts of the search tree affected by cost changes, dramatically reducing computation time compared to a complete A* rerun. This makes it suitable for real-time applications where the environment model is updated frequently by sensor data.

The algorithm is mathematically equivalent to LPA* but is derived from the perspective of the original D* algorithm. It uses the same two key heuristic estimates for each node s:

• g(s): The current cost from the start to s.
• rhs(s): A one-step lookahead value, rhs(s) = min_{s'∈Pred(s)}(g(s') + c(s', s)), where Pred(s) are the predecessors of s and c is the edge cost. A node is consistent if g(s) = rhs(s). The algorithm works to repair inconsistencies caused by edge cost changes, propagating them efficiently through the graph.

Unlike forward-searching algorithms like A*, D* Lite performs its search backwards from the goal to the start. This key design choice is optimal for mobile robot navigation where the start position (the robot's current location) changes with every move, but the goal often remains fixed. By searching from the goal, the algorithm maintains a consistent heuristic rooted at the goal, and the robot simply moves to the neighbor with the lowest g-value, recalculating the path only when needed.

D* Lite uses a priority queue to efficiently manage which nodes to process. The queue is ordered by a two-component key: k(s) = [k1(s); k2(s)].

• k1(s) = min(g(s), rhs(s)) + h(s_start, s) + km
• k2(s) = min(g(s), rhs(s)) The h(s_start, s) term is the heuristic from the start to the node, and km is a correction factor that tracks changes in the start position. This key structure ensures nodes are expanded in an order that focuses the search effectively on the most relevant inconsistencies.

The algorithm maintains an adaptive heuristic that remains admissible despite changes in the robot's start position. The km variable is incremented by the heuristic cost h(s_last, s_new) whenever the robot moves from s_last to s_new. This adjustment is added to all new priority queue keys, effectively lowering the priority of nodes affected by the robot's movement and preserving the optimality of the search without requiring a full heuristic recalculation.

A major advantage of D* Lite over the original D* is its conceptual and implementation simplicity. By being derived from and equivalent to LPA*, it can be implemented with a standard priority queue and the well-understood g/rhs value propagation logic. This makes it more accessible, debuggable, and maintainable in production robotics software stacks, leading to its widespread adoption for dynamic grid-based navigation in warehouses, autonomous vehicles, and video games.

Game AI engines utilize D* Lite to manage unit pathfinding for hundreds of entities in dynamically changing battlefields. It handles:

• Terrain deformation from explosions or spell effects that alter traversability.
• Dynamic blocking by moving units, requiring constant, efficient path updates to avoid congestion and deadlock.
• Resource-gathering agent routing where new resource nodes are discovered or depleted. The algorithm's deterministic performance ensures predictable frame-rate impact, which is essential for real-time gaming.

D* Lite is integral to Autonomous Mobile Robot (AMR) fleets in fulfillment centers. It enables efficient replanning in response to:

• Dynamic inventory: Pallets, carts, and human workers constantly change the free space on the floor.
• Zone management: Temporarily blocked aisles for maintenance or high-priority traffic.
• Task re-prioritization: Immediate rerouting to handle a new high-urgency pick request. By minimizing replanning latency, D* Lite maximizes fleet throughput and minimizes stoppages, directly impacting operational Key Performance Indicators like orders per hour.

For drones performing surveillance, inspection, or delivery in complex airspace, D* Lite provides robust in-flight replanning. It addresses:

• Pop-up no-fly zones or temporary airspace restrictions.
• Unexpected static obstacles like newly constructed buildings or cranes not on the original map.
• Adverse weather avoidance, where wind shear or storm cells create high-cost regions that must be navigated around. The algorithm's focus on cost-to-goal optimization is used to balance path safety, battery efficiency, and mission completion time.

Understanding where D* Lite fits among other algorithms clarifies its application scope.

• Vs. A*: A* is optimal for a single, static planning query. D* Lite is superior for repeated replanning in changing environments, as it is incremental.
• Vs. D*: The original D* algorithm is more complex. D* Lite provides equivalent functionality with simpler implementation, making it the preferred choice in most practical robotics systems.
• Vs. RRT*: RRT* is sampling-based and excels in high-dimensional spaces (e.g., manipulator arms). D* Lite is search-based and is typically used for 2D or 3D grid-based navigation.
• Vs. Model Predictive Control (MPC): MPC optimizes a continuous control sequence. D* Lite finds a discrete path; they are often used together, with D* Lite providing a global path and MPC executing smooth local trajectory tracking.

The foundational graph search algorithm upon which D* Lite is built. A* finds the least-cost path from a start to a goal node using a best-first search guided by a heuristic function h(n) that estimates the cost to the goal. Its core components are:

• g(n): The known cost from the start node to node n.
• h(n): The admissible heuristic estimating cost from n to the goal.
• f(n) = g(n) + h(n): The estimated total path cost through n, used to prioritize node expansion. D* Lite inherits A*'s optimality guarantees but modifies its operation for efficient replanning.

The direct algorithmic predecessor to D* Lite. LPA* is an incremental search algorithm that reuses information from previous searches to find new optimal paths when edge costs in the graph change. Key innovations include:

• Rhs-values: A one-step lookahead value that allows efficient inconsistency detection.
• Priority queue management: Nodes are processed based on a key that combines g and rhs values.
• Efficient updates: Only locally affected parts of the graph are recalculated. D* Lite simplifies LPA*'s implementation and is often preferred for its conceptual clarity while maintaining similar performance for path planning in dynamic grids.

The original incremental replanning algorithm for unknown environments, which D* Lite was designed to emulate more simply. The original D* (Dynamic A*) works by searching backwards from the goal and propagating cost changes through the graph. Its characteristics include:

• Backward search: Maintains optimal paths from all states to the goal.
• State tagging: Uses NEW, OPEN, and CLOSED states with complex propagation rules.
• Robotic heritage: Famously used on NASA's Mars rovers for online navigation. While powerful, D*'s implementation complexity led to the development of the simpler, forward-searching D* Lite, which produces equivalent paths.

The broader computational class to which D* Lite belongs. An incremental algorithm is designed to efficiently update its output when given a small change to its input, reusing previous computations rather than restarting from scratch. This is critical for real-time systems where:

• Environment changes are local (e.g., a new obstacle appears).
• Recomputation from scratch is prohibitively expensive.
• Low latency is required for responsive control. D* Lite's incremental nature allows it to repair paths orders of magnitude faster than replanning with A* after each environmental change.

The problem domain where D* Lite is often deployed as a single-agent component within a larger coordination framework. MAPF involves finding collision-free paths for multiple agents from start to goal locations. D* Lite can be used for individual agent navigation in MAPF systems that employ:

• Coupled approaches: Where a joint plan is made for all agents (e.g., Conflict-Based Search).
• Decoupled approaches: Where agents plan independently but coordinate (e.g., with ORCA). In decoupled systems, each agent may use D* Lite for its local, dynamic path planning while a higher-level protocol resolves inter-agent conflicts.

The operational process that triggers D* Lite's replanning cycle. Execution monitoring is the continuous comparison of an agent's actual sensor state against its expected plan state. When a discrepancy is detected—such as an unmapped obstacle—it generates a replanning trigger. This closed-loop process is essential for robust autonomy:

1. Plan: Generate an initial path with D* Lite.
2. Execute & Monitor: Move along the path while checking sensors.
3. Detect Change: Identify new obstacles or cost changes.
4. Replan: Invoke D* Lite's incremental update to repair the path. D* Lite provides the computational engine for the rapid replanning required in this cycle.