Simpler Bounded Suboptimal Search

Matthew Hatem, Wheeler RumlAAAI 2014 · DOI

Abstract

State-of-the-art search algorithms like Explicit Estimation Search (EES) are powerful but computationally expensive due to the overhead of managing multiple synchronized priority queues. This paper introduces SEES and SA*ε, simplified versions that replace complex data structures with an iterative deepening approach. These algorithms are significantly easier to implement and up to 2.5x faster in practice while matching or exceeding the performance of their more complex predecessors.

Introduction

In heuristic search, $A^*$ is the standard for finding optimal paths, but its resource requirements often make it impractical for large state spaces. Bounded suboptimal search algorithms, such as Weighted $A^*$, address this by finding solutions within a user-defined factor ($w$) of the optimal cost. Recent advancements like EES incorporate additional information—distance-to-go estimates and inadmissible heuristics—to improve search efficiency. However, the implementation of EES requires maintaining and synchronizing three separate priority queues, leading to significant "per-node overhead" that can negate the benefits of reduced node expansions.

The Overhead of Complexity

The primary bottleneck in modern search research is often the "overhead tax." An algorithm that expands fewer nodes but takes significantly longer to process each node may result in a net loss in total execution time. EES's reliance on synchronized focal lists (often implemented as red-black trees) creates a nightmare for implementation and maintenance. Furthermore, the rapid changes in the focal list can cause "thrashing," where the search frontier fluctuates inconsistently.

Simplified Search: SA*ε and SEES

The authors propose a "simpler is better" philosophy, replacing dynamic focal lists with Iterative Deepening.

  • SAε (Simplified Aε): Instead of a dynamic focal list, it uses a fixed cost threshold ($t_f$). It performs a "Speedy Search" (prioritizing nodes with the lowest distance-to-go) and prunes nodes exceeding the threshold. If no goal is found, the threshold is increased for the next iteration.
  • SEES (Simplified EES): This extends SA*ε by adding a second threshold based on an inadmissible heuristic ($\hat{f}$), ensuring nodes satisfy both admissible and inadmissible bounds.

By utilizing iterative deepening, these algorithms require only one priority queue at any given time, eliminating the need for complex synchronization logic.

Experimental Evaluation

The algorithms were evaluated on four classic benchmarks: the 15-Puzzle (Unit and Inverse costs), the Heavy Pancake Puzzle, and the Heavy Vacuum World. These domains test the algorithms against varying edge costs and heuristic accuracies.

Performance comparison of SEES and SA*ε against state-of-the-art algorithms. The plots show that SEES often achieves lower CPU time despite similar or slightly higher expansion counts compared to EES.

Results and Analysis

The experimental results demonstrate that SEES and SA*ε are highly effective. In the 15-puzzle, SEES was approximately 2.5 times faster per node expansion than EES. In the "Inverse Tiles" domain, where Weighted $A^*$ failed to solve any instances within the time limit, SEES provided solutions in less than a second.

Beyond raw speed, the reduction in implementation complexity is a major contribution. Using McCabe’s Cyclomatic Complexity, the authors showed that SEES is substantially simpler than EES.

Comparison of implementation complexity. SEES shows a significant reduction in both Cyclomatic Complexity (CC) and Lines of Code (LoC) compared to EES.

Conclusion

SEES and SA*ε represent a shift toward practical, maintainable search algorithms. While iterative deepening introduces some re-expansion waste, this is largely offset by the reduction in per-node overhead. Future work may explore integrating "Fringe Search" techniques to eliminate re-expansions or developing optimistic variants for domains with highly accurate heuristics.

Summary updated

BibTeX
@inproceedings{hatem2014simpler,
  author = {Matthew Hatem and Wheeler Ruml},
  title = {{Simpler Bounded Suboptimal Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.8846},
}
Figure