Incremental Beam search

Abstract

Beam search is a heuristic search algorithm that explores a state-space graph by expanding w most promising nodes at each level (depth) of the graph, where w is called the beam-width which is taken as input from the user. The quality of the solution produced by beam search does not always monotonically improve with the increase in beam-width making it difficult to choose an appropriate beam-width for effective use. We present an algorithm called Incremental Beam Search (IncB) which guarantees monotonicity, and is also anytime in nature. Experimental results on the sliding-tile puzzle, the traveling salesman, and the single-machine scheduling problems show that IncB significantly outperforms basic monotonic methods such as iterative widening beam search as well as some of the state-of-the-art anytime heuristic search algorithms in terms of the quality of the solution produced at the end as well as the anytime performance.