A*+BFHS: A Hybrid Heuristic Search Algorithm

AAAI 2022 pp. 10138-10145

doi:10.1609/AAAI.V36I9.21253 /aaai/2022/bu2022aaai-bfhs/

Abstract

We present a new algorithm called A*+BFHS for solving problems with unit-cost operators where A* and IDA* fail due to memory limitations and/or the existence of many distinct paths between the same pair of nodes. A*+BFHS is based on A* and breadth-first heuristic search (BFHS). A*+BFHS combines advantages from both algorithms, namely A*'s node ordering, BFHS's memory savings, and both algorithms' duplicate detection. On easy problems, A*+BFHS behaves the same as A*. On hard problems, it is slower than A* but saves a large amount of memory. Compared to BFIDA*, A*+BFHS reduces the search time and/or memory requirement by several times on a variety of planning domains.

PDF AAAI Semantic Scholar

Cite

Text

Bu and Korf. "A*+BFHS: A Hybrid Heuristic Search Algorithm." AAAI Conference on Artificial Intelligence, 2022. doi:10.1609/AAAI.V36I9.21253

Markdown

[Bu and Korf. "A*+BFHS: A Hybrid Heuristic Search Algorithm." AAAI Conference on Artificial Intelligence, 2022.](https://mlanthology.org/aaai/2022/bu2022aaai-bfhs/) doi:10.1609/AAAI.V36I9.21253

BibTeX

@inproceedings{bu2022aaai-bfhs,
  title     = {{A*+BFHS: A Hybrid Heuristic Search Algorithm}},
  author    = {Bu, Zhaoxing and Korf, Richard E.},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2022},
  pages     = {10138-10145},
  doi       = {10.1609/AAAI.V36I9.21253},
  url       = {https://mlanthology.org/aaai/2022/bu2022aaai-bfhs/}
}