How to construct the found path in bidirectional search

Question

I am trying to implement bidirectional search in a graph. I am using two breadth first searches from the start node and the goal node. The states that have been checked are stored in two hash tables (closed lists). How can I get the solution (path from the start to the goal), when I find that a state that is checked by one of the searches is in the closed list of the other?

EDIT

Here are the explanations from the book: "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; if so, a solution has been found... Checking a node for membership in the other search tree can be done in constant time with a hash table..."

Some pages before: "A node is a boolkkeeping data structure used to represent the search tree. A state corresponds to a configuration of the world... two different nodes can contain the same world state, if that state is generated via two different search paths." So from that I conclude that if nodes are kept in the hash tables than a node from the BFS started from the start node would not match a node constructed from the other BFS started from the goal node.

And later in general Graph search algorithm the states are stored in the closed list, not the nodes, but it seems to me that even that the states are saved in the hash tables after that the nodes are retrieved from there.

Answer 1

Let me give this question a try. I am not sure I do fully understand it so I was considering to post a comment but in the end, I preferred to try an explanation. Hope it helps!

Raphael already suggested a solution (so I voted up his comment) which works even if you only store states instead of nodes. To make it clear:

• states: those in the original problem. These are unique
• nodes: those enumerated by your search algorithm (bidirectional breadth-first search in your case). As stated in your book "two different nodes can contain the same world state, if that state is generated via two different search paths" so that it is very likely to have more nodes than states (since the former distinguish states by the different paths ---which can be exponentially large--- that lead to the same state).

Obviously, the path from the start state $s$ to the target $t$ is computed by concatenating the paths from $s$ to $n$ and from $n$ to $t$ where $n$ is the node that was found in the hash table of the opposite search.

Now, assuming you are using a consistent-heuristic function (a heuristic function $h (n)$ is said to be consistent if and only if it satisfies the triangular inequality $h(n) \leq c(n,m) + h(m)$ where $c(n,m)$ is the cost of the operator from node $n$ to one of its offsprings $m$) or no heuristic function at all (so that your BFS is a blind search) let me suggest the following procedure:

Let me assume wlg that $n$ was generated by the forward search (i.e., from the start state $s$) and that it was found in the hash table of the backward search (i.e., the one issued from the goal node). In this case it suffices to expand the node $n$ and to select any descendant that appears also in the hash table of the backward search. You can do this since you are storing all states (instead of nodes) in both hash tables. No matter of the difference between nodes and states, if you generated $n$ in the backward search (which results from the fact that it is stored in the hash table) it had to be done via one of its parents which can be recovered now as one of its descendants (assuming you are traversing undirected graphs, otherwise just apply the inverse operators to recover the parents). Acting like this you will eventually get to the target node.

The same mechanism applies to the forward search ---i.e., no need to store with each node its path to the start node, just use the closed list implemented as a hash table. Reverse the path obtained in the previous paragraph, concatenate them and there you are a solution path.

If you are not using a consistent heuristic function, then you should store along each node in the hash table its value $g(n)$ ---i.e., the cost of the path from its corresponding root node, either $s$ or $t$. Doing so, the previous procedure is just slightly modified by selecting the parent (now generated as a successor) whose $g$ value is $g(n)-1$. However, this is not even necessary in case you are seeking (as it seems) any path from $s$ to $t$.

Bidirectional search is one of the most intriguing "paradigms" in heuristic search. Noone has already found a simple way that makes it as efficient as in the case of blind search (where it is clearly a winner).

Hope this helps,

Answer 2

Just have a dictionary storing where each node came from. So each time you expand a node, you mark all its neighbors that the neighbor came from node.
eg breadcrumbs[neighbor] = node

Then when you reach the goal, you just loop through your dictionary back to the start.