Online Courses
Free Tutorials  Go to Your University  Placement Preparation 
Artificial Intelligence(AI) & Machine Learning(ML) Training in Jaipur
Online Training - Youtube Live Class Link
0 like 0 dislike
24.1k views
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 cum Internship program-2021

Goeduhub's Online Courses @Udemy

For Indian Students- INR 570/- || For International Students- $12.99/-

S.No.

Course Name

Apply Coupon

1.

Tensorflow 2 & Keras:Deep Learning & Artificial Intelligence

Apply Coupon

2.

Computer Vision with OpenCV | Deep Learning CNN Projects

Apply Coupon

3.

Complete Machine Learning & Data Science with Python Apply Coupon

4.

Natural Language Processing-NLP with Deep Learning in Python Apply Coupon

5.

Computer Vision OpenCV Python | YOLO| Deep Learning in Colab Apply Coupon

6.

Complete Python Programming from scratch with Projects Apply Coupon

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.

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 cum Internship program-2021

Our Mentors(For AI-ML)


Sharda Godara Chaudhary

Mrs. Sharda Godara Chaudhary

An alumna of MNIT-Jaipur and ACCENTURE, Pune

NISHA (IIT BHU)

Ms. Nisha

An alumna of IIT-BHU

 Goeduhub:

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