Real-time A*
Algorithms AIMech:RealTimeAStar DRAFT
Aliases: RTA*, Real-time A-star
A real-time heuristic search algorithm that moves to a neighbor with minimum edge-cost-plus-heuristic estimate and stores the second-best such estimate at the state it leaves, using bounded lookahead or initial heuristics for previously unvisited states.
Identity Notes & Concept Scope
The record identifies the basic RTA* control algorithm with a second-best backup, not ordinary A* frontier search, IDA* repeated cost-bounded passes, LRTA* minimum-value learning, or the additional graph-correction procedure sketched in the 1988 paper. Distances used to choose the next move are relative to the current state rather than the original start. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 313 preceding native IDs/names/aliases. Full-checkout fixed-string searches included ignored and hidden files in worktree and main, returning 24 and 24 lines respectively. All 24 unique lines were inspected, and the sorted checkout hit sets were identical: prior leads, neighboring Breakout descriptions and their saved reviews/ledgers, not existing candidate records. Seven exact AIO CLASS nodes with scoped synonyms/comments and outgoing edges and four full native neighboring records were inspected. Absence is bounded to this snapshot and semantic neighborhood.
Claims & Grounded Evidence
1 Claim
Mechanism
#method
Maintain a table for states actually visited. At the current non-goal state, enumerate neighboring states and evaluate edge cost plus the stored heuristic of a visited neighbor or a heuristic estimate, optionally produced by bounded minimin lookahead, for a new neighbor. Move to a neighbor with minimum resulting score, resolving ties among minima, and store the second-best score at the old state. With tied best alternatives, the second-best score may equal the best. The table persists during the search and allows revisits and backtracking. Only roots actually visited need enter this table; lookahead descendants need not all be retained. The 1990 paper proves eventual goal finding for a finite problem space with positive edge costs, finite heuristic values and a goal reachable from every state. Its local-optimality theorem concerns decisions relative to the cumulative searched frontier on a tree, not globally shortest returned paths.
⚠️ Curated Limitations & Negative Results
- A finite reachable goal from the initial state alone is insufficient if an irreversible move can enter a region with no route to any goal. Infinite spaces, zero/negative cost cycles and infinite heuristic barriers are outside the stated completeness theorem.
- The 1990 tree local-optimality theorem does not extend unchanged to graphs with cycles. The 1988 paper separately sketches a recursive correction of stored values and omits its proof for space; the 1990 article says significant modifications would be required. That variant is not silently included in basic RTA*.
- Real-time work depends on a fixed lookahead/resource policy and manageable branching and heuristic evaluation. The method is not a uniform constant-time implementation for arbitrary successor sets or lookahead depths, and the visited-state table can grow with execution.
- The second-best rule assumes alternatives from which that value can be obtained. The inspected method description does not state a general single-successor fallback; an executable implementation must declare this boundary rather than invent an undocumented convention here.
- Second-best backups can overestimate remaining goal distance when reused across trials. The source motivates LRTA* as a separate multi-trial learning modification. No puzzle benchmark or complete graph-correction proof was audited.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No suitable AIO counterpart was established for this basic state-space search procedure in the inspected snapshot and neighborhood. Shared graph, reasoning or heuristic words do not justify a model/task mapping.
Search Scope: All 442 pinned AIO labels/scoped synonyms and 313 preceding maintained IDs/names/aliases; ignored/hidden text in both full checkouts; semantic label search for search, planning, heuristic, path, traversal, symbolic, reasoning, graph, reinforcement and learning-task terminology; seven exact AIO CLASS nodes and four complete native neighbors.
| Examined AIO Candidate | Rejection Reason |
|---|---|
AIO:GraphLanguageModel
|
Operating on a state-space graph does not make this procedure a language model over graph representations. |
AIO:ReasoningLLM
|
The target is a language model with reasoning during language tasks, not a general path or constraint search algorithm. |
AIO:NeuroSymbolicLLM
|
This procedure does not require neural language modeling or a neuro-symbolic language-model architecture. |
AIO:MachineLearningTask
|
This basic single-search procedure adjusts search bookkeeping; it does not require learning a reusable predictor from multiple problem-solving trials. The separately curated LRTA* extension explicitly does that. |
AIO:MathematicalFunction
|
The algorithm uses and updates a cost function; it is not identical to the mathematical function itself. |
AIO:ReinforcementLearning
|
Search, revisitation and adaptive costs alone do not identify the basic procedure with a learning task balancing exploration and exploitation. Multi-trial heuristic learning is separately represented. |
AIO:TrainingStrategy
|
This algorithm does not require preprocessing or training a machine-learning model. |
Evidence Sources & Primary Literature
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Richard E. Korf
|
primary paper
full_text
|
ID: doi:10.1016/0004-3702(90)90054-4
sha256:8cf1b89fb487…
|
earlier-conference-paper
|
Richard E. Korf
|
primary paper
full_text
|
sha256:ab17a837c83e…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T15:04:45Z
Updated: 2026-10-11T15:04:45Z
Source File:
data/curated/RealTimeAStar.yaml