Bidirectional search

Bidirectional search is a graph search algorithm designed to find the shortest path from an initial vertex to a goal vertex in a directed graph by simultaneously conducting two searches, one forward from the start node and one backward from the goal node, terminating when their frontiers intersect. This approach can significantly outperform unidirectional search by exploring fewer nodes, potentially reducing computational complexity from O(b^d) to approximately O(b^d/2) for a tree with branching factor b and goal distance d, making it particularly effective in graphs with high branching factors, such as road networks, game trees, or puzzle-solving domains. For example, Bidirectional A* employs heuristic estimates to guide the forward search toward the goal ($t$) and the backward search toward the start ($s$), while bidirectional Dijkstra’s algorithm uses actual path costs, both aiming to minimize node expansions. Widely applied in navigation systems, artificial intelligence, and scheduling, bidirectional search excels in structured graphs but faces challenges like coordinating searches to meet efficiently and handling asymmetric edge costs, which require precise termination conditions to ensure optimality.

Moreover, bidirectional heuristic search explores a state space from a start state $s$ to a goal state $t$, using two searches to find a sequence of operators that transforms $s$ into $t$. Operators need not be invertible; it suffices to identify, for any node $n$, its parent nodes reachable by valid operators, similar to determining the start of a one-way street from its end in route-finding. For edges with inverse arcs, costs may differ: the forward search uses $k(p,n)$ from parent $p$ to $n$, and the backward search uses $k(n,p)$, supporting graphs with asymmetric costs like road networks. The algorithm terminates when a node appears in both search frontiers, forming an optimal path if the total cost $g_{f}(n)+g_{b}(n)$ is no greater than the minimum cost of unexpanded nodes, ensuring completeness on finite graphs with non-negative weights. Bidirectional Dijkstra’s algorithm, a non-heuristic variant resembling unidirectional Dijkstra’s with $h(n)=0$, excels in navigation by minimizing path costs.

History

When a disc is grown from S only, area covered before contact is made S and G is twice that required when discs are grown from S and G simultaneously- by J.R. Doran, 1966

Although Dijkstra's algorithm (1959) with no heuristics, explores outwards from a single source, its fundamental approach of systematically expanding the set of reached nodes laid the groundwork for later search algorithms like bidirectional search, which independently explores from both the start and goal states.

Bidirectional search was pioneered in 1966 by J.R. Doran and T.A.J. Nicholson, whose independent contributions established its core principles. Doran, at the University of Edinburgh, conducted “doubletree searching” experiments on the Eight- and Fifteen-puzzles using the Graph Traverser program, employing heuristics to guide dual search trees from start and goal. His approach aimed to reduce computational effort but revealed coordination challenges, as misleading heuristics led to excessive node expansions. Despite these limitations, Doran’s work introduced the idea of simultaneous searches meeting in the middle, laying a foundation for heuristic-driven bidirectional methods.

Concurrently, T.A.J. Nicholson (1966) developed a non-heuristic bidirectional algorithm at Harwell for finding shortest routes in networks, such as traffic systems. His method extended paths with the least accumulated distance from both start and goal, alternating searches until a common point formed an optimal route. Nicholson’s algorithm included a termination condition ensuring the path’s cost was no greater than unexpanded alternatives, demonstrating efficiency in practical graph problems. Unlike Doran’s puzzle-focused experiments, it targeted real-world routing, showcasing bidirectional search’s versatility. This dual 1966 origin highlighted the concept’s adaptability across heuristic and non-heuristic domains.

Besides, A* search (1968) introduced heuristics to guide the search towards the goal, the concept of bidirectional search, aiming to improve efficiency by searching from both ends, remained a distinct optimization strategy that could potentially be combined with heuristic search techniques like those used in A*.

In 1969, Ira Pohl advanced bidirectional heuristic search, building on earlier ideas to integrate A*-like heuristics, published in 1971. His approach aimed to improve efficiency by guiding searches toward each other, but it struggled with inefficient frontier convergence, often exploring far more nodes than necessary. Pohl’s implementations, tested on problems like the Fifteen Puzzle, were suboptimal, as the dual trees failed to meet effectively in the solution space. Despite these challenges, his work popularized heuristic bidirectional search, influencing subsequent research. Pohl’s efforts bridged Doran’s heuristic concepts to more formal algorithmic frameworks, setting the stage for later refinements.

