Cognition · Software component
Incremental Search Replanner
Software componentCognitionCognition & Memoryarc:IncrementalSearchReplanner
A replanner that retains the previous search tree and, on edge-cost changes, recomputes only nodes made inconsistent, restoring an optimal path without full re-search.
Responsibility. Repairs the optimal path by updating only search nodes affected by environment changes.
Also known as: LPA* replanner, D* Lite replanner, Layer 3 operational incremental replanning, Dynamic A*
Variant of Replanner abstract
When to choose. Choose when changes are frequent but localized edge-cost modifications on a stable topology, state spaces are large, memory permits search-tree persistence, and optimal solutions matter.
Relationships
invokes dependency
- Heuristic Estimator abstract Ch5.6
reads dependency
writes dependency
is routed to by dynamic
is triggered by dynamic
sends data to dynamic
is failover for control
alternative to variability
Design guidance
- SHOULD be used when environment changes are frequent but localized, the state space is large, and memory allows persisting the search tree.
- SHOULD be replaced by complete replanning when changes are global, since nearly all nodes become inconsistent while memory overhead remains.
- MAY run continuously in the background as new cost data arrives.
Quantitative guidance
As stated by the sources; verify before use.
- Grid navigation experiments show 10-100x speedups over replanning from scratch (Ch5.6).
- Blocked edge: ~60 inconsistent nodes reprocessed vs ~1,500 for fresh A* (Ch5.6).
- Warehouse, 20 changes/hour: 0.8 s vs 100 s of replanning compute per hour (125x reduction) (Ch5.6).
- Delivery robot: 150 ms initial planning, 400 ms per incremental replan; 25 s/day vs 85 s reactive and 55 s contingency at 25% failure rate (Ch5.6).
Classification
- Patterns
- Lifelong Planning A* (LPA*)D*D* LiteAnytime D*Inconsistent-node priority queue
- Quality attributes
- Performance efficiency (ISO/IEC 25010)Functional suitability: correctness and validity (ISO/IEC 25010 | NIST AI RMF: valid)
- Risks mitigated
- Redundant re-search of unchanged state space
Sources
- Ch5.6: T. Nguyen, "A* Search and Replaning," in Mastering Agentic AI Systems: Guide for the NVIDIA NCP-AAI Exam, 1st ed. 2026, ch. 5.6. ISBN: 9798244538229.