Online Bridged Pruning for Real-Time Search with Arbitrary Lookaheads
Authors: Carlos Hernandez, Adi Botea, Jorge A. Baier, Vadim Bulitko
IJCAI 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | An experimental evaluation shows that our pruning often improves the performance of a base real-time search algorithm by over an order of magnitude. This allows our implemented system to outperform state-of-the-art real-time search algorithms used in the evaluation. 7 Empirical Evaluation |
| Researcher Affiliation | Collaboration | Chilean Center for Semantic Web Research IBM Research, Ireland Pontificia Universidad Cat olica de Chile Universidad Andr es Bello, Chile University of Alberta, Canada |
| Pseudocode | Yes | Algorithm 1: Real-time Heuristic Search Framework; Algorithm 2: PALMA; Algorithm 3: PALMACONNECT |
| Open Source Code | No | No explicit statement about open-source code release or a link to a repository for the described methodology. |
| Open Datasets | Yes | We took maps from the commonly used Moving AI pathfinding repository [Sturtevant, 2012]. |
| Dataset Splits | No | For each map we generated 100 random solvable problems. |
| Hardware Specification | Yes | Experiments are run on a 2.60GHz Intel Core i7 machine under Linux, as a single-threaded process. |
| Software Dependencies | No | We implemented all algorithms in C over a common code base. |
| Experiment Setup | Yes | For both algorithms we use the best parameters as reported in the original publications (w = 8 for w LSS-LRTA* and C = 8 for EDA*). We implemented all algorithms in C over a common code base. For LSS-LRTA* and its variants, we use a binary heap for Open in which ties are broken in favor of larger g-values. We took maps from the commonly used Moving AI pathfinding repository [Sturtevant, 2012]. We used all five 1024 × 1024 Star Craft maps, 30 maze maps of size 512 × 512 (corridor widths of 4, 8, 16), all 512 × 512 maps World of Warcraft III (WC3) and all room maps of size 512 × 512. Finally, as a fifth benchmark, we consider the same maze maps, but with 1% of their obstacles removed. For each map we generated 100 random solvable problems. Each map is modeled as an undirected eight-connected grid, with costs set to 1 for cardinal moves and √2 for diagonal moves. The octile distance is used as a heuristic. By varying the lookahead value (i.e., number of expanded states per episode) LSS (1, 10, 100 and 200). |