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

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

Manuel Heusner, Thomas Keller, Malte Helmert

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Best Sister Conferences. Pages 5269-5273. https://doi.org/10.24963/ijcai.2018/735

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.
Keywords:
Heuristic Search and Game Playing: Heuristic Search