Minimin search with alpha pruning
Algorithms AIMech:MiniminAlphaPruning DRAFT
A bounded single-agent lookahead planner that backs up minimum path-cost-plus-heuristic frontier estimates and prunes branches using an incumbent frontier value when the evaluation is nondecreasing along paths.
Identity Notes & Concept Scope
The actual 2026-10-15 post-cohort 351 collection at commit 8481972c496a6f9a40d645bb60e25800b6e5f8c3 covers 783 maintained and 442 generated records. Four fixed-word searches included ignored and hidden files across the original checkout and three retained discovery/recovery checkouts. All 23247 occurrences were reconstructed into 1030 distinct contents, freshly read in three attributed supporting partitions. Root read the focused complete candidate/restoration contents, all eight normalized identity/definition rows and fourteen contextual fields, every matching field for 43 frontier objects, both selected owners and all six restoration context owners. Normalization covered 4867 identity-field occurrences. No candidate collision was found within this bounded scope. This is bounded single-agent minimum-backup lookahead with alpha pruning under consistent f values. It is optional planning for RTA*, not its second-best execution controller, LRTA* heuristic learning, IDA* repeated bound search or the separately pending graph-correction method. Source versions, horizon-relative estimates and per-root-child incumbent reset are explicit; owner 291 is unchanged.
Claims & Grounded Evidence
5 Claims
Mechanism
#bounded-minimum-backup
From the current planning root, simulate successors to a fixed number-of-moves horizon. Evaluate frontier nodes with f(n)=g(n)+h(n), where g is the path cost from that root, and back up minima because the single agent controls every move. This yields bounded-lookahead estimates and a direction toward a minimizing child rather than a minimax opponent response.
Mechanism
#terminal-evaluation
Terminate a simulated path early at a goal with heuristic value zero, preserving its accumulated path cost. A nongoal dead end before the horizon receives an infinite heuristic value. The intended branch selection avoids such dead ends when a finite alternative is available.
Mechanism
#monotonic-alpha-cutoff
Maintain alpha as the lowest evaluated frontier cost in the current search. Evaluate interior nodes as well. Under nondecreasing f along each generated path, stop expanding a branch whose interior f equals or exceeds alpha; when a frontier node has a smaller f, lower alpha. This preserves the bounded-tree minimum while potentially avoiding descendants that cannot improve it.
Mechanism
#complete-child-values
The 1990 presentation reinitializes alpha to infinity before searching each immediate child of the current state. This sacrifices some cross-child pruning to return an actual backed-up value for every child, as required by the separate RTA* controller rather than only identifying the overall best direction.
Scope
#planning-component-boundary
The source treats minimin lookahead with alpha pruning as a planning procedure that can be encapsulated as a more expensive heuristic evaluator. Executing one recommended move and planning again is distinct from RTA* second-best memory updates, LRTA* repeated-trial learning and the separate 1988 graph-correction sketch.
⚠️ Curated Limitations & Negative Results
- The literal alpha cutoff requires nondecreasing f on the generated paths. Admissible but inconsistent h can hide a lower-valued horizon descendant behind a pruned interior node. A learned or altered heuristic must satisfy the same condition; no consistency repair is silently inserted.
- Equality cutoffs retain a minimum value, not every tied leaf or a prescribed tie distribution. Exact inequality comparisons are the mathematical rule; numerical tolerances and all-infinite/empty alternatives need explicit implementation conventions. Infinite dead-end scores do not certify a solution when no finite alternative exists.
- Finite-depth heuristic estimates do not certify a globally shortest solution. With nonuniform costs, merely encountering a goal within the horizon does not force the minimum frontier to be a goal; the source’s broad p. 10 statement must be qualified rather than promoted to an unrestricted theorem.
- Repeated memoryless use can cycle even on a finite positive-cost graph with a reachable goal. The RTA* execution table, LRTA* learning updates and their assumptions are separate mechanisms; minimin pruning alone supplies none of their global guarantees.
- Fixed depth is a real-time policy only relative to bounded successor generation and evaluation costs. Work may remain exponential in depth, and exploration order changes pruning work even when the final minimum value is unchanged. The paper’s immediate-f ordering experiment reports overhead rather than a universal speedup.
- The finite sliding-tile observations and independent zero/one-increment analytic model do not prove that larger branching factors always permit deeper search, or that deeper lookahead always improves a particular executed solution. The 1990 article explicitly reports model mismatch and nonmonotone empirical behavior. No benchmark, figure-value reproduction or author-code execution was performed here.
- The 1990 consistency formulation is the defining operational account; the 1988 metric shorthand and more optimistic model discussion are not interchangeable guarantees. Graph-corrected RTA* remains a separate source-version lead: its 1988 proof is omitted, and the 1990 article states that graph local optimality requires significant modifications. No complete graph-correction implementation, formal proof or family exhaustion is claimed.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No substantive counterpart to this source-defined single-agent lookahead/pruning procedure was identified in the inspected AIO snapshot and selected semantic neighborhood. Shared graph, heuristic, function or reasoning words do not establish a model/task mapping.
Search Scope: The actual 2026-10-15 post-cohort 351 collection at commit 8481972c496a6f9a40d645bb60e25800b6e5f8c3 covers 783 maintained and 442 generated records. Four fixed-word searches included ignored and hidden files across the original checkout and three retained discovery/recovery checkouts. All 23247 occurrences were reconstructed into 1030 distinct contents, freshly read in three attributed supporting partitions. Root read the focused complete candidate/restoration contents, all eight normalized identity/definition rows and fourteen contextual fields, every matching field for 43 frontier objects, both selected owners and all six restoration context owners. Normalization covered 4867 identity-field occurrences. No candidate collision was found within this bounded scope. The ten exact pinned AIO CLASS definitions, scoped synonyms and incident graph contexts listed here were inspected in the accepted research. Generic mathematical-function, task/training, network/process and reasoning-language-model classes do not identify this source-defined bounded lookahead algorithm. No suitable target was found in that inspected snapshot and semantic scope; this is not universal upstream absence.
| Examined AIO Candidate | Rejection Reason |
|---|---|
AIO:GraphLanguageModel
|
A language model over graph-structured inputs or outputs is not a bounded state-space planner; a search tree does not supply a language-model identity. |
AIO:ReasoningLLM
|
The target requires language-model reasoning during language tasks, whereas the planner needs neither language nor a learned model. |
AIO:NeuroSymbolicLLM
|
No neural language modeling or neuro-symbolic architecture is necessary to the method. |
AIO:MachineLearningTask
|
Using a supplied heuristic and computing bounded backups is not necessarily a process of learning from data. LRTA* repeated-trial learning is separately maintained. |
AIO:MathematicalFunction
|
The method evaluates and backs up mathematical functions, but its exploration, incumbent and cutoff procedure is not identified by this generic mathematical-rule class. |
AIO:ReinforcementLearning
|
The source-scoped planner does not require reward-driven policy or value learning; simulated lookahead alone does not establish the target learning-task relation. |
AIO:TrainingStrategy
|
The method need not preprocess or train a machine-learning model. |
AIO:Network
|
The implicit state graph is a search representation, not a mandatory communication/computational network being designed or a network architecture; the generic representation is insufficient for a substantive mapping. |
AIO:ArtificialNeuralNetwork
|
Search-tree nodes are not required artificial neurons with weighted neural signaling. |
AIO:MarkovChain
|
A stochastic transition model could be added, but the source method is not defined as a stochastic process with the target dependency structure. |
Evidence Sources & Primary Literature
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
korf1990
|
Richard E. Korf
|
primary paper
full_text
|
ID: https://doi.org/10.1016/0004-3702(90)90054-4
sha256:8cf1b89fb487…
|
korf1988
|
Richard E. Korf
|
primary paper
full_text
|
sha256:ab17a837c83e…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-15T22:07:33Z
Updated: 2026-10-15T22:07:33Z
Source File:
data/curated/MiniminAlphaPruning.yaml