And-Or graph

PROBLEM REDUCTION:

So far we have considered search strategies for OR graphs through which we want to find a single path to a goal. Such structure represent the fact that we know how to get from anode to a goal state if we can discover how to get from that node to a goal state along any one of the branches leaving it.

AND-OR GRAPHS

The AND-OR GRAPH (or tree) is useful for representing the solution of problems that can solved by decomposing them into a set of smaller problems, all of which must then be solved. This decomposition, or reduction, generates arcs that we call AND arcs. One AND arc may point to any number of successor nodes, all of which must be solved in order for the arc to point to a solution. Just as in an OR graph, several arcs may emerge from a single node, indicating a variety of ways in which the original problem might be solved. This is why the structure is called not simply an AND-graph but rather an AND-OR graph (which also happens to be an AND-OR tree)

EXAMPLE FOR AND-OR GRAPH

ALGORITHM:

1. Let G be a graph with only starting node INIT.
2. Repeat the followings until INIT is labeled SOLVED or h(INIT) >  FUTILITY

a)      Select an unexpanded node from the most promising path from INIT (call it NODE)

b)      Generate successors of NODE. If there are none, set h(NODE) = FUTILITY (i.e., NODE is unsolvable); otherwise for each SUCCESSOR that is not an ancestor of NODE do the following:

                                                         i.            Add SUCCESSSOR to G.

                                                       ii.            If SUCCESSOR is a terminal node, label it SOLVED and set h(SUCCESSOR) = 0.

                                                      iii.            If SUCCESSPR is not a terminal node, compute its h

c)       Propagate the newly discovered information up the graph by doing the following: let S be set of SOLVED nodes or nodes whose h values have been changed and need to have values propagated back to their parents. Initialize S to Node. Until S is empty repeat the followings:

                                                         i.            Remove a node from S and call it CURRENT.

                                                       ii.            Compute the cost of each of the arcs emerging from CURRENT. Assign minimum cost of its successors as its h.

                                                      iii.            Mark the best path out of CURRENT by marking the arc that had the minimum cost in step ii

                                                     iv.            Mark CURRENT as SOLVED if all of the nodes connected to it through new labeled arc have been labeled SOLVED

                                                       v.            If CURRENT has been labeled SOLVED or its cost was just changed, propagate its new cost back up through the graph. So add all of the ancestors of CURRENT to S.

EXAMPLE: 1

STEP 1:

A is the only node, it is at the end of the current best path. It is expanded, yielding nodes B, C, D. The arc to D is labeled as the most promising one emerging from A, since it costs 6compared to B and C, Which costs 9.

STEP 2:

 

Node B is chosen for expansion. This process produces one new arc, the AND arc to E and F, with a combined cost estimate of 10.so we update the f’ value of D to 10.Going back one more level, we see that this makes the AND arc B-C better than the arc to D, so it is labeled as the current best path.

STEP 3:

We traverse the arc from A and discover the unexpanded nodes B and C. If we going to find a solution along this path, we will have to expand both B and C eventually, so let’s choose to explore B first. This generates two new arcs, the ones to G and to H. Propagating their f’ values backward, we update f’ of B to 6(since that is the best we think we can do, which we can achieve by going through G). This requires updating the cost of the AND arc B-C to 12(6+4+2). After doing that, the arc to D is again the better path from A, so we record that as the current best path and either node E or node F will chosen for expansion at step 4.

 

STEP4:                                 

EXAMPLE: 2