CMSC 471 Fall 2002Today’s classInformed Search Chapter 4HeuristicInformed methods add domain-specific informationHeuristicsWeak vs. strong methodsBest-first searchGreedy searchBeam searchAlgorithm ASlide 12Algorithm A*Some observations on AExample search spaceExampleSlide 17A* searchProof of the optimality of A*Dealing with hard problemsWhat’s a good heuristic?Iterative improvement searchHill climbing on a surface of statesHill-climbing searchHill climbing exampleDrawbacks of hill climbingExample of a local maximumSimulated annealingSimulated annealing (cont.)The simulated annealing algorithmSummary: Informed searchCMSC 471CMSC 471Fall 2002Fall 2002Class #5-6 – Monday, September 16 /Wednesday, September 18Today’s class•Heuristic search•Bestfirst search–Greedy search–Beam search–A, A*–Examples•Memory-conserving variations of A*•Heuristic functions•Iterative improvement methods–Hill climbing–Simulated annealingInformedInformedSearchSearchChapter 4Chapter 4Some material adopted from notes by Charles R. Dyer, University of Wisconsin-MadisonHeuristicWebster's Revised Unabridged Dictionary (1913) (web1913)Heuristic \Heu*ris"tic\, a. [Gr. ? 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 methods add domain-specific information•Add domain-specific information to select the best path along which to continue searching•Define 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 goalHeuristics•All domain knowledge used in the search is encoded in the heuristic function h. •Heuristic search is an example of a “weak method” because of the limited way that domain-specific information is used to solve the problem. •Examples:–Missionaries and Cannibals: Number of people on starting river bank–8-puzzle: Number of tiles out of place –8-puzzle: Sum of distances each tile is from its goal position •In general:–h(n) >= 0 for all nodes n –h(n) = 0 implies that n is a goal node –h(n) = infinity implies that n is a dead-end from which a goal cannot be reachedWeak vs. strong methods•We use the term weak methods to refer to methods that are extremely general and not tailored to a specific situation. •Examples of weak methods include –Means-ends analysis is a strategy in which we try to represent the current situation and where we want to end up and then look for ways to shrink the differences between the two. –Space splitting is a strategy in which we try to list the possible solutions to a problem and then try to rule out classes of these possibilities. –Subgoaling means to split a large problem into several smaller ones that can be solved one at a time.•Called “weak” methods because they do not take advantage of more powerful domain-specific heuristicsBest-first search•Order nodes on the nodes list by increasing value of an evaluation function, f(n), that incorporates domain-specific information in some way. •This is a generic way of referring to the class of informed methods.Greedy search•Use as an evaluation function f(n) = h(n), sorting nodes by increasing values of f.•Selects node to expand believed to be closest (hence “greedy”) to a goal node (i.e., select node with smallest f value) •Not complete •Not admissible, as in the example. Assuming all arc costs are 1, then greedy search will find goal g, which has a solution cost of 5, while the optimal solution is the path to goal I with cost 3. agbcdeghih=2h=1h=1h=1h=0h=4h=1h=0Beam search•Use an evaluation function f(n) = h(n), but the maximum size of the nodes list is k, a fixed constant •Only keeps k best nodes as candidates for expansion, and throws the rest away •More space efficient than greedy search, but may throw away a node that is on a solution path •Not complete •Not admissibleAlgorithm A•Use as an evaluation functionf(n) = g(n) + h(n)•g(n) = minimal-cost path from the start state to state n. •The g(n) term adds a “breadth-first” component to the evaluation function.•Ranks nodes on search frontier by estimated cost of solution from start node through the given node to goal. •Not complete if h(n) can equal infinity.•Not admissible. SBADG1583815C194589g(d)=4h(d)=9C is chosen next to expandAlgorithm A1. Put the start node S on the nodes list, called OPEN 2. If OPEN is empty, exit with failure 3. Select node in OPEN with minimal f(n) and place on CLOSED4. If n is a goal node, collect path back to start and stop.5. Expand n, generating all its successors and attach to them pointers back to n. For each successor n' of n 1. If n' is not already on OPEN or CLOSED•put n ' on OPEN•compute h(n'), g(n')=g(n)+ c(n,n'), f(n')=g(n')+h(n')2. If n' is already on OPEN or CLOSED and if g(n') is lower for the new version of n', then:•Redirect pointers backward from n' along path yielding lower g(n').•Put n' on OPEN.Algorithm A*•Algorithm A with constraint that h(n) <= h*(n)•h*(n) = true cost of the minimal cost path from n to a goal. •h is admissible when h(n) <= h*(n) holds.•Using an admissible heuristic guarantees that the first solution found will be an optimal one. •A* is complete whenever the branching factor is finite, and every operator has a fixed positive cost •A* is admissibleSome observations on A•Perfect heuristic: If h(n) = h*(n) for all n, then only the nodes on the optimal solution path will be expanded. So, no extra work will be performed. •Null heuristic: If h(n) = 0 for all n, then this is an admissible heuristic