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; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
Tie-Breaking Strategies for Cost-Optimal Best First Search
Authors: Masataro Asai, Alex Fukunaga
JAIR 2017 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We investigate and improve tie-breaking strategies for cost-optimal search using A*. We first experimentally analyze the performance of common tie-breaking strategies that break ties according to the heuristic value of the nodes. We find that the tie-breaking strategy has a significant impact on search algorithm performance when there are 0-cost operators that induce large plateau regions in the search space. Based on this, we develop two new classes of tie-breaking strategies. We first propose a depth diversification strategy which breaks ties according to the distance from the entrance to the plateau, and then show that this new strategy significantly outperforms standard strategies on domains with 0-cost actions. |
| Researcher Affiliation | Academia | Masataro Asai GUICHO2.71828 α GMAIL.COM Alex Fukunaga FUKUNAGA α IDEA.C.U-TOKYO.AC.JP Graduate School of Arts and Sciences The University of Tokyo Japan |
| Pseudocode | Yes | Algorithm 1 Best-First Search Algorithm using OPEN/CLOSED list Algorithm 2 Class Definition of Depth-Diversified Node Selector |
| Open Source Code | No | The paper mentions that "The current implementation of the State-of-the-Art A* based planner Fast Downward (Helmert, 2006)" is used, and it also refers to a heuristic search code library by Burns (2012) at "https://github.com/eaburns/search". However, these are third-party tools/libraries used by the authors, not the open-source code for the methodology described in this specific paper by the authors themselves. There is no explicit statement or link provided by the authors for their own implementation code. |
| Open Datasets | Yes | We used 1104 instances from 35 standard IPC benchmark domains: airport (50 instances), barman-opt11(20), blocks(35), cybersec(19), depot(22), driverlog(20), elevators-opt11(20), floortile-opt11(20), freecell(80), grid(5), gripper(20), hanoi(30), logistics00(28), miconic(150), mprime(35), mystery(30), nomystery-opt11(20), openstacks-opt11(20), parcprinter-opt11(20), parking-opt11(20), pathways(30), pegsol-opt11(20), pipesworld-notankage(50), pipesworld-tankage(50), psr-small(50), rovers(40), scanalyzer-opt11(20), sokoban-opt11(20), storage(30), tidybot-opt11(20), tpp(30), transport-opt11(20), visitall-opt11(20), woodworking-opt11(20), zenotravel(20). |
| Dataset Splits | No | The paper states that it uses instances from standard IPC benchmark domains (e.g., "1104 instances from 35 standard IPC benchmark domains") and introduces "Zerocost domains" also based on standard IPC domains. While the number of instances for each domain is given, there is no explicit mention of how these datasets were split into training, validation, or test sets. The standard IPC domains typically have predefined problem instances, but the paper does not specify how they are used for any potential splits beyond being a collection of problems for evaluation. |
| Hardware Specification | Yes | All experiments were conducted on Xeon E5410@2.33GHz CPUs. |
| Software Dependencies | Yes | In our experiments, all planners are based on Fast Downward, and all experiments are run with a 5-minute, 4GB memory limit for the search binary (FD translation/preprocessing times are not included in the 5-minute limit). We used two State-of-the-Art heuristic functions LMcut (Helmert & Domshlak, 2009) and M&S (Helmert, Haslum, Hoffmann, & Nissim, 2014) as the primary heuristic functions used for calculating f and h. For M&S, we used the bisimulation-based shrink strategy, DFP merge strategy, and exact label reduction. |
| Experiment Setup | Yes | Each experiment is run for 5 minutes excluding SAS translation time, with 4GB memory constraints. We used two State-of-the-Art heuristic functions LMcut (Helmert & Domshlak, 2009) and M&S (Helmert, Haslum, Hoffmann, & Nissim, 2014) as the primary heuristic functions used for calculating f and h. For M&S, we used the bisimulation-based shrink strategy, DFP merge strategy, and exact label reduction. These basic experimental configurations are shared in all performance evaluation experiments throughout this paper. |