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.
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.
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