Best-Case and Worst-Case Behavior of Greedy Best-First Search

Best-Case and Worst-Case Behavior of Greedy Best-First Search

Manuel Heusner, Thomas Keller, Malte Helmert

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1463-1470. https://doi.org/10.24963/ijcai.2018/203

We study the impact of tie-breaking on the behavior of greedy best-first search with a fixed state space and fixed heuristic. We prove that it is NP-complete to determine the number of states that need to be expanded by greedy best-first search in the best case or in the worst case. However, the best- and worst-case behavior can be computed in polynomial time for undirected state spaces. We perform computational experiments on benchmark tasks from the International Planning Competitions that compare the best and worst cases of greedy best-first search to FIFO, LIFO and random tie-breaking. The experiments demonstrate the importance of tie-breaking in greedy best-first search.
Keywords:
Heuristic Search and Game Playing: Heuristic Search