A*+BFHS: A Hybrid Heuristic Search Algorithm
This work addresses memory and efficiency issues in heuristic search algorithms for planning problems, representing an incremental improvement over existing methods.
The authors tackled the problem of memory limitations and duplicate paths in heuristic search by introducing A*+BFHS, a hybrid algorithm that combines A* and breadth-first heuristic search, resulting in reduced search time and memory usage by several times compared to BFIDA* in planning domains.
We present a new algorithm 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.