Informed search algorithms

Informed search algorithms CHAPTER 3b CMPT 310 Oliver Schulte Outline Best-first search A* search Heuristics

Environment Type Discussed In this Lecture 3 Fully Observable Static Environment

yes Deterministic yes yes yes Sequential no Discrete

Discrete no no yes Planning, heuristic search

Control, cybernetics CMPT 310 - Blind Search Vector Search: Constraint Satisfaction Continuous Function Optimization

Review: Tree search A search strategy is defined by picking the order of node expansion Which nodes to check first? Heuristic Search Knowledge and Heuristics

Simon and Newell, Human Problem Solving, 1972. Thinking out loud: experts have strong opinions like this looks promising, no way this is going to work. S&N: intelligence comes from heuristics that help find promising states fast. Evaluation Functions Idea: use an evaluation function f(n) for each node.

estimate of "desirability" Expand most desirable unexpanded node. Especially useful with state transition costs. Implementation: Order the paths in frontier in decreasing order of desirability. Special cases:

greedy best-first search A* search Romania with step costs in km Greedy 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 goal Greedy best-first search example

Greedy best-first search example Greedy best-first search example Greedy best-first search example http://aispace.org/search/ Properties of greedy best-first search Complete? No can get stuck in loops, e.g. as Oradea as goal

Iasi Neamt Iasi Neamt Time? O(bm) = full tree in worst case. But a good heuristic can give dramatic improvement. Space? O(bm) -- keeps all nodes in memory Optimal? No The A* Search Algorithm

A* search Idea: avoid expanding paths that are already expensive. Widely used! Evaluation function f(n) = g(n) + h(n) h(n) = estimated cost from n to goal f(n) = estimated total cost of path through n to goal

g(n) = cost so far to reach n A* search example A* search example A* search example A* search example A* search example

A* search example http://aispace.org/search/ We stop when the node with the lowest f-value is a goal state. Is this guaranteed to find the shortest path? Behaviour of A*

A* expands nodes in order of increasing f value. Let C* be cost of optimal solution. 1. 2. A* expands all nodes n with f(n) < C*. A* expands no nodes n with f(n) > C*.

1. Gradually adds "f- contours" of nodes Contour i has all nodes with f=fi, where fi < fi+1.

Admissible 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) (straight-line distance never overestimates the actual road distance) Fly heuristic is not admissible: if wall is dark,

then distance from exit is large. Theorem: If h(n) is admissible, A* using TREE- SEARCH finds the optimal solution. Optimality of A* (proof) I Suppose some suboptimal goal path G2 has been generated and is in the frontier. Let n be an unexpanded path in the

frontier such that n is on a shortest path to an optimal goal G. f(G2) = g(G2) since h(G2) = 0 because h is admissible g(G2) > g(G) since G2 is suboptimal, cost of reaching G is less. f(G) = g(G)

since h(G) = 0 f(G2) > f(G) from above Optimality of A* (proof) II Suppose some suboptimal goal path G2 has been generated and is in the frontier. Let n be an unexpanded node in the frontier 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, h* is minimal distance. g(n) + h(n) g(n) + h*(n) = f(G)

f(n) f(G) Hence f(G2) > f(n), and A* will never select G2 for expansion Properties of A* Complete? Yes (unless there are infinitely many nodes with f f(Goal) ) Time? Exponential

Space? Keeps all nodes in memory Optimal? Yes Admissible Heuristics Admissible heuristics E.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) = ? h2(S) = ?

Admissible heuristics E.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 = 18

Dominance If h2(n) h1(n) for all n (both admissible) then h2 dominates h1 . h2 is better for search (closer to true cost). Typical search costs (average number of nodes expanded): 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

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 8-puzzle 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 Summary

Heuristic functions estimate costs of shortest paths Good heuristics can dramatically reduce search cost Greedy best-first search expands lowest h incomplete and not always optimal A search expands lowest g + h

complete and optimal also optimally efficient (up to tie-breaks) Admissible heuristics can be derived from exact solution of relaxed problems