Envelope-Based Approaches to Real-Time Heuristic Search
Authors: Kevin Gall, Bence Cserna, Wheeler Ruml2351-2358
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimental results indicate that intra-envelope search is beneficial in state spaces that are highly interconnected, such as those for grid pathfinding. |
| Researcher Affiliation | Academia | Kevin C. Gall, Bence Cserna, Wheeler Ruml Department of Computer Science University of New Hampshire, USA kcg245@gmail.com, {bence, ruml}@cs.unh.edu |
| Pseudocode | Yes | Algorithm 1: TBA*... Algorithm 2: Intra-Envelope Search (I-ES)... Algorithm 3: Envelope Search Backward Strategy |
| Open Source Code | No | The paper does not explicitly state that the source code for the described methodology is publicly available, nor does it provide a link to a repository. |
| Open Datasets | Yes | We tested variants of TBA* and I-ES on: 1) the 100 15puzzles of Korf (1985) using Manhattan distance (MD); 2) a deterministic version of the racetrack game (Barto, Bradtke, and Singh 1995)...; 3) grid pathfinding using four-way movement and MD in a) the Starcraft cauldron map (Sturtevant 2012) and b) 1500 x 1500 grids with large randomly-generated minima, referred to as the Minima domain (Figure 2 shows example maps). |
| Dataset Splits | No | The paper describes testing on 'test instances' but does not specify explicit dataset splits (e.g., train/validation/test percentages, counts, or cross-validation setup). |
| Hardware Specification | No | The paper mentions 'Each experiment was given 7GB RAM and 5 minutes' but does not specify any particular CPU, GPU, or other detailed hardware components used for the experiments. |
| Software Dependencies | No | The paper does not provide specific version numbers for any software dependencies or libraries used in the implementation of the experiments. |
| Experiment Setup | Yes | The algorithm takes a parameter bound which is a resource limit on the iteration execution time. This limit is split into 2 parts by multiplying by a factor 0 < r1 < 1. In our experimentation we used r1 = 0.8, implying more frontier expansion and less search within the envelope. |