Overview
LRTA* is a heuristic search method for online pathfinding. It works by updating heuristic estimates while acting one step at a time.
ExtendedSource checked
LRTA*
LRTA* addresses online pathfinding by updating heuristic estimates while acting one step at a time.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pathfinding
- Difficulty
- Intermediate
- Family
- Heuristic Search
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Learning Real-Time A*
Core Concepts
online pathfindingheuristic searchpathfinding
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use LRTA* when solving online pathfinding and you want to benefit from updating heuristic estimates while acting one step at a time.
- Choose it when O(n log n) average/worst-case time and O(n) memory match your workload profile.
- Prefer it over Visibility Graph Roadmap or 0-1 BFS when the problem structure favors online pathfinding.
When Not to Use
- Avoid when path costs or obstacles change in ways the method cannot update efficiently.
- Avoid when approximate paths are unacceptable and the method does not guarantee optimality.
What It Does
- Computes online pathfinding within Heuristic Search workloads (O(n log n) time, O(n) space).
- Works by updating heuristic estimates while acting one step at a time.
- Maintains key invariants across online pathfinding, heuristic search, pathfinding.
Use Cases
- Production and research workloads requiring online pathfinding via updating heuristic estimates while acting one step at a time.
- Heuristic Search pipelines where O(n log n) time and O(n) space fit system constraints.
- Engineering comparisons against Visibility Graph Roadmap and 0-1 BFS when tuning online pathfinding.
Inputs
- Heuristic Search input instance for online pathfinding
- Configuration parameters controlling online pathfinding
Outputs
- Computed online pathfinding solution produced by LRTA*
- Diagnostic state over online pathfinding and heuristic search
Pseudocode
- 1.Initialize the search space, start/goal states, and cost/priority tables for LRTA*.
- 2.Insert the initial state into the open frontier or roadmap with its baseline cost and heuristic estimate.
- 3.Expand or sample candidate transitions by updating heuristic estimates while acting one step at a time.
- 4.Update path costs, parent pointers, or conflict constraints whenever an improved trajectory is found.
- 5.Reconstruct and return the collision-free path from start to goal once the termination criterion holds.
Canonical Example
- Input
- Heuristic Search input instance for online pathfinding configured for a representative online pathfinding test case
- Output
- Computed online pathfinding solution produced by LRTA* satisfying LRTA* invariants
- Explanation
- LRTA* processes the input by updating heuristic estimates while acting one step at a time, tracking online pathfinding and heuristic search to produce the verified online pathfinding result.
Implementation Notes
- Separate search state from world state so changes can be tested.
- Use small maps with known optimal answers before large scenarios.
- Track whether returned paths are optimal, bounded, or heuristic.
Common Pitfalls
- Using an inadmissible heuristic where optimality is expected.
- Ignoring dynamic obstacles, time-dependent costs, or changing edge weights.
- Testing only open grids and missing narrow-passage cases.
Interactive Mechanism Walkthrough
2D Grid Wavefront & TrajectoryShow updating heuristic estimates while acting one step at a time on a small online pathfinding example.
S
#
#
#
#
#
#
#
G
Step 1 of 5: Initialize the search space, start/goal states, and cost/priority tables for LRTA*.
pathfinding-mechanismNotes
LRTA* operates in O(n log n) time and O(n) space within the Heuristic Search family. Often compared with Visibility Graph Roadmap and 0-1 BFS.
Sources (2)
What each reference supports for this entry.
Artificial Intelligence: A Modern Approach
BookAI search reference for real-time heuristic search and learning updates.
Open sourceReal-Time Heuristic Search
PaperOriginal LRTA* reference for online heuristic search with local learning updates.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborIDA*
LRTA* and IDA* are heuristic search variants that trade memory, repeated search, and online behavior differently.
Conceptual neighborReal-Time Adaptive A*
Real-Time Adaptive A* builds on real-time heuristic search ideas by updating heuristic values across episodes.
Related Algorithms
Tags
PathfindingGraph