FIFA-2022 Career Guide Free Tutorials Go to Your University Placement Preparation 
0 like 0 dislike
in VTU B.Tech (CSE-VII Sem) Artificial Intelligence and Machine Learning Lab by Goeduhub's Expert (3.1k points)

Implement AO* Search algorithm.

Summer Training-Internship program-2021

1 Answer

0 like 0 dislike
by Goeduhub's Expert (3.1k points)
edited by
Best answer

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.


  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

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.

Best Data Science Courses on Datacamp
Best Data Science Courses on Coursera
Best Data Science Courses on Udemy
Best Data Science Courses on Pluralsight
Best Data Science Courses & Microdegrees on Udacity
Best Artificial Intelligence[AI] Courses on Coursera
Best Machine Learning[ML] Courses on Coursera
Best Python Programming Courses on Coursera
Best Artificial Intelligence[AI] Courses on Udemy
Best Python Programming Courses on Udemy

 Important Lists:

Important Lists, Exams & Cutoffs Exams after Graduation PSUs


About Us | Contact Us || Terms & Conditions | Privacy Policy ||  Youtube Channel || Telegram Channel © Social::   |  | 


Free Online Directory