Informed search methods Tuomas Sandholm Computer Science Department Carnegie Mellon University Read Section 3.5-3.7 of Russell and NorvigInformed Search MethodsBest-First SearchGreedy SearchGreedy Search…Beam SearchA* SearchA* Search…Slide 9Monotonicity of a heuristicMonotonicity of a heuristic…Completeness of A*Proof of optimality of A* tree searchComplexity of A*A* is optimally efficientGenerating heuristics (h-functions)Heuristics (h(n)) for A*Heuristics (h(n)) for A* …Inventing heuristic functions h(n)More efficient variants of A* search (and approximations)Approximate A* versions (less search effort, but only an approximately optimal solution)Best-bound search = A* search but uses tricks in practiceMemory-bounded search algorithmsIterative Deepening A* (IDA*)IDA* …Slide 26A* vs. IDA*Slide 28Simple Memory-bounded A* (SMA*)SMA* pseudocode (from 1st edition of Russell & Norvig)Informed search methodsTuomas SandholmComputer Science DepartmentCarnegie Mellon UniversityRead Section 3.5-3.7 of Russell and NorvigInformed Search MethodsHeuristic = “to find”, “to discover”• “Heuristic” has many meanings in general• How to come up with mathematical proofs• Opposite of algorithmic• Rules of thumb in expert systems• Improve average case performance, e.g. in CSPs• Algorithms that use low-order polynomial time (and come within a bound of the optimal solution)• % from optimum• % of cases• % PAC• h(n) that estimates the remaining cost from a state to a solutionBest-First Search function BEST-FIRST-SEARCH (problem, EVAL-FN) returns a solution sequence inputs: problem, a problemEval-Fn, an evaluation function Queuing-Fn – a function that orders nodes by EVAL-FN return GENERAL-SEARCH (problem, Queuing-Fn)An implementation of best-first search using the general search algorithm.Usually, knowledge of the problem is incorporated in an evaluation function that describes the desirability of expanding the particular node.If we really knew the desirability, it would not be a search at all. “Seemingly best-first search”f(n)Greedy Searchfunction GREEDY-SEARCH (problem) returns a solution or failure return BEST-FIRST-SEARCH (problem, h)h(n) = estimated cost of the cheapest path from the state at node n to a goal stateGreedy Search…Stages in a greedy search for Bucharest, using the straight-line distance to Bucharest as the heuristic function hSLD. Nodes are labeled with their h-values.Not OptimalIncompleteO(bm) timeO(bm) spaceBeam SearchUse f(n) = h(n) but |nodes|  K• Not complete• Not optimalA* Searchfunction A*-SEARCH (problem) returns a solution or failure return BEST-FIRST-SEARCH (problem, g+h)f(n) = estimated cost of the cheapest solution through n = g(n) + h(n)A* Search…Stages in an A* search for Bucharest. Nodes are labeled with f = g+h. The h values are the straight-line distances to Bucharest.f=291+380=671f=291+380=671A* Search…In a minimization problem, an admissible heuristic h(n) never overestimates the real value(In a maximization problem, h(n) is admissible if it never underestimates)Best-first search using f(n) = g(n) + h(n) and an admissible h(n) is known as A* searchA* tree search is complete & optimalMonotonicity of a heuristich(n) is monotonic if, for every node n and every successor n’ of n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n’ plus the estimated cost of reaching the goal from n’: h(n) ≤ c(n,a,n’) +h(n’). This implies that f(n) (which equals g(n)+h(n)) never decreases along a path from the root. Monotonic heuristic => admissible heuristic.Map of Romania showing contours at f = 380, f = 400 and f = 420, with Arad as the start state. Nodes inside a given contour have f-costs lower than the contour value.With a monotonic heuristic, we can interpret A* as searching through contours:A* expands all nodes n with f(n) < f*, and may expand some nodes right on the “goal contour” (f(n) = f*), before selecting a goal node.With a monotonic heuristic, even A* graph search (i.e., search that deletes later-created duplicates) is optimal.Another option, which requires only admissibility – not monotonicity – is to have the duplicate detector always keep the best (rather than the first) of the duplicates.Monotonicity of a heuristic…Completeness of A*Because A* expands nodes in order of increasing f, it must eventually expand to reach a goal state. This is true unless there are infinitely many nodes with f(n)  f*How could this happen?• There is a node with an infinity branching factor• There is a path with finite path cost but an infinite number of nodes on itSo, A* is complete on graphs with a finite branching factor provided there is some positive constant  s.t. every operator costs at least Proof of optimality of A* tree searchLet G be an optimal goal state, and f(G) = f* = g(G).Let G2 be a suboptimal goal state, i.e. f(G2) = g(G2) > f*.Suppose for contradiction that A* has selected G2 from the queue. (This would terminate A* with a suboptimal solution)Let n be a node that is currently a leaf node on an optimal path to G.Situation at the point where a sub-optimal goal state G2 is about to be picked from the queueBecause h is admissible, f*  f(n). If n is not chosen for expansion over G2, we must have f(n)  f(G2)So, f*  f(G2). Because h(G2)=0, we have f*  g(G2), contradiction.Assumes h is admissible, but does not assume h is monotonicComplexity of A*• Generally O(bd) time and space.• Sub-exponential growth when |h(n) - h*(n)|  O(log h*(n))• Unfortunately, for most practical heuristics, the error is at least proportional to the path costA* is optimally efficient for any given h-function among algorithms that extend search paths from the root. I.e. no other optimal algorithm is guaranteed to expand fewer nodes (for a given search formulation)Intuition: any algorithm that does not expand all nodes in the contours between the root and the goal contour runs the risk of missing the optimal solution.A* is optimally efficientGenerating heuristics (h-functions)Heuristics (h(n)) for A*56741382187 62 345Start state Goal stateA typical instance of the 8-puzzleh1: #tiles in wrong positionh2: sum of Manhattan distances of the tiles from their goal positionsh2 dominates h1: n, h2(n)  h1(n)Heuristics?Heuristics (h(n)) for A* …It is always better to use a heuristic h(n) with