Slide 1Best-first searchRomania with step costs in kmGreedy best-first searchGreedy best-first search exampleGreedy best-first search exampleGreedy best-first search exampleGreedy best-first search exampleProperties of greedy best-first searchSide Discussion “Greedy Algorithms”A* searchA* search exampleA* search exampleA* search exampleA* search exampleA* search exampleA* search exampleAdmissible heuristicsOptimality of A* (proof)Consistent heuristicsAdmissible heuristicsDominanceSlide 23Slide 24Discussion of Greedy Search, A*and SMA*Best-first search•Idea: use an evaluation function f(n) for each nodeestimate of "desirability"Expand most desirable unexpanded node•Implementation:•Order the nodes in fringe in decreasing order of desirability•Special cases:–greedy best-first search–A* search–A* variations such as SMA*Romania with step costs in kmGreedy best-first search•Evaluation function f(n) = h(n) (heuristic): estimate of cost from n to goal•e.g., hSLD(n) = straight-line distance from n to Bucharest•Greedy best-first search expands the node that appears to be closest to goalGreedy best-first search exampleGreedy best-first search exampleGreedy best-first search exampleGreedy best-first search exampleProperties of greedy best-first search•Complete? No – can get stuck in loops, e.g., Iasi  Neamt  Iasi  Neamt  •Time? O(bm), but a good heuristic can give dramatic improvement•Space? O(bm) -- keeps all nodes in memory•Optimal? NoSide Discussion “Greedy Algorithms”•Makes locally optimal choices at each stage •Fast and therefore attractive to solve NP-hard and other problems with high complexity. Later decisions are made in the context of decision selected early dramatically reducing the size of the search space.•They do not backtrack: if they make a bad decision (based on local criteria), they never revise the decision.•They are not guaranteed to find the optimal solution(s), and sometimes can get deceived and find really bad solutions.•In spite of what is said above, a lot successful and popular algorithms in Computer Science are greedy algorithms.•Greedy algorithms are particularly popular in AI and Operations Research. •See also: http://en.wikipedia.org/wiki/Greedy_algorithm Popular Greedy Algorithms: Decision Tree Induction,…A* search•Idea: avoid expanding paths that are already expensive•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 goalA* search exampleA* search exampleA* search exampleA* search exampleA* search exampleA* search exampleAdmissible heuristics•A 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) (never overestimates the actual road distance)•Theorem: If h(n) is admissible, A* using TREE-SEARCH is optimalOptimality 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) h* measures the “true cost” 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; Contradiction: Algorithm would have not terminated at G2 and expanded n instead because f(n)<f(G)f(G2)Consistent heuristics•A heuristic is consistent if for every node n, every successor n' of n generated by any action a, h(n) ≤ c(n,a,n') + h(n')•If h is consistent, we havef(n') = g(n') + h(n') = g(n) + c(n,a,n') + h(n') ≥ g(n) + h(n) = f(n)•i.e., f(n) is non-decreasing along any path.Theorem: If h(n) is consistent, A* using GRAPH-SEARCH is optimalRemark: Optimal means A* directly moves to the goal stateAdmissible heuristicsE.g., for the 8-puzzle:•h1(n) = number of misplaced tiles•h2(n) = total Manhattan distance•(i.e., no. of squares from desired location of each tile)•h1(S) = ? 8•h2(S) = ? 3+1+2+2+2+3+3+2 = 18Dominance•If 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):•d=12 IDS = 3,644,035 nodesA*(h1) = 227 nodes A*(h2) = 73 nodes •d=24 IDS = too many nodesA*(h1) = 39,135 nodes A*(h2) = 1,641 nodesSMA* Algorithm Modifies A* to work with a limited memoryKey Idea: •Uses a given amount of memory to remember nodes so that they don’t have to be repeatedly regenerated.•Utilizes whatever memory is made available to it.•It avoids repeated states as far as its memory allows. https://en.wikipedia.org/wiki/SMA* Khadijahttp://www2.cs.uh.edu/~ceick/ai/SMA.pdfSMA* Algorithm Steps: • Expand deepest lowest f-cost leaf-node (Best first search on f-cost) • Update f-cost of nodes whose successors have higher f-cost • Drop shallowest & highest f-cost leaf node • remember best forgotten descendant• Paths longer than node limit get ∞ cost.