edoc

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
253Kb

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

Downloads: Statistics Overview

Abstract

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
ISBN:978-0-9992411-2-7
ISSN:1045-0823
Note:Publication type according to Uni Basel Research Database: Conference paper
Language:English
Identification Number:
Last Modified:01 Oct 2018 12:04
Deposited On:17 Sep 2018 14:16

Repository Staff Only: item control page