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].
Anchor Search: A Unified Framework for Suboptimal Bidirectional Search
Authors: Sepehr Lavasani, Lior Siag, Shahaf S. Shperberg, Ariel Felner, Nathan R. Sturtevant
AAAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experiments evaluate three anchor search instances across diverse domains, outperforming existing methods, particularly as the search scales. ... Experimental results across domains show that the new anchor search algorithms exhibit promising performance, surpassing existing unbounded suboptimal algorithms. ... We broadly compare the performance of anchor search instances with baseline algorithms, including GBFS, BGBFS, DNR with 100 consecutive expansions before retargeting, and two versions of TTBS (TTBS(F) and TTBS(L)) with alternating direction selection policies. The evaluation metrics include state expansions and time, measured on three problem domains: grid pathfinding, the 4 4 sliding tile puzzle (STP), and the 4-peg towers of Hanoi (TOH). While unbounded solution lengths are allowed, we also consider path length as an evaluation metric. |
| Researcher Affiliation | Academia | 1 University of Alberta 2 Ben-Gurion University of the Negev 3Alberta Machine Intelligence Institute (Amii) EMAIL, EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: Anchor Search |
| Open Source Code | Yes | Code https://github.com/nathansttt/hog2/tree/PDBrefactor/papers/Anchor Search |
| Open Datasets | Yes | We experimented on four sets of 8-connected maps from the Moving AI repository (Sturtevant 2012): Dragon Age: Origins (DAO), Starcraft 1 (SC1), Warcraft 3 (WC3), and mazes, with the octile distance as the heuristic. ... Table 4 shows the average expansions, time, and solution length of 100 problems with ith and i+10th Korf s instances (Korf 1985) as the start/goal states and the Manhattan distance (MD) as the heuristic. |
| Dataset Splits | No | The paper describes using existing benchmarks (Moving AI repository for grid pathfinding, Korf's instances for STP) and generating random states for TOH. However, it does not specify explicit training/test/validation splits in the traditional machine learning sense, nor percentages or sample counts for such splits. The problems are referred to as 'instances' rather than 'datasets' with defined splits. |
| Hardware Specification | Yes | TOH and STP experiments were conducted on an Intel Gold 6148 Skylake CPU, 2.4GHz, with 180GB of available memory. For grid pathfinding, an Intel E5-2683 v4 Broadwell CPU, running at 2.1GHz, and featuring 250GB of available memory, was utilized. ... For TOH(30) and TOH(32), we employed larger PDBs with 15 disks and increased the available memory to 700GB. |
| Software Dependencies | No | The paper does not provide specific version numbers for any software dependencies, libraries, or programming languages used in the experiments. It mentions implementation details like using a 'C++ vector' and 'hash table' but no versioned software. |
| Experiment Setup | Yes | We fix k = 10 in our experiments; a study of different values of k is in the appendix. ... In all experiments, we utilized DH PDBs using the start and goal states as the pivots. ... In the first experiment, the PDBs contained a single lookup capturing the five largest disks. ... In the second experiment, ... in three settings: 1. One strong lookup: using a single lookup capturing the 12 largest disks, referred to as PDB(0-11), 2. One strong + one weak lookup: using PDB(0-11) in addition to a lookup capturing the 4 largest remaining disks, referred to as PDB(12-15), 3. Two strong lookups: using PDB(0-11) as well as a lookup capturing all the disks not included in PDB(0-11), referred to as PDB(12). ... In settings with two lookups, we combined the lookups in a weighted additive manner, multiplying PDB(0-11) by 100 to make it the primary guide for the search. |