Overview
The Opportunity: Most path planners assume a robot knows its environment before it starts moving. Real robots rarely get that luxury — a delivery robot's map doesn't show a street closed for construction, a warehouse robot doesn't know a pallet moved until it gets there. The naive response, rerunning A* from scratch every time the map turns out to be wrong, works but throws away almost everything the robot already knew about the rest of the map.
My Role: I independently implemented the full algorithm stack — A* and D* Lite (including the optimized variant from Koenig & Likhachev's original paper) — designed and ran the benchmarking harness, and led the multi-agent extension using a Conflict-Based Search-style constraint mechanism.
The Outcome: A working incremental replanner that repairs only the part of a previous solution affected by new information, benchmarked against full re-search across 8 grid sizes and 4 dynamic-obstacle scenarios, and extended to coordinate 2–3 robots replanning around both map changes and each other.
Process & Methodology
Building the Baseline
I began by implementing plain A* as a known-correct reference, using a binary heap priority queue with lazy deletion. To keep the heuristic admissible under variable terrain difficulty (cells costing 0.5, 1.0, or 3.0 to traverse), I constrained the heuristic to assume every cell costs the traversal minimum — otherwise A* loses its optimality guarantee.
From A* to D* Lite
I then implemented D* Lite's core bookkeeping: two cost values per node, g (current best-known cost) and rhs (a one-step lookahead), with a priority queue keyed by a two-part comparison function. Unlike A*, D* Lite searches backward from the goal, which means the robot's position can move without invalidating the search tree — a property LPA* doesn't share, since LPA* roots its values at the start and forces re-evaluation whenever that start moves. As a sanity check, I confirmed D* Lite converged to the same-cost path as A* on static maps before trusting it on dynamic ones; the two algorithms occasionally selected different but equal-cost routes, a byproduct of tie-breaking rather than a bug.
Incremental Repair
With the static case validated, I implemented UpdateVertex and edge-cost-change handling, then scripted a sequence of map changes (an obstacle appearing, an obstacle clearing, a corridor turning out to be blocked) to confirm the robot replanned correctly while reprocessing only nodes near the change — visualized directly to make the "repair, don't recompute" behavior visible rather than assumed.
Building the Benchmark
I built a harness comparing D* Lite (incremental) against A* (from scratch on every replan), logging node evaluations and wall-clock time across 8 grid sizes (15×15 to 1000×1000) and 4 change scenarios (single blocked cell, small blocked region, large blocked region, reopened shortcut), averaged over multiple trials per scenario to control for timing noise. This surfaced a result more interesting than "D* Lite wins": incremental replanning cut node evaluations by 35–42% consistently, but ran 2.7–4.7x slower in wall-clock time.
Performance Summary by Grid Size
| Terrain Size | A* Time (s) | D* Time (s) | Speed Ratio | A* Eval. | D* Eval. | Eval. Reduction |
|---|---|---|---|---|---|---|
| 15 | 0.0006 | 0.0026 | 4.67x | 254 | 188 | 25.94% |
| 30 | 0.0028 | 0.0103 | 3.72x | 1,178 | 687 | 41.68% |
| 50 | 0.0091 | 0.0307 | 3.37x | 3,406 | 1,982 | 41.80% |
| 80 | 0.0209 | 0.0800 | 3.82x | 7,772 | 4,912 | 36.80% |
| 150 | 0.0706 | 0.2807 | 3.98x | 26,573 | 17,112 | 35.60% |
| 300 | 0.3106 | 1.1628 | 3.74x | 106,994 | 67,042 | 37.34% |
| 500 | 0.9403 | 3.3456 | 3.56x | 298,128 | 189,308 | 36.50% |
| 1000 | 3.9105 | 13.5164 | 3.46x | 1,197,215 | 752,573 | 37.14% |
Performance Summary by Change Type
| Change Type | A* Time (s) | D* Time (s) | Speed Ratio | A* Eval. | D* Eval. | Eval. Reduction |
|---|---|---|---|---|---|---|
| large_region | 0.8039 | 2.8056 | 3.49x | 252,446 | 157,110 | 37.76% |
| reopen_shortcut | 0.8077 | 2.7971 | 3.46x | 251,592 | 157,085 | 37.56% |
| single_cell | 0.4638 | 1.6635 | 3.59x | 144,044 | 93,235 | 35.27% |
| small_region | 0.8096 | 2.7962 | 3.45x | 251,798 | 157,092 | 37.61% |
Note: Speed Ratio is the ratio of A* time to D* Lite time. Eval. Reduction is the node evaluation reduction from A* to D* Lite.
I traced this to per-node overhead from maintaining rhs-values and two-part keys — a constant-factor cost in Python that outweighed the algorithmic savings at these grid sizes. Rather than treat this as a failed result, I implemented the optimized D* Lite variant described in the original paper (inline UpdateVertex logic to avoid O(N) queue-membership checks, single-neighbor rhs updates instead of full neighbor sweeps on every change), which recovered a consistent 1.2–1.3x speedup over the unoptimized version — still slower than A* in this implementation, but a measured, explained gap rather than an unexplained one.
Execution Time by Terrain Size
| Terrain Size | A* Time (s) | D* Lite Time (s) | D* Lite Optimized Time (s) | Speed Ratio (A* vs D* Lite Opt) | Speed Ratio (D* Lite vs D* Lite Opt) |
|---|---|---|---|---|---|
| 15 | 0.0007 | 0.0032 | 0.0026 | 3.65x | 1.25x |
| 30 | 0.0034 | 0.0161 | 0.0121 | 3.57x | 1.33x |
| 50 | 0.0097 | 0.0369 | 0.0304 | 3.14x | 1.21x |
| 80 | 0.0229 | 0.0945 | 0.0757 | 3.31x | 1.25x |
| 150 | 0.0814 | 0.3403 | 0.2753 | 3.38x | 1.24x |
| 300 | 0.3459 | 1.3715 | 1.0990 | 3.18x | 1.25x |
| 500 | 1.1586 | 3.9297 | 3.1641 | 2.73x | 1.24x |
| 1000 | 5.0458 | 15.7906 | 13.5248 | 2.68x | 1.17x |
Execution Time by Change Type
| Change Type | A* Time (s) | D* Lite Time (s) | D* Lite Optimized Time (s) | Speed Ratio (A* vs D* Lite Opt) | Speed Ratio (D* Lite vs D* Lite Opt) |
|---|---|---|---|---|---|
| large_region | 0.9219 | 3.3815 | 2.7480 | 2.98x | 1.23x |
| reopen_shortcut | 0.9529 | 3.3588 | 2.7360 | 2.87x | 1.23x |
| single_cell | 0.7370 | 1.8212 | 1.6637 | 2.26x | 1.09x |
| small_region | 0.9110 | 3.3339 | 2.7611 | 3.03x | 1.21x |
Extending to Multiple Robots
The stretch goal was coordinating 2–3 robots without collisions, which exposed a structural mismatch: D* Lite has no concept of time, so it can't natively distinguish a permanent terrain change (blocks every robot, forever) from a robot-specific, single-timestep conflict. I resolved this by decoupling the two roles — D* Lite computes distances only (g and rhs), while a separate time-aware wrapper, closer to A* in structure, uses those distances to find the actual per-timestep path. On top of this, I implemented a Conflict-Based Search-style loop: plan every robot independently, simulate the paths together, find the first vertex or edge conflict, add a timestep-scoped constraint to one robot, and replan only that robot — reusing the same "something changed, repair the plan" machinery that powered the single-agent incremental replanning, now applied to conflicts instead of terrain.
Key Design Decisions
Rooting the Search at the Goal, Not the Start
D* Lite's backward search from the goal was the deciding factor over LPA*: since the robot's current position is free to change without invalidating g and rhs values elsewhere in the graph, the algorithm avoids the large-scale re-evaluation that a start-rooted approach like LPA* would require every time the robot moves.
Separating Terrain Changes from Agent Constraints
In the multi-agent extension, a terrain update blocks a cell for every robot at every future timestep, while a Conflict-Based Search constraint blocks one robot at one timestep only. Keeping these as distinct data structures — rather than encoding a robot "stop" as a fake terrain change — was what made the single-agent repair machinery reusable for conflict resolution instead of requiring a second, parallel replanning system.
Optimizing Before Concluding
Rather than reporting "D* Lite evaluates fewer nodes but runs slower" as a final result, I implemented the paper's optimized variant to check whether the wall-clock gap was inherent to the algorithm or an artifact of a naive implementation. It was partly the latter — optimization closed some, not all, of the gap, which is a more defensible and specific finding than either extreme.
Results
- Node evaluations: 35–42% reduction for incremental replanning vs. full re-search, consistent across all 8 grid sizes
- Wall-clock time: unoptimized D* Lite ran 2.7–4.7x slower than A* despite fewer evaluations, traced to per-node key/queue overhead
- Optimized D* Lite: 1.2–1.3x faster than the unoptimized version across all grid sizes, most pronounced on large-region changes
- Scenario invariance: performance varied less than 2% across single-cell, small-region, large-region, and reopened-shortcut change types at a given grid size, indicating the initial full-grid search — not the incremental repair step — dominated the compute budget in this harness
- Multi-agent extension: successfully coordinated 2–3 robots replanning around both terrain changes and each other using agent- and time-scoped constraints
Lessons Learned
A smaller search space doesn't guarantee a faster program. The headline "D* Lite wins" story from node-evaluation counts alone would have been misleading — the real finding required measuring wall-clock time too and understanding why the two diverged (Python's per-node constant-factor overhead), which is a distinction between algorithmic complexity and implementation performance that only shows up when you benchmark honestly instead of stopping at the first favorable metric.
Reusable abstractions reveal themselves under new requirements. The multi-agent extension wasn't a separate system bolted onto the single-agent planner — it worked because I'd already framed single-agent replanning as "something changed, repair only what's affected." Recognizing that a robot-to-robot conflict was just another instance of "something changed" let the same repair machinery generalize, rather than requiring a second planner built from scratch.
An unfavorable result is still a result. Finding that D* Lite was slower in wall-clock time despite fewer node evaluations could have been treated as something to hide or minimize. Instead, digging into why — and then testing whether optimization could close the gap — turned a potentially disappointing benchmark into the most substantive finding of the project.
Project Documentation - view full process from research to product (PDF)
