Real-Time Adaptive A*
Algorithms AIMech:RealTimeAdaptiveAStar DRAFT
Aliases: RTAA*
A real-time heuristic search algorithm that repeatedly runs bounded forward A*, updates every expanded state to the selected next-to-expand boundary f value minus its own g value, and executes a capped prefix of the A* path before replanning while retaining learned heuristic values.
Identity Notes & Concept Scope
Current cohort359 assessment on clean base 0f7e2c5df224901e9284a883dfd0457fd4c29375: the same ignored-inclusive collection and attributed root/independent matching-content readings found no candidate identity collision in the1,239-record snapshot. Bounded current comparisons distinguish CLOSED-only F-minus-g heuristic repair and separately controlled movement from ordinary A*, basic LRTA*/RTA*, LSS reverse-Dijkstra learning and memory/threshold search. The accepted2006 defining source,2018 later-comparison artifact, eight claims, ten limitations and weak learning-task related mapping remain unchanged; the task class is not algorithm identity or subclass. Nested393 is the accepted exact source responsibility, with main8 retaining an umbrella cross-reference. All20 bibliography occurrences, five original questions and two retrieval routes remain exact. The current2018 reading advances the historical route question but retains timing aggregation, caption/axis and thesis limits; D* Lite/LPA, Adaptive A*, earlier LSS and framework/variant questions remain pending.
Claims & Grounded Evidence
8 Claims
Mechanism
#bounded-local-search
From the current state, forward A* uses the retained consistent heuristic until a goal is about to expand or a positive lookahead expansion budget is reached. CLOSED is the expanded local space; the selected next-to-expand OPEN state b supplies the boundary value F=g(b)+h(b). OPEN exhaustion returns failure.
Mechanism
#uniform-f-minus-g-learning
For each expanded state s, assign h(s)=F−g(s). Do not update other states. The update uses one selected boundary f value and needs no reverse-Dijkstra propagation; ordinary OPEN states need not yet have optimal g values.
Mechanism
#execution-and-retention
After learning, follow the cost-minimal A* path toward b, stopping at b, an independently chosen positive movement cap, or an observed increase on the remaining path. Repeat planning from the new state, retaining learned h; action costs may increase between moves.
Scope
#consistency-and-completion
In the stated finite deterministic state/action setting, costs exceed a fixed positive epsilon, initial h is consistent with h(goal)=0, cost changes are increases, and all state goal distances remain uniformly bounded above. Learned h does not decrease and remains consistent; the potential argument then guarantees reaching a goal.
Scope
#repeated-trial-scope
If each goal arrival resets the agent to the same start and learned h persists, the source bounds the number of nonoptimal trials when nonzero cost increases also have a positive lower bound, under its preceding assumptions. This is neither first-trial optimality nor exact learning of every state.
Scope
#lrta-comparison-boundary
For lookahead one and identical tie handling, RTAA and the paper’s 2004 larger-lookahead LRTA comparator behave identically. At greater lookahead the comparator solves the boundary backup problem while RTAA uses F−g. The one-episode informativeness comparison starts with identical h and does not imply dominance along diverging trajectories.
Application
#navigation-application
The defining application is goal-directed navigation in unknown four-neighbor grids using Manhattan h and the freespace assumption; newly discovered blocked cells increase entering costs. The reported maze experiment uses 2,500 solvable 151×151 mazes, with implementation-specific trajectory/time tradeoffs.
Scope
#later-comparator
The 2018 study reports domain- and lookahead-dependent relative performance, not consistent RTAA superiority. Its timing comparisons use amortized CPU time per episode and interpolation from expansion-bounded runs.
⚠️ Curated Limitations & Negative Results
- The defining proofs assume finite states/actions, action costs bounded below by positive epsilon, and initial consistency with zero goal values; mere admissibility is insufficient for the same no-reopening A* and monotonic-update proof.
- Goal reachability from only the initial state does not establish the source’s bounded-goal-distance assumption for all states. Reachable traps/dead ends are outside that completion theorem. OPEN-exhaustion failure is an explicit branch.
- Costs may increase; arbitrary decreases, changing goals, stochastic transitions and moving-goal extensions are not covered by the defining theorem.
- The lookahead cap bounds expansions, and the update takes one assignment per expanded state; it is not an unconditional wall-clock or total-memory guarantee. Successor generation, queue operations and accumulated learned h have implementation costs.
- Exploratory trajectories may be suboptimal and repeated. Theorem4 is conditional on fixed-start repeated trials and lower-bounded nonzero cost increases; it does not guarantee optimal first execution.
- The 2006 paper calls a 2004 larger-lookahead LRTA variant LRTA*, not exclusively Korf’s original one-state method. Its equivalence result is lookahead one with identical ties; Adaptive A* complete-search and later RTAA variants are separate source/version questions.
- Reported relative advantages depend on domain, heuristic, lookahead, movement choice, tie handling, hardware and implementation. No universal superiority, monotonic lookahead benefit or reproduced benchmark is asserted.
- 2018 PDF2 prose says microseconds and 77.22us crossover, while visible plot axes on PDF3–5 say ms. The Figure1 center axis reads planning time (ms), without the per-episode qualifier used in nearby prose; actual aggregation remains unresolved. Preserve these inconsistencies and avoid absolute timing/crossover claims until clarified.
- The 2018 Traffic benchmark resets an agent with no successors to the start and reports collisions/restarts; this experiment does not extend the 2006 completion theorem to arbitrary directed dead-end graphs.
- The 2018 authors did not compare original implementation code and defer statistical-anomaly details to an unread 2017 thesis. Neither claim is independently reproduced here. Publisher PDF access failed; author manuscript supplies the inspected evidence.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:MachineLearningTask
Machine Learning Task
|
related_match | Persistent state-heuristic learning from repeated search experience supplies a weak relation to the pinned task context. The bounded forward-search, CLOSED-only F−g update and movement controller are not identical to a general task class. This proposal asserts neither exact equivalence nor subclass inclusion and does not identify the algorithm with a sampled reinforcement-learning method. |
Evidence Sources & Primary Literature
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
koenig-likhachev2006
|
Sven Koenig, Maxim Likhachev
|
primary paper
full_text
|
sha256:9ad098fbeaa3…
|
kochvi-ruml2018
|
Shane Kochvi, Wheeler Ruml
|
primary paper
full_text
|
ID: doi:10.1609/socs.v9i1.18465
sha256:a30caf4dcfe9…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-16T03:43:16Z
Updated: 2026-10-16T03:43:16Z
Source File:
data/curated/RealTimeAdaptiveAStar.yaml