Robust Bidirectional Search via Heuristic Improvement

Authors

  • Christopher Wilt University of New Hampshire
  • Wheeler Ruml University of New Hampshire

DOI:

https://doi.org/10.1609/aaai.v27i1.8662

Keywords:

bidirectional search, heuristic improvement

Abstract

Although the heuristic search algorithm A* is well-known to be optimally efficient, this result explicitly assumes forward search. Bidirectional search has long held promise for surpassing A*'s efficiency, and many varieties have been proposed, but it has proven difficult to achieve robust performance across multiple domains in practice. We introduce a simple bidirectional search technique called Incremental KKAdd that judiciously performs backward search to improve the accuracy of the forward heuristic function for any search algorithm. We integrate this technique with A*, assess its theoretical properties, and empirically evaluate its performance across seven benchmark domains. In the best case, it yields a factor of six reduction in node expansions and CPU time compared to A*, and in the worst case, its overhead is provably bounded by a user-supplied parameter, such as 1%. Viewing performance across all domains, it also surpasses previously proposed bidirectional search algorithms. These results indicate that Incremental KKAdd is a robust way to leverage bidirectional search in practice.

Downloads

Published

2013-06-30

How to Cite

Wilt, C., & Ruml, W. (2013). Robust Bidirectional Search via Heuristic Improvement. Proceedings of the AAAI Conference on Artificial Intelligence, 27(1), 954-961. https://doi.org/10.1609/aaai.v27i1.8662