Home / Curated / Algorithms / RBFS-epsilon

RBFS-epsilon

Algorithms AIMech:RBFSEpsilon DRAFT

Aliases: RBFSϵ

A recursive best-first search variant that adds a finite nonnegative epsilon tolerance to the competitive expansion threshold, retaining the baseline regeneration and backup structure while using additional incumbent stopping conditions when a solution-quality certificate is required.

Identity Notes & Concept Scope This record denotes the 2015 additive competitive-threshold RBFS variant. A finite nonnegative epsilon changes continuation eligibility relative to the alternative-derived bound while retaining the baseline recursive organization. Its separately qualified incumbent certificate is not an unqualified first-goal guarantee. Ordinary RBFS, histogram-controlled RBFS_CR and the kth-root split are distinct procedure scopes; epsilon=0 is an algebraic comparison endpoint, not a global alias. The source-local RBFSϵ label is retained, with no generic epsilon-search alias. Later 2024 use of RBFS_CR for an epsilon relaxation remains a source terminology question. Current insertion context was reconciled at merged commit c222454fe2e2ce2b9be5fd78a01d47e9961d1f26: 807 native and 442 pinned AIO records, 4,946 identity-field occurrences and 3,781 normalized values. Four ignored- and hidden-inclusive roots returned 165 matching contents / 1,085 occurrences, all byte-identical to the bound prior readings; no candidate exact normalized identity collision was found. All 1,249 native and generated record files match that evidence. Earlier full 25-node / 92-edge AIO and native-neighbor readings are reused with attribution, not claimed as fresh whole-ontology review. Source tracking uses existing main 912 while preserving prior IE, main 6/7/822/911 responsibilities and every historical source question.

Claims & Grounded Evidence

4 Claims

Mechanism #additive-threshold-relaxation

The variant replaces the competitive comparison F(best)<=B in RBFS with F(best)<=B+epsilon. Interpreting epsilon as a finite nonnegative cost tolerance lets search continue within a subtree beyond the unrelaxed competing bound; this changes traversal eligibility rather than the static heuristic formula.

supports Source: Recursive Best-First Search with Bounded Overhead · Locator: Author PDF p.3 / official p.1153, RBFS-epsilon paragraph; Figure 1 on author p.2 / official p.1152

Mechanism #baseline-regeneration-and-backup

The proposed change is to the upper-bound comparison of the baseline procedure. Conditional inheritance of previously backed-up values, selection of the best two children, recursive competition with the alternative branch, and return-value backup retain their baseline roles. The explicit empty-successor return and finite-F guard remain relevant; the additive relaxation does not replace them.

supports Source: Recursive Best-First Search with Bounded Overhead · Locator: Author PDF p.2 / official p.1152, Figure 1 and explanation; author p.3 / official p.1153, first variant paragraph

Scope #incumbent-quality-stopping

The source requires continued branch-and-bound after finding an incumbent when optimality is required, and gives f(goal)<=w*B as a bounded-suboptimal stopping condition. Here that certificate is interpreted with a sound uninflated lower bound B, w>=1 and h(goal)=0 so f(goal) is the solution cost; the relaxed traversal threshold B+epsilon is not substituted for the certificate.

supports Source: Recursive Best-First Search with Bounded Overhead · Locator: Author PDF p.3 / official p.1153, RBFS-epsilon paragraph and quality stopping condition

Scope #parameter-and-overhead-scope

The paper identifies the useful epsilon choice as potentially domain- or instance-dependent and explicitly says this modification does not improve its theoretical O(N^2) total-expansion upper bound. This additive variant is presented separately from both the multiplicative kth-root split and the later histogram-controlled RBFS_CR method.

supports Source: Recursive Best-First Search with Bounded Overhead · Locator: Author PDF p.3 / official p.1153, first two variant paragraphs and RBFS_CR subsection

⚠️ Curated Limitations & Negative Results

The variant is specified as a modification of baseline Figure 1, not a complete separate executable listing. Root/caller initialization, tie handling, numeric infinities and complete incumbent-management conventions require explicit implementation decisions; the finite-F guard and empty-successor return must not be silently dropped.
A first goal reached under an additive relaxed threshold need not be optimal. The source’s incumbent certificate requires a sound uninflated competitive lower bound; arbitrary weighted or relaxed values cannot be reused as that lower bound without justification. An unqualified first-goal or optimality guarantee is not claimed.
Finite epsilon>=0 is the bounded interpretation used here; negative or infinite tolerance behavior is not certified. Epsilon has the units of f and is not itself a multiplicative quality factor. At epsilon=0 the upper-bound comparison reduces algebraically to the baseline comparison, without proving that all unspecified implementation choices coincide.
No automatic parameter-selection rule or universal reduction in work follows. Larger epsilon can change ordering and the quality-stopping work, and the source retains an O(N^2) expansion bound. The conditional O(N) histogram-overhead theorem and its additional assumptions concern RBFS_CR, not this variant.
Depth-linear path/sibling storage presumes bounded branching and node data; optional transposition tables have separate costs. The source description does not establish completeness or termination for arbitrary cyclic, infinite, negative-cost or unsolvable graph inputs.
Reported performance depends on domain, heuristic, implementation and tolerance. The square-root puzzle’s epsilon=16 is a particular setting, and Dockyard uses an unlimited transposition table. Historical Java/hardware results and the anytime RBFS-versus-RBFS_CR curves are not portable speedups or evidence about this variant’s total memory; no experiment is reproduced here.
The author and official 2015 PDFs are two byte artifacts of one work with matching normalized page bodies, not independent studies. The later 2024 ILBFS source labels an epsilon relaxation RBFS_CR, whereas the defining 2015 source separates them. This terminology difference and the retained source/version/code questions do not justify merging their identities.

