CSEP 573 Chapters 3-5 Problem Solving using Search

1 1 Chapters 3-5 Problem Solving using SearchChapters 3-5 Problem Solving using SearchCSEP 573 CSE AI Faculty First, they do an on-line Search 2 Example: The 8-puzzleExample: The 8-puzzle123675841238754623 Example: Route PlanningExample: Route Planningstartend4 Example: N QueensExample: N Queens4 Queens35 Example: N QueensExample: N Queens4 Queens6 State-Space Search ProblemsState-Space Search ProblemsGeneral Problem :Given a start state, find a path to a goal state Can test if a state is a goal Given a state, can generate its successorstates Variants: Find any path least-cost path Goal is completely specified, task is just to find the path Route planning Path doesn t matter, only finding the goal state 8 puzzle, N queens47 Tree Representation of 8-Puzzle Problem SpaceTree Representation of 8-Puzzle Problem Space8fringe(= frontierin the textbook) is the set of all leaf nodes available for expansion 5910action = Rightchildren61112713148151691718101920= O(bd), , exponential in d 1121= O(bd), , exponential in d O(bd)22 Space is the big Problem for BFS.

2 Example: b = 10, 10,000 nodes/sec, 1KB/node d = 3 1000 nodes, sec, 1 MBd = 5 100,000 nodes, 10 secs, 100 MBd = 9 109nodes, 31 hours, 1 TB= O(bd), , exponential in d O(bd)1223(usepriority queue)(used when step costs are unequal)(small positive constant; 0 cost may cause infinite loop)24132526142728152930163132173334183 5361937( GRAPH- Search in textbook) 38(m= maximum depth)( GRAPH- Search in textbook) 203940(may find a solution but least cost solution may be on a different branch)214142224344234546244748254950265 1 Increasing path-cost limits instead of depth limitsThis is called Iterative lengthening Search (exercise )522753 Forwards : Find the shortest route54 Bidirectional SearchBidirectional SearchMotivation.

3 Bd/2+ bd/2<< bdCan use breadth-first Search or uniform-cost searchHard for implicit goals , goal = checkmate in chess2855 Repeated StatesRepeated StatesFailure to detect repeated states can turn a linear Problem into an exponential one! ( , repeated states in 8 puzzle)Graph Search algorithm: Store expanded nodes in a set called closed(or explored) and only add new nodes to the fringe56 Graph SearchGraph Search2957 All these methods are slow (blind)Can we do better?58 Informed SearchInformed SearchUse Problem -specific knowledge to guide Search (use heuristic function )3059 Best-first SearchBest-first SearchGeneralization of breadth first searchPriority queue of nodes to be exploredEvaluation function f(n)used for each nodeInsert initial state into priority queueWhile queue not emptyNode = head(queue)If goal(node) then return nodeInsert children of node into pr.

4 Queue60 Who s on (best) first?Who s on (best) first?Breadth first Search is special case of best first with f(n) = depth(n)Dijkstra s Algorithm is best first with f(n) = g(n)where g(n) = sum of edge costs from start to n3161 Greedy best-first searchGreedy best-first searchEvaluation function f(n) = h(n) ( heuristic ) = estimate of cost from nto , Route finding problems: hSLD(n)= straight-line distance from nto destinationGreedy best-first Search expands the node that appearsto be closest to goal62 Example: Lost in RomaniaExample: Lost in RomaniaNeed: Shortest path from Arad to Bucharest3263 Example.

5 Greedily Searching for BucharestExample: Greedily Searching for BucharesthSLD(Arad)64 Example: Greedily Searching for BucharestExample: Greedily Searching for Bucharest3365 Example: Greedily Searching for BucharestExample: Greedily Searching for Bucharest66 Example: Greedily Searching for BucharestExample: Greedily Searching for BucharestNot optimal! Arad, Sibiu, Rimnicu Vilcea, Pitesti, Bucharest shorterGreed doesn t pay!3467 Properties of Greedy Best-First SearchProperties of Greedy Best-First SearchComplete?No can get stuck in loops (unless closedlist is used)Time?O(bm), but a good heuristic can give dramatic improvement Space?

