blue lines) is two.

That means that the number of nodes you have in each level of the search is
2^d where d is the depth. If the number of steps to solve a particular state is 18, then that�s
262,144 nodes just at that level.

The 8 puzzle game state is as simple as representing a list of the 9 squares and what's in them.
Here are two states for example; the last one is the GOAL state, at which point we've found the
solution. The first is a jumbled up example that you may start from.

Start state SPACE, A, C, H, B, D, G, F, E

There is example code to to solve the 8-puzzle on the github site.

Pathfinding
In a video game, or some other pathfinding scenario, you want to search a state space and find
out how to get from somewhere you are to somewhere you want to be, without bumping into
walls or going too far. For reasons we will see later, the A* algorithm will not only find a path, if
there is one, but it will find the shortest path. A state in pathfinding is simply a position in the
world. In the example of a maze game like Pacman you can represent where everything is using
a simple 2d grid. The start state for a ghost say, would be the 2d coordinate of where the ghost is
at the start of the search. The goal state would be where pacman is so we can go and eat him.
There is also example code to do pathfinding on the github site.

Figure 2 : The first three steps of a pathfinding state space

45
Implementing A*
We are now ready to look at the operation of the A* algorithm. What we need to do is start with
the goal state and then generate the graph downwards from there. Let's take the 8-puzzle in
figure 1. We ask how many moves can we make from the start state? The answer is 2, there are
two directions we can move the blank tile, and so our graph expands.
If we were just to continue blindly generating successors to each node, we could potentially fill
the computer's memory before we found the goal node. Obviously we need to remember the best
nodes and search those first. We also need to remember the nodes that we have expanded
already, so that we don't expand the same state repeatedly.
Let's start with the OPEN list. This is where we will remember which nodes we haven't yet
expanded. When the algorithm begins the start state is placed on the open list, it is the only state
we know about and we have not expanded it. So we will expand the nodes from the start and put
those on the OPEN list too. Now we are done with the start node and we will put that on the
CLOSED list. The CLOSED list is a list of nodes that we have expanded.

f=g+h

Using the OPEN and CLOSED list lets us be more selective about what we look at next in the
search. We want to look at the best nodes first. We will give each node a score on how good we
think it is. This score should be thought of as the cost of getting from the node to the goal plus
the cost of getting to where we are. Traditionally this has been represented by the letters f, g and
h. 'g' is the sum of all the costs it took to get here, 'h' is our heuristic function, the estimate of
what it will take to get to the goal. 'f' is the sum of these two. We will store each of these in our
nodes.
Using the f, g and h values the A* algorithm will be directed, subject to conditions we will look
at further on, towards the goal and will find it in the shortest route possible.

So far we have looked at the components of the A*, let's see how they all fit together to make the
algorithm :

Pseudocode

Hopefully the ideas we looked at in the preceding paragraphs will now click into place as we
look at the A* algorithm pseudocode. You may find it helpful to print this out or leave the
window open while we discuss it.

To help make the operation of the algorithm clear we will look again at the 8-puzzle problem in
figure 1 above. Figure 3 below shows the f,g and h scores for each of the tiles.

46
Figure 3 : 8-Puzzle state space showing f,g,h scores

First of all look at the g score for each node. This is the cost of what it took to get from the start
to that node. So in the picture the center number is g. As you can see it increases by one at each
level. In some problems the cost may vary for different state changes. For example in
pathfinding there is sometimes a type of terrain that costs more than other types.
Next look at the last number in each triple. This is h, the heuristic score. As I mentioned above I
am using a heuristic known as Nilsson's Sequence, which converges quickly to a correct solution
in many cases. Here is how you calculate this score for a given 8-puzzle state :

Advantages:

It is complete and optimal.

It is the best one from other techniques. It is used to solve very complex problems.

It is optimally efficient, i.e. there is no other optimal algorithm guaranteed to expand fewer nodes
than A*.

Disadvantages:

This algorithm is complete if the branching factor is finite and every action has fixed cost.

The speed execution of A* search is highly dependant on the accuracy of the heuristic algorithm
that is used to compute h (n).

47
AO* Search: (And-Or) Graph

The Depth first search and Breadth first search given earlier for OR trees or graphs can be easily
adopted by AND-OR graph. The main difference lies in the way termination conditions are
determined, since all goals following an AND nodes must be realized; where as a single goal
node following an OR node will do. So for this purpose we are using AO* algorithm.

Like A* algorithm here we will use two arrays and one heuristic function.

OPEN:

It contains the nodes that has been traversed but yet not been marked solvable or unsolvable.

CLOSE:

It contains the nodes that have already been processed.

6 7:The distance from current node to goal node.

Algorithm:

Step 1: Place the starting node into OPEN.

Step 2: Compute the most promising solution tree say T0.

