Towards a Better Understanding of Bidirectional Search

Henry W. Davis, Randy B. Pollack, Thomas A. SudkampAAAI 1984

Abstract

Bidirectional search, which explores a state space simultaneously from start and goal nodes, offers the potential for significant efficiency gains over unidirectional search. However, practical implementations have historically struggled with the "passing in the night" problem and high computational overhead. This paper introduces the Generalized Pohl (GP) algorithm, a theoretical framework that unifies bidirectional search strategies. We demonstrate that while bidirectional search can exponentially reduce node expansions—particularly when heuristic information is weak—it introduces a "tax" in the form of increased heuristic calculations. We provide formal proofs for admissibility and introduce GP2, a variation that optimizes list processing complexity.

Introduction

In pathfinding, unidirectional A* search expands a frontier until it reaches the goal. Theoretically, bidirectional search should be more efficient: two smaller frontiers meeting in the middle cover a much smaller area than one large frontier. Despite this promise, early bidirectional algorithms faced two major hurdles: the "passing in the night" problem, where frontiers miss each other, and the extreme computational cost of "front-to-front" heuristics.

Theoretical Framework and Notation

To analyze these challenges, we establish a formal notation for bidirectional search components, including node expansion routines and heuristic estimates. This notation is crucial for defining the relationships between forward and backward search fronts.

Notation used for bidirectional search algorithms

The notation distinguishes between the forward search ($s$) and backward search ($t$), denoted by $x$ and its complement $\bar{x}$. Key functions include $g_x(m)$, the cost of the path found so far, and $h_x(m)$, the heuristic estimate of the remaining distance to the target front.

The GP Algorithm

The Generalized Pohl (GP) algorithm provides a flexible framework for bidirectional search. It addresses the overhead problem through the use of "target sets"—specific subsets of nodes on the opposing front used for heuristic calculations. This allows for a balance between heuristic accuracy and computational efficiency.

We distinguish between two primary versions:

  • GP1: A traditional front-to-front approach where heuristics are calculated between all nodes on opposing frontiers.
  • GP2: A novel variation utilizing smaller target sets and a "casual update" procedure. By only updating heuristic values based on newly discovered nodes, GP2 reduces the complexity of list processing from $O(N^3)$ to $O(N^2)$.

Comparative Analysis and Results

Our analysis utilizes a theoretical search space model with a uniform branching factor $b$ and a path of length $K$. We compare GP against unidirectional search (UNI) and a "Cartesian product" algorithm (X) across varying levels of heuristic knowledge.

Summary of complexity and performance comparisons across algorithms and knowledge levels

Key Insights

  1. The Heuristic Trade-off: Bidirectional search reduces the number of nodes expanded ($N$) but increases the number of heuristic calculations ($H$). The total efficiency depends on the relative cost of these operations. As shown in Table 1, GP2 significantly improves upon GP1's complexity.
  2. Performance under Weak Heuristics: When heuristic information is minimal ("No Knowledge"), GP is exponentially more efficient than UNI. Conversely, with "Perfect Knowledge," the advantages of bidirectional search diminish, as seen in Table 2.
  3. Algorithm X: The analysis in Table 3 reveals that Algorithm X, which searches the space of node pairs, is a highly competitive alternative, often outperforming traditional bidirectional approaches in specific complexity metrics.

Conclusion

The GP framework provides a rigorous basis for understanding the trade-offs in bidirectional search. While the computational overhead of front-to-front heuristics is significant, optimizations like those in GP2 make bidirectional search a powerful tool, especially in domains where heuristics are weak. Future work should focus on empirical validation in real-world graphs to further refine target set selection and balance heuristic power with calculation costs.

Summary updated

BibTeX
@inproceedings{davis1984towards,
  author = {Henry W. Davis and Randy B. Pollack and Thomas A. Sudkamp},
  title = {{Towards a Better Understanding of Bidirectional Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}
Figure