Rectangle Search: An Anytime Beam Search
Sofia Lemons, Wheeler Ruml, Rob Holte, Carlos Linares Lopez
Abstract
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.
BibTeX
@article{Lemons_Ruml_Holte_Linares Lopez_2024, title={Rectangle Search: An Anytime Beam Search}, volume={38}, url={https://ojs.aaai.org/index.php/AAAI/article/view/30063}, DOI={10.1609/aaai.v38i18.30063}, abstractNote={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.}, number={18}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Lemons, Sofia and Ruml, Wheeler and Holte, Rob and Linares Lopez, Carlos}, year={2024}, month={Mar.}, pages={20751-20758} }