Beam Search: Faster and Monotonic

Authors

  • Sofia Lemons University of New Hampshire Earlham College
  • Carlos Linares López Universidad Carlos III de Madrid
  • Robert C. Holte University of Alberta Alberta Machine Intelligence Institute (Amii)
  • Wheeler Ruml University of New Hampshire

DOI:

https://doi.org/10.1609/icaps.v32i1.19805

Keywords:

Heuristic Search, Suboptimal Search, Beam Search

Abstract

Beam search is a popular satisficing approach to heuristic search problems that allows one to trade increased computation time for lower solution cost by increasing the beam width parameter. We make two contributions to the study of beam search. First, we show how to make beam search monotonic; that is, we provide a new variant that guarantees nonincreasing solution cost as the beam width is increased. This makes setting the beam parameter much easier. Second, we show how using distance-to-go estimates can allow beam search to find better solutions more quickly in domains with non-uniform costs. Together, these results improve the practical effectiveness of beam search.
ICAPS-22 Proceedings Cover

Downloads

Published

2022-06-13

How to Cite

Lemons, S., Linares López, C., Holte, R. C., & Ruml, W. (2022). Beam Search: Faster and Monotonic. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 222-230. https://doi.org/10.1609/icaps.v32i1.19805

Issue

Vol. 32 (2022): Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling

Section

Main Track