Bidirectional Search That Is Guaranteed to Meet in the Middle
Authors: Robert Holte, Ariel Felner, Guni Sharon, Nathan Sturtevant
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We also present experimental results that support our theoretical analysis. Overall, our experiments on the Pancake Puzzle and Rubik’s Cube show that the algorithm expanding the fewest nodes could be any one of Uni-HS, MM0 or MM, depending on the heuristic used. We ran MM0, MM, Uni-BS, and A* on 30 random instances for each possible value of C (1 C 11). |
| Researcher Affiliation | Academia | Robert C. Holte Computing Science Dept. University of Alberta Edmonton, Canada T6G 2E8 (rholte@ualberta.ca) Ariel Felner ISE Department Ben-Gurion University Be er-Sheva, Israel (felner@bgu.ac.il) Guni Sharon ISE Department Ben-Gurion University Be er-Sheva, Israel (gunisharon@gmail.com) Nathan R. Sturtevant Computer Science Dept. University of Denver (sturtevant@cs.du.edu) |
| Pseudocode | Yes | Algorithm 1: Pseudocode for MM |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | Yes | The two domains used in our study are the 10-Pancake Puzzle and Rubik’s Cube. We used the GAP heuristic (Helmert 2010) and derived less accurate heuristics from it... We use two heuristics in this study: h888 is the more accurate, using two 8-edge PDBs and the 8-corner PDB. h1997 is the heuristic used to first optimally solve random instances of Rubik’s Cube (Korf 1997). |
| Dataset Splits | No | The paper states "We ran MM0, MM, Uni-BS, and A* on 30 random instances for each possible value of C (1 C 11)" for the Pancake Puzzle and refers to "ten standard test instances (Korf 1997)" for Rubik's Cube. While these are test cases, the paper does not specify distinct training, validation, and test dataset splits or a cross-validation setup. |
| Hardware Specification | No | The paper mentions "two 500GB SSD disks" for the MM implementation's storage of open/closed lists but does not specify CPU, GPU, or other specific hardware models used for computation. For example, "Our MM implementation has priority-based open- and closed-lists stored across two 500GB SSD disks." Computational facilities for some of our experiments were provided by Compute Canada. |
| Software Dependencies | No | The paper mentions using specific heuristics and algorithms (e.g., IDA*), but it does not specify software dependencies with version numbers (e.g., Python 3.8, PyTorch 1.9, CPLEX 12.4). |
| Experiment Setup | Yes | We used the GAP heuristic (Helmert 2010) and derived less accurate heuristics from it, referred to as GAP-X, by not counting the gaps involving any of the X smallest pancakes. For example, GAP-2 does not count the gaps involving pancakes 0 or 1. Our MM0 implementation expands a full g-layer in one direction, and then removes duplicates and checks for a solution. Our MM implementation has priority-based open- and closed-lists stored across two 500GB SSD disks. States with the same priority are found in the same file; before a set of states is expanded, duplicate detection against the closed list is performed. Then, solution detection is performed in parallel to expanding states in the file. |