Revisiting the Theory and Practice of Bidirectional and Suboptimal Heuristic Search Algorithms

Abstract

Heuristic Search is a general problem-solving method widely used in artificial intelligence (AI). This thesis presents contributions to heuristic search, including contributions to bidirectional optimal search and unidirectional suboptimal search. For bidirectional optimal search, this thesis presents fundamental theory for the analysis of necessary expansions and the minimum possible number of node expansions needed to solve a given problem in front-to-end heuristic search. A new front-to-end heuristic search algorithm, NBS, which has a worst case guarantee for the number of node expansions, is also presented in this thesis. For unidirectional suboptimal search, this thesis presents the theory of best-first bounded-suboptimal search using priority functions that do not need to perform state re-expansions as long as the search heuristic is consistent. Also, particular priority functions, such as piecewise linear functions are presented in this document. Several new priority functions can significantly outperform existing approaches according to empirical results.