Session 13

AO*
Memory Bounded Heuristic search
Heuristic functions
 Algorithm AO*

1.Initialize: Set G* = {s}, f(s) = h(s)

If s  T, label s as SOLVED
2.Terminate: If s is SOLVED, then terminate
3.Select: Select a non-terminal leaf node n from the
marked sub-tree below s in G*
4.Expand: Make explicit the successors of n
For each successor, m, not already in G*:
Set f(m) = h(m)
If m is a terminal node, label m as SOLVED
5.Cost Revision: Call cost-revise(n)
6.Loop: Go To Step 2.
Cost Revision in AO*: cost-revise(n)
1. Create Z = {n}
2. If Z = { } return
3. Select a node m from Z such that m has no descendants in Z
4. If m is an AND node with successors r1, r2, … rk:
Set f(m) =  [ f(ri) + c(m, ri) ]
Mark the edge to each successor of m
If each successor is labeled SOLVED, then label m as SOLVED
• If m is an OR node with successors r1, r2, … rk:
Set f(m) = min { f(ri) + c(m, ri) }
Mark the edge to the best successor of m
If the marked successor is labeled SOLVED, label m as SOLVED
1. If the cost or label of m has changed, then insert those parents of m into Z for
which m is a marked successor
2. Go to Step 2.
3
 AO* SEARCH ALGORITHM
Problem Reduction In Artificial Intelligence
AO* is informed search algorithm ,work based on heuristic
We already know about the divide and conquer strategy, a solution to a
problem can be obtained by decomposing it into smaller sub-problems.

Each of this sub-problem can then be solved to get its sub solution.
These sub solutions can then recombined to get a solution as a whole.
That is called is Problem Reduction. AND-OR graphs or AND - OR trees
are used for representing the solution.

This method generates arc which is called as AND-OR arcs. One AND
arc may point to any number of successor nodes, all of which must be
solved in order for an arc to point to a solution.
AND-OR graph is used to represent various kind of complex problem
solutions.
AO* search algo. is based on AND-OR graph so ,it is called AO* search
algo.
 AO* SEARCH ALGORITHM
 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 OR-graph but rather an
AND-OR graph (which also happens to be an AND-OR tree)
 AO* SEARCH ALGORITHM
 An algorithm to find a solution in an AND - OR graph must handle
AND area appropriately.
 A* algorithm can not search AND - OR graphs efficiently.
 This can be understand from the give figure
 In figure (a) the top node A has been expanded producing two area one
leading to B and leading to C-D . the numbers at each node represent
the value of f ' at that node (cost of getting to the goal state from
current state). For simplicity, it is assumed that every operation(i.e.
applying a rule) has unit cost, i.e., each are with single successor will
have a cost of 1 and each of its components.
 AO* SEARCH ALGORITHM
 With the available information till now , it appears that C is the most
promising node to expand since its f ' = 3 , the lowest but going through
B would be better since to use C we must also use D' and the cost would
be 9(3+4+1+1). Through B it would be 6(5+1).
 Thus the choice of the next node to expand depends not only on a value
but also on whether that node is part of the current best path form the
initial mode. Figure (b) makes this clearer. In figure the node G appears
to be the most promising node, with the least f ' value. But G is not on
the current beat path, since to use G we must use GH with a cost of 9
and again this demands that arcs be used (with a cost of 27).
 AO* SEARCH ALGORITHM
 The path from A through B, E-F is better with a total cost of (17+1=18).
Thus we can see that to search an AND-OR graph, the following three
things must be done.
 1. traverse the graph starting at the initial node and following the
current best path, and accumulate the set of nodes that are on the path
and have not yet been expanded.

 2. Pick one of these best unexpanded nodes and expand it. Add its
successors to the graph and compute f ' (cost of the remaining distance)
for each of them.
 AO* SEARCH ALGORITHM
 3. Change the f ' estimate of the newly expanded node to reflect the new
information produced by its successors. Propagate this change
backward through the graph. Decide which of the current best path.

 The propagation of revised cost estimation backward is in the tree is not

necessary in A* algorithm. This is because in AO* algorithm expanded
nodes are re-examined so that the current best path can be selected.
The working of AO* algorithm is illustrated in figure as follows:
 AO* SEARCH ALGORITHM
Advantages of AO*:
 It is Complete
 Will not go in infinite loop
 Less Memory Required

Disadvantages of AO*:
 It is not optimal as it does not explore all the path once it find a
solution.
 MEMORY-BOUNDED HEURISTIC SEARCH

The simplest way to reduce memory requirements for A* is to adapt the idea
of ITERATIVE DEPENING deepening to the heuristic search context,
resulting in the iterative-deepening A* (IDA*) algorithm.

The main difference between IDA* and standard iterative deepening is that
the cutoff used is the f-cost (g + h) rather than the depth; at each iteration, the
cutoff value is the smallest f-cost of any node that exceeded the cutoff on the
previous iteration.

 IDA* is practical for many problems with unit step costs and avoids the
substantial overhead associated with keeping a sorted queue of nodes.

 Two memory bound algorithms are RBFS and MA*

 RECURSIVE BEST FIRST SEARCH

 Similar to standard best-first search, but using only linear space.

 Its structure is similar to that of a recursive depth-first search, but rather than
