Bidirectional search

Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph. It runs two simultaneous searches: one forward from the initial state, and one backward from the goal, stopping when the two meet. The reason for this approach is that in many cases it is faster: for instance, in a simplified model of search problem complexity in which both searches expand a tree with branching factor b, and the distance from start to goal is d, each of the two searches has complexity O(b^d/2) (in Big O notation), and the sum of these two search times is much less than the O(b^d) complexity that would result from a single search from the beginning to the goal.

Andrew Goldberg and others explained the correct termination conditions for the bidirectional version of Dijkstra’s Algorithm.

As with A* search, bidirectional search can be guided by a heuristic estimate of the remaining distance—toward the goal ($t$) in the forward tree and from the start ($s$) in the backward tree — a detailed explanation and example of Bidirectional A* search provided in the example section below.

Ira Pohl was the first one to design and implement a bi-directional heuristic search algorithm. Search trees emanating from the start and goal nodes failed to meet in the middle of the solution space. The BHFFA algorithm of de Champeaux fixed this defect.

A solution found by the uni-directional A* algorithm using an admissible heuristic has a shortest path length; the same property holds for the BHFFA2 bidirectional heuristic version described by de Champeaux . BHFFA2 has, among others, more careful termination conditions than BHFFA.

Description

A Bidirectional Heuristic Search is a state space search from some state $s$ to another state $t$, searching from $s$ to $t$ and from $t$ to $s$ simultaneously. It returns a valid list of operators that if applied to $s$ will give us $t$.

While it may seem as though the operators have to be invertible for the reverse search, it is only necessary to be able to find, given any node $n$, the set of parent nodes of $n$ such that there exists some valid operator from each of the parent nodes to $n$. This has often been likened to a one-way street in the route-finding domain: it is not necessary to be able to travel down both directions, but it is necessary when standing at the end of the street to determine the beginning of the street as a possible route.

Similarly, for those edges that have inverse arcs (i.e. arcs going in both directions) it is not necessary that each direction be of equal cost. The reverse search will always use the inverse cost (i.e. the cost of the arc in the forward direction). More formally, if $n$ is a node with parent $p$, then $k_{1}(p,n)=k_{2}(n,p)$, defined as being the cost from $p$ to $n$.

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 algorithms can be broadly split into three categories: Front-to-Front, Front-to-Back (or Front-to-End), and Perimeter Search. These differ by the function used to calculate the heuristic.

Front-to-back

Front-to-Back algorithms calculate the $h$ value of a node $n$ by using the heuristic estimate between $n$ and the root of the opposite search tree, $s$ or $t$.

Front-to-Back is the most actively researched of the three categories. As of 2004, the current best algorithm (at least in the Fifteen puzzle domain) is the BiMAX-BS*F algorithm.

Front-to-front

