1Heuristic SearchHeuristic SearchRussell and Norvig: Chapter 4CSMSC 421 – Fall 2003Modified Search AlgorithmModified Search Algorithm1. INSERT(initial-node,FRINGE)2. Repeat:If FRINGE is empty then return failuren Å REMOVE(FRINGE)s Å STATE(n)If GOAL?(s) then return path or goal stateFor every state s’ in SUCCESSORS(s) Create a node n’ INSERT(n’,FRINGE)Search 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 searchIdea: use an evaluation function f(n) for each node Estimate of desirabilityExpand most desirable unexpanded nodeImplementation: fringe is queue sorted by descreasing order of desirability Greedy search A* search2HeuristicWebster'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.6heuristic 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 goal Greedy SearchGreedy Searchf(N) = h(N) Æ greedy best-firstRobot NavigationRobot Navigation3Robot NavigationRobot Navigation02115877347676328645233365 244355465645f(N) = h(N), with h(N) = Manhattan distance to the goalRobot NavigationRobot Navigation02115877347676328645233365 244355465645f(N) = h(N), with h(N) = Manhattan distance to the goal70What happened???Greedy SearchGreedy Searchf(N) = h(N) Æ greedy best-firstIs it complete?If we eliminate endless loops, yesIs it optimal?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 overalllength of the path to the goal!Let g(N) be the cost of the bestpath found so far between the initial node and Nf(N) = g(N) + h(N)4Robot NavigationRobot Navigationf(N) = g(N)+h(N), with h(N) = Manhattan distance to goal02115877347676328645233365 2443554656457+06+16+18+17+07+26+17+26+18+17+28+37+2 6+36+3 5+45+4 4+54+5 3+63+6 2+78+3 7+47+4 6+55+66+3 5+62+7 3+84+75+6 4+73+84+7 3+83+8 2+92+93+102+93+82+91+101+10 0+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 states, the search is in general not completeIf the state space is infinite, the search is in general not completeAdmissible heuristicAdmissible heuristicLet h*(N) be the true cost of the optimal path from N to a goal nodeHeuristic h(N) is admissible if: 0 ≤ h(N) ≤ h*(N)An admissible heuristic is always optimisticA* SearchA* SearchEvaluation function:f(N) = g(N) + h(N)where: g(N) is the cost of the best path found so far to N h(N) is an admissible heuristicThen, best-first search with this evaluation function is called A* searchImportant AI algorithm developed by Fikes and Nilsson in early 70s. Originally used in Shakey robot.5Completeness & Optimality of A*Completeness & Optimality of A*Claim 1: If there is a path from the initial to a goal node, A* (with no removal of repeated states) terminates by finding the best path, hence is: complete optimalrequirements: 0 < ε ≤ c(N,N’) Each node has a finite number of successorsCompleteness of A*Completeness of A*Theorem: If there is a finite path from the initial state to a goal node, A* will find it.Proof of CompletenessProof of CompletenessLet g be the cost of a best path to a goal nodeNo path in search tree can get longer than g/ε, before the goal node is expandedOptimality of A*Optimality of A*Theorem: If h(n) is admissable, then A* is optimal.6Proof of OptimalityProof of OptimalityG1NG2f(G1) = g(G1)f(N) = g(N) + h(N) ≤ g(N) + h*(N)f(G1) ≤ g(N) + h(N) ≤ g(N) + h*(N)Cost of best path to a goal thru NHeuristic FunctionHeuristic FunctionFunction h(N) that estimate the cost of the cheapest path from node N to goal node.Example: 8-puzzle1234567812345678Ngoalh(N) = number of misplaced tiles= 6Heuristic FunctionHeuristic FunctionFunction h(N) that estimate the cost of the cheapest path from node N to goal node.Example: 8-puzzle1234567812345678Ngoalh(N) = sum of the distances of every tile to its goal position= 2 + 3 + 0 + 1 + 3 + 0 + 3 + 1= 1388--PuzzlePuzzle4553343 442 120343f(N) = h(N) = number of misplaced tiles788--PuzzlePuzzle0+41+51+51+33+33+43+43+2 4+15+25+02+32+42+3f(N) = g(N) + h(N) with h(N) = number of misplaced tiles88--PuzzlePuzzle566442 120553f(N) = h(N) = Σ distances of tiles to goal88--PuzzlePuzzle1234567812345678Ngoal•h1(N) = number of misplaced tiles = 6 is admissible•h2(N) = sum of distances of each tile to goal = 13is admissible•h3(N) = (sum of distances of each tile to goal)+ 3 x (sum of score functions for each tile) = 49is not admissibleRobot navigationRobot navigationCost of one horizontal/vertical step = 1Cost of one diagonal step = √2f(N) = g(N) + h(N), with h(N) = straight-line distance from N to goal8Search Problems from last time…Consistent HeuristicConsistent HeuristicThe admissible heuristic h is consistent(or satisfies the monotone restriction) if for every node N and every successor N’ of N:h(N) ≤ c(N,N’) + h(N’)(triangular