A*+BFHS: A Hybrid Heuristic Search Algorithm
Authors: Zhaoxing Bu, Richard E. Korf10138-10145
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Third, we present experimental results on 32 hard instances from 18 International Planning Competition (IPC) domains. On those problems, A*+BFHS is slower than A* but requires significantly less memory. Compared to BFIDA*, an algorithm that requires less memory than A*, A*+BFHS reduces the search time and/or memory requirement by several times, and sometimes by an order of magnitude, on a variety of domains. |
| Researcher Affiliation | Academia | Zhaoxing Bu, Richard E. Korf Computer Science Department University of California, Los Angeles Los Angeles, CA 90095 {zbu, korf}@cs.ucla.edu |
| Pseudocode | No | The paper describes the algorithm in prose and uses a figure to illustrate concepts, but it does not include a formally structured pseudocode or algorithm block. |
| Open Source Code | No | The paper does not provide an explicit statement or link indicating that the source code for the A*+BFHS algorithm developed in this paper is publicly available. |
| Open Datasets | Yes | We solved about 550 problem instances from 32 unit-cost domains. We present the results of A*, BFIDA*, and A*+BFHS on the 32 hardest instances. ... We used the landmark-cut heuristic (LM-cut, Helmert and Domshlak 2009) for the satellite domain, the merge-and-shrink heuristic (M&S) with the recommended configuration (Sievers, Wehrle, and Helmert 2014, 2016; Sievers 2018) for the tpp and hiking14 domains, and the i PDB heuristic with the default configuration (Haslum et al. 2007; Sievers, Ortlieb, and Helmert 2012) for all other domains. |
| Dataset Splits | No | The paper evaluates performance on problem instances from planning domains and does not describe explicit training, validation, or test dataset splits in the context of machine learning. It focuses on solving individual problem instances optimally. |
| Hardware Specification | Yes | All tests were run on a 3.33 GHz Intel Xeon X5680 CPU with 236 GB of RAM. |
| Software Dependencies | Yes | We implemented BFIDA*, A*+IDA*, and A*+BFHS in the planner Fast Downward 20.06 (Helmert 2006) |
| Experiment Setup | Yes | In our experiments, we first generated pattern databases or the merge-and-shrink heuristic, then allocated 1/10 of the remaining memory of 8 GB for the A* phase. ... We used the landmark-cut heuristic (LM-cut, Helmert and Domshlak 2009) for the satellite domain, the merge-and-shrink heuristic (M&S) with the recommended configuration (Sievers, Wehrle, and Helmert 2014, 2016; Sievers 2018) for the tpp and hiking14 domains, and the i PDB heuristic with the default configuration (Haslum et al. 2007; Sievers, Ortlieb, and Helmert 2012) for all other domains. |