Front-to-Front algorithms calculate the h value of a node n by using the heuristic estimate between n and some subset of $\mathrm {OPEN} _{d'}$. The canonical example is that of the BHFFA (bidirectional heuristic front-to-front algorithm), where the h function is defined as the minimum of all heuristic estimates between the current node and the nodes on the opposing front. Or, formally:

$h_{d}(n)=\min _{i}\left\{H(n,o_{i})|o_{i}\in \mathrm {OPEN} _{d'}\right\}$

where $H(n,o)$ returns an admissible (i.e. not overestimating) heuristic estimate of the distance between nodes n and o.

Front-to-Front suffers from being excessively computationally demanding. Every time a node n is put into the open list, its $f=g+h$ value must be calculated. This involves calculating a heuristic estimate from n to every node in the opposing OPEN set, as described above. The OPEN sets increase in size exponentially for all domains with b > 1.

Adding A* to bidirectional search

When combined with A* (Bidirectional A*), the algorithm enhances efficiency by guiding both searches with a heuristic function. In unidirectional A*, the cost function is $f(n)=g(n)+h(n)$, where $g(n)$ is the cost from the start to node $n$, and $h(n)$ is the heuristic estimate to the goal. In Bidirectional A*, the forward search uses $h(n)$ to estimate the cost from $n$ to $t$, while the backward search estimates the cost from $n$ to $s$. This heuristic guidance prioritizes nodes likely to lie on the shortest path, reducing the number of nodes explored compared to basic bidirectional search (e.g., using BFS or Dijkstra’s algorithm). For example, while basic bidirectional search expands nodes based solely on path cost, Bidirectional A* uses $f(n)$ to focus on promising paths, often achieving practical speedups in domains like route planning or puzzle solving.

Bidirectional A* search

Class	Search algorithm, Graph traversal
Data structure	Graph, Priority queue
Worst-case performance	$O(|E|\log |V|)$
Worst-case space complexity	$O(|V|)$

Historical context

The concept of bidirectional search predates A*, with early mentions in the 1960s, but its integration with A* heuristics was formalized later. Ira Pohl pioneered bidirectional heuristic search in the 1970s, though his initial implementation struggled with search trees failing to meet effectively. and its successor, BHFFA2, introduced refined termination conditions. Andrew Goldberg and others later clarified termination for bidirectional Dijkstra’s, while Bidirectional A* emerged as a prominent variant in the 1980s and 1990s, notably refined for applications like robotics and road networks (e.g., Nannicini et al., 2012).

Properties

Like unidirectional A*, Bidirectional A* guarantees an optimal path if the heuristic is admissible and consistent. However, it requires careful termination logic: the algorithm stops when the frontiers meet at a node $n$ such that the total path cost ($g_{f}(n)+g_{b}(n)$) is less than or equal to the minimum $f$-values in both open sets, ensuring no better path exists. This makes it particularly effective in large graphs, balancing efficiency and optimality.

The algorithm terminates when a node is reached by both searches, indicating the frontiers have met. The path is then reconstructed by tracing back through the parent pointers from the meeting point.

Key Features

• Admissibility: If the heuristic is admissible (never overestimates the true cost), Bidirectional A* guarantees an optimal path.
• Consistency: If the heuristic is consistent (satisfies $h(x)\leq d(x,y)+h(y)$), the algorithm avoids re-expanding nodes unnecessarily.
• Efficiency: By searching from both ends, it often explores fewer nodes than unidirectional A*, especially in graphs with high branching factors.

Pseudocode

The following pseudocode describes the bidirectional A* algorithm, using two priority queues and heuristic-guided searches that terminate upon intersection:

function buildPath(cameFromForward, cameFromBackward, meetingNode)
    // Build path from start to meeting node
    pathFromStart := {meetingNode};
    currentNode := meetingNode;
    while currentNode in cameFromForward do
        currentNode := cameFromForward[currentNode];
        pathFromStart.prepend(currentNode);
    end;
    
    // Build path from meeting node to goal
    pathToGoal := {};
    currentNode := meetingNode;
    while currentNode in cameFromBackward do
        currentNode := cameFromBackward[currentNode];
        pathToGoal.append(currentNode);
    end;
    
    return pathFromStart + pathToGoal;
end;

function bidirectionalAStar(graph, startNode, goalNode, heuristic)
    // Priority queues for nodes to explore
    openSetForward := {startNode};
    openSetBackward := {goalNode};
    
    // Track parent nodes for path reconstruction
    cameFromForward := empty map;
    cameFromBackward := empty map;
    
    // Actual costs from start and goal
    costFromStart := map with infinity default, startNode at 0;
    costFromGoal := map with infinity default, goalNode at 0;
    
    // Estimated total costs (cost so far + heuristic)
    totalCostForward := map with infinity default, startNode at heuristic(startNode, goalNode);
    totalCostBackward := map with infinity default, goalNode at heuristic(goalNode, startNode);
    
    // Track best intersection point
    bestIntersection := null;
    minPathCost := infinity;
    
    while (openSetForward is not empty) and (openSetBackward is not empty) do
        // Process forward search
        currentNode := node in openSetForward with lowest totalCostForward;
        if currentNode in costFromGoal then
            totalCost := costFromStart[currentNode] + costFromGoal[currentNode];
            if totalCost < minPathCost then
                bestIntersection := currentNode;
                minPathCost := totalCost;
            end;
        end;
        
        openSetForward.Remove(currentNode);
        for each neighbor of currentNode in graph do
            tentativeCost := costFromStart[currentNode] + graph.distance(currentNode, neighbor);
            if tentativeCost < costFromStart[neighbor] then
                cameFromForward[neighbor] := currentNode;
                costFromStart[neighbor] := tentativeCost;
                totalCostForward[neighbor] := tentativeCost + heuristic(neighbor, goalNode);
                if neighbor not in openSetForward then
                    openSetForward.add(neighbor);
                end;
            end;
        end;
        
        // Process backward search
        currentNode := node in openSetBackward with lowest totalCostBackward;
        if currentNode in costFromStart then
            totalCost := costFromStart[currentNode] + costFromGoal[currentNode];
            if totalCost < minPathCost then
                bestIntersection := currentNode;
                minPathCost := totalCost;
            end;
        end;
        
        openSetBackward.Remove(currentNode);
        for each neighbor of currentNode in graph do
            tentativeCost := costFromGoal[currentNode] + graph.distance(currentNode, neighbor);
            if tentativeCost < costFromGoal[neighbor] then
                cameFromBackward[neighbor] := currentNode;
                costFromGoal[neighbor] := tentativeCost;
                totalCostBackward[neighbor] := tentativeCost + heuristic(neighbor, startNode);
                if neighbor not in openSetBackward then
                    openSetBackward.add(neighbor);
                end;
            end;
        end;
        
        // Check if we’ve found the optimal path
        if bestIntersection is not null then
            minRemainingCost := min(min(totalCostForward), min(totalCostBackward));
            if minPathCost <= minRemainingCost then
                return buildPath(cameFromForward, cameFromBackward, bestIntersection);
            end;
        end;
    end;
    
    return 'no path found';
end;

Illustration

Bidirectional_astar

The GIF demonstrates the algorithm's execution with the following steps:

• Step 1: Node 1 (green → orange) explored forward.
• Step 2: Node 12 (blue → purple) explored backward.
• Step 3: Node 3 (orange) explored forward.
• Step 4: Node 10 (purple) explored backward.
• Step 5: Node 6 (orange) explored forward.
• Step 6: Node 9 (purple) explored backward.
• Step 7: Node 9 (orange) explored forward (meeting point).
• Step 8: Final path (1 → 3 → 6 → 9 → 12) in red.

This illustration highlights the bidirectional nature of the algorithm:

• The forward search (orange) starts at 1 and moves toward 9 (1 → 3 → 6 → 9).
• The backward search (purple) starts at 12 and moves toward 9 (12 → 10 → 9).
• They meet at node 9, simulating the bidirectional process.

Execution Table

Bidirectional A* Execution

Step	Open Set Forward	Open Set Backward	Visited Forward	Visited Backward	Meeting Node
1	{1:0}	{12:0}	{1}	{12}	-
2	{2:3, 3:2}	{9:1, 10:2, 11:4}	{1, 2, 3}	{12, 9, 10, 11}	-
3	{6:7}	{6:3}	{1, 2, 3, 6}	{12, 9, 10, 11, 6}	6
4	{9:9}	-	{1, 2, 3, 6, 9}	{12, 9, 10, 11, 6}	9
5	-	-	Path Found	Path Found	9

Properties

Termination and Completeness

On finite graphs with non-negative edge weights, Bidirectional A* is guaranteed to terminate and is complete if a path exists. On infinite graphs with bounded edge costs, termination requires a solution to exist.

Admissibility

Bidirectional A* is admissible if both forward and backward heuristics are admissible. The meeting point ensures the combined path is optimal when reconstructed correctly.

Optimality and Consistency

With consistent heuristics in both directions, Bidirectional A* is optimally efficient among A*-like bidirectional algorithms, expanding a subset of nodes compared to alternatives. Inconsistent heuristics may lead to suboptimal paths unless corrected.

Complexity

• Time Complexity: $O(b^{d})$ in the worst case, where $b$ is the branching factor and $d$ is the solution depth. The bidirectional approach often reduces $d$ effectively.
• Space Complexity: $O(b^{d})$, as it stores nodes in both forward and backward open sets.

Applications

Bidirectional A* is widely used in:

• GPS Navigation: Efficiently finds routes in road networks.
• Video Games: Optimizes AI pathfinding in large maps.
• Robotics: Plans motion in dynamic environments.

Relations to Other Algorithms

• Dijkstra's algorithm: A special case of Bidirectional A* with $h(n)=0$ in both directions.

Variants

• New Bidirectional A* (NBA*): Enhances efficiency with adaptive heuristics.
• Time-Dependent Bidirectional A*: Adapts to dynamic graphs (e.g., traffic).

See Also

• A* search algorithm
• Dijkstra's algorithm
• Graph traversal

Notes

• The heuristic for the backward search must estimate the cost to the start node, which may differ from the forward heuristic unless the graph is symmetric.
• The stopping criterion requires careful design to ensure optimality, often using a condition like $f_{f}+f_{b}\geq \mu$, where $\mu$ is the shortest path cost.

Further reading

• Russell, Stuart J.; Norvig, Peter (2002). "3.4 Uninformed search strategies". Artificial Intelligence: A Modern Approach (2nd ed.). Prentice Hall..