Understanding the Search Behaviour of Greedy Best-First Search

Heusner, Manuel and Keller, Thomas and Helmert, Malte. (2017) Understanding the Search Behaviour of Greedy Best-First Search. In: Proceedings of the 10th Annual Symposium on Combinatorial Search (SoCS 2017). Palo Alto, California.

[img] PDF - Published Version

Official URL: http://edoc.unibas.ch/55518/

Downloads: Statistics Overview


A classical result in optimal 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. For satisficing search algorithms, a similarly clear understanding is currently lacking. We examine the search behaviour of greedy best-first search (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 a gbfs algorithm in sequence. High-water mark benches allow us to exactly determine the set of states that are not expanded under any gbfs tie-breaking strategy. For the remaining states, we show that some are expanded by all gbfs searches, while others are expanded only if certain conditions are met.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Heusner, Manuel and Keller, Thomas and Helmert, Malte
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
edoc DOI:
Last Modified:01 Oct 2018 12:26
Deposited On:22 Aug 2017 07:44

Repository Staff Only: item control page