Recursive Best-First Search with Bounded Overhead

Matthew Hatem, Scott Kiesel, Wheeler RumlAAAI 2015 · DOI

Introduction

Heuristic search is a fundamental component of AI planning, yet it faces a persistent trade-off between memory and time. While standard best-first searches like A are computationally efficient, their exponential memory consumption often leads to failure on large-scale problems. Linear-space alternatives, such as Iterative Deepening A (IDA*) and Recursive Best-First Search (RBFS), address this by using memory proportional only to the search depth.

However, RBFS has historically suffered from a significant drawback: to maintain its best-first order within strict memory limits, it frequently backtracks and discards subtrees, only to regenerate them later. In domains with non-uniform action costs—such as real-valued weights or square-root costs—this "forgetting" behavior can cause node re-expansions to explode. This increases the algorithm's complexity from linear $O(N)$ to quadratic $O(N^2)$, making standard RBFS unreliable for many real-world applications where operator costs are not uniform.

Controlled Reexpansion: The $RBFS_{CR}$ Algorithm

To address the overhead issues of RBFS, this research introduces $RBFS_{CR}$ (Controlled Reexpansion). This algorithm is the first best-first search that is both memory-efficient and theoretically guaranteed to have bounded overhead.

The primary innovation in $RBFS_{CR}$ is a novel histogram-based technique used to manage node re-expansions. Unlike previous global approaches, $RBFS_{CR}$ maintains local histograms along the current search path to track the distribution of $f$-values (estimated total costs) of pruned nodes. When the algorithm backtracks, it uses these histograms to select a new cost threshold that ensures geometric growth in the number of nodes expanded. By guaranteeing that each subsequent visit to a subtree expands at least twice as many nodes as the previous visit, $RBFS_{CR}$ ensures that the total number of expansions remains $O(N)$.

The authors also explored simpler "slack" methods like $RBFS_\epsilon$, which allow the algorithm to stay in a subtree longer by slightly relaxing cost bounds. While effective for suboptimal search, these lack the rigorous theoretical guarantees provided by $RBFS_{CR}$.

Experimental Evaluation

The performance of $RBFS_{CR}$ was evaluated against several benchmarks designed to test varying costs:

  • 15-Puzzle: Evaluated with unit costs and "square root" costs (where moving tile $n$ costs $\sqrt{n}$).
  • 25-Pancake Puzzle: Tested with square root costs to create a wide range of $f$-values.
  • Dockyard Robot Planning: A complex domain with real-valued costs and numerous duplicate states, testing the algorithm's robustness in graph-like search spaces.

Key Results and Anytime Performance

A critical advantage of RBFS over IDA is its behavior as an anytime algorithm. While IDA behaves like a depth-first search when costs are non-monotonic, RBFS maintains a best-first order, allowing it to find decent solutions quickly and improve them over time.

Anytime performance comparison of RBFS-cr and RBFS across different puzzle domains.

As shown in the figures above, $RBFS_{CR}$ consistently outperforms standard RBFS in domains with non-unit costs. In the 15-Puzzle and 25-Pancake benchmarks with square root costs, standard RBFS often "flatlines," failing to improve solution quality significantly over time due to excessive re-expansions. In contrast, $RBFS_{CR}$ finds higher-quality solutions much faster, demonstrating its robustness to varying costs.

Performance metrics comparing IDA*CR and RBFS variants.

In terms of raw efficiency, $RBFS_{CR}$ demonstrates superior node management. In the Dockyard Robot domain, while IDA* might have a higher per-node expansion rate, it often expands an order of magnitude more nodes than $RBFS_{CR}$ because it cannot maintain an efficient best-first order. The table above highlights how $RBFS_{CR}$ balances expansion counts and time, often solving instances that cause other linear-space algorithms to struggle. Specifically, $RBFS_{CR}$ expanded roughly 10 times fewer nodes than $IDA^*_{CR}$ in these tests.

Insights and Limitations

The "aha moment" for $RBFS_{CR}$ is the realization that perfect cost thresholds are unnecessary; one only needs to ensure that every revisit to a subtree performs significantly more work than the last. This "doubling trick" effectively tames the $O(N^2)$ complexity nightmare.

However, $RBFS_{CR}$ is not without limitations. RBFS-based algorithms are more complex to implement and carry a higher per-node overhead because they require sorting child nodes at every expansion. Additionally, like all linear-space algorithms, $RBFS_{CR}$ can struggle with duplicate states in graph search spaces, though transposition tables can mitigate this. Future work may further explore the interaction between these tables and the $O(N)$ expansion bound.

Conclusion

$RBFS_{CR}$ represents a significant step forward in heuristic search, providing a robust, linear-space algorithm that handles varying action costs without the prohibitive overhead of standard RBFS. Its ability to maintain a best-first order while guaranteeing bounded re-expansions makes it a powerful tool for anytime search in complex, large-scale AI planning problems.

Summary updated

BibTeX
@inproceedings{hatem2015recursive,
  author = {Matthew Hatem and Scott Kiesel and Wheeler Ruml},
  title = {{Recursive Best-First Search with Bounded Overhead}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9352},
}
Figure