Local search space learning real-time A*
Algorithms AIMech:LocalSearchSpaceLearningRealTimeAStar DRAFT
Aliases: LSS-LRTA*, Local search space LRTA*
A real-time heuristic learning algorithm that constructs a bounded local search space with A*, repairs the heuristic values of its expanded states from the unexpanded boundary using reverse Dijkstra propagation, and executes the A* path to a selected boundary state before repeating.
Identity Notes & Concept Scope
The identity is the 2009 Koenig–Sun LSS-LRTA* algorithm: bounded local A*, reverse-Dijkstra boundary repair over predecessor edges, then original-tree-path commitment. It differs from basic LRTA* one-state updates, RTA* second-best backups, ordinary full A*, Dijkstra alone, EHC escape and RTAA* F-minus-g repair/movement-cap controls. The 2004 predecessor remains a source-version follow-up rather than an accepted separate identity. Fresh16 October 2026 collection at merged base917e850123890bd00e671353652fe53101f83bfb compared 790 native and 442 pinned AIO records, 4,888 identity fields/3,732 normalized values with zero candidate collisions. Four ignored/hidden-inclusive searches returned 128/119/297/636 occurrences, grouped into78 exact contents and read in full as unique contents by root, with independent supporting readings separately recorded. All 913 main/394nested objects were recursively queried; the 3 matching objects and 12 neighbor identity/definition projections were read. Eleven exact AIO CLASS contexts with 51incident edges were inspected. This bounded search is not all-literature coverage. Nested 393 is the specific LSS residual under responsible main 8; main 3/286 remain crosslinks only. Five LSS source/variant questions stay under nested 393 and the KBFS/multi-state commitment umbrella remains partial. The related mapping to MachineLearningTask denotes persistent heuristic learning without an is-a or exact-equivalence assertion.
Claims & Grounded Evidence
6 Claims
Mechanism
#bounded-local-lookahead
From the current state, run A* with the current learned heuristic, expanding at most a positive lookahead count and stopping earlier when the goal is about to be expanded. The expanded CLOSED states form the local search space; generated unexpanded OPEN states form its boundary. Before learning, select a minimum-g+h boundary endpoint, preferring the goal when tied.
Mechanism
#boundary-based-heuristic-repair
Perform a reverse, multi-source Dijkstra repair initialized by the unchanged heuristic values on the A* OPEN boundary. Reset local CLOSED labels to infinity, reprioritize OPEN by h, and propagate costs through predecessor edges into the local space. A completed repair assigns each local state the minimum cost of reaching a boundary state through the local space plus that boundary state’s retained h value. This uses relevant predecessor edges rather than only A* tree edges, and is not a single backup at the current state.
Mechanism
#execution-and-persistent-learning
After the repair, follow the original A* tree path to the boundary endpoint chosen before repair, stopping at that endpoint or when an action cost on the remaining path increases. Update the current state and observed costs and repeat until the goal is reached. Cache learned h values across searches; per-search g values and A* tree bookkeeping are freshly initialized, with lazy initialization described for implementation. The base method can execute several actions before replanning.
Scope
#conditional-learning-properties
For the stated finite deterministic state/action setting with positive costs, initially consistent h values and h(goal)=0, and cost changes restricted to increases, completed local repairs preserve consistency and admissibility and do not lower learned h values between completed search episodes. With well-defined repairs and finite upper bounds on future goal distances of visited states, the positive-cost potential argument bounds action executions to the goal. The result does not follow from initial-state goal reachability alone.
Scope
#repeated-trial-boundary
The repeated-trial theorem teleports the agent back to a fixed start whenever it reaches the same goal and retains learned h values. Under bounded future goal distances of the relevant visited states and a positive lower bound on nonzero action-cost increases, it bounds the number of trials that do not follow a shortest start-to-goal trajectory. It does not claim an optimal first trial or exact learning of every state in the graph.
Scope
#rtaa-boundary
RTAA* shares bounded A* local search but updates each expanded state with the selected frontier value F minus that state’s A* g value, rather than solving the local boundary-value problem with reverse Dijkstra. Its general pseudocode also has an independently chosen movement cap. The2006 comparison’s LRTA* label denotes a larger-lookahead2004 variant, not only Korf’s basic one-state update. Equal lookahead and identical tie handling give the same one-state update, but larger-lookahead procedures need not coincide.
⚠️ Curated Limitations & Negative Results
- The supplied heuristic must be consistent, with zero at the goal, for the stated analyses. Admissibility alone is weaker. Costs may increase; arbitrary decreases, stochastic transitions, changing goals and function approximation are outside this method assessment.
- A bound on A* expansions is not an unconditional constant bound on all computation or memory. Successor/predecessor access, branching, priority queues, heuristic evaluation and Dijkstra repair cost matter, and cached h values can accumulate. The manuscript explicitly replaces conceptual global initialization by lazy initialization.
- The monotonicity claim concerns learned values after completed repairs. Figure5 temporarily sets local labels to infinity and then lowers these work labels during Dijkstra; those transient assignments are not monotone learned estimates.
- Figure5 tests OPEN exhaustion after A* but shows no empty-OPEN fallback inside Dijkstra while CLOSED remains nonempty. A directed local dead end can lack a route to any boundary even when the start has a goal path. The present mechanism scope therefore requires complete, well-defined boundary repair, as in the relevant reversible goal-connected navigation setting; no undocumented fallback or code conformance is invented.
- Successful finite-time navigation requires more than a goal path from the original start: the theorem bounds future goal distances of states the agent may visit. Dead ends, unbounded future goal distances, zero or negative costs, and arbitrary infinite state spaces do not inherit that guarantee. The repeated-trial result also needs its fixed-start/goal and cost-increase assumptions.
- Small lookaheads can cause repeated motion through heuristic depressions and long early trajectories. Neither increasing lookahead nor using stronger initial heuristics is asserted to improve every trajectory, and no unconditional superiority over D* Lite or RTAA* is claimed. Experimental conclusions in the source are specific to its terrains, heuristic choices, implementation and objective.
- The2009 author manuscript supplies the method assessed here; its2004 predecessor is not claimed read and no invention-priority claim is made. D* Lite is contrasted only using the inspected primary comparison article’s description. No implementation audit, benchmark reproduction or later variant coverage is claimed.
- The algorithm is distinct from basic LRTA*, RTA* second-best backups, ordinary full A* search, Dijkstra alone, EHC breadth-first escape, and RTAA*. The scalar heuristic learned here is not automatically a sampled state-action learner, neural network or language model.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:MachineLearningTask
Machine Learning Task
|
related_match | The primary method persistently learns state cost-to-go estimates from local search and observed costs, and explicitly retains them across repeated trials. This connects the algorithm to the pinned learning-from-data task/process without class equivalence or an is-a claim; it agrees with, but is independently grounded beyond, the maintained basic LRTA* mapping. |
Evidence Sources & Primary Literature
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
koenig-sun2009
|
Sven Koenig, Xiaoxun Sun
|
primary paper
full_text
|
ID: doi:10.1007/s10458-008-9061-x
sha256:0938f78c7960…
|
koenig-likhachev2006
|
Sven Koenig, Maxim Likhachev
|
primary paper
full_text
|
sha256:9ad098fbeaa3…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-16T01:07:36Z
Updated: 2026-10-16T01:07:36Z