AO star algorithm -Adv-Ltms-comp AI.pptx

AO * algorithm in Artificial Intelligence with example. it is a best first search algorithm. advantages and limitations of AO* was given along with the comparison of A* and AO* algorithm.

1. AO* Algorithm Dr.M.Karthika Head/ Department of Information Technology Mannar Thirumalai Naicker College(A) Pasumalai, Madurai – 4.

2. Basics The AO* algorithm is an advanced search algorithm utilized in artificial intelligence, particularly in problem-solving and decision-making contexts. It is an extension of the A* algorithm, designed to handle more complex problems that require handling multiple paths and making decisions at each node. 30-01-2025 2

3. Overview The  A O algorithm * (short for “And-Or Star”)  is a powerful  best-first search  method used to solve problems that can be represented as a  directed acyclic graph (DAG) . Unlike traditional algorithms like  A *, which explore a single path, the AO* algorithm evaluates multiple paths simultaneously. This makes it more efficient for problems that involve  AND-OR nodes . The AND nodes represent tasks where all child nodes must be satisfied, while OR nodes offer multiple alternative paths where only one child node needs to be satisfied to achieve the goal. 30-01-2025 3

4. 30-01-2025 4

5. Working Principles of AO* Algorithm The AO* algorithm works by utilizing a tree structure where each node represents a state in the problem space. The key components of the algorithm are: Node Types AND Nodes : Represent states where all child nodes must be satisfied to achieve a goal. If a task requires multiple conditions to be met, it would be represented as an AND node. OR Nodes : Represent states where at least one child node must be satisfied to achieve a goal. This type is useful in scenarios where multiple paths can lead to a solution. Heuristic Function The algorithm employs a heuristic function, similar to A*, to estimate the cost to reach the goal from any given node. This function helps in determining the most promising paths to explore. The heuristic function h(n) h ( n ) estimates the cost to reach the goal from node  n n : h(n)=estimated cost to reach the goal from node  h ( n )=estimated cost to reach the goal from node  30-01-2025 5

6. Working Principles contd.. 30-01-2025 6 Search Process The search begins at the initial node and explores its child nodes based on the type (AND or OR). The costs associated with nodes are calculated using the following principles: For OR Nodes : The algorithm considers the lowest cost among the child nodes. The cost for an OR node can be expressed as: C(n)=min⁡{C(c1),C(c2),…,C( ck )} C ( n )=min{ C ( c 1​), C ( c 2​),…, C ( ck ​)} where C(n) C ( n ) is the cost of node  n n  and c1,c2,…,ck c 1​, c 2​,…, ck ​​ are the child nodes of  n n . For AND Nodes : The algorithm computes the cost of all child nodes and selects the maximum cost, as all conditions must be met. The cost for an AND node can be expressed as: C(n)=max⁡{C(c1),C(c2),…,C( ck )} C ( n )=max{ C ( c 1​), C ( c 2​),…, C ( ck ​)} where C(n) C ( n ) is the cost of node  n n , and c1,c2,…,ck c 1​, c 2​,…, ck ​​ are the child nodes of  n n . Total Estimated Cost The total estimated cost f(n) f ( n ) at any node  n n  is given by: f(n)=C(n)+h(n) f ( n )= C ( n )+ h ( n ) where: C(n) C ( n ) is the actual cost to reach node  n n  from the start node. h(n) h ( n ) is the estimated cost from node  n n  to the goal.

7. Example of AO* Algorithm with AND-OR Graph In this example, we will demonstrate how the  AO algorithm * works using an  AND-OR graph . Each node in the graph is assigned a heuristic value, denoted as  h(n) , and the edge length is considered as  1 . 30-01-2025 7

