Simpler Bounded Suboptimal Search
Authors: Matthew Hatem, Wheeler Ruml
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In an empirical evaluation, we find that SEES matches or outperforms classic bounded suboptimal search algorithms, such as WA , on all domains tested. We also confirm that, while SEES and SA ϵ expand roughly the same number of nodes as their progenitors, they solve problems significantly faster and are much easier to implement. |
| Researcher Affiliation | Academia | Matthew Hatem and Wheeler Ruml Department of Computer Science University of New Hampshire Durham, NH 03824 USA mhatem and ruml at cs.unh.edu |
| Pseudocode | Yes | Figure 2: Pseudo-code for SEES. Ignoring the code in square brackets gives pseudo-code for SA ϵ. |
| Open Source Code | No | The paper states "All algorithms were written in Java and compiled with Open JDK 1.6.0.24" and acknowledges Jordan Thayer and Ethan Burns for "sharing code and experiments", but it does not provide an explicit statement that the authors' own code for the described methodology is open-source or publicly available, nor does it provide a link. |
| Open Datasets | Yes | We evaluated the performance of SA ϵ and SEES on a simple unit-cost domain by comparing them to A ϵ, EES and WA on Korf s 100 15-puzzles [Korf, 1985b] using the Manhattan distance heuristic for both heuristic and distance-to-go estimates. |
| Dataset Splits | No | The paper uses established benchmark instances like "Korf s 100 15-puzzles" and "100 random instances with 14 pancakes" but does not specify any training/validation/test dataset splits. It describes evaluating performance on these problem sets. |
| Hardware Specification | Yes | All experiments were run on a machine with a Core Duo 3.16 GHz processor and 8 GB of RAM running Linux. |
| Software Dependencies | Yes | All algorithms were written in Java and compiled with Open JDK 1.6.0.24. |
| Experiment Setup | Yes | For all experiments, we used path-based single step error correction of the admissible heuristic h to construct a more accurate but potentially inadmissible heuristic bh, as described by Thayer and Ruml [2011]. All algorithms were written in Java and compiled with Open JDK 1.6.0.24. We implemented the optimizations recommended by Burns et al. [2012] and Hatem, Burns, and Ruml [2013] with the exception of bucket based priority queues and C++ templates. ...WA is not able to solve all instances with our timeout of 60 seconds at any suboptimality bound. ...within our memory limit of 8GB or our timeout of 500 seconds |