Informed SearchOutlinePreviously: Graph search algorithmBlind Search…Search AlgorithmsBest-first searchHeuristicSlide 8Greedy Best-First SearchRobot NavigationSlide 11Slide 12Greedy SearchMore informed searchA* searchSlide 16Can we Prove Anything?Admissible heuristicOptimality of A*(standard proof)BUT … graph searchConsistencyOptimality of A*(more useful)A* search, evaluationSlide 24Slide 25Slide 26Memory-bounded heuristic searchRecursive best-first searchSlide 29RBFS evaluation(simplified) memory-bounded A*Heuristic functionsHeuristic FunctionSlide 378-PuzzleSlide 39Slide 40Slide 41Heuristic qualityHeuristic quality and dominanceInventing admissible heuristicsAnother approach… Local SearchLocal search and optimizationSlide 47Hill-climbing searchSlide 49Slide 50Examples of problems with HCDrawbacks of hill climbingHill-climbing variationsSimulated annealingSlide 57Simulated AnnealingLocal beam searchWhen to Use Search Techniques?Summary: Informed SearchInformed SearchInformed SearchRussell and Norvig: Ch. 4.1 - 4.3CSMSC 421 – Fall 2006OutlineInformed = use problem-specific knowledgeWhich search strategies?Best-first search and its variantsHeuristic functions?How to invent themLocal search and optimizationHill climbing, simulated annealing, local beam search,…Previously: Graph search algorithmfunction GRAPH-SEARCH(problem,fringe) return a solution or failureclosed  an empty setfringe  INSERT(MAKE-NODE(INITIAL-STATE[problem]), fringe)loop doif EMPTY?(fringe) then return failurenode  REMOVE-FIRST(fringe)if GOAL-TEST[problem] applied to STATE[node] succeedsthen return SOLUTION(node)if STATE[node] is not in closed thenadd STATE[node] to closedfringe  INSERT-ALL(EXPAND(node, problem), fringe)A strategy is defined by picking the order of node expansionBlind Search……[the ant] knew that a certain arrangement had to be made, but it could not figure out how to make it. It was like a man with a tea-cup in one hand and a sandwich in the other, who wants to light a cigarette with a match. But, where the man would invent the idea of putting down the cup and sandwich—before picking up the cigarette and the match—this ant would have put down the sandwich and picked up the match, then it would have been down with the match and up with the cigarette, then down with the cigarette and up with the sandwich, then down with the cup and up with the cigarette, until finally it had put down the sandwich and picked up the match. It was inclined to rely on a series of accidents to achieve its object. It was patient and did not think… Wart watched the arrangements with a surprise which turned into vexation and then into dislike. He felt like asking why it did not think things out in advance… T.H. White, The Once and Future KingSearch AlgorithmsBlind search – BFS, DFS, uniform costno notion concept of the “right direction”can only recognize goal once it’s achievedHeuristic search – we have rough idea of how good various states are, and use this knowledge to guide our searchBest-first searchGeneral approach of informed search:Best-first search: node is selected for expansion based on an evaluation function f(n)Idea: evaluation function measures distance to the goal. Choose node which appears bestImplementation:fringe is queue sorted in decreasing order of desirability.Special cases: Greedy search, A* searchHeuristicWebster's Revised Unabridged Dictionary (1913) (web1913)Heuristic \Heu*ris"tic\, a. [Greek. to discover.] Serving to discover or find out. The Free On-line Dictionary of Computing (15Feb98) heuristic 1. <programming> A rule of thumb, simplification or educated guess that reduces or limits the search for solutions in domains that are difficult and poorly understood. Unlike algorithms, heuristics do not guarantee feasible solutions and are often used with no theoretical guarantee. 2. <algorithm> approximation algorithm. From WordNet (r) 1.6 heuristic adj 1: (computer science) relating to or using a heuristic rule 2: of or relating to a general formulation that serves to guide investigation [ant: algorithmic] n : a commonsense rule (or set of rules) intended to increase the probability of solving some problem [syn: heuristic rule, heuristic program]Informed SearchAdd domain-specific information to select the best path along which to continue searchingDefine a heuristic function, h(n), that estimates the “goodness” of a node n. Specifically, h(n) = estimated cost (or distance) of minimal cost path from n to a goal state. The heuristic function is an estimate, based on domain-specific information that is computable from the current state description, of how close we are to a goalGreedy Best-First SearchGreedy Best-First Search f(N) = h(N)  greedy best-firstRobot NavigationRobot NavigationRobot NavigationRobot Navigation0 21158 77347676 3 2864523 336 5 24 43 554 65645f(N) = h(N), with h(N) = Manhattan distance to the goalRobot NavigationRobot Navigation0 21158 77347676 3 2864523 336 5 24 43 554 65645f(N) = h(N), with h(N) = Manhattan distance to the goal70What happened???Greedy SearchGreedy Search f(N) = h(N)  Greedy best-firstIs it complete?Is it optimal?Time complexity?Space complexity?More informed searchMore informed searchWe kept looking at nodes closer and closer to the goal, but were accumulating costs as we got further from the initial stateOur goal is not to minimize the distance from the current head of our path to the goal, we want to minimize the overall length of the path to the goal!Let g(N) be the cost of the best path found so far between the initial node and N f(N) = g(N) + h(N)  A*A* searchBest-known form of best-first search.Idea: avoid expanding paths that are already expensive.Evaluation function f(n)=g(n) + h(n)  A*g(n) the cost (so far) to reach the node.h(n) estimated cost to get from the node to the goal.f(n) estimated total cost of path through n to goal.Robot NavigationRobot Navigationf(N) = g(N)+h(N), with h(N) = Manhattan distance to goal0 21158 77347676 3 2864523 336 5 24 43 554 656457+06+16+18+17+07+26+17+26+18+17+28+37+26+36+35+45+44+54+53+63+62+78+37+47+46+55+66+35+62+73+84+75+64+73+84+73+83+82+92+93+102+93+82+91+101+100+11Can we Prove Anything?Can we Prove Anything?If the state space is finite and we avoid repeated states, the search is complete, but in general is not optimalIf the state space is finite and we do not avoid repeated