Dennis de Champeaux addressed Pohl’s limitations with the Bidirectional Heuristic Front-to-Front Algorithm (BHFFA) in 1977, followed by BHFFA2 in 1983. BHFFA used front-to-front heuristics, estimating costs between opposing search frontiers to better coordinate dual searches. BHFFA2 introduced refined termination conditions, ensuring paths were optimal when the searches met, akin to unidirectional A* guarantees. These algorithms improved efficiency on complex graphs, reducing unnecessary node expansions. De Champeaux’s contributions solidified bidirectional search’s theoretical underpinnings, making it practical for diverse applications.

In the 2000s, Andrew Goldberg and collaborators optimized bidirectional Dijkstra’s algorithm, focusing on termination conditions for large-scale graphs like road networks. Their work ensured the algorithm stopped with an optimal path, minimizing node explorations in navigation systems. Building on Nicholson’s non-heuristic framework, Goldberg’s refinements enhanced computational efficiency for real-world routing. His contributions made bidirectional search a standard tool in practical applications, from GPS to logistics. These advancements underscored the algorithm’s scalability beyond theoretical puzzles.

In 2017, researchers introduced theories of necessary expansions and minimum vertex cover, advancing bidirectional search’s efficiency. The Near-Optimal Bidirectional Search (NBS) algorithm achieved expansions within twice the necessary optimum using vertex cover approximations, effective even with inconsistent heuristics. NBS provides similar guarantees with consistent and front-to-front heuristics, but selecting pairs of nodes to expand in these cases is computationally inefficient. For consistent heuristics, BAE* efficiently leverages this property for high practical performance, while DIBBS, a similar algorithm, was independently developed. These methods optimized node selection across domains like robotics and puzzles. The 2017 theories marked a significant step in refining bidirectional search for modern applications.

Terminology and notation

The following terms and notations are commonly used in the context of search algorithms, particularly bidirectional heuristic search:

• $b$: The branching factor of a search tree, representing the average number of child nodes per node.
• $\mathrm {CLOSED} _{d}$: The set of non-leaf nodes in $\mathrm {TREE} _{d}$, containing nodes already visited or explored by the search in direction $d$.
• $d$: The current search direction. By convention, $d=1$ denotes the forward direction (from start to goal), and $d=2$ denotes the backward direction (from goal to start).
• $d'$: The opposite search direction, defined as $d'=3-d$. For example, if $d=1$, then $d'=2$, and vice versa.
• $g(n)$: The cost of the path from the root node to node $n$ in the search tree.
• $h(n)$: The heuristic estimate of the cost from node $n$ to the goal node, used to guide the search.
• $k(n,m)$: The cost associated with moving from node $n$ to node $m$ in the search tree.
• $\mathrm {OPEN} _{d}$: The set of leaf nodes of $\mathrm {TREE} _{d}$, sometimes called $\mathrm {FRINGE} _{d}$. This set represents the nodes available for expansion in direction $d$. In bidirectional search, these are often referred to as the search "frontiers" or "wavefronts" when visualized graphically. A "collision" occurs when a node from one wavefront has successors in the opposing wavefront during expansion.
• $s$: The start state or initial node of the search.
• $t$: The goal state or target node of the search (sometimes denoted $g$, though not to be confused with the cost function $g(n)$).
• $\mathrm {TREE} _{d}$: The search tree in direction $d$. If $d=1$, the root is $s$ (forward search); if $d=2$, the root is $t$ (backward search).

Approaches for bidirectional heuristic search

Bidirectional heuristic search varies by how it estimates paths, with three main types: Front-to-Front, Front-to-Back, and Perimeter Search.

Front-to-back

Front-to-Back methods estimate the heuristic $h(n)$ for a node $n$ based on the cost to the opposite search’s starting point ($s$ or $t$). BiMAX-BS*F, for example, performs well in puzzles like the Fifteen puzzle.

Front-to-front

