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 non-increasing 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.
