# Rectangle Search: An Anytime Beam Search (Extended Version)

arXiv: https://arxiv.org/abs/2312.12554 · HTML: https://mlsanity.com/paper/2312.12554/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 30 references that are in the map.
- First posted on arXiv 19 Dec 2023.

## Abstract (arXiv)

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.