Lifelong Planning A*
term_id: lifelong_planning_a
Category: application_paradigms
Definition
Lifelong Planning A* (LPA*) is an extension of the A* search algorithm designed for environments where costs change over time. Instead of restarting the search, LPA* maintains a priority queue and updates only the affected nodes when edge weights are modified. This makes it highly efficient for robotics and navigation systems operating in partially known or changing terrains, significantly reducing computational overhead compared to standard replanning methods.
Summary
An incremental pathfinding algorithm that efficiently updates shortest paths in dynamic graphs without recomputing from scratch after edge weight changes.
Key Concepts
- Incremental Search
- Pathfinding
- Dynamic Graphs
- Robotics Navigation
Use Cases
- Autonomous vehicle routing in traffic
- Robot navigation in changing warehouses
- Real-time strategy game AI movement