Termination Criteria for Bidirectional Search

Question

According to most of the reading I have done, a bidirectional search algorithm is said to terminate when the "forward" and "backward" frontiers first intersect. However, in Section 3.4.6 of Artificial Intelligence: A Modern Approach, Russel and Norvig state:

Bidirectional search is implemented by replacing the goal test with a check to see whether the frontiers of the two searches intersect; if they do, a solution has been found. It is important to realize that the first solution found may not be optimal, even if the two searches are both breadth-first; some additional search is required to make sure there isn't a shortcut across the gap.

I have considered this statement for quite some time, but am unable to find an example of this behavior. Can anyone provide an example graph where the first intersection between the forward and backward frontiers of a bidirectional BFS or A* search is not the shortest path?

Edit: Clearly BFS will not find the shortest path in a weighted graph. It sounds like this excerpt is referring to bidirectional BFS on a undirected graph. Alternatively, I would be interested in seeing a counterexample using bidirectional A* on a weighted graph.

Solution 1

I don't know if this is what Russel and Norvig had in mind, but if the graph is weighted (i.e. some edges are longer than others), the shortest path might have more steps than another which would be found sooner in a BFS. Even if the number of steps is the same, the best might not be found first; consider a graph with six nodes:

(A->B) = (A->C) = 0

(B->D) = 2

(C->E) = 1

(D->F) = (E->F) = 0

After one step forward from A and one step backward from F, the forward frontier is {B,C} and the backward frontier is {D,E}. The searcher now expands B and hey! intersection! (A->B->D->F) = 2. But it should still search a little farther to discover that (A->C->E->F) is better.

Solution 2

I think it has to do with how bidirectional search is implemented.

The pseudocode for BFS goes something like this:

until frontier.empty?
    node <- frontier.pop()
    add node to explored
    for each child not in expored or frontier:
        if child is goal then
            return path
        add child to frontier

Imagine implementing bidirectional search like this:

until frontierForward.emtpy? or frontierBackward.empty?
    node <- frontierForward.pop()
    add node to exploredForward
    for each child not in exporedForward or frontierForward:
        if child in frontierBackward then
            return pathForward + pathBackward
        add child to frontierForward

    Do something similar but now searching backwards

Basically, alternating steps of "forward" BFS and "backwards" BFS. Now imagine a graph like this:

    B-C-D
  /       \
A           E
  \       /
    F - G

The first forward and backward runs of BFS would give us a state like this:

1) expandedForward = A ; frontierForward = B, F
2) expandedBackward = E ; frontierBackward = D, G

Now the algorithm picks the next node to expand from the forward frontier and it picks B.

3) expandedForward = A, B ; frontierForward = F, C

Now we run a backwards BFS and expand node D. D's child, C, is in the forward frontier, so we return the path A - B - C - D - E.

I think this is what Russel and Norvig where referring to. If the implementation doesn't consider this scenario it could give you a solution that's not optimal.

It should finish expanding all the nodes in the frontier that have the same "depth" before deciding it has found an optimal solution. Or maybe alternate the forward and backward BFS searches by layer and not by node (expand forward all nodes in layer 0, expand backward all nodes in layer 0, expand forward all nodes in layer 1, etc.)

Solution 3

In an unweighted (unit cost) graph, bidirectional BFS has found the optimal solution when it hits the intersection, as Russell & Norvig themselves state on page 80 of the 2003 edition of ''AIMA'':

Bidirectional search is implemented by having one or both of the searches check each node before it is expanded to see if it is in the fringe of the other search tree [...] The algorithm is complete and optimal (for uniform step costs) if both searches are breadth-first[.]

(By "expanding a node", R&N mean generating the successors. Emphasis added.)

Solution 4

a simple triangle would satisfy your condition, with the sides being 6,6,10 with the optimal path going through the segment of length 10. In Bi-directional, the algorithm searches the shorter path forward, then reverse would also take the shorter path, they would meet, a complete path is found

but clearly 2 segments of 6 + 6 is worse than one segment of length 10.

View more solutions

Comments

[Joel]

This answer stackoverflow.com/a/35782623/2966723 addresses in detail how this can be done (stepping through the algorithm on an example of this behavior). Short version: it does some extra work to track candidate shortest paths that are upcoming. When the two finally intersect, it can be sure that the candidate shortest path is optimal, but it may not be the path that the algorithm intersected along.

[Michael Koval]

This is definitely true since BFS finds the path of the shortest length instead of the lowest cost, however it is not unique to a bidirectional implementation of BFS. For a weighted graph, I would be interested in finding a counterexample for bidirectional A*. Regardless, +1 for the thoughtful comment.

[Beta]

@Michael Koval: I think the weighted graph I gave works for bidirectional A* (we can increase the A->{} and {}->F weights to 1 to be on the safe side). WLOG we can assume that the search will expand A and F, then B.

[Michael Koval]

You're right...sorry for missing that. It seems that bidirectional A* terminates when the intersection node is expanded, not when the frontiers meet. Thanks for the additional explanation! I am still curious, however, when this could possibly occur in an unweighted graph with BFS.