Search Progress and Potentially Expanded States in Greedy Best-First Search

Heusner, Manuel and Keller, Thomas and Helmert, Malte. (2018) Search Progress and Potentially Expanded States in Greedy Best-First Search. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence. pp. 5269-5273.

[img] PDF - Published Version

Official URL: https://edoc.unibas.ch/64995/

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 behavior 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 expanded by at least one GBFS tie-breaking strategy and give us a clearer understanding of search progress.
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:International Joint Conferences on Artificial Intelligence
Note:Publication type according to Uni Basel Research Database: Conference paper
Identification Number:
edoc DOI:
Last Modified:01 Oct 2018 12:04
Deposited On:17 Sep 2018 14:27

Repository Staff Only: item control page