Artificial Intelligence Ontology (AIO) Grounding

Explicit AIO Snapshot Assessment: No Match

Rationale: RBFS-epsilon is a source-defined search-control procedure. No inspected target denotes its identity or a justified hierarchy, and the source establishes no sufficiently specific positive related mapping to these learning/model/layer classes.

Search Scope: Prospective snapshot collected at HEAD bcf1e846fe3d3dbb6d0651d32db6b7045fd28cae on goal/discover-ai-concepts-round361: 804 native and 442 AIO records, 4,937 ID/local-ID/name/alias/scoped-synonym occurrences and 3,774 normalized values. Four roots searched including ignored and hidden files (excluding .git internals), 142 complete distinct matching contents/977 occurrences freshly read. All inventory identities were screened and normalized exact probes compared. Full 25 selected pinned AIO CLASS nodes and all 92 incident edge occurrences were freshly read. Four closest native records were read in full; definition, identity and claim statements of 18 other selected neighbors were freshly read. This is bounded historical prospective evidence, not future insertion clearance or all-ontology semantic absence.

Examined AIO Candidate	Rejection Reason
`AIO:ArtificialNeuralNetwork`	The algorithms traverse search nodes and maintain cost bounds; their defining mechanisms do not use artificial neurons or learned connection weights.
`AIO:AvailabilityHeuristicBias`	Heuristic cost estimates and additive tolerance are algorithmic control quantities, not the human availability bias of overweighting easily recalled information.
`AIO:DecisionTree`	A search tree of possible paths is not the classification/decision-support model defined by this node and its Classification parent.
`AIO:GraphConvolutionalNetwork`	No graph convolution or neural-layer architecture is part of the source-defined procedures.
`AIO:GraphConvolutionalPolicyNetwork`	The procedures do not learn a graph-generating policy using rewards and adversarial loss; a planning application alone is insufficient.
`AIO:GraphLanguageModel`	The node concerns graph-structured language modeling, not search-tree generation and bound-based traversal.
`AIO:LinearFunction`	Linear storage in depth does not mean an affine activation. Weighted g/h evaluation is a scalar component, not the identity of the complete search algorithm.
`AIO:MachineLearningTask`	The inspected mechanisms search with supplied evaluations and per-search backups. They do not by themselves build a method that learns from data; no specific training relationship is established.
`AIO:MathematicalFunction`	Each algorithm evaluates mathematical quantities but also selects, stores, regenerates and terminates search. Mere arithmetic use is not an exact, hierarchical or sufficiently specific related mapping.
`AIO:MaximumLayer`	Conditional max inheritance is a scalar search-bound rule, not a tensor-merging neural layer.
`AIO:MemoryAugmentedLLM`	Stored branch alternatives or OPEN/TREE are search memory, not an external memory component of an LLM.
`AIO:MemoryCellLayer`	Retained search-node values are not cells or weights of a neural-network layer.
`AIO:MinimumLayer`	Minimum alternatives and backups in a search controller do not identify an element-wise tensor-merging layer.
`AIO:Model`	The algorithm operates on a problem representation; it is not the abstract system representation itself.
`AIO:Network`	An interconnected state graph can be input to a search procedure. That input structure does not make the traversal procedure a network entity.
`AIO:NeuralTuringMachineNetwork`	No feedforward neural architecture, learned pattern matching or neural memory controller is required by these procedures.
`AIO:NeuroSymbolicLLM`	Symbolic search without a neural language model is not a neuro-symbolic LLM.
`AIO:ProbabilisticGraphicalModel`	Search-tree branches and backed-up costs do not encode conditional dependencies among random variables.
`AIO:ReasoningLLM`	Goal-directed heuristic search is not, by itself, deductive inference during language tasks in a large language model.
`AIO:RecursiveLLM`	The definition requires recursive neural language architecture such as TreeLSTM; program recursion or iterative emulation does not establish it.
`AIO:RecursiveLanguageModel`	Its DeepNeuralNetwork and input/memory/output-layer relations concern learned syntactic composition, not recursive bounded search.
`AIO:RecursiveNeuralNetwork`	RBFS recursion and its iterative emulation apply search control, not shared learned weights over structured input.
`AIO:ReinforcementLearning`	Exploring alternative search branches with given costs is not evidence for a learning process balancing exploration and exploitation over trials.
`AIO:TrainingStrategy`	The sources define search-control procedures, not preprocessing or model-training strategies; optional use inside training would require separate evidence.
`AIO:WeightedLayer`	The kth-root variant weights a heuristic scalar; this does not define values applied to neurons or a layer in a network.

Evidence Sources & Primary Literature

1 Source

Source ID	Publication / Document	Type / Access	Reference & Checksum
`hatem2015`	Recursive Best-First Search with Bounded Overhead 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-16T06:52:12Z

Updated: 2026-10-16T06:52:12Z

Source File: data/curated/RBFSEpsilon.yaml