Optimal Any-Angle Pathfinding In Practice
Authors: Daniel Damir Harabor, Alban Grastien, Dindar Öz, Vural Aksakalli
JAIR 2016 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In a range of empirical comparisons we show that Anya is competitive with several recent (sub-optimal) online and pre-processing based techniques and is up to an order of magnitude faster than the most common benchmark algorithm, a grid-based implementation of A*. |
| Researcher Affiliation | Academia | Daniel Harabor EMAIL The University of Melbourne and National ICT Australia, Victoria Laboratory 115 Batman St, Melbourne, 3003, Australia; Alban Grastien EMAIL National ICT Australia, Canberra Laboratory 7 London Circuit, Canberra, 2601, Australia; Dindar Oz EMAIL Yasar University Bornova, Izmir, 35100, Turkey; Vural Aksakalli EMAIL Istanbul Sehir University Altunizade, Istanbul, 34662, Turkey. The work of Daniel Harabor and Alban Grastien is supported by NICTA. NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program. |
| Pseudocode | Yes | Algorithm 1 Computing the successor set |
| Open Source Code | Yes | Source code for our implementation of Anya is available from https://bitbucket.org/dharabor/pathfinding. |
| Open Datasets | Yes | We conduct experiments on seven benchmark problem sets taken from Nathan Sturtevant s well known repository (Sturtevant, 2012). Three of the benchmarks originate from popular computer games and often appear in the literature. They are: Baldur s Gate II , Dragon Age Origins and Star Craft. The maps in these benchmarks vary in size; from several thousand nodes up to several million. The remaining four benchmarks comprise grids of size 512 × 512 with randomly placed obstacles of varying densities, from 10% to 40%. |
| Dataset Splits | No | The paper describes problem sets and instances within benchmarks but does not specify explicit training/test/validation dataset splits. While statistics on node expansions are provided, these do not constitute data partitioning for reproducibility in a training/evaluation context. |
| Hardware Specification | Yes | All experiments are performed on a 3GHz Intel Core i7 machine with 8GB of RAM and running OSX 10.8.4. |
| Software Dependencies | Yes | Anya is implemented in Java and executed on JVM 1.8. To allow for comparisons across different implementation languages we use the A* algorithm (Hart, Nilsson, & Raphael, 1968), implemented in both C++ and Java, as a reference point8. |
| Experiment Setup | Yes | We conduct experiments on seven benchmark problem sets taken from Nathan Sturtevant s well known repository (Sturtevant, 2012). ... We compare our purely online and optimal Anya algorithm with a number of state-of-the-art any-angle techniques. These are: Theta* (Nash et al., 2007), Lazy Theta* (Nash, Koenig, & Tovey, 2010), Field A* (Uras & Koenig, 2015a) and an any-angle variant of two-level Subgoal Graphs (SUB-TL) (Uras & Koenig, 2015b). ... We evaluate performance using three different metrics: search time, nodes expanded and path length. All results are presented relative to a benchmark algorithm, A*, which we combine with a standard octile distance heuristic. |