Overview
Lifelong Planning A* maintains g and rhs values so only affected parts of the search graph need to be repaired after edge-cost updates.
ExtendedSource checked
Lifelong Planning A*
Reuses previous A* search work when graph costs change.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pathfinding
- Difficulty
- Advanced
- Family
- Incremental Heuristic Search
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
- Aliases
- LPA*
Core Concepts
incremental searchrhs valuepriority queuegraph repair
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(E log V)
Average
O(k log V)
Worst
O(E log V)
Space
O(V)
When to Use
- Use when route planning needs incremental search.
- Use when the input matches the assumptions behind incremental Heuristic Search.
When Not to Use
- Avoid when edge costs or movement rules change faster than the search can update them.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Reuses previous A* search work when graph costs change
- Uses incremental search and rhs value to guide the work.
- Produces path.
Use Cases
- Route planning
- Game navigation
- Robotics motion planning
Inputs
- Search graph or state space
- Start state
- Goal state or target set
Outputs
- Path
- Distance estimate
- Search frontier state
Key Formulas (1)
One-step lookahead
rhs(v) = min_{u in pred(v)} g(u) + cost(u, v)
rhs(v) = min_{u in pred(v)} g(u) + cost(u, v)Stores the best locally consistent predecessor cost.
Pseudocode
- 1.Prepare the inputs and state needed for Lifelong Planning A*.
- 2.Apply the incremental search step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return path.
Canonical Example
- Input
- Lifelong Planning A* input with a small representative case
- Output
- Path
- Explanation
- Lifelong Planning A* applies incremental search to produce path.
Implementation Notes
- Store predecessor information separately from distance or priority values.
- Keep the incremental search step separate enough to test independently.
Common Pitfalls
- Using a heuristic or preprocessed data that does not match the actual cost model breaks path quality.
- Forgetting to check edge cases can make Lifelong Planning A* look correct on only ideal inputs.
Interactive Mechanism Walkthrough
2D Grid Wavefront & TrajectoryShow the frontier, settled nodes, and the final path over the search space.
S
#
#
#
#
#
#
#
G
Step 1 of 4: Prepare the inputs and state needed for Lifelong Planning A*.
pathfinding-mechanismNotes
Lifelong Planning A* should be used with the assumptions and tradeoffs of incremental Heuristic Search in mind.
Sources (1)
What each reference supports for this entry.
Lifelong Planning A*
PaperOriginal LPA* paper supporting incremental heuristic replanning with g and rhs values.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Variant ofA* Search
Pathfinding · Core
LPA* incrementally repairs A*-style shortest-path estimates.
Compare with thisPrerequisite ofD* Lite
Pathfinding · Specialized
D* Lite builds on ideas from Lifelong Planning A*.
Compare with thisConceptual neighborsDynamic Window Approach
Pathfinding · Core
Dynamic Window Approach and Lifelong Planning A* both relate to local robot navigation, but use different structures or assumptions.
Compare with thisRelationships
View full relationship pageRelated Algorithms
Tags
PathfindingPath ReplanningHeuristic SearchDynamic Programming