Informed search algorithms.pptx

Informed search algorithms are commonly used in various AI applications, including pathfinding, puzzle solving, robotics, and game playing. They are particularly effective when the search space is large and the goal state is not immediately visible. By intelligently guiding the search based on heuristic estimates, informed search algorithms can significantly reduce the search effort and find solutions more efficiently than uninformed search algorithms like depth-first search or breadth-first search.

1. Artificial Intelligence Topic : Informed search algorithms by:Dr . Shweta Saraswat

2. informed search algorithm The informed search algorithm is also called heuristic search or directed search. In contrast to uninformed search algorithms, informed search algorithms require details such as distance to reach the goal, steps to reach the goal, cost of the paths which makes this algorithm more efficient. Here, the goal state can be achieved by using the heuristic function . The heuristic function is used to achieve the goal state with the lowest cost possible. This function estimates how close a state is to the goal.

3. heuristic function The heuristic function is used in Informed Search, and it finds the most promising path. It takes the current state of the agent as its input and produces the estimation of how close the agent is from the goal. The heuristic method, however, might not always give the best solution, but it guaranteed to find a good solution in a reasonable time. Heuristic function estimates how close a state is to the goal. It is represented by h(n), and it calculates the cost of an optimal path between the pair of states. The value of the heuristic function is always positive. Admissibility of the heuristic function is given as: h(n) <= h*(n) Here h(n) is heuristic cost, and h*(n) is the estimated cost. Hence heuristic cost should be less than or equal to the estimated cost.

4. 1. Greedy best-first search algorithm Greedy best-first search uses the properties of both depth-first search and breadth-first search. Greedy best-first search traverses the node by selecting the path which appears best at the moment. The closest path is selected by using the heuristic function. Consider the below graph with the heuristic values.

5. Greedy best-first search algorithm

6. Greedy best-first search algorithm Here, A is the start node and H is the goal node. Greedy best-first search first starts with A and then examines the next neighbour B and C. Here, the heuristics of B is 12 and C is 4. The best path at the moment is C and hence it goes to C. From C, it explores the neighbours F and G. the heuristics of F is 8 and G is 2. Hence it goes to G. From G, it goes to H whose heuristic is 0 which is also our goal state.

7. Greedy best-first search algorithm Advantages of Greedy best-first search Greedy best-first search is more efficient compared with breadth-first search and depth-first search. Disadvantages of Greedy best-first search In the worst-case scenario, the greedy best-first search algorithm may behave like an unguided DFS. There are some possibilities for greedy best-first to get trapped in an infinite loop. The algorithm is not an optimal one.

8. 2. A* search algorithm A* search algorithm is a combination of both uniform cost search and greedy best-first search algorithms. It uses the advantages of both with better memory usage. It uses a heuristic function to find the shortest path. A* search algorithm uses the sum of both the cost and heuristic of the node to find the best path.

9. EXAMPLE Consider the following graph with the heuristics values as follows.

10. EXAMPLE Let A be the start node and H be the goal node. First, the algorithm will start with A. From A, it can go to B, C, H. Note the point that A* search uses the sum of path cost and heuristics value to determine the path. Here, from A to B, the sum of cost and heuristics is 1 + 3 = 4. From A to C, it is 2 + 4 = 6. From A to H, it is 7 + 0 = 7. Here, the lowest cost is 4 and the path A to B is chosen. The other paths will be on hold. Now, from B, it can go to D or E. From A to B to D, the cost is 1 + 4 + 2 = 7. From A to B to E, it is 1 + 6 + 6 = 13. The lowest cost is 7. Path A to B to D is chosen and compared with other paths which are on hold. Here, path A to C is of less cost. That is 6. Hence, A to C is chosen and other paths are kept on hold. From C, it can now go to F or G. From A to C to F, the cost is 2 + 3 + 3 = 8. From A to C to G, the cost is 2 + 2 + 1 = 5. The lowest cost is 5 which is also lesser than other paths which are on hold. Hence, path A to G is chosen. From G, it can go to H whose cost is 2 + 2 + 2 + 0 = 6. Here, 6 is lesser than other paths cost which is on hold. Also, H is our goal state. The algorithm will terminate here.

11. A* search algorithm Advantages of A* search algorithm This algorithm is best when compared with other algorithms. This algorithm can be used to solve very complex problems also it is an optimal one. Disadvantages of A* search algorithm The A* search is based on heuristics and cost. It may not produce the shortest path. The usage of memory is more as it keeps all the nodes in the memory.

12. 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.

13. AO* Algorithm

14. AO* Algorithm 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.

15. How AO* works Let's try to understand it with the following diagram

16. How AO* works 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)

17. How AO* works 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.

18. 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.

19. Comparison of uninformed and informed search algorithms Uninformed search is also known as blind search whereas informed search is also called heuristics search. Uniformed search does not require much information. Informed search requires domain-specific details. Compared to uninformed search, informed search strategies are more efficient and the time complexity of uninformed search strategies is more. Informed search handles the problem better than blind search.