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

• Author / Creator

  Chen, Jingwei

• 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.

• Subjects / Keywords

  • heuristic search
  • bidirectional search
  • suboptimal search
  • search algorithms

• Graduation date

  Fall 2022

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/r3-pmxz-yx43

• License

  This thesis is made available by the University of Alberta Library with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.