Abstract
Bidirectional heuristic search (Bi-HS) has historically faced challenges in consistently outperforming unidirectional A*. This research presents a unifying framework for Bi-HS that utilizes "individual bounds" to identify nodes that cannot belong to an optimal solution at the current cost level. By generalizing techniques for measuring heuristic inaccuracies, the authors introduce two new algorithms, DBS and DBBS. These methods demonstrate a reduction in node expansions by up to an order of magnitude compared to previous state-of-the-art algorithms like NBS across classic AI benchmarks.
Introduction
Searching simultaneously from a start and a goal—bidirectional heuristic search—is a promising approach that often fails to exploit heuristic inaccuracies effectively. While recent "near-optimal" algorithms like NBS provide theoretical guarantees, they typically rely on consistent heuristics providing a lower bound on remaining cost. However, as search progresses, the actual path costs ($g$-values) from the opposite direction can reveal the extent of heuristic underestimation. This paper unifies historical approaches to measuring these inaccuracies into a rigorous lower-bound framework.
Methodology: Individual Bounds and Heuristic Inaccuracies
The proposed framework centers on Individual Bounds and Relative Minimum Node Values. Modern Bi-HS algorithms maintain a lower bound $C$ on the optimal solution cost, aiming to raise $C$ until it meets the cost of the best solution found ($U$).
A node is classified as "delayed" if it can be proven that no solution of cost $C$ passes through it. Only "expandable" nodes contribute to calculating the minimum values for the next search layer. The framework integrates two primary types of bounds:
- KK Bounds: Utilize $d$-values ($d(n) = g(n) - h_{opposite}(n)$) to measure local heuristic inaccuracy.
- b-Bounds: Aggregate estimates from both directions into a single bidirectional estimate ($b(n) = f(n) + d(n)$).
Because delaying a node affects the minimum values of the open list—which may in turn delay further nodes—the algorithm employs a "fixpoint" calculation to determine the tightest possible bounds for each layer. This logic is implemented in two new algorithms: DBS (d-using Bidirectional Search) and DBBS (d and b using Bidirectional Search).
Experimental Evaluation
The algorithms were tested on standard AI benchmarks, including the 14-Pancake Puzzle, 12-disk 4-peg Towers of Hanoi (ToH-12), the 15-Sliding Tile Puzzle, and grid-based pathfinding maps.
The results indicate significant efficiency gains. In the ToH-12 (10+2) configuration, DBBS expanded approximately 70k nodes, a substantial improvement over the 233k required by NBS. Even more dramatic results were seen in the 15-Puzzle, where the new variants improved upon NBS by three orders of magnitude. Notably, these algorithms often expand fewer than half of the nodes previously considered "necessarily-expanded" by theoretical models, effectively breaking the established "floor" for node expansions in optimal search.
Discussion and Conclusion
The primary contribution of this work is the theoretical unification of disparate approaches to heuristic inaccuracy. The paper demonstrates that the methods of Kaindl & Kainz (KK) and Sadhukhan (BAE*) are complementary tools within a single lower-bound logic. By focusing on "expandable" nodes rather than the entire open list, the global lower bound $C$ can be raised much faster.
While the fixpoint computation introduces some overhead, the massive reduction in node expansions typically leads to faster total search times, particularly in domains where node expansion is costly. Future work remains in optimizing the handling of the "last layer" of search and refining the theoretical definition of "must-expand pairs" to account for these tighter individual bounds.
Summary updated