№  Слайд  Текст 
1 

Lecture 4: Informed/Heuristic SearchICS 271 Fall 2007 
2 

Organizational itemsHomework 1 Due Thursday in class Problem 3.12 in text: 2nd part, IDS: some printings say “constant step cost”, others say “variable step costs” Assume either one, state clearly in your solution 
3 

OutlineLimitations of uninformed search methods Informed (or heuristic) search uses problemspecific heuristics to improve efficiency Bestfirst A* RBFS SMA* Techniques for generating heuristics Can provide significant speedups in practice e.g., on 8puzzle But can still have worstcase exponential time complexity Reading: Chapter 4, Sections 4.1 and 4.2 
4 

Limitations of uninformed search8puzzle Avg. solution cost is about 22 steps branching factor ~ 3 Exhaustive search to depth 22: 3.1 x 1010 states E.g., d=12, IDS expands 3.6 million states on average [24 puzzle has 1024 states (much worse)] 
5 

Recall tree search… 
6 

Recall tree search…This “strategy” is what differentiates different search algorithms 
7 

Bestfirst searchIdea: use an evaluation function f(n) for each node estimate of "desirability“ Expand most desirable unexpanded node Implementation: Order the nodes in fringe by f(n) (by desirability, lowest f(n) first) Special cases: uniform cost search (from last lecture): f(n) = g(n) = path to n greedy bestfirst search A* search Note: evaluation function is an estimate of node quality => More accurate name for “best first” search would be “seemingly bestfirst search” 
8 

Heuristic functionHeuristic: Definition: “using rules of thumb to find answers” Heuristic function h(n) Estimate of (optimal) cost from n to goal h(n) = 0 if n is a goal node Example: straight line distance from n to Bucharest Note that this is not the true statespace distance It is an estimate – actual statespace distance can be higher Provides problemspecific knowledge to the search algorithm 
9 

Heuristic functions for 8puzzle8puzzle Avg. solution cost is about 22 steps branching factor ~ 3 Exhaustive search to depth 22: 3.1 x 1010 states. A good heuristic function can reduce the search process. Two commonly used heuristics h1 = the number of misplaced tiles h1(s)=8 h2 = the sum of the distances of the tiles from their goal positions (Manhattan distance). h2(s)=3+1+2+2+2+3+3+2=18 
10 

Greedy bestfirst searchSpecial case of bestfirst search Uses h(n) = heuristic function as its evaluation function Expand the node that appears closest to goal 
11 

Romania with step costs in km 
12 

Greedy bestfirst search example 
13 

Greedy bestfirst search example 
14 

Greedy bestfirst search example 
15 

Greedy bestfirst search example 
16 

Optimal Path 
17 

Properties of greedy bestfirst searchComplete? Not unless it keeps track of all states visited Otherwise can get stuck in loops (just like DFS) Optimal? No – we just saw a counterexample Time? O(bm), can generate all nodes at depth m before finding solution m = maximum depth of search space Space? O(bm) – again, worst case, can generate all nodes at depth m before finding solution 
18 

A* SearchExpand node based on estimate of total path cost through node Evaluation function f(n) = g(n) + h(n) g(n) = cost so far to reach n h(n) = estimated cost from n to goal f(n) = estimated total cost of path through n to goal Efficiency of search will depend on quality of heuristic h(n) 
19 

A* search example 
20 

A* search example 
21 

A* search example 
22 

A* search example 
23 

A* search example 
24 

A* search example 
25 

Admissible heuristicsA heuristic h(n) is admissible if for every node n, h(n) ? h*(n), where h*(n) is the true cost to reach the goal state from n. An admissible heuristic never overestimates the cost to reach the goal, i.e., it is optimistic Example: hSLD(n) is admissible never overestimates the actual road distance Theorem: If h(n) is admissible, A* using TREESEARCH is optimal 
26 

Optimality of A* (proof)Suppose some suboptimal goal G2 has been generated and is in the fringe. Let n be an unexpanded node in the fringe such that n is on a shortest path to an optimal goal G. f(G2) = g(G2) since h(G2) = 0 g(G2) > g(G) since G2 is suboptimal f(G) = g(G) since h(G) = 0 f(G2) > f(G) from above 
27 

Optimality of A* (proof)Suppose some suboptimal goal G2 has been generated and is in the fringe. Let n be an unexpanded node in the fringe such that n is on a shortest path to an optimal goal G. f(G2) > f(G) from above h(n) ? h*(n) since h is admissible g(n) + h(n) ? g(n) + h*(n) f(n) ? f(G) Hence f(G2) > f(n), and A* will never select G2 for expansion 
28 