Step 3: Select a node n that is both on OPEN and a member of T0. Remove it from OPEN and
place it in

CLOSE

Step 4: If n is the terminal goal node then leveled n as solved and leveled all the ancestors of n
as solved. If the starting node is marked as solved then success and exit.

Step 5: If n is not a solvable node, then mark n as unsolvable. If starting node is marked as
unsolvable, then return failure and exit.

Step 6: Expand n. Find all its successors and find their h (n) value, push them into OPEN.

Step 7: Return to Step 2.

Step 8: Exit.

48
Implementation:

Let us take the following example to implement the AO* algorithm.

Step 1:

In the above graph, the solvable nodes are A, B, C, D, E, F and the unsolvable nodes are G, H.
Take A as the starting node. So place A into OPEN.

49
50
51
Advantages:

It is an optimal algorithm.

If traverse according to the ordering of nodes. It can be used for both OR and AND graph.

Disadvantages:

Sometimes for unsolvable nodes, it can’t find the optimal path. Its complexity is than other
algorithms.

PROBLEM REDUCTION

Problem Reduction with AO* Algorithm.

When a problem can be divided into a set of sub problems, where each sub problem can be
solved separately and a combination of these will be a solution, AND-OR graphs or AND - OR
trees are used for representing the solution. The decomposition of the problem or problem
reduction generates AND arcs. One AND are may point to any number of successor nodes. All

52
these must be solved so that the arc will rise to many arcs, indicating several possible solutions.
Hence the graph is known as AND - OR instead of AND. Figure shows an AND - OR graph.

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.

FIGURE : AND - OR graph

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. 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 n 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). 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 unexpanded nodes and expand it. Add its successors to the graph and
computer f ' (cost of the remaining distance) for each of them.

53
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:

Referring the figure. The initial node is expanded and D is Marked initially as promising node. D
is expanded producing an AND arc E-F. f ' value of D is updated to 10. Going backwards we can
see that the AND arc B-C is better . it is now marked as current best path. B and C have to be
expanded next. This process continues until a solution is found or all paths have led to dead ends,
indicating that there is no solution. An A* algorithm the path from one node to the other is
always that of the lowest cost and it is independent of the paths through other nodes.

The algorithm for performing a heuristic search of an AND - OR graph is given below. Unlike
A* algorithm which used two lists OPEN and CLOSED, the AO* algorithm uses a single
structure G. G represents the part of the search graph generated so far. Each node in G points
down to its immediate successors and up to its immediate predecessors, and also has with it the
value of h' cost of a path from itself to a set of solution nodes. The cost of getting from the start
nodes to the current node "g" is not stored as in the A* algorithm. This is because it is not
possible to compute a single such value since there may be many paths to the same state. In AO*
algorithm serves as the estimate of goodness of a node. Also a there should value called
FUTILITY is used. The estimated cost of a solution is greater than FUTILITY then the search is
abandoned as too expansive to be practical.
For representing above graphs AO* algorithm is as follows

AO* ALGORITHM:
1. Let G consists only to the node representing the initial state call this node INTT. Compute
h' (INIT).

2. Until INIT is labeled SOLVED or hi (INIT) becomes greater than FUTILITY, repeat the
following procedure.

54
(I) Trace the marked arcs from INIT and select an unbounded node NODE.

(II) Generate the successors of NODE . if there are no successors then assign FUTILITY as
h' (NODE). This means that NODE is not solvable. If there are successors then for each
one
called SUCCESSOR, that is not also an ancester of NODE do the following

(a) add SUCCESSOR to graph G

(b) if successor is not a terminal node, mark it solved and assign zero to its h ' value.

(c) If successor is not a terminal node, compute it h' value.

(III) propagate the newly discovered information up the graph by doing the following . let S be a
set of nodes that have been marked SOLVED. Initialize S to NODE. Until S is empty
repeat
the following procedure;

(a) select a node from S call if CURRENT and remove it from S.

(b) compute h' of each of the arcs emerging from CURRENT , Assign minimum h' to
CURRENT.

(c) Mark the minimum cost path a s the best out of CURRENT.

(d) Mark CURRENT SOLVED if all of the nodes connected to it through the new marked
are have been labeled SOLVED.

(e) If CURRENT has been marked SOLVED or its h ' has just changed, its new status
must
be propagate backwards up the graph . hence all the ancestors of CURRENT are added
to S.
(Refered From Artificial Intelligence TMH)

AO* Search Procedure.

1. Place the start node on open.

2. Using the search tree, compute the most promising solution tree TP .

3. Select node n that is both on open and a part of tp, remove n from open and place it no closed.

4. If n is a goal node, label n as solved. If the start node is solved, exit with success where tp is
the solution tree, remove all nodes from open with a solved ancestor.

55