**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 **

- To pass any exam, we have two options, either cheating or hard work.
- In this graph we are given two choices, first do cheating
**or (The red line) **work hard and **(The arc) **pass. - 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). - Basically the
**ARC **here denote** AND condition**. 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***

- Both are part of informed search technique and use heuristic values to solve the problem.
- The solution is guaranteed in both algorithm.
- A*
**always** gives an **optimal solution** (shortest path with low cost) But It is not guaranteed to that** AO* ** always provide **an optimal solutions**. **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.**

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

**Procedure:**

- 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 **F(A-D)= 1+10 = 11** and **F(A-BC) = 1 + 1 + 6 +12 = 20**- As we can see
** F(A-D) **is less than **F(A-BC) **then the algorithm choose the path **F(A-D).** - Form D we have one choice that is
**F-E.** **F(A-D-FE) = 1+1+ 4 +4 =10**- 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. - 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:**

- 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 **F(A-D)= 1+10 = 11** and **F(A-BC) = 1 + 1 + 6 +12 = 20**- As we know the cost is more of
**F(A-BC) **but let's take a look - Now from B we have two path G and H , let's calculate the cost
**F(B-G)= 5+1 =6 ** and **F(B-H)= 7 + 1 = 8**- So, cost from
** F(B-H)** is more than **F(B-G) **we will take the path B-G. - The Heuristic value fro
**m G to I is 1 but let's calculate the cost form G to I.** **F(G-I) = 1 +1 = 2. **which is less than **Heuristic value 5**. So, the new** Heuristic value form G to I is 2.**- 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)** - F(B-G)= 1+2 =3 . Mean the
** New Heuristic value of B is 3.** **But A is associated with both B and ****C .**- 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. - Cost form C to
**J= F(C-J) = 1+1= 2** Which is less than Heuristic value - No
**w the New Heuristic value of C is 2. ** **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. **- 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