Analyzing and Improving the Use of the FastMap Embedding in Pathfinding Tasks
Authors: Reza Mashayekhi, Dor Atzmon, Nathan R. Sturtevant
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experimental results give insight into the performance of the A* and MM* algorithms using our improved Fast Map embedding. In A*, our improved embeddings are up two 2x better than the original Fast Map, when measured by average expansions, while there is minimal difference in runtime speed. |
| Researcher Affiliation | Academia | Reza Mashayekhi1, Dor Atzmon3, 4, Nathan R. Sturtevant1, 2 1Department of Computing Science, University of Alberta, Canada 2Alberta Machine Intelligence Institute (Amii) 3Ben Gurion University of the Negev, Israel 4Royal Holloway, University of London |
| Pseudocode | Yes | Algorithm 1 Generalized Metric Embedding, Algorithm 2 SELECTPIVOTS (Farthest) for DH, Algorithm 3 EMBED for DH, Algorithm 4 SELECTPIVOTSED (Embedding Distance) for Fast Map, Algorithm 5 EMBED for Fast Map, Algorithm 6 UPDATECOSTS for Fast Map, Algorithm 7 SELECTPIVOTSHE with Heuristic Error (HE) |
| Open Source Code | Yes | Our implementation is in C++ in the HOG2 repository1. (Footnote 1: https://github.com/nathansttt/hog2/tree/PDBrefactor/papers/FMDH) |
| Open Datasets | Yes | We solve problems on maps from the games Dragon Age: Origins (DAO) and Starcraft (SC1), as well as artificial maps including random maps, room maps, and maze maps... We began this research by attempting to replicate previous published results that claimed Fast Map as an L1 heuristic is competitive with other state-of-the-art heuristics (Cohen et al. 2018). The distribution of node expansions on a single grid map by A* with a 10-dimensional Fast Map embedding (FM10) and DH with 10 heuristics (DH10) is found in Figure 2. This distribution suggests that Fast Map is not competitive. ...on a variety of grid maps from the Moving AI pathfinding repository (Sturtevant 2012) and the standard associated benchmark problems. |
| Dataset Splits | No | The paper uses standard benchmark problem sets but does not explicitly describe training, validation, and test splits (e.g., percentages or counts) within its own experimental methodology. It refers to solving problems on map sets. |
| Hardware Specification | Yes | Our original implementation used somewhat inefficient data structures for storing the heuristic values, which resulted in unstable timing results, likely due to issues such as cache locality. Thus, we re-implemented the algorithms from scratch storing each state s embedding locations adjacently in memory to improve cache locality. We then looked up the heuristic value of every start/goal pair in the benchmark problem sets, and recorded the total time to do this on each map. Then we report the average time per map in microseconds when running on an Apple M1 Pro with 16 GB of RAM on mac OS Monterey version 12.6.1 and with the code compiled with Apple clang version 14.0.0. |
| Software Dependencies | Yes | running on an Apple M1 Pro with 16 GB of RAM on mac OS Monterey version 12.6.1 and with the code compiled with Apple clang version 14.0.0. |
| Experiment Setup | Yes | The Fast Map embeddings used 10 dimensions. We created instances for five agents to meet by taking each set of five consecutive start locations from the standard benchmark problems and using them as starting locations for the agents. The cost metric optimized was Sum of Costs. |