Search Progress and Potentially Expanded States in Greedy Best-First Search
Abstract
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.
Cite
Text
Heusner et al. "Search Progress and Potentially Expanded States in Greedy Best-First Search." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/735Markdown
[Heusner et al. "Search Progress and Potentially Expanded States in Greedy Best-First Search." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/heusner2018ijcai-search/) doi:10.24963/IJCAI.2018/735BibTeX
@inproceedings{heusner2018ijcai-search,
title = {{Search Progress and Potentially Expanded States in Greedy Best-First Search}},
author = {Heusner, Manuel and Keller, Thomas and Helmert, Malte},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
pages = {5269-5273},
doi = {10.24963/IJCAI.2018/735},
url = {https://mlanthology.org/ijcai/2018/heusner2018ijcai-search/}
}