State Space Search and Admissible Heuristics

State Space Search : Characterization of Heuristic Function Piyali Chatterjee

We may evaluate the behavior of heuristics along a number of dimensions. For instance, we may not only desire a solution but also may require the algorithm to find the shortest path to the goal. Informedness Monotonicity When a state is discovered by using heuristic search, is there any guarantee that the same state won t be found later in the search at a cheaper cost? We may want to ask whether any better heuristics are available. In what sense is one heuristic better than another? Admissibility Heuristics that find the shortest path to a goal whenever it exists are said to be admissible.

Admissibility The first condition we require for optimality is that h(n) be an admissible heuristic. An admissible heuristic is one that never overestimates the cost to reach the goal. Because g(n) is the actual cost to reach n along the current path, and f(n)=g(n)+h(n), we have as an immediate consequence that f(n) never overestimates the true cost of a solution along the current path through n. Admissible heuristics are by nature optimistic because they think the cost of solving the problem is less than it actually is.

Important Notes A search algorithm is admissible if it is guaranteed to find a minimal path to a solution whenever such a path exists. In determining the properties of admissible heuristics, we define an evaluation function f* (n) f*(n)=g*(n)+h*(n), where g*(n) is the cost of the shortest path from the start node to node n and h* (n) returns the actual cost of the shortest path from the node n to to goal node it follows that f*(n) is the actual cost of the optimal path from a start node to a goal node that passes through node n. When we employ best_first_search with the evaluation function f*, the resulting search strategy is admissible.

Important Notes Although f* does not exist for most real problems, we would like the evaluation f to be a close estimate of f*. In algorithm A, g(n) , the cost of the current path to state n, is a reasonable estimate of g* , but they may not be equal: g(n) g*(n). These are equal only if the search has discovered the optimal path to state n. Similarly, we replace h*(n) with h(n), a heuristic estimate of the minimal cost to a goal state. Although we usually may not compute h*, it is often possible to determine whether or not the heuristic estimate, h(n), is bounded from above, i.e., is always less than or equal to the actual cost of a minimal path, h*(n). If algorithm A uses an evaluation function f in which h(n) h*(n), it is called algorithm A*.

Algorithm A* 1. Create a search graph, G, consisting solely of the start node, n0. Put n0on a list called OPEN. 2. Create a list called CLOSED that is initially empty. 3. If OPEN is empty, exit with failure. 4. Select the node n on OPEN that has the smallest value of f , remove it from OPEN, and put it on CLOSED. If the node n is goal node return success, stop otherwise, 5. Expand n, generating all successors n and place node n on CLOSED. For every successor n , if n is not already on OPEN or CLOSED, attach a back pointer to n, f (n ) and place it on OPEN. compute if n is already on OPEN or CLOSED should be attached to back which reflect the lowest g(n ) path. pointers to n If not, remove it, and place it on OPEN. Return to Step 3.

Admissibility of A* There are conditions on graphs and on h that guarantee that algorithm A* applied to these graphs always finds minimal cost paths. The conditions on the graphs are a) Each node in the graph has a finite number of successors (if any). b) All arcs in the graph have costs greater than some positive amount, The condition on h is For all nodes n in the search graph, h(n) h*(n). That is, h never overestimates the actual value, h*.

Monotonicity A heuristic function h is monotone if For all states niand nj, wherenjis a descendant ofni, h(ni)-h(nj) cost (ni,nj), where cost(ni,nj) is the actual cost (in number of moves) of going from state nito nj. The heuristic evaluation of the goal state is zero., or h(Goal)=0. One way of describing the monotone property is that the search space is everywhere locally consistent with the heuristic employed. The difference between the heuristic measure for a state and any one of its successors is bound by the actual cost of going between that state and its successors. This is to say that the heuristic is everywhere admissible, reaching each state along the shortest path from its ancestors. When using a monotone heuristic, as the search moves through the space, the heuristic measure for each state n is replaced by the actual cost of generating that piece of the path to n. Because the actual cost is equal to larger than the heuristic in each instance, f will not decrease; i.e., f is monotonically nondecreasing ( hence the name).

A simple argument can show that any monotonic heuristic is admissible. This argument considers any path in the space as a sequence of state S1, S2,..,Sg, where S1is the start state and Sgis the goal. For the sequence of moves in this arbitrarily selected path: This means that monotone heuristic h is A* and admissible.

Informedness For two A* heuristics h1and h2, if h1(n) h2(n), for all states n in the search space, heuristic h2is said to be more informed than h1. Breadth first search is equivalent to the A* algorithm with heuristic h1such that 1(?) = 0 ??? ??? ?????? ?. This is, trivially, less than h*. We have also shown that h2, the number of tiles out of place with respect to the goal state, is a lower bound for h*. In this case, 1 2 . It follows that the number of tiles out of place heuristic is more informed than breadth-first search.

This figure compares the spaces searched by these two heuristics . Both h1and h2 find the optimal path but h2evaluates many fewer states in the process. h1(n)=0 used by Breadth First Search h2(n)=some positive value ( no. of tiles out of place) h2(n)>h1(n), h2is more informed and finds optimal solution by examining 14 nodes. Whereas h1does the same by examining 47 nodes.

Similarly, we can argue that the heuristic that calculates the sum of the direct distances by which all the tiles are out of place is again more informed than the calculation of the number of tiles that are out of place with respect to the goal state, and indeed this is the case. If a heuristic 2is more informed than 1, then the set of states examined by 2is a subset of those expanded by 1. In general, then the more informed an A* , the less of the space it needs to expand to get the optimal solution. Verify the case for two heuristics in 8-puzzle problem