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

Heusner, Manuel and Keller, Thomas and Helmert, Malte. (2018) Best-Case and Worst-Case Behavior of Greedy Best-First Search. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence. pp. 1463-1470.

[img] PDF - Published Version

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

Downloads: Statistics Overview


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.
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:16

Repository Staff Only: item control page