Beam-stack search: integrating backtracking with beam search

We describe a method for transforming beam search into a complete search algorithm that is guaranteed to find an optimal solution. Called beam-stack search, the algorithm uses a new data structure, called a beam stack, that makes it possible to integrate systematic backtracking with beam search. The resulting search algorithm is an anytime algorithm that finds a good, sub-optimal solution quickly, like beam search, and then backtracks and continues to find improved solutions until convergence to an optimal solution. We describe a memory-efficient implementation of beam-stack search, called divide-and-conquer beam-stack search, as well as an iterative-deepening version of the algorithm. The approach is applied to domain-independent STRIPS planning, and computational results show its advantages.