Beam-Stack Search: Integrating Backtracking with Beam Search

Rong Zhou and Eric A. Hansen

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.