Robust Bidirectional Search via Heuristic Improvement

Christopher Makoto Wilt, Wheeler RumlAAAI 2013 · DOI

Abstract

Bidirectional search has long promised performance gains over unidirectional A, yet it often suffers from brittleness and high overhead. This paper introduces Incremental KKAdd, a robust bidirectional search algorithm that dynamically improves the forward heuristic using backward search. By interleaving expansions and bounding backward effort, the algorithm achieves up to a 6x speedup over A while maintaining theoretical guarantees against significant performance degradation.

Introduction

While A* is optimally efficient for unidirectional search, bidirectional search—simultaneously searching from start and goal—remains a challenge. Traditional bidirectional methods often fail to meet in the middle efficiently or require manual parameter tuning, such as setting a fixed "perimeter" for backward search. If this perimeter is poorly chosen, performance can plummet.

Incremental KKAdd addresses these issues by integrating backward search directly into the search process. It uses the backward frontier to "correct" the forward heuristic, effectively learning the heuristic error in real-time. This approach ensures robustness, providing significant speedups in many domains without the risk of the "catastrophic failure" (DNF) common in previous bidirectional algorithms.

Methodology

The core of Incremental KKAdd lies in three key mechanisms:

  1. Heuristic Correction: The algorithm identifies the "heuristic error"—the discrepancy between the heuristic estimate and the actual distance to the goal—using information from the backward search. This error is then used to refine the forward heuristic, making the search more targeted.
  2. Dynamic Balancing: Instead of a fixed pre-processing step, forward and backward expansions are interleaved. A user-defined ratio (e.g., 1 backward expansion per 100 forward) bounds the overhead of the backward search.
  3. Adaptive Expansion: An adaptive variant uses linear regression during the search to predict whether forward or backward expansions will yield the greatest progress, automatically adjusting the search strategy.

Theoretically, Incremental KKAdd guarantees that its forward search will never expand a node that standard A would not have expanded, ensuring its worst-case performance is strictly bounded relative to A.

Experimental Evaluation

The authors evaluated Incremental KKAdd across seven diverse benchmarks, including Robot Path Planning, Towers of Hanoi, and the Sliding Tile Puzzle. Performance was measured in terms of CPU time (T), node expansions (E), and nodes generated (H).

Performance comparison of A*, KKAdd, Incremental KKAdd, Perimeter Search, and SBS across multiple domains.

As shown in the results table, Incremental KKAdd consistently outperforms or matches standard A*. In the Robot Path Planning and Towers of Hanoi domains, it achieved a 6x reduction in both time and expansions. Crucially, it avoided the "Did Not Finish" (DNF) results seen with other bidirectional methods like SBS on complex benchmarks. In domains where backward search offered little benefit, such as the Pancake puzzle, the overhead remained minimal and predictable.

Discussion

The primary insight of this work is treating backward search as a "teacher" for the forward heuristic. By quantifying heuristic error, the search becomes more focused. Unlike previous methods that required "pilot experiments" to tune parameters, Incremental KKAdd's interleaving approach makes it practical for general-purpose use.

However, the algorithm is still subject to memory constraints similar to A*. In domains where node expansion is extremely cheap, the computational overhead of heuristic correction (hash table lookups) may occasionally offset the reduction in node expansions. Future work may explore more sophisticated decision-making for expansion interleaving based on heuristic value distributions.

Conclusion

Incremental KKAdd represents a significant step toward making bidirectional search a reliable tool for pathfinding. By providing a robust mechanism for heuristic improvement with bounded overhead, it offers a practical alternative to A* that can deliver substantial speedups across a wide variety of problem domains.

Summary updated

BibTeX
@inproceedings{wilt2013robust,
  author = {Christopher Makoto Wilt and Wheeler Ruml},
  title = {{Robust Bidirectional Search via Heuristic Improvement}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8662},
}
Figure