A*+BFHS: A Hybrid Heuristic Search Algorithm

Authors

  • Zhaoxing Bu UCLA
  • Richard E. Korf UCLA

DOI:

https://doi.org/10.1609/aaai.v36i9.21253

Keywords:

Search And Optimization (SO), Planning, Routing, And Scheduling (PRS)

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.

Downloads

Published

2022-06-28

How to Cite

Bu, Z., & Korf, R. E. (2022). A*+BFHS: A Hybrid Heuristic Search Algorithm. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9), 10138-10145. https://doi.org/10.1609/aaai.v36i9.21253

Issue

Section

AAAI Technical Track on Search and Optimization