Search behavior of greedy best-first search

Heusner, Manuel. Search behavior of greedy best-first search. 2019, Doctoral Thesis, University of Basel, Faculty of Science.


Official URL: http://edoc.unibas.ch/diss/DissB_13297

Downloads: Statistics Overview


Greedy best-first search (GBFS) is a sibling of A* in the family of best-first state-space search algorithms. While A* is guaranteed to find optimal solutions of search problems, GBFS does not provide any guarantees but typically finds satisficing solutions more quickly than A*. A classical result of optimal best-first search shows that A* with an admissible and consistent heuristic expands every state whose f-value is below the optimal solution cost and no state whose f-value is above the optimal solution cost. Theoretical results of this kind are useful for the analysis of heuristics in different search domains and for the improvement of algorithms. For satisficing algorithms, a similarly clear understanding is currently lacking. We examine the search behavior of GBFS in order to make progress towards such an understanding.
We introduce the concept of high-water mark benches, which separate the search space into areas that are searched by GBFS in sequence. High-water mark benches allow us to exactly determine the set of states that GBFS expands under at least one tie-breaking strategy. We show that benches contain craters. Once GBFS enters a crater, it has to expand every state in the crater before being able to escape.
Benches and craters allow us to characterize the best-case and worst-case behavior of GBFS in given search instances. We show that computing the best-case or worst-case behavior of GBFS is NP-complete in general but can be computed in polynomial time for undirected state spaces.
We present algorithms for extracting the set of states that GBFS potentially expands and for computing the best-case and worst-case behavior. We use the algorithms to analyze GBFS on benchmark tasks from planning competitions under a state-of-the-art heuristic. Experimental results reveal interesting characteristics of the heuristic on the given tasks and demonstrate the importance of tie-breaking in GBFS.
Advisors:Helmert, Malte and Holte, Rudolf
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Heusner, Manuel and Helmert, Malte
Item Type:Thesis
Thesis Subtype:Doctoral Thesis
Thesis no:13297
Thesis status:Complete
Number of Pages:1 Online-Ressource (viii, 129 Seiten)
Identification Number:
edoc DOI:
Last Modified:18 Oct 2019 04:30
Deposited On:17 Oct 2019 12:03

Repository Staff Only: item control page