Front-to-Front methods calculate $h(n)$ using costs to nodes in the opposite search’s frontier ($\mathrm {OPEN} _{d'}$). The BHFFA algorithm, for instance, picks the smallest estimate.

Perimeter search

Perimeter Search examines a set area around the start or goal, though it’s less widely used.

Example

Bidirectional search can be illustrated with a simple road network of five intersections (A, B, C, D, E), aiming to find the shortest path from A to E. The forward search starts at A, exploring B (cost 2) and C (cost 3), while the backward search begins at E, reaching D (cost 2) and C (cost 4). They meet at C, forming the path A→C→E (cost 7), verified as optimal since no unexpanded path has lower cost. Using Bidirectional A*, a heuristic (e.g., straight-line distance to E or A) prioritizes C, reducing expansions compared to exploring all nodes.

Bidirectional Search Example

Step	Forward Frontier	Backward Frontier	Meeting Node
1	A	E	-
2	B, C	D, C	-
3	C	C	C
4	-	-	A→C→E

State of the Art

Recent bidirectional search advancements focus on scaling to large graphs and optimizing node expansions with modern techniques. The MM algorithm, introduced in 2024, ensures forward and backward searches meet at the solution’s midpoint, using consistent heuristics to avoid expanding beyond the optimal path’s halfway point. In 2021, Consistent-Heuristic Bucket-Based Bidirectional Search (CBBS) grouped nodes by cost estimates, cutting expansions in problems like the pancake puzzle. Front-to-Front GPU Bidirectional Search (FFGBS) uses GPU parallelism for front-to-front heuristics, excelling on large road networks.

Parallel External Memory BAE* (PEM-BAE*) adapts BAE* for distributed systems, outperforming parallel A* on complex graphs. Non-parametric approaches, like enriched NBS variants, adjust strategies dynamically for robustness in robotics and planning. New Bidirectional A* (NBA*) and Time-Dependent Bidirectional A* tackle dynamic graphs, boosting efficiency. Ongoing work on front-to-front heuristics promises further gains, particularly for AI and operations research.

Applications

Bidirectional search is widely used in navigation systems, enabling efficient route planning for GPS and autonomous vehicles. Algorithms like bidirectional Dijkstra’s compute shortest paths in road networks, handling real-time traffic updates with low computational cost. The 2024 MM algorithm ensures searches meet at the path’s midpoint, enhancing long-distance routing for self-driving cars. Front-to-Front GPU Bidirectional Search (FFGBS) leverages parallel processing, speeding up queries in large urban graphs. These methods support dynamic rerouting, critical for modern navigation apps.

In robotics and automated planning, bidirectional search optimizes pathfinding and task scheduling. The 2017 Near-Optimal Bidirectional Search (NBS) reduces node expansions, enabling robots to navigate complex warehouse layouts efficiently. Bidirectional A* with Enhanced efficiency (BAE*) plans real-time, collision-free paths for drones and multi-agent systems. In 2024, Parallel External Memory BAE* (PEM-BAE*) scaled these capabilities for distributed planning, improving logistics scheduling. Consistent-Heuristic Bucket-Based Bidirectional Search (CBBS) streamlines task sequences in supply chains.

Bidirectional search advances puzzle-solving and graph-based artificial intelligence, addressing complex combinatorial and network problems. NBS and Dynamically Improved Bounds Bidirectional Search (DIBBS) solve puzzles like the pancake puzzle and Rubik’s Cube faster than unidirectional methods. CBBS, introduced in 2021, optimizes large state spaces by grouping nodes, enhancing puzzle-solving efficiency. In AI, bidirectional search supports social network analysis and bioinformatics by finding shortest paths or optimizing flows in sparse graphs. Non-parametric NBS variants handle diverse network structures, from protein interactions to recommendation systems.

See Also

• A* search algorithm
• Dijkstra’s algorithm
• Graph traversal
• Breadth-first search

Further reading

• Russell, Stuart J.; Norvig, Peter (2010). "3.4 Uninformed search strategies". Artificial Intelligence: A Modern Approach (3rd ed.). Prentice Hall. ISBN 978-0136042594..