Recursive best-first search with controlled re-expansion
Algorithms AIMech:RBFSControlledReexpansion DRAFT
Aliases: RBFS_CR, RBFS with bounded overhead
An RBFS variant that estimates subtree evaluation-value distributions and inflates backed-up values to make later visits expand geometrically more nodes, while retaining original lower-bound information for solution-cost pruning.
Identity Notes & Concept Scope
RBFS_CR is the histogram-based controlled re-expansion method of Hatem, Kiesel and Ruml. It is distinct from their fixed-tolerance RBFS-epsilon and weighted-root RBFS-kth-root heuristics. Its inflated ordering can depart from strict best-first order in the original evaluation values. No normalized identity match was found across the 442 AIO and 124 prior native records; ignored-inclusive text hits in the main checkout were prior discovery leads, source citations and search-order contrasts, plus incidental dependency substrings, not existing concept records.
Claims & Grounded Evidence
2 Claims
Mechanism
#search-procedure
Maintain original backed-up values F and additional inflated values F_CR. Histograms of generated but pruned evaluation values guide the inflation so the next visit is estimated to perform geometrically more work. Use inflated values to control traversal and backtracking, and original bounds for branch-and-bound after an incumbent solution is available.
Limitation
#conditional-bound
The overhead theorem relies on explicit distribution and extra-node assumptions. The paper also explains that relaxing original best-first order is intentional and that its Dockyard experiment uses an unlimited transposition table; those experiments do not demonstrate the memory bound of a path-only implementation.
⚠️ Curated Limitations & Negative Results
- The published O(N) expansion analysis is conditional on accurate subtree histograms, enough counts to choose appropriate backups, and a bound of O(N) on extra unique nodes beyond optimal solution cost. N is the specified A-star search-tree expansion count without duplicate pruning and with worst-case ties.
- The implementation’s finite histogram buckets estimate distributions; they do not automatically satisfy the analysis’s exact-distribution assumption on every problem.
- The paper retains one histogram per current-path node. Its depth-linear storage argument assumes bounded per-node histogram and successor storage; an added unbounded transposition table changes the memory scope.
- Liberal thresholds require continuing branch-and-bound after finding an incumbent to establish optimality under admissible bounds. The first encountered solution is not automatically certified optimal.
- The record does not certify the pseudocode as a complete executable implementation or claim universal speed improvement.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No suitable AIO counterpart for this graph/state-space search procedure was identified in the inspected snapshot. Using graphs, evaluation functions or a search subroutine in an AI system does not equate the algorithm with a learned model, a learning task or a mathematical function.
Search Scope: All 442 pinned AIO labels and scoped synonyms and 124 preceding native identities were compared. Both updated checkouts were searched including hidden and ignored files. Exact CLASS nodes and edges for GraphLanguageModel, ReasoningLLM, NeuroSymbolicLLM, MachineLearningTask, MathematicalFunction and ReinforcementLearning were inspected, alongside semantic search for search, planning, heuristic, path, traversal, symbolic, reasoning and graph terminology.
| Examined AIO Candidate | Rejection Reason |
|---|---|
AIO:GraphLanguageModel
|
A language model operating on structured graph representations is not a graph traversal or shortest-path algorithm. |
AIO:ReasoningLLM
|
Language-task deductive inference does not denote general state-space search. |
AIO:NeuroSymbolicLLM
|
A language-model architecture combining neural and symbolic components is not the search procedure itself. |
AIO:MachineLearningTask
|
Building methods that learn from data is not the identity of an algorithm traversing a specified graph. |
AIO:MathematicalFunction
|
The search procedure is distinct from the mathematical functions it may evaluate. |
AIO:ReinforcementLearning
|
A learning task balancing exploration and exploitation is distinct from deterministic graph/state-space traversal. |
Evidence Sources & Primary Literature
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Matthew Hatem, Scott Kiesel, Wheeler Ruml
|
primary paper
full_text
|
ID: doi:10.1609/aaai.v29i1.9352
sha256:71550d1c85a5…
|
analysis-and-scope
|
Matthew Hatem, Scott Kiesel, Wheeler Ruml
|
primary paper
full_text
|
ID: doi:10.1609/aaai.v29i1.9352
sha256:71550d1c85a5…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T05:44:44Z
Updated: 2026-10-11T05:44:44Z
Source File:
data/curated/RBFSControlledReexpansion.yaml