Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
The 2^k Neighborhoods for Grid Path Planning
Authors: Nicolás Rivera, Carlos Hernández, Nicolás Hormazábal, Jorge A Baier
JAIR 2020 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our empirical evaluation shows that, when increasing k, the cost of the solution found improves substantially. Used with the 2k-neighborhood, Canonical A* and JPS, in many configurations, are also superior to the any-angle path planner Theta both in terms of solution quality and runtime. Our planner is competitive with one implementation of the any-angle path planner, ANYA in some configurations. |
| Researcher Affiliation | Academia | Nicol as Rivera EMAIL Computer Laboratory, University of Cambridge, Cambridge, UK Carlos Hern andez EMAIL Nicol as Hormaz abal EMAIL Departamento de Ciencias de la Ingenier ıa, Universidad Andr es Bello, Santiago, Chile Jorge A. Baier EMAIL Departamento de Ciencia de la Computaci on Pontificia Universidad Cat olica de Chile Santiago, Chile |
| Pseudocode | Yes | Algorithm 1: Heuristics for the 8-, 16-, 32-, and 64-neighborhoods... Algorithm 2: A general distance function for N2k... Algorithm 4: JPS successor generator... Algorithm 5: jump function |
| Open Source Code | No | The paper mentions that an implementation of ANYA is available at http://idm-lab.org/anyangle. However, this refers to a third-party implementation used for comparison, not the authors' own implementation of the 2k-neighborhood methodologies described in the paper. There is no explicit statement or link for the authors' own code. |
| Open Datasets | Yes | We use three sets of game maps from the Moving AI repository (Sturtevant, 2012). |
| Dataset Splits | No | The paper mentions using game maps, random maps, and room maps with varying sizes or percentages of blocked cells, but it does not specify any explicit training/validation/test splits, fold-cross validation, or specific sample counts for partitioning the datasets used in the experiments. |
| Hardware Specification | Yes | All experiments were run on a 2.20GHz Intel(R) Xeon(R) CPU Linux machine with 128GB of RAM. |
| Software Dependencies | No | The paper mentions that the algorithms were implemented "on top of Uras and Koenig s implementation of Subgoal graphs (2015)" and refers to "Uras and Koenig," but it does not provide specific version numbers for any software libraries, programming languages, or specialized packages used. |
| Experiment Setup | Yes | The objective of our evaluation was twofold. First, we wanted to investigate the impact on solution quality of using N2k with A*, the most standard heuristic search algorithm, and to compare the obtained solution with those generated by the any-angle path planners ANYA and Theta*. Second, we wanted to investigate the impact that increasing k had on the runtime performance of A*, Canonical A*, and JPS using h2k heuristic and the Euclidean distance. We evaluated seven values for 2k: 8, 16, 32, 64, 128, 256, and 512. |