Local Minima, Heavy Tails, and Search Effort for GBFS
Authors: Eldan Cohen, J. Christopher Beck
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section we present an empirical analysis of the local minima phenomenon in GBFS. We present results for the FF heuristic [Hoffmann and Nebel, 2001] with deferred ( lazy ) heuristic evaluation [Richter and Helmert, 2009], however experiments with standard ( eager ) evaluation and other heuristics (causal graphs [Helmert, 2004], landmark count [Richter et al., 2008], landmark cut [Helmert and Domshlak, 2009]) yielded similar trends. We use Fast Downward [Helmert, 2006], configured not to re-open nodes. |
| Researcher Affiliation | Academia | Eldan Cohen and J. Christopher Beck Department of Mechanical & Industrial Engineering, University of Toronto, Toronto, Canada {ecohen, jcb}@mie.utoronto.ca |
| Pseudocode | Yes | Algorithm 1 presents pseudocode for a randomized restarting GBFS (RRGBFS). |
| Open Source Code | No | The paper does not provide an explicit statement or link to the open-source code for the methodology described in this paper. |
| Open Datasets | Yes | We use the six benchmark domains in Cohen and Beck [2018], for which the constrainedness of problems can be controlled either by resource-constrainedness parameter (denoted C) or by goal-constrainedness parameter (denoted λ): No Mystery, Rovers, TPP, Maintenance, Parking, and Freecell. |
| Dataset Splits | No | The paper does not explicitly provide training/validation/test dataset splits. It mentions using ensembles of random problems and multiple runs on single instances, but not specific partitioning for training, validation, or testing. |
| Hardware Specification | No | The paper does not explicitly describe the hardware used to run its experiments. |
| Software Dependencies | No | The paper mentions using "Fast Downward [Helmert, 2006]" and "FF heuristic [Hoffmann and Nebel, 2001]" but does not specify exact version numbers for these or any other software dependencies. |
| Experiment Setup | Yes | We use randomized heuristic search with a geometric restart policy [Walsh, 1999] with an initial value of 16, increasing with a factor of 1.5: (16, 24, 36, ...). |