A*+BFHS: A Hybrid Heuristic Search Algorithm

Zhaoxing Bu, Richard E. KorfAAAI 2022 · DOI

Abstract

A+BFHS is a hybrid search algorithm designed to overcome the memory limitations of A while avoiding the redundant work of iterative deepening methods like IDA. By combining A's optimal node ordering with the memory efficiency of Breadth-First Heuristic Search (BFHS), it solves large-scale planning problems that are otherwise intractable. Experimental results across various International Planning Competition domains demonstrate that A*+BFHS significantly reduces memory usage while maintaining competitive search speeds.

Introduction

In automated planning and pathfinding, researchers often face a trade-off between optimality, speed, and memory. Standard A is fast and optimal but suffers from exponential space requirements, often exhausting available RAM on complex problems. Conversely, Iterative Deepening A (IDA) is memory-efficient but performs poorly on "diamond-shaped" graphs due to the lack of a closed list, leading to redundant state re-searches. Breadth-First Heuristic Search (BFHS) offers better memory management than A but lacks efficient node ordering, often expanding nearly all nodes at the final cost level.

A*+BFHS bridges this gap, providing an algorithm that handles duplicate paths effectively while operating within strict memory constraints.

Methodology

The A*+BFHS algorithm operates in two distinct phases:

  1. Phase 1: The A* Sprint: The algorithm executes standard A* until a pre-defined memory threshold is reached (e.g., 90% of RAM). The remaining "Open" list is then treated as a search frontier.
  2. Phase 2: The BFHS Siege: Instead of terminating, the algorithm initiates BFHS iterations starting from the frontier nodes.

The core innovation is Deepest-First Ordering. Standard BFHS is typically indifferent to which frontier nodes are most promising. A*+BFHS partitions the frontier by depth and prioritizes BFHS calls on the deepest nodes. This strategy increases the likelihood of finding a goal early and terminating the search before shallower, more numerous parts of the frontier are expanded.

A*+BFHS search tree illustrating the deepest-first frontier ordering strategy.

A variant, A*+BFHS(4), groups frontier nodes from four adjacent depths into a single BFHS call to reduce the overhead of re-generating duplicate nodes, balancing surgical early termination with search efficiency.

Experimental Evaluation

The algorithm was evaluated using 32 hard instances from 18 International Planning Competition (IPC) domains, including Logistics, Depot, Snake, Tidybot, and Parking. Tests were conducted using the Fast Downward planning framework, comparing A+BFHS against A, BFIDA, and A+IDA*.

Results and Discussion

The experimental results demonstrate that A*+BFHS significantly extends the reach of heuristic search under memory pressure.

Detailed performance comparison of A*, BFIDA*, and A*+BFHS across various IPC domains.

Key Findings:

  • Scalability: A+BFHS solved 22 instances that A could not solve within an 8GB memory limit. For problems A could solve, A+BFHS used 5-10x less memory, albeit with increased search time.
  • Efficiency vs. BFIDA*: A+BFHS outperformed BFIDA in 27 out of 32 instances, often being twice as fast and using half the memory. In the logistics00 domain, it achieved an order-of-magnitude speedup.
  • Last Iteration Performance: On 28 of 32 instances, the deepest-first ordering led to significantly fewer node generations in the final iteration compared to competitors.

Conclusion

A*+BFHS proves that node ordering remains critical even when memory is exhausted. By maintaining "best-first" pressure through depth-sorted frontiers, the algorithm avoids the massive breadth-first expansions typical of other memory-limited searches. Future work includes extending the algorithm to non-unit cost domains and exploring external memory for even larger frontiers.

Summary updated

BibTeX
@inproceedings{bu2022bfhs,
  author = {Zhaoxing Bu and Richard E. Korf},
  title = {{A*+BFHS: A Hybrid Heuristic Search Algorithm}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i9.21253},
}
Figure