continuing indefinitely down the current path, it uses the f-limit variable to keep
track of the f -value of the best alternative path available from any ancestor of
the current node. If the current node exceeds this limit, the recursion unwinds
back to the alternative path. As the recursion unwinds, RBFS replaces the f-value
of each node along the path with a backed-up value—the best f-value of its
children. In this way, RBFS remembers the f-value of the best leaf in the
forgotten sub-tree and can therefore decide whether it's worth re-expanding the
sub-tree at some time later.
1. RBFS is an optimal algorithm if the heuristic function h(n) is admissible.
2. Its space complexity is linear in the depth of the deepest optimal solution, but its time
complexity is rather difficult to characterize: it depends both on the accuracy of the
heuristic function and on how often the best path changes as nodes are expanded.
3. IDA* and RBFS suffer from using too little memory. Between iterations, IDA* retains
only a single number: the current f-cost limit. RBFS retains more information in
memory, but it uses only linear space: even if more memory were available, RBFS has
no way to make use of it. Because they forget most of what they have done, both
algorithms may end up re-expanding the same states many times over.
4. They suffer the potentially exponential increase in complexity associated with
redundant paths in graphs.
To use all available memory, can use two algorithms :- MA* (memory-
bounded A*) and SMA* (simplified MA*).

SMA proceeds just like A*, expanding the best leaf until memory is full. At
this point, it cannot add a new node to the search tree without dropping an old
one.

SMA* always drops the worst leaf node—the one with the highest f -value.
Like RBFS, SMA* then backs up the value of the forgotten node to its parent. In
this way, the ancestor of a forgotten sub-tree knows the quality of the best path
in that sub-tree.

With this information, SMA* regenerates the sub-tree only when all other
paths have been shown to look worse than the path it has forgotten.

Another way of saying this is that, if all the descendants of a node n are
forgotten, then we will not know which way to go from n, but we will still have
an idea of how worthwhile it is to go anywhere from n.
SMA* expands the Best leaf and deletes the worst leaf.

To avoid selecting the same node for deletion and expansion, SMA* expands
the newest best leaf and deletes the oldest worst leaf.

These coincide when there is only one leaf, but in that case, the current search
tree must be a single path from root to leaf that fills all of memory.

If the leaf is not a goal node, then even if it is on an optimal solution path, that
solution is not reachable with the available memory. Therefore, the node can be
discarded exactly as if it had no successors.

SMA" is complete if there is any reachable solution—that is, if d, the depth of

the shallowest goal node, is less than the memory size (expressed in nodes).
 It is optimal if any optimal solution is reachable; otherwise, it returns the best
reachable solution.

In practical terms, SMA* is a fairly robust choice for finding optimal
solutions, particularly when the state space is a graph, step costs are not
uniform, and node generation is expensive compared to the overhead of
maintaining the frontier and the explored set.
 Heuristic Functions
An informed search make use of heuristic functions in order to reach the goal node in
a more prominent way. Therefore, there are several pathways in a search tree to reach
the goal node from the current node.

The selection of a good heuristic function matters certainly. A good heuristic function
is determined by its efficiency. More is the information about the problem, more is the
processing time.

Examples: Toy problems, such as 8-puzzle, 8-queen, tic-tac-toe, etc., can be solved
more efficiently with the help of a heuristic function. 
 8-Puzzle Problem
Consider the following 8-puzzle problem where we have a start state and a goal state.
Our task is to slide the tiles of the current/start state and place it in an order followed
in the goal state. There can be four moves either left, right, up, or down. There can
be several ways to convert the current/start state to the goal state, but, we can use a
heuristic function h(n) to solve the problem more efficiently.
 Heuristic Functions
A heuristic function for the 8-puzzle problem is defined below:
h(n)=Number of tiles out of position.
So, there is total of three tiles out of position i.e., 6,5 and 4. Do not count the empty
tile present in the goal state). i.e. h(n)=3. Now, we require to minimize the value
of h(n) =0.
We can construct a state-space tree to minimize the h(n) value to 0, as shown below:
 Heuristic Functions

It is seen from the above state space tree that the goal state is minimized from h(n)=3
to h(n)=0. However, we can create and use several heuristic functions as per the
reqirement. It is also clear from the above example that a heuristic function h(n) can
be defined as the information required to solve a given problem more efficiently. The
information can be related to the nature of the state, cost of transforming from one
state to another, goal node characteristics, etc., which is expressed as a heuristic
function.
 Properties of a Heuristic search Algorithm

Use of heuristic function in a heuristic search algorithm leads to following properties

of a heuristic search algorithm:
•Admissible Condition: An algorithm is said to be admissible, if it returns an optimal
solution.
•Completeness: An algorithm is said to be complete, if it terminates with a solution (if
the solution exists).
•Dominance Property: If there are two admissible heuristic
algorithms A1 and A2 having h1 and h2 heuristic functions, then A1 is said to
dominate A2  if h1 is better than h2 for all the values of node n.
•Optimality Property: If an algorithm is complete, admissible,
and dominating other algorithms, it will be the best one and will definitely give an
optimal solution.