  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.
