A warehouse robot follows a planned aisle until a new pallet blocks its route. It must use new sensor information to reach its goal without colliding. Running A* from the beginning is one option; D* Lite instead repairs a previous shortest-path search, reusing information still valid after the map changes. Sven Koenig and Maxim Likhachev published the method in 2002, building on incremental heuristic search.
Video: MIT OpenCourseWare students explain incremental path planning and D* Lite in a Cognitive Robotics lecture. The recording is educational, not a benchmark of modern commercial robots.
What changes compared with A*?
Our OSREC.016 lesson on A* examined the shortest-path search over a graph with known costs. D* Lite allows edge costs to change as the robot detects obstacles or discovers openings. It normally searches backward from the fixed goal toward the current robot position, then updates affected states without discarding all earlier results.
Two quantities are central. A node’s g-value is its current cost estimate. Its rhs-value is the best one-step lookahead cost from successor states. When they agree, a node is locally consistent. After an obstacle update, some nodes become inconsistent. A priority queue then directs processing to the states needed to restore a valid path. The mathematics assume appropriate nonnegative edge costs and a consistent planning model.
Example: a blocked warehouse aisle
Suppose a hypothetical grid has a known 12-metre route from a robot to its delivery point. A newly detected pallet blocks one edge. Marking the transition as impassable may leave a 17-metre detour. The new route is 5 metres longer, but the example is illustrative, not a measured result from Koenig and Likhachev. The planner changes the corresponding graph costs, updates affected states and chooses a new path from the robot’s current position.
Real maps change more than once. A pallet may move again, a corridor may become free, or a fresh obstacle may appear. Each update can trigger another incremental repair. Planning is distinct from perception and collision avoidance: a theoretically shortest grid route does not guarantee safe physical motion.

Map accuracy determines planner usefulness
A robot also needs a reliable occupancy map, its own pose and a safe physical footprint. Consult OSREC.015 on occupancy-grid maps, OSREC.014 on pose-graph SLAM, and OSREC.013 on state estimation. Incorrect localization, stale obstacles or excessive confidence in an inaccurate map can invalidate the resulting plan.
Demonstration: a student-built mobile robot uses an overhead camera and D* Lite to navigate around reported obstacles. The independent project is not a peer-reviewed performance comparison.
An engineering validation exercise
Test repeated A* and D* Lite on identical maps, edge-cost changes and goal locations. Record time spent planning, expanded states, path length, failures to find a route and collisions during physical execution. D* Lite can reduce computation when a small portion of the map changes, but the advantage depends on update patterns, graph size and implementation. Dynamic people require a separate responsive safety system and motion controller.
Knowledge check: What makes a node inconsistent? A mismatch between g and rhs. What should trigger replanning? A meaningful change in the traversability graph. Does D* Lite alone guarantee safe motion? No; sensing, localization and collision avoidance remain essential.
Primary references: Koenig and Likhachev, D* Lite, AAAI 2002; Carnegie Mellon Robotics Institute; NASA JPL’s earlier D* navigation work. The D* family and D* Lite are related but not interchangeable product claims.
We volunteer daily to ensure the credibility of the information on this platform is Verifiably True. If you would like to support to help further secure the integrity of our research initiative, please scan the QR code below.


Leave a Reply