Understanding Subgoal Graphs by Augmenting Contraction Hierarchies
Authors: Tansel Uras, Sven Koenig
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We propose three different modiļ¬cations, analyze their runtime/memory trade-offs, and provide experimental results on grids using canonical-freespace-reachability as R, which show that both N-level subgoal graphs and contraction hierarchies are dominated in terms of the runtime/memory trade-off by some of our new variants. |
| Researcher Affiliation | Academia | Tansel Uras and Sven Koenig Department of Computer Science, University of Southern California, Los Angeles, USA {turas, skoenig}@usc.edu |
| Pseudocode | No | The paper describes algorithms and their modifications in prose but does not include any explicitly labeled pseudocode or algorithm blocks. |
| Open Source Code | Yes | The source code is available at http://idm-lab.org/sg-ch. |
| Open Datasets | Yes | We used Nathan Sturtevant s publicly available 8-neighbor grid benchmarks [Sturtevant, 2012], which has four types of maps, each with several subtypes: Game maps with maps from different games, maze maps with varying corridor widths, room maps with varying room dimensions, and random maps with varying percentages of blocked cells. |
| Dataset Splits | No | The paper mentions using publicly available grid benchmarks but does not specify how these benchmarks are split into training, validation, or test sets, or if any such splits are predefined within the benchmarks. |
| Hardware Specification | Yes | We ran our experiments on a PC with a 3.6GHz Intel Core i7-7700 CPU and 32GB of RAM. |
| Software Dependencies | No | The paper states 'We implemented all our algorithms from scratch in a single framework' but does not list specific software dependencies with version numbers (e.g., programming languages, libraries, or compilers). |
| Experiment Setup | Yes | All searches use the Octile distance heuristic and a binary heap as priority queue. In all hierarchies, downward edges are discarded. Our implementation follows the implementation of the CH entry in the GPPC with respect to the online node ordering for contractions and using stall-on-demand for searches. We have replaced unpacking using midpoints with unpacking using pointers to the bridged edges and replaced the bidirectional Dijkstra searches with bidirectional A* searches. |