Artificial Intelligence/Search/Heuristic search/Bidirectional Search

Bidirectional Search

Bidirectional search is an algorithm that uses two searches occurring at the same time to reach a target goal. Bidirectional search generally appears to be an efficient graph search because instead of searching through a large tree, one search is conducted backwards from the goal and one search is conducted forward from the start. The reason that this is faster is because the trees grow exponentially by their depth and therefore two smaller trees have a smaller area than one large tree. Once both searches have been conducted, they will intersect in the middle to finish the path. The section of the search before they meet is called the main phase and after the intersection, it is called the post processing phase.It is important to note that most many bidirectional searches use a heuristic which means that there is no way to confirm whether the solution that is found is the most optimal solution.

The algorithm of a graph search goes through nodes in a graph systematically until an optimal solution is found whereas a heuristic search will only confirm some kind of solution in a short amount of time. The path of a bidirectional search is generally determined based on several different types of other searches which include:

Breadth-first: Adds nodes to a list every time it checks for the goal node using a tree structure until it is reached
Best-first: Will choose which node should be next using the node's score (often an f-value) which takes into account its cost and length
A*: similar to best-first but will take into account the cost of the path from the start to the specified node as well as the cost from that node to the goal

Search Example & Pseudo Code

Road Map:

Figure 1 : Paths from start address and goal address connect to finish the search.

The most effective map search would be bidirectional combined with A*

posA(x, y, f) and posB (x, y, f): Create a position to demonstration where you are at that time in both search trees that will have an x coordinate, y coordinate and an f value to explain the cost of the path

startPoint (coordX, coordY): Begin with a starting node with options for further travel: Also have a list of coordinates with nodes demonstrating movement options towards goal intersection

endPoint (coordX, coordY): Begin with an ending position (node) with several options that lead to it -

Also have a list of coordinates with nodes demonstrating movement options towards start intersection

if posA= posB(x, y): This means intersection so end search

else move posA from startpoint to the next node with the smallest f-valueA && move posB from endPoint to the next node with the smallest f-valueB until the two points intersect

Notes:

Green nodes show the path that should be taken, red node shows hopeful intersection
Thicker lines show higher cost, dotted line shows the separation between posA’s movement and posB’s
f-valueA will take into account the cost from the startpoint to the posA and the cost from posA to posB
f-valueB will take into account the cost from endPoint to posB and the cost from posB to posA

Main problems with bidirectional search

1- Concrete information regarding goal state is necessary

2- Intersection is difficult to guarantee when there are many options

3- Computational storage

Specific models / Solutions to problems

Although bidirectional search seems to be one of the quickest search options, there are many cases that it would not be practical. For example, if you were trying to find a lost item, there would be no way to begin a search from where you are as well as where the item is because you have no information of its location. A scenario that could however use a bidirectional search design is shown in the example above if you were trying to get from one address to another known location.

Des Champeaux (1983) created an algorithm to overcome the intersection problem. The solution was basically to conduct two front to front searches that would ideally aim at each other. This bidirectional heuristic front to front algorithm (BHFFA) however turned out to take up too much space computationally. Another model, designed by Politowisky and Pohl (1984), was created to overcome the problems brought up by Champeaux. This algorithm, called d-Node retargeting, was able to use less computational space as well as find an effective way to meet in the middle. Using the idea suggested from Champeaux’s model, Politowisky and Pohl used a front to front design where the start node's pathway aims at the most promising node of the goal's pathway and vice versa. Unfortunately, more problems arouse with this algorithm because it could only be used for inadmissible heuristics, and even then, the solution was not always clear enough. When a search algorithm is admissible, it means that the search will end in a branch with the lowest cost.

Ghosh and Mehanti (1991) then attempted to solve these problems with the suggestion of yet another front to front heuristic algorithm for bi-directional search. This algorithm used predefined parameters that cut down on computer storage. Their algorithm was a combination of breadth-first and best-first search. The 15-puzzle was chosen to test their algorithm. The 15-puzzle consists of a board of tiles with random numbers placed on them and the search system must go through and place the tiles in order. The results showed that their algorithm was the most successful of the previously mentioned algorithms when judging the quality of solutions.

References

Champeaux, D.D. (1983). Bidirectional heuristic search again. J. ACM 30, 22-32

Davis, H.W., Pollack, R.B., Sudkamp, T. (1984). Towards a better understanding of Bidirectional search. AAAI-84 Proceedings

Ghosh, S., Mahanti, A. (1991). Bidirectional heuristic search with limited resources. Information Processing Letters 40, 335-340.

Pijils, W., Post, H. (2006). A new bidirectional search algorithm with shortened postprocessing. European Journal of Operational Research.

Pohl, I., (1970). Heuristic Search Viewed as a Path Finding in a Graph. Artificial Intelligence 1 193-204.

Pohl, I., Politowiski, G. (1984). D-Node retargeting in bidirectional heuristic search. AAAI-84, 274-277