In this article we will discuss about:- 1. And-OR Graph during Search Methods 2. Difference Between OR and AND-OR Graph during Search Methods 3. Limitations of AND-OR Graph.
And-OR Graph during Search Methods:
AND OR graph (to tree) is useful for representing the solutions of problems which can be solved by decomposing them into a set of smaller problems, all of which must then be solved independently and then combined. This decomposition or reduction generates arcs, called 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. In OR graph several arcs may emerge from a simple node, indicating a variety of ways in which the original problem might be solved.
An example of AND-OR graph/tree is shown in Fig. 4.10. AND arcs are indicated with a arc connecting all the components.
Best-first is not suitable for searching AND-OR graphs. In the Fig. 4.11, the top node A, has been expanded, producing two arcs, one leading to B and the second leading to C and D. The numbers at each node represents the value of approximate value of heuristic function (f‘) at that node. For simplicity, we assume that every operation has a uniform cost, so each arc with a single successor has a cost of 1 and each arc with multiple success or has a cost of 1 for each of its components.
If we select the node with lowest, f‘ value for further expansion, it is C. But node C forms a part of AND arc and node D must also be expanded. The cost of expansion of AND arc is 9 (C + D + 2) compared to cost of 6 by going through B. So node B is explored (Fig. 4.11) next.
Now the AND arcs E F through B and C D through A are compared. The arc CD is explored as the cost 9 (C + D + 2) is cheaper than the cost 17 (E + F + 2) so this arc is expanded (Fig. c). The most promising single node is G with an f value of 3.
ADVERTISEMENTS:
It is even part of the most promising arc G H with a total cost of 9. But that aFC is not part of current best path since to use it we must also expand arc I J with a cost of 27. The path from A, through B, to E and F is better with a total cost of 18. So we do not expand G now, rather we now consider for expansion either E or F (rather E and F).
So from the tree expanded like this it becomes clear that the choice to expand any node depends upon:
ADVERTISEMENTS:
1. Its f‘ value
2. Whether that node is part of the current best path from the initial node.
In order to describe an algorithm for searching an AND-OR graph, we should define a value called FUTILITY. If the estimated cost of a solution becomes greater than the value of FUTILITY, then the search is abandoned. FUTILITY should be chosen to correspond to a threshold such that any solution with a cost above it is too expensive to be practical, even if it could ever be found.
ADVERTISEMENTS:
For finding are optimum path in AND/OR graph, we use an algorithm, called an AO* algorithm.
Then major steps of the AO* algorithm are presented below (follows backward chaining):
1. Given the Goal node or the starting state, find the possible off-springs of the starting state, such that the Goal can be derived from them by AND/OR clauses.
2. Estimate the h’ values at the leaves and find the leaf (leaves) with minimum h’. The cost of the parent of the leaf (leaves) is the minimum of the cost of the OR clauses plus one or the cost of the AND clauses plus the number of AND clauses. After the children with minimum h’ are estimated, a pointer is attached to point from the parent node to its promising children (assuming uniform-cost search).
ADVERTISEMENTS:
3. One of the unexpanded OR clauses/the set of unexpanded AND clauses, where the pointer points from its parent, is now expanded and the h’ of the newly generated children are estimated. The effect of this h’ has to be propagated up to the root by re-calculating the h’ of the parent or the parents of the newly created child/children clauses through a least cost path. Thus, the pointers may be modified depending on the revised cost of the existing clauses.
A few steps of the AO* algorithm are illustrated below based on the above principle.
Algorithm AO*:
Begin:
1. Given the goal node INIT in the graph G; evaluate h’ at INIT.
2. Repeat:
(a) Trace the marked arcs from the node INIT, if any such exists and select one of the unexpanded nodes, named NODE that occurs on this path, for expansion.
(b) If NODE cannot be expanded. Then assign FUTILITY as the h’ value of NODE, indicating that NODE is not solvable;
Else for each such successor, called SUCCESSOR, which is not an ancestor of-
NODE, do
Begin:
(i) Append SUCCESSOR to the graph G.
(ii) If SUCCESSOR is a terminal node, Then label it SOLVED and set its h’ value 0.
(iii) If SUCCESSOR is not a terminal node, Then estimate its h’ value;
End;
(a) Initialize S to NODE;
(b) Repeat
(i) Select from S a node, none of whose descendants belong to S Call it Current and remove it from S.
(ii) Estimate the cost of each of the arcs, emerging from CURRENT. The cost of each arc is equal to the sum of h’ value of each of the nodes at the end of the arc plus the cost of the arc itself. The new h’ value of CURRENT is the minimum of the cost just computed for the arcs emerging from it.
(iii) Label the best path out of CURRENT by marking the arc that had the least cost as computed in the last step.
(iv) If all of nodes connected to CURRENT through the new marked arcs have been labeled SOLVED, Then mark the CURRENT SOLVED.
(v) If CURRENT is marked SOLVED or the cost of CURRENT was changed. Then propagate its new status back up the tree, add all the ancestors of CURRENT to S.
Until S is empty.
Until INIT is labeled solved or its f‘ value becomes greater then a maximum, level called FUTILITY-
End.
Difference Between OR and AND-OR Graph during Search Methods:
1. Propagation of the revised cost estimates back up the tree is not needed for OR graph because only unexpanded nodes are expanded and examined only once. In AND-OR graph expanded nodes must be re-examined to select the best current path.
2. Individual paths from node to node cannot be considered independently of the paths through other nodes connected to the original ones by AND arcs. In the best-first (A*) algorithm the desired path from one node to another was always the one with the lowest cost. This is not always the case with AND-OR search.
For example, consider the graph shown in Fig. 4.17 (a). The nodes were generated in alphabetical order. Now suppose that node J is expanded at next step and one of its successors is node E, producing the graph shown in Fig. 4.17 (b).
The new path to E is longer than the previous path to E going through C. But since path through C will only lead to a solution if there is also a solution to D, which we know is dead end, so the path through J is better which is obviously not optimum.
Limitations of AND-OR Graph during Search Methods:
It fails to take into account any interaction between the sub-goals of the problem as illustrated in Fig. 4.18.
Assuming that both nodes AND C and E ultimately lead to a solution, our algorithm shall report a complete solution which includes both of them. The AND-OR graph states that for A to be solved, both C or D must be solved. But then the algorithm considers the solution of D as a completely separate process from the solution of C.
Looking just at the alternatives from D, E is the best path. But it turns out that C is necessary also, so it would be better also to use it to satisfy D. But since our algorithm does not consider such, interactions it will find non-optimal path.
One application of problem reduction, the SAINT program, pioneered the use of artificial intelligence in mathematical problem solving.
Basically, SAINT was a program which inter grated symbolic expressions in one variable.
For example, when given:
Saint:
Like programs perform variable substitutions and other algebraic manipulations to transform difficult integrands into one or more simpler integrands, thus exhibiting problem reduction, with the hope of eventually producing integrands so simple that the answers are given directly in integral tables.
Saint was conceived and developed by James R. Slagle (1963) and was superseded by programs based on SIN, a program written by Joel Moses (1967).