Rectangle Search: An Anytime Beam Search (Extended Version)
This work addresses the need for efficient anytime search algorithms, particularly for problems with deep local minima, though it appears incremental as it builds on existing beam search methods.
The paper tackles the problem of anytime heuristic search by proposing rectangle search, a new algorithm based on beam search, which is competitive with fixed-width beam search and often outperforms previous best anytime algorithms in experiments on popular benchmarks.
Anytime heuristic search algorithms try to find a (potentially suboptimal) solution as quickly as possible and then work to find better and better solutions until an optimal solution is obtained or time is exhausted. The most widely-known anytime search algorithms are based on best-first search. In this paper, we propose a new algorithm, rectangle search, that is instead based on beam search, a variant of breadth-first search. It repeatedly explores alternatives at all depth levels and is thus best-suited to problems featuring deep local minima. Experiments using a variety of popular search benchmarks suggest that rectangle search is competitive with fixed-width beam search and often performs better than the previous best anytime search algorithms.