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.