8. Step 1: Initial Evaluation Using f(n) = g(n) + h(n) Starting from node  A , we use the evaluation function: f(A -> B) = g(B) + h(B) = 1 + 5 (g(n) = 1 is the default path cost) = 6 For the path involving  AND  nodes ( C  and  D ): f(A -> C + D) = g(C) + h(C) + g(D) + h(D) = 1 + 2 + 1 + 4 (C & D are AND nodes) = 8 Since f(A -> B) = 6 is smaller than f(A -> C + D) = 8, we select the path A -> B. 30-01-2025 8

9. Step 2: Explore Node B Next, we explore node  B , and calculate the values for nodes  E  and  F : f(B -> E) = g(E) + h(E) = 1 + 7 = 8 f(B -> F) = g(F) + h(F) = 1 + 9 = 10 Thus,  f(B -> E) = 8  is chosen as the optimal path. Since  B ’s heuristic value differs from its actual cost, we update the heuristic for  A . f(A -> B) = g(B) + updated h(B) = 1 + 8 = 9 30-01-2025 9

10. Step 3: Compare and Explore Paths we compare  f(A -> B) = 9  with  f(A -> C + D) = 8 . Since   f(A -> C + D)  is smaller, we explore this path and move to node  C . For node  C : f(C -> G) = g(G) + h(G) = 1 + 3 = 4 f(C -> H + I) = g(H) + h(H) + g(I) + h(I) = 1 + 0 + 1 + 0 (H & I are AND nodes) = 2 For node  D : f(D -> J) = g(J) + h(J) = 1 + 0 = 1 After updating the heuristic for  D , we recalculate: f(A -> C + D) = g(C) + h(C) + g(D) + h(D) = 1 + 2 + 1 + 1 = 5 Now that  f(A -> C + D)  has the lowest cost, this becomes the solved path, and the  AND-OR graph  is now fully resolved. 30-01-2025 10

11. Real-Life Applications of AO* Algorithm in AI Vehicle Routing Problem : The AO* algorithm can be applied to determine the shortest routes for a fleet of vehicles, minimizing the total distance traveled and time taken while visiting a set of customers and returning to the depot. Portfolio Optimization : In financial portfolio optimization, the AO* algorithm can help choose the best set of investments that maximize returns and minimize risks. It explores different combinations of investments to find the optimal portfolio that satisfies both objectives. 30-01-2025 11

12. Advantages of AO* Algorithm in Artificial Intelligence Efficiency : AO* can efficiently handle complex decision trees by evaluating multiple paths simultaneously, which can significantly reduce the search space. Flexibility : The algorithm’s ability to deal with AND and OR nodes makes it versatile for various applications and problem types. Optimal Solutions : By using heuristic functions, AO* aims to find optimal solutions, similar to the A* algorithm. 30-01-2025 12

13. Limitations of AO* Algorithm in AI Complexity : The algorithm can become computationally expensive, especially in highly complex graphs with many nodes and connections, as it must evaluate numerous possibilities. Memory Usage : AO* may require significant memory resources to store the nodes and paths being evaluated, which can be a limitation in resource-constrained environments. Dependency on Heuristics : The performance of AO* heavily relies on the quality of the heuristic function. A poorly designed heuristic can lead to suboptimal solutions and increased search times. 30-01-2025 13

14. Conclusion The AO* algorithm represents a powerful tool in the field of artificial intelligence for solving complex problems involving multiple decision paths. Its ability to handle AND and OR nodes allows for flexibility and efficiency in various applications, from gaming to robotics and natural language processing. 30-01-2025 14

15. Aspect A Algorithm * AO Algorithm * Search Type Best-first search Best-first search Type of Search Informed search using heuristics Informed search using heuristics Solution Optimality Always gives the optimal solution Does not guarantee an optimal solution Path Exploration Explores all possible paths Stops exploring once a solution is found Memory Usage Uses more memory Uses less memory Endless Loop May go into an endless loop without proper checks Cannot go into an endless loop Comparison between A* Algorithm and AO* algorithm 30-01-2025 15

16. Thank you 30-01-2025 16