Question

Implement AO* Search algorithm.

Summer Training-Internship program-2021

Answer 1

AO* Algorithm

AO* Algorithm basically based on  problem decompositon (Breakdown problem into small pieces)

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.

AND-OR Graph 

The figure shows an AND-OR graph 

1. To pass any exam, we have two options, either cheating or hard work.
2. In this graph we are given two choices, first do cheating or (The red line) work hard and (The arc) pass. 
3. When we have more than one choice and we have to pick one, we apply OR condition to choose one.(That's what we did here).
4. Basically the ARC here denote AND condition.

5. Here we have replicated the arc between the work hard and the pass because by doing the hard work possibility of passing an exam is more than cheating.

A* Vs AO*

1. Both are part of informed search technique and use heuristic values to solve the problem.
2. The solution is guaranteed in both algorithm.
3. A*  always gives an optimal solution (shortest path with low cost) But It is not guaranteed to that AO*  always provide an optimal solutions.
4. Reason: Because AO* does not explore all the solution path once it got solution.

How AO* works

Let's try to understand it with the following diagram

The algorithm always moves towards a lower cost value.

Basically, We will calculate the cost function here (F(n)= G (n) + H (n))

H:  heuristic/ estimated  value of the nodes. and G: actual cost or edge value (here unit value).

Here we have taken the edges value 1 , meaning we have to focus solely on the heuristic value.

1. The Purple color values are edge values (here all are same that is one).
2. The Red color values are Heuristic values for nodes.
3. The Green color values are New Heuristic values for nodes.

Procedure:

1. In the above diagram we have two ways from A to D or A to B-C (because of and condition). calculate cost to select a path
2. F(A-D)= 1+10 = 11            and               F(A-BC) = 1 + 1 + 6 +12 = 20
3. As we can see F(A-D) is less than F(A-BC) then the algorithm choose the path F(A-D).
4. Form D we have one choice that is F-E.
5. F(A-D-FE) = 1+1+ 4 +4 =10
6. Basically 10 is the cost of reaching FE from D. And Heuristic value of node D also denote the cost of reaching FE from D. So, the new Heuristic value of D is 10. 
7. And the Cost from A-D remain same that is 11.

Suppose we have searched this path and we have got the Goal State, then we will never explore the other path. (this is what AO* says  but here we are going to explore other path as well to see what happen)

Let's Explore the other path:

1. In the above diagram we have two ways from A to D or A to B-C (because of and condition). calculate cost to select a path
2. F(A-D)= 1+10 = 11            and               F(A-BC) = 1 + 1 + 6 +12 = 20
3. As we know the cost is more of F(A-BC) but let's take a look 
4. Now from B we have two path G and H , let's calculate the cost
5. F(B-G)= 5+1 =6    and F(B-H)= 7 + 1 = 8
6. So, cost from F(B-H) is more than F(B-G) we will take the path B-G.
7. The Heuristic value from G to I is 1 but let's calculate the cost form G to I.
8. F(G-I) = 1 +1 = 2. which is less than Heuristic value 5. So, the new Heuristic value form G to I is 2.
9. If it is a new value, then the cost from G to B must also have changed. Let's see the new cost form (B to G)
10. F(B-G)= 1+2 =3 . Mean the New Heuristic value of B is 3.
11. But A is associated with both B and C .
12. As we can see from the diagram C only have one choice or one node to explore that is J. The Heuristic value of C is 12.
13. Cost form C to J= F(C-J) = 1+1= 2 Which is less than Heuristic value 
14. Now the New Heuristic value of C is 2. 
15. And the New Cost from A- BC that is F(A-BC) = 1+1+2+3 = 7 which is less than F(A-D)=11. 
16. In this case Choosing path A-BC is more cost effective and good than that of A-D.

But this will only happen when the algorithm explores this path as well. But according to the algorithm, algorithm will not accelerate this path (here we have just did  it to see how the other path can also be correct).

But it is not the case in all the cases that it will happen in some cases that the algorithm will get optimal solution.

Summer Training-Internship program-2021