Suboptimal Search with Dynamic Distribution of Suboptimality
Authors: Mohammadreza Hami, Nathan R. Sturtevant
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments show that dynamic policies can consistently outperform existing algorithms across a diverse set of domains, particularly those with dynamic costs. |
| Researcher Affiliation | Academia | 1 University of Alberta 2Alberta Machine Intelligence Institute (Amii) EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: Best-First Search with No Re-expansion |
| Open Source Code | Yes | Code https://github.com/nathansttt/hog2/tree/PDBrefactor/papers/DSWA |
| Open Datasets | Yes | Our study included grid maps from the Moving AI pathfinding repository (Sturtevant 2012) using the octile heuristic. We tested our policies on all maps from the Dragon Age 2 (DA2) game, as well as on all artificial maps such as Random maps and Mazes maps. In the 8-connected grid domains, we used the octile heuristic function. Additionally, we evaluated the standard 100 Korf instances of the Sliding Tile Puzzle (STP) (Korf 1985) using the Manhattan Distance (MD) heuristic. |
| Dataset Splits | No | The paper mentions using "all maps from the Dragon Age 2 (DA2) game," "all artificial maps such as Random maps and Mazes maps," and "standard 100 Korf instances." It also states, "evaluated at most 1000 problems for each map, sampled randomly from all problems." This describes the datasets and problem sampling but does not provide specific training, validation, or test dataset splits. |
| Hardware Specification | Yes | The experiments were run on a cluster with Intel E5-2683 CPUs and our implementation is in C++ in the HOG2 repository. |
| Software Dependencies | No | The paper states, "our implementation is in C++ in the HOG2 repository," but does not specify any version numbers for the C++ compiler or any other ancillary software components, which are required for a reproducible description. |
| Experiment Setup | Yes | Algorithms were executed until they found a solution or expanded 107 nodes. [...] Then, the policy calculates the angle between the new ray and h-axis, and returns wmin+(wmax wmin) (angle/90)i for i = 3 (a tuned parameter). [...] Using the DH with 10 pivots on DW maze maps, both MAP and DWP significantly outperformed other baselines. |