Bidirectional search

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

; b : the branching factor of a search tree ; k(n,m) : the cost associated with moving from node n to node m ; g(n) : the cost from the root to the node n ; h(n) : the heuristic estimate of the distance between the node n and the goal ; s : the start state ; t : the goal state (sometimes g , not to be confused with the function) ; d : the current search direction. By convention, d is equal to 1 for the forward direction and 2 for the backward direction ; d' : the opposite search direction (i.e. d' = 3 - d ) ; \mathrm{TREE}_d : the search tree in direction d. If d = 1 , the root is s , if d = 2 , the root is t ; \mathrm{OPEN}_d : the leaves of \mathrm{TREE}_d (sometimes referred to as \mathrm{FRINGE}_d ). It is from this set that a node is chosen for expansion. In bidirectional search, these are sometimes called the search 'frontiers' or 'wavefronts', referring to how they appear when a search is represented graphically. In this metaphor, a 'collision' occurs when, during the expansion phase, a node from one wavefront is found to have successors in the opposing wavefront. ; \mathrm{CLOSED}_d : the non-leaf nodes of \mathrm{TREE}_d . This set contains the nodes already visited by the 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.

References

References

1. (2006-04-05). "Efficient point-to-point shortest path algorithms, COS423 handout". Princeton University.
2. Pohl, Ira. (1971). "Bi-directional Search". Edinburgh University Press.
3. (1977). "An improved bidirectional heuristic search algorithm". [[Journal of the ACM]].
4. de Champeaux, Dennis. (1983). "Bidirectional heuristic search again". [[Journal of the ACM]].
5. Kwa, James B.H.. (1989). "BS∗: An admissible bidirectional staged heuristic search algorithm". Elsevier BV.
6. Kaindl, H.. (1997-12-01). "Bidirectional Heuristic Search Reconsidered". AI Access Foundation.
7. (2004). "A case study of revisiting best-first vs. depth-first search".