Scalable Landmark Hub Labeling for Optimal and Bounded Suboptimal Pathfinding
Authors: Sabine Storandt
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In an extensive experimental study, we demonstrate the effectiveness of our methods and illuminate that sensible trade-offs between space consumption, query time, and path quality can be achieved with LHL. We implemented all described algorithms in C++. As benchmarks, we used grid and road networks of different size. |
| Researcher Affiliation | Academia | Sabine Storandt Universit at Konstanz, Germany sabine.storandt@uni-konstanz.de |
| Pseudocode | No | The paper describes algorithms such as 'Tree Select' and the 'k-center algorithm' in paragraph text, but it does not contain structured pseudocode or algorithm blocks with explicit labels like 'Algorithm' or 'Pseudocode'. |
| Open Source Code | No | The paper mentions that the algorithms were implemented in C++ but does not provide any concrete access information such as a repository link or an explicit statement about the code being publicly released. |
| Open Datasets | Yes | For grid networks, we used the Baldurs Gate II game maps from an established 2D pathfinding benchmark [Sturtevant, 2012]. road networks (extracted from Open Street Map1) until n nodes were settled, and used their induced subgraphs. 1https://i11www.iti.kit.edu/resources/roadgraphs.php |
| Dataset Splits | No | The paper references various datasets (Baldurs Gate II game maps, Open Street Map for road networks) but does not provide specific information about how these datasets were partitioned into training, validation, or test sets for reproducibility purposes. |
| Hardware Specification | Yes | Experiments were conducted on a single core of an AMD Ryzen 7 PRO 6850U Processor clocked at 3,2GHz and using up to 32 GB RAM. |
| Software Dependencies | No | The paper states, 'We implemented all described algorithms in C++.', but it does not specify version numbers for C++ or any other ancillary software components, libraries, or solvers used in the experiments. |
| Experiment Setup | Yes | For road networks, we ran Dijkstra s algorithm from randomly selected nodes in the European road network (extracted from Open Street Map1) until n nodes were settled, and used their induced subgraphs. To also have strong landmarks with high ranks, we proceed as follows: We first compute a greedy k-center order as described for bounded suboptimal pathfinding. Then, we take the first 5% of the nodes in this order and assign them the highest ranks. For the remaining nodes, we proceed with the CH-order. Using β =5 kilometers in road networks with n = 106 nodes yielded a center set of size 1,494 and reduced the average label size from 131.7 to 81.5. Choosing α = 1.05, in over 98% of random queries, upper bound path reporting was valid. |