Beam stack search

Beam Stack Search is a search algorithm which integrates backtracking with beam search.

This search algorithm was put forward by Rong Zhou and Eric A. Hansen, Department of Computer Science and Engineering ,Mississippi State University, Mississippi State during the 15th International Conference on Automated Planning and Scheduling , Monterey, CA.

It could be describes as a method for transforming beam search into a complete search algorithm that is guaranteed to find an optimal solution. It 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.

The following web page has the original paper submitted by Zhou and Hansen. http://www.cs.msstate.edu/~hansen/papers/icaps05beam.pdf