Optimality for graphsAdmissibility is not sufficient for graph search In graph search, the optimal path to a repeated state could be discarded if it is not the first one generated Can fix problem by requiring consistency property for h(n) A heuristic is consistent if for every successor n' of a node n generated by any action a, h(n) ? c(n,a,n') + h(n') (aka “monotonic”) admissible heuristics are generally consistent 
29 

A* is optimal with consistent heuristicsIf h is consistent, we have f(n') = g(n') + h(n') = g(n) + c(n,a,n') + h(n') ? g(n) + h(n) = f(n) i.e., f(n) is nondecreasing along any path. Thus, first goalstate selected for expansion must be optimal Theorem: If h(n) is consistent, A* using GRAPHSEARCH is optimal 
30 

Contours of A* SearchA* expands nodes in order of increasing f value Gradually adds "fcontours" of nodes Contour i has all nodes with f=fi, where fi < fi+1 
31 

Contours of A* SearchWith uniformcost (h(n) = 0, contours will be circular With good heuristics, contours will be focused around optimal path A* will expand all nodes with cost f(n) < C* 
32 

Properties of A*Complete? Yes (unless there are infinitely many nodes with f ? f(G) ) Optimal? Yes Also optimally efficient: No other optimal algorithm will expand fewer nodes, for a given heuristic Time? Exponential in worst case Space? Exponential in worst case 
33 

Comments on A*A* expands all nodes with f(n) < C* This can still be exponentially large Exponential growth will occur unless error in h(n) grows no faster than log(true path cost) In practice, error is usually proportional to true path cost (not log) So exponential growth is common 
34 

Memorybounded heuristic searchIn practice A* runs out of memory before it runs out of time How can we solve the memory problem for A* search? Idea: Try something like depth first search, but let’s not forget everything about the branches we have partially explored. 
35 

Recursive BestFirst Search (RBFS)Similar to DFS, but keeps track of the fvalue of the best alternative path available from any ancestor of the current node If current node exceeds flimit > backtrack to alternative path As it backtracks, replace fvalue of each node along the path with the best f(n) value of its children This allows it to return to this subtree, if it turns out to look better than alternatives 
36 

Recursive Best First Search: ExamplePath until Rumnicu Vilcea is already expanded Above node; flimit for every recursive call is shown on top. Below node: f(n) The path is followed until Pitesti which has a fvalue worse than the flimit. 
37 

RBFS exampleUnwind recursion and store best fvalue for current best leaf Pitesti result, f [best] ? RBFS(problem, best, min(f_limit, alternative)) best is now Fagaras. Call RBFS for new best best value is now 450 
38 

RBFS exampleUnwind recursion and store best fvalue for current best leaf Fagaras result, f [best] ? RBFS(problem, best, min(f_limit, alternative)) best is now Rimnicu Viclea (again). Call RBFS for new best Subtree is again expanded. Best alternative subtree is now through Timisoara. Solution is found since because 447 > 418. 
39 

RBFS propertiesLike A*, optimal if h(n) is admissible Time complexity difficult to characterize Depends on accuracy if h(n) and how often best path changes. Can end up “switching” back and fortyh Space complexity is O(bd) Other extreme to A*  uses too little memory. 
40 

(Simplified) Memorybounded A* (SMA*)This is like A*, but when memory is full we delete the worst node (largest fvalue). Like RBFS, we remember the best descendant in the branch we delete. If there is a tie (equal fvalues) we delete the oldest nodes first. simplifiedMA* finds the optimal reachable solution given the memory constraint. Time can still be exponential. 
41 

Heuristic functions8puzzle Avg. solution cost is about 22 steps branching factor ~ 3 Exhaustive search to depth 22: 3.1 x 1010 states. A good heuristic function can reduce the search process. Two commonly used heuristics h1 = the number of misplaced tiles h1(s)=8 h2 = the sum of the distances of the tiles from their goal positions (manhattan distance). h2(s)=3+1+2+2+2+3+3+2=18 
42 

Notion of dominanceIf h2(n) ? h1(n) for all n (both admissible) then h2 dominates h1 h2 is better for search Typical search costs (average number of nodes expanded) for 8puzzle problem d=12 IDS = 3,644,035 nodes A*(h1) = 227 nodes A*(h2) = 73 nodes d=24 IDS = too many nodes A*(h1) = 39,135 nodes A*(h2) = 1,641 nodes 
43 

Effective branching factorEffective branching factor b* Is the branching factor that a uniform tree of depth d would have in order to contain N+1 nodes. Measure is fairly constant for sufficiently hard problems. Can thus provide a good guide to the heuristic’s overall usefulness. 
44 

Effectiveness of different heuristicsResults averaged over random instances of the 8puzzle 
45 

Inventing heuristics via “relaxed problems”A problem with fewer restrictions on the actions is called a relaxed problem The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem If the rules of the 8puzzle are relaxed so that a tile can move anywhere, then h1(n) gives the shortest solution If the rules are relaxed so that a tile can move to any adjacent square, then h2(n) gives the shortest solution Can be a useful way to generate heuristics E.g., ABSOLVER (Prieditis, 1993) discovered the first useful heuristic for the Rubik’s cube puzzle 
46 

More on heuristicsh(n) = max{ h1(n), h2(n),……hk(n) } Assume all h functions are admissible Always choose the least optimistic heuristic (most accurate) at each node Could also learn a convex combination of features Weighted sum of h(n)’s, where weights sum to 1 Weights learned via repeated puzzlesolving Could try to learn a heuristic function based on “features” E.g., x1(n) = number of misplaced tiles E.g., x2(n) = number of goaladjacentpairs that are currently adjacent h(n) = w1 x1(n) + w2 x2(n) Weights could be learned again via repeated puzzlesolving Try to identify which features are predictive of path cost 
47 

Pattern databasesAdmissible heuristics can also be derived from the solution cost of a subproblem of a given problem. This cost is a lower bound on the cost of the real problem. Pattern databases store the exact solution to for every possible subproblem instance. The complete heuristic is constructed using the patterns in the DB 
48 

SummaryUninformed search methods have their limits Informed (or heuristic) search uses problemspecific heuristics to improve efficiency Bestfirst A* RBFS SMA* Techniques for generating heuristics Can provide significant speedups in practice e.g., on 8puzzle But can still have worstcase exponential time complexity Next lecture: local search techniques Hillclimbing, genetic algorithms, simulated annealing, etc 
«InformedHeuristic Search» 