Best-Case and Worst-Case Behavior of Greedy Best-First Search
Authors: Manuel Heusner, Thomas Keller, Malte Helmert
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 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. |
| Researcher Affiliation | Academia | Manuel Heusner, Thomas Keller and Malte Helmert University of Basel, Switzerland {manuel.heusner,tho.keller,malte.helmert}@unibas.ch |
| Pseudocode | No | The paper describes algorithms verbally and illustrates concepts with figures, but it does not contain any formal pseudocode or algorithm blocks. |
| Open Source Code | No | The paper states 'We implemented all presented algorithms in the Fast Downward planning system [Helmert, 2006]', but it does not provide a link or explicit statement that their specific implementation for this paper is open-source or publicly available. |
| Open Datasets | Yes | We implemented all presented algorithms in the Fast Downward planning system [Helmert, 2006] and performed experiments on the benchmark sets of the 1998 2014 International Planning Competitions (IPC) with the h FF heuristic [Hoffmann and Nebel, 2001] and unit cost. |
| Dataset Splits | No | The paper mentions using 'benchmark sets of the 1998 2014 International Planning Competitions', but it does not specify any training, validation, or test dataset splits. |
| Hardware Specification | No | The paper does not provide any specific hardware details such as CPU/GPU models, memory, or cloud computing instance types used for the experiments. |
| Software Dependencies | No | The paper mentions 'Fast Downward planning system [Helmert, 2006]' and 'h FF heuristic [Hoffmann and Nebel, 2001]', but it does not provide specific version numbers for these software dependencies as used in their experiments. |
| Experiment Setup | Yes | We restricted the benchmark sets to tasks where GBFS search with h FF and FIFO tie-breaking found a plan within 30 minutes and 3.5 GB memory, which has been possible for 2519 instances. For each instance, we computed the reduced state space with step 1 4 of surface graph computation, and determined the relevant properties of the state space topology, i.e., if it is overlap-free (with respect to benches and craters) or not overlap-free but undirected. This was possible for 764 instances from 78 domains within a time limit of 30 minutes and a memory limit of 3.5 GB. |