Learning real-time A*
Algorithms AIMech:LearningRealTimeAStar DRAFT
Aliases: LRTA*, Learning real-time A-star
A real-time heuristic learning algorithm that moves to a minimum estimated path-cost neighbor, stores that minimum edge-cost-plus-heuristic value at the state it leaves, and retains learned state estimates across repeated problem-solving trials with the same goals.
Identity Notes & Concept Scope
This is Korf’s LRTA* formulation with a minimum-value backup rather than basic RTA*’s second-best backup. It learns state cost-to-go estimates from search experience; it is not ordinary A*, a trained neural network, Fill’s local-minimum-only cost increments, or Q-learning’s sampled action-value update. The inspected formulation is direct assignment of the minimum backup, not an added maximum with the state’s old value. 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
At each non-goal state n, use stored or initial heuristic values for its neighbors and form k(n,n′)+h(n′), where k is the edge cost. Move to a neighbor attaining the minimum and assign that minimum to h(n). Preserve the table across subsequent trials in the same problem space with the same goal set. This best-value backup replaces RTA*’s second-best backup. It can change values even when the state is not a local minimum and can decrease an initially inconsistent estimate. The source gives the same finite-space, positive-edge, finite-heuristic and everywhere-goal-reachable conditions for eventual goal finding as basic RTA*. For learning convergence, it additionally assumes non-overestimating initial estimates, zero estimates at goals, repeated random sampling of the initial states and random tie handling so the relevant alternatives continue to be explored. Under those conditions, its theorem concerns exact learned values along every optimal path from the sampled initial-state set to a goal over repeated trials.
⚠️ Curated Limitations & Negative Results
- The learning result does not say every state in an arbitrary graph is learned exactly, nor that a fixed finite number of trials certifies convergence. Random initial-state sampling and random tie resolution provide the repeated exploration used in the proof.
- Non-overestimation matters: an initially overestimated state can be avoided and remain uncorrected. The 1988 proof explicitly assumes h(goal)=0; the 1990 proof uses the same equality. Non-overestimation alone would not imply that equality if negative goal estimates were permitted.
- LRTA* can repeatedly traverse a heuristic depression before escaping and does not inherit basic RTA*’s tree local-optimality theorem. Good asymptotic estimates do not ensure that an early trial follows a shortest path.
- Replacing h(n) with max(old h(n), minimum backup) is an additional convention not asserted as the same literal source update. The direct minimum can decrease an admissible but inconsistent initial value; that does not contradict preservation of non-overestimation.
- The table stores state estimates, and the method evaluates successor costs. It is not Q-learning’s model-free sampled state-action update. No stochastic-transition extension, function-approximation guarantee, convergence rate or numerical puzzle result is curated.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:MachineLearningTask
Machine Learning Task
|
related_match | The primary papers explicitly formulate repeated-trial learning of heuristic values from problem-solving experience. The pinned AIO target denotes the task/process of developing methods that learn from data; this algorithm-to-task relation records that connection without asserting class equivalence or an is-a hierarchy. No language-model, neural-network or preprocessing identity is implied. |
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/LearningRealTimeAStar.yaml