6 O(bm) -- keeps all nodes in memory a labreadth first searchOptimal?No, as our example illustrated68A* Search (Hart, Nilsson & Rafael 1968)A* Search (Hart, Nilsson & Rafael 1968) Best first Search with f(n) = g(n) + h(n)g(n) = sum of edge costs from start to n h(n) = heuristic function= estimate of lowest cost path from n to goal If h(n) is admissible then Search will be optimalUnderestimates cost of any solution which can be reached from node{3569 Back in Romania AgainBack in Romania AgainendstartAici noienergieiar!70A* Example for RomaniaA* Example for Romaniaf(n) = g(n) + h(n) whereg(n) = sum of edge costs from start to n h(n) = hSLD(n)= straight-line distance from nto destination3671A* ExampleA* Example72A* ExampleA* Example3773A* ExampleA* Example74A* ExampleA* Example3875A* ExampleA* Example76 Admissible heuristicsAdmissible heuristicsA heuristic h(n)is admissibleif for every node n,h(n) h*(n)where h*(n)}

7 Is the true cost to reach the goal state from admissible heuristic never overestimatesthe cost to reach the goal, , it is optimistic3977 Admissible HeuristicsAdmissible HeuristicsIs the Straight Line Distance heuristic hSLD(n) admissible? 78 Admissible HeuristicsAdmissible HeuristicsIs the Straight Line Distance heuristic hSLD(n) admissible? Yes, it never overestimates the actual road distanceTheorem: If h(n) is admissible, A* using TREE- Search is of A*(proof)Optimality of A*(proof)Suppose some suboptimal goal G2has been generated and is in the fringe. Let nbe an unexpanded node in the fringe such that n is on a shortest path to an optimal goal (G2) = g(G2)since h(G2) = 0 > g(G) since G2is suboptimal f(G) = g(G)since h(G) = 0 f(G2) > f(G)from above 80 Optimality of A*(cont.)

8 Optimality of A*(cont.)Suppose some suboptimal goal G2has been generated and is in the fringe. Let nbe an unexpanded node in the fringe such that n is on a shortest path to an optimal goal (G2) > f(G) from prev slide h(n) h*(n)since h is admissibleg(n) + h(n) g(n) + h*(n) f(n) f(G) < f(G2)Hence f(n) < f(G2) A*will never select G2for of A*Optimality of A*A*expands nodes in order of increasing fvalueGradually adds "f-contours" of nodes82 Okay, proof is done!Time to wake , proof is done!Time to wake rocks!4283 Properties of A*Properties of A*Complete?Yes (unless there are infinitely many nodes with f f(G) )Time?

9 Exponential (for most heuristic functions in practice)Space?Keeps all generated nodes in memory (exponential number of nodes)Optimal?Yes84 Admissible heuristicsAdmissible , for the 8-puzzle, what are some admissible heuristic functions? (for # steps to goal state)h1(n) = ?h2(n) = ?4385 Admissible heuristicsAdmissible , for the 8-puzzle:h1(n) = number of misplaced tilesh2(n) = total Manhattan distance (no. of squares from desired location of each tile)h1(S) = ? h2(S) = ?S86 Admissible heuristicsAdmissible , for the 8-puzzle:h1(n) = number of misplaced tilesh2(n) = total Manhattan distance (no.)

10 Of squares from desired location of each tile)h1(S) = ?8h2(S) = ?3+1+2+2+2+3+3+2 = 184487 DominanceDominanceIf h2(n) h1(n)for all n(both admissible) then h2dominatesh1h2is better for , for 8-puzzle heuristics h1and h2, typical Search costs (average number of nodes expanded for solution depth d):d=12 IDS = 3,644,035 nodesA*(h1) = 227 nodes A*(h2) = 73 nodes d=24 IDS = too many nodesA*(h1) = 39,135 nodes A*(h2) = 1,641 nodes45In general, A* not practical for large scale problems due to memory requirements (all generated nodes in memory)In general, A* not practical for large scale problems due to memory requirements (all generated nodes in memory)Idea.