Complete Anytime Beam Search

Beamsearch executes a search method, such as best-first search or depth-first search, but mayabandon nonpromising search avenues in order to reduce complexity. Although it has existed for more than two decades and has been applied to many real-world problems, beamsearch still suffers from the drawback of possible termination with no solution or a solution of unsatisfactory quality. In this paper, wefirst propose a domain-independent heuristic for node pruning, and a method to reduce the possibility that beamsearch will fail. Wethen develop a complete beamsearch algorithm. The new algorithm can not only find an optimal solution, but can also reach better solutions sooner than its underlying search method. We apply complete beam search to the maximum boolean satisfiability and the symmetric and asymmetric Traveling Salesman Problems. Our experimental results show that the domain-independent pruning heuristic is effective and the newalgorithm significantly improvesthe performanceof its underlying search algorithm.

Authors

• Weixiong Zhang The Hong Kong Polytechnic University

Keywords

No keywords are indexed for this paper.