Position Paper: On the Impact of Direction-Selection in BAE*

Shahaf Shperberg, Lior Siag, Nathan Sturtevant, Ariel FelnerProceedings of the International Symposium on Combinatorial Search 2025 · DOI

Abstract

BAE, and the independently developed DIBBS, are state-of-the-art bidirectional heuristic search algorithms that exploit heuristic consistency to efficiently prove solution optimality. Historically, BAE has been studied with various direction-selection policies, determining whether to expand the next state from the forward or backward search. However, some of these policies expand nodes with an $f$-value exceeding the optimal solution cost, $C^*$, which clearly cannot be part of any optimal solution. In this position paper, we review direction-selection strategies in BAE* and bidirectional search more broadly, analyzing their impact on the behavior of the search. Additionally, we present a low-overhead solution that prevents the expansion of nodes with $f > C^*$ across all direction-selection strategies.

In the world of pathfinding, A* is the gold standard for unidirectional search because it is "optimally efficient"—it never expands a node whose estimated total cost ($f(n)$) exceeds the actual optimal solution cost ($C^*$). However, bidirectional heuristic search (BiHS), which grows search frontiers from both the start and the goal simultaneously, is often faster in practice.

The authors focus on BAE, a leading BiHS algorithm. Unlike A, BAE must decide at every step which frontier to expand. The authors discovered a startling inefficiency: common strategies for making this choice (like simply alternating directions) can force the algorithm to expand nodes that A would have ignored because their $f$-values are too high. In some cases, up to 84% of the work BAE* does is "useless" in the sense that those nodes could never be part of an optimal path.

Comparison of node expansions between A* and BAE*, highlighting the 'black' nodes where $f > C^*$.

Visualizing Inefficiency

The power of visualization was central to this discovery. By using a visualizer from the MovingAI website, the authors observed "black" nodes—states where $f > C^*$—being expanded by BAE that were completely untouched by A. This demonstrates that direction selection is not just a minor implementation detail; it fundamentally dictates which parts of the graph are explored and can lead to significant redundant work.

Methods: The BL-BAE* Solution

The paper analyzes three main direction-selection policies:

  1. Alternating: Swapping between forward and backward search every step.
  2. Pohl’s Cardinality: Expanding from the side with the smaller "Open" list.
  3. Min-b: Expanding the direction that currently has the minimum lower bound ($b$-value).

To solve the inefficiency found in the first two policies, the authors propose BL-BAE (Bi-Level BAE). This approach uses a bi-level data structure for each search direction to decouple pruning from expansion. It utilizes a Waiting Queue to store nodes sorted by their $f$-value and a Ready Queue containing only nodes whose $f$-value is less than or equal to the current lower bound of the search. These are then sorted by $b$-value for expansion.

Example graph and table illustrating the calculation of heuristic values (h), total cost estimates (f), and priority values (b).

By separating nodes into "waiting" and "ready" states, the algorithm ensures that no node with $f(n) > C^*$ is ever expanded, regardless of which direction-selection policy is used. This mimics the efficiency of A* while keeping the speed of bidirectional search.

Key Results and Performance

The authors evaluated their approach on standard benchmarks including the 15-Sliding Tile Puzzle, 16-Pancake Puzzle, and Grid Pathfinding maps from Dragon Age: Origins.

  • Eliminating Redundancy: BL-BAE* successfully eliminated all expansions where $f(n) > C^*$ across all tested domains.
  • Performance Gains: In the Sliding Tile Puzzle, BL-BAE reduced the average number of node expansions by roughly 13–17% compared to standard BAE.
  • Low Overhead: Unlike previous attempts to solve this (like the DBBS algorithm), the Bi-Level structure only adds about a 5% overhead to the processing speed.
  • Domain Sensitivity: The results showed that different policies win in different domains (e.g., Pohl’s is effective for Grids, while Alternating is strong for Pancakes), making the BL-BAE framework valuable because it makes all* policies safer to use.

Conclusion and Future Work

While BL-BAE* eliminates a specific type of useless expansion with minimal overhead, the overall reduction in total nodes expanded varies by domain. The current work assumes consistent heuristics; exploring how these direction-selection policies behave with inconsistent heuristics remains an open question. Future research may involve refining these selection policies further to better predict which direction will lead to the fastest meeting of the two search frontiers.

Summary updated

Abstract

BAE*, and the independently developed DIBBS, are state-of-the-art bidirectional heuristic search algorithms that exploit heuristic consistency to efficiently prove solution optimality. Historically, BAE* has been studied with various direction-selection policies, determining whether to expand the next state from the forward or backward search. However, some of these policies expand nodes with an f-value exceeding the optimal solution cost, C*, which clearly cannot be part of any optimal solution. In this position paper, we review direction-selection strategies in BAE* and bidirectional search more broadly, analyzing their impact on the behavior of the search. Additionally, we present a low-overhead solution that prevents the expansion of nodes with f > C* across all direction-selection strategies.
BibTeX
@inproceedings{shperberg2025position,
  author = {Shahaf Shperberg and Lior Siag and Nathan Sturtevant and Ariel Felner},
  title = {{Position Paper: On the Impact of Direction-Selection in BAE*}},
  booktitle = {Proceedings of the International Symposium on Combinatorial Search},
  year = {2025},
  doi = {10.1609/socs.v18i1.36000},
}
Figure