Artificial Intelligence: Informed Search (PDF)

Artificial Intelligence Solving Problems by Searching Informed Search Artificial Intelligence – Solving Problems by Searching Slide ‹#› Search paradigms ◼ Uniformed search ◼ Blind, naïve ◼ Brute force ◼ Informed search ◼ Guided with heuristics Artificia...

Artificial Intelligence Solving Problems by Searching Informed Search Artificial Intelligence – Solving Problems by Searching Slide ‹#› Search paradigms ◼ Uniformed search ◼ Blind, naïve ◼ Brute force ◼ Informed search ◼ Guided with heuristics Artificial Intelligence – Solving Problems by Searching Slide ‹#› 1. Informed Search ◼ What we will learn ◼ Informed search (Heuristic search): Why ◼ Informed search: How ◼ Variants ◼ Algorithms Artificial Intelligence – Solving Problems by Searching Slide ‹#›  Heuristic Search Methods Why ◼ Uninformed search (Blind search) techniques uses no information that may be available about the structure of the tree or availability of goals, or any other information that may help optimize the search. ◼ They simply trudge through the search space until a solution is found. ◼ Most real-world AI problems are susceptible to combinatorial explosion. ◼ A heuristic search makes use of available information in making the search more efficient. Artificial Intelligence – Solving Problems by Searching Slide 4 Heuristic Search Methods Why ◼ It uses heuristics, or rules-of-thumb to help decide ◼ Which parts of a tree shall we explore ◼ Which path shall we take ◼ Optimize the search ◼ A heuristic is a rule or method that almost always improves the decision process. Artificial Intelligence – Solving Problems by Searching Slide 5 Heuristic Search Methods Why Examples of heuristic rules: In a shop with several checkouts, it is usually best to go to the one with the shortest queue. This holds true in most cases but further information could sway this ◼ (1) if you saw that there was a checkout with only one person in that queue but that the person currently at the checkout had three trolleys full of shopping and ◼ (2) that at the fast-checkout all the people had only one item, you may choose to go to the fast-checkout instead. ◼ (3) you don't go to a checkout that doesn't have a cashier - it may have the shortest queue but you'll never get anywhere. Artificial Intelligence – Solving Problems by Searching Slide 6  Uniform cost search ◼ Uses costs associated with paths ◼ This cost is evaluated with a function g(n) tree version Courtesy Algorithmic thoughts word press Artificial Intelligence – Solving Problems by Searching Slide 7  Uniform cost search Start with queue = [initial-state (path)] and found=FALSE. While queue not empty and not found, do: Remove the least-cost path queue. If path ends with goal state, then found = TRUE, return path otherwise Find all the successor nodes of N, append them to the corresponding paths, End While Artificial Intelligence – Solving Problems by Searching Slide 8  Uniform cost search: ◼ The path of the queue in the previous examples evolves as follows ◼ Initial S_0 ◼ 1st itr: SG_12, SA_1 ◼ 2nd:itr: SG_12, SAB_4, SAC_2 ◼ 3rd itr: SG_12, SAB_4, SACG_4, SACD_3 ◼ 4th itr: SG_12, SAB_4, SAC G_4, SACDG_6 ◼ 5th itr: SG_12, SABD_7, SACG_4, SACDG_6 Artificial Intelligence – Solving Problems by Searching Slide 9  Uniform cost search: ◼ Apply Uniform Cost Search to this tree (goal state is E) ◼ Initial A_0 ◼ 1st itr: AB_5, AC_1, AD_2 ◼ 2nd:itr: AB_5, ACE_13, AD_2 ◼ 3rd itr: AB_5, ACE_13, ADE_9 ◼ 4th itr: ABE_11, ACE_13, ADE_9 the minimum path ends with the goal state: the algorithm terminates Artificial Intelligence – Solving Problems by Searching Slide 10 Uniform cost search: ◼ Uniform cost search is complete (i.e. if there is a solution it finds it) ◼ UCS is optimal (i.e., minimum cost path is found) ◼ But it can be highly inefficient: it considers all possible paths regardless of the distance to the target. Artificial Intelligence – Solving Problems by Searching Slide 11 2. Definition of a Heuristic Function ◼ A heuristic function h :  --> R, where  is a set of all states and R is a set of real numbers, maps each state s in the state space  into a measurement h(s) which is an estimate of the relative cost / benefit of extending the partial path through s. ◼ Node A has 3 children. ◼ h(s1)=0.8, h(s2)=2.0, h(s3)=1.6 ◼ The value refers to the cost involved for an action. A continual Figure 5.1 Example Graph based on H(s1) is ‘heuristically’ the best. Artificial Intelligence – Solving Problems by Searching Slide 12  3. Best First Search ◼ A combination of depth first (DFS) and breadth first search (BFS). ◼ DFS is good because a solution can be found without computing all nodes, and BFS is good because it does not get trapped in dead ends. ◼ The Best First Search (BestFS) allows us to switch between paths, thus allowing us to benefit from both approaches. Artificial Intelligence – Solving Problems by Searching Slide 13  BestFS1: Greedy Search ◼ This is one of the simplest BestFS strategy. Artificial Intelligence – Solving Problems by Searching Slide 14  BestFS1: Greedy Search ◼ This is one of the simplest BestFS strategy. ◼ Heuristic function: h(n) - prediction of path cost left to the goal. If n is the goal then h(n) = 0. Artificial Intelligence – Solving Problems by Searching Slide 15 BestFS1: Greedy Search Artificial Intelligence – Solving Problems by Searching Slide 16 BestFS1: Greedy Search Artificial Intelligence – Solving Problems by Searching Slide 17 BestFS1: Greedy Search Artificial Intelligence – Solving Problems by Searching Slide 18 BestFS1: Greedy Search: Algorithm Artificial Intelligence – Solving Problems by Searching Slide 19 BestFS1: Greedy Search (cont) Figure 5.3 Map of Romania with road distances in km, and straight-line distances to Bucharest. hSLD(n) = straight-line distance between n and the goal location. Artificial Intelligence – Solving Problems by Searching Slide 20 Remind: BestFS1: Greedy Search: Algorithm open = [initial-state], Found =false While open not empty and not found Pick the best node n in open. If it is the goal node then found =true Else -Find the children of n -Assign the successor nodes a score using the evaluation function and add the scored nodes to open End While Artificial Intelligence – Solving Problems by Searching Slide 21 Remind: BestFS1: Greedy Search (cont) Figure 5.3 Map of Romania with road distances in km, and straight-line distances to Bucharest. hSLD(n) = straight-line distance between n and the goal location. Artificial Intelligence – Solving Problems by Searching Slide 22 BestFS1: Greedy Search (cont) Stages in a greedy search for Bucharest, using the straight-line distance to Bucharest as the heuristics function hSLD. Nodes are labelled with their h-values. Artificial Intelligence – Solving Problems by Searching Slide 23 Artificial Intelligence – Solving Problems by Searching Slide 24 Artificial Intelligence – Solving Problems by Searching Slide 25 Artificial Intelligence – Solving Problems by Searching Slide 26 Artificial Intelligence – Solving Problems by Searching Slide 27 BestFS1: Greedy Search (cont) ◼ Note that the solution for A ➔ S ➔ F ➔ B is not optimum. It is 32 miles longer than the optimal path A ➔ S ➔ R ➔ P ➔ B. ◼ ASFB = 140 + 99 + 211 =450 ◼ ASRPB = 140 + 80 + 97 + 101 =418 ◼ The strategy takes the best remaining cost to reach the goal, without worrying whether this is the best in the long run - hence the name ‘greedy search’. ◼ GS perform quite well though not always optimal. Artificial Intelligence – Solving Problems by Searching Slide 28 BestFS1: Greedy Search (cont) ◼ GS is susceptible to false start. Consider the case of going from Iasi to Fagaras. Neamt will be consider before Vaslui even though it is a dead end. Artificial Intelligence – Solving Problems by Searching Slide 29 BestFS1: Greedy Search (cont) ◼ GS resembles DFS in the way it prefers to follow a single path all the way to the goal, but can back up when it hits a dead end (with a list of visited nodes). Artificial Intelligence – Solving Problems by Searching Slide 30 BestFS1: Greedy Search (cont) ◼ GS resembles DFS in the way it prefers to follow a single path all the way to the goal but will back up when it hits a dead end (with a list of visited nodes). ◼ Thus, suffering the same defects as DFS - not optimal and incomplete. ◼ Not optimal: not the best solution, as we saw in the last examples ◼ Incomplete: can get stuck in loops (unless we record the visited nodes (the explored set)) Artificial Intelligence – Solving Problems by Searching Slide 31 BestFS1: Greedy Search (cont) ◼ The worst-case time complexity for GS is O(bm), where m is the max depth of the search space. ◼ With good heuristic function, the space and time complexity can be reduced substantially. ◼ The amount of reduction depends on the particular problem and the quality of h function. Artificial Intelligence – Solving Problems by Searching Slide 32 BestFS2: A* Search ◼ GS minimizes the estimated cost to the goal, h(n), thereby cutting the search cost considerably - but it is not optimal and incomplete. ◼ UCS minimizes the path’s cost so far, g(n), and is optimal and complete but can be very inefficient. ◼ A* Search combines both GS h(n) and UCS g(n) to give f(n) , which estimates the cost of the cheapest solution through n, i.e., f(n) = g(n) + h(n). ◼ h(n) must be an admissible solution, ie. It never overestimates the actual cost of the best solution through n. ◼ h(n)