AI Glossary / AI and machine learning / Advanced
Lifelong Planning A*
Definition
Lifelong Planning A*, usually written LPA*, is an incremental shortest-path search algorithm that reuses information from earlier searches when a graph's edge costs change. It combines heuristic search ideas from A* with mechanisms for repairing affected parts of a previous solution.
What it means
A route-planning problem may need to be solved repeatedly as travel costs or available connections change. Starting from scratch can repeat work that remains valid. LPA* preserves useful search information and updates it when changes make some estimates inconsistent.
“Lifelong” here refers to repeated planning across related problems. It does not mean lifelong machine learning or a system that gains general intelligence from experience. The algorithm reasons over a specified graph and cost model.
Reuse is most helpful when successive problems are similar. If changes affect much of the relevant graph, repairing the old search can still require substantial work. LPA* also needs appropriate assumptions about edge costs and the heuristic to support its shortest-path guarantees.
How it works
For each vertex, LPA* maintains a g value and a one-step lookahead value commonly called rhs. The g value stores the current path-cost estimate, while rhs is computed from predecessor estimates and edge costs, with a special value for the start.
A vertex is locally consistent when g and rhs agree. Changed edge costs can make vertices inconsistent. A priority queue, ordered using cost information and a heuristic toward the goal, directs processing toward the inconsistencies relevant to the current shortest-path calculation.
The algorithm propagates repairs until its stopping condition is satisfied. It can then extract a path under the current graph. When costs change again, it updates affected vertices and continues from stored information. Correct implementation of queue keys, updates and termination is important; simply caching an old A* path is not equivalent to LPA*.
Three practical examples
1. A simulated robot replans on a map when it learns that a corridor has become expensive or unavailable.
2. A planning service repeatedly solves related graph problems after a small number of link-cost changes.
3. An algorithms class compares the work done by repeated A* searches and LPA* when one edge changes between searches.
Think of it this way
Think of correcting a route calculation by revisiting the parts affected by a road closure while keeping still-valid work. The limit is that LPA* uses precise consistency conditions, not human intuition about which notes can safely be reused.
Worked example
Consider a tiny graph with two routes from S to G. Route S-A-G has edge costs 2 and 3, totaling 5. Route S-B-G has costs 4 and 2, totaling 6. Initially, the first route is shortest.
Now the cost of A-G rises from 3 to 8. The first route costs 2 + 8 = 10, so the second route with cost 6 becomes preferable. An incremental search updates the information affected by the changed edge rather than assuming the old route remains valid.
This arithmetic illustrates the replanning problem, not a full trace of LPA*'s queue operations. On such a tiny graph, reuse offers little practical benefit; its value is evaluated on larger repeated-search workloads.
Illustrative case study
A fictional warehouse-robotics team tests LPA* in a simulator where aisle costs change after temporary obstructions. The algorithm often reuses substantial search information, but a large layout change causes much more repair work.
The team measures path cost and planning time across both local and widespread changes. It also verifies that the graph updates reflect the simulator's current conditions, because a correct shortest path through an outdated graph would still be operationally wrong.
The case shows that algorithmic correctness and world-model accuracy are separate requirements. Replanning can only respond to changes that the system represents and supplies to the search.
Common misconceptions and mistakes
- LPA* is a form of lifelong learning. Its name concerns repeated path planning, not general model training.
- Reusing search guarantees constant-time updates. The amount of repair depends on the changes and graph.
- A shortest graph path is automatically a safe real-world route. The graph and costs must accurately represent relevant constraints.
Business use
LPA* is relevant to robotics and software that repeatedly solves related shortest-path problems. Its business value can come from reducing repeated computation when changes are limited and timely replanning matters.
Compare it with restarting A* and other appropriate incremental methods under realistic change patterns. Test correctness after cost increases, decreases and disconnected routes. Track how the world model is updated and how stale information is handled. The planner's output should be understood as optimal relative to the represented graph and cost assumptions, not as a guarantee about every physical condition.
People also ask
How is LPA* related to A*?
It is an incremental heuristic-search method that reuses information across related shortest-path calculations.
What does local consistency mean?
A vertex's stored g estimate agrees with its one-step lookahead rhs value.
Is LPA* the same as D* Lite?
No. They are related incremental planning methods, but their formulations and typical use differ.
Check your understanding
Why must a changed edge cost trigger updates even if the robot's start and goal stay the same?
Answer: The cost change can invalidate the previous shortest route and make stored path estimates inconsistent with the current graph.
Related terms
- Shortest Paths
- Heuristic
- Graph
- A* search
- incremental search
- shortest path
- D* Lite
- replanning
Learn next
Read A* and shortest-path search. Work through a small graph before and after an edge-cost change, then examine how g and rhs identify information that needs repair.
More in AI and machine learning
- Learning to rank - Learning to rank is the use of machine learning to order items according to relevance, preference or another defined criterion.
- Learning vector quantization - Learning vector quantization, or LVQ, is a family of supervised classification methods that represents classes with labeled prototype vectors.
- Life-time of correlation - In the source-specific stock-market study, life-time of correlation is the duration for which a rolling-window correlation coefficient remains continuously...
- Limited Memory AI - Limited memory AI is an informal category used to describe AI systems that use past information, learned patterns or recent observations when producing an...
- Linde - Buzo - Gray algorithm - The Linde - Buzo - Gray algorithm, or LBG algorithm, is an iterative method for designing a vector quantizer.
- Linear - Linear describes a relationship that follows a straight line: double the input and you double the output's contribution, with no curves, thresholds or...
Sources
Koenig, Likhachev and Furcy, Lifelong Planning A* (2004), author institution record: https://publications.ri.cmu.edu/lifelong-planning-a. Research-paper copy: https://citeseerx.ist.psu.edu/document?doi=e4481d5f8a3a06caafa1a8eebb4cfacb66ad6004&repid=rep1&type=pdf. The graph and warehouse simulation are fictional. Source review: the relevant algorithm and assumptions were consulted in the CMU author copy: https://www.cs.cmu.edu/afs/cs/Web/People/maxim/files/aij04.pdf.
Previous: Life-time of correlation Next: LIFO queue