More Heuristic Search

Recall that heuristic search is about choosing a path that looks promising. For example, that looks closer to the goal.

"Distance from start" combined with "Distance to goal"

In many problems, we are interested not just in any solution but in a short (or the shortest) path to a solution.

Consider an evaluation function f of state n that incorporates "distance from start".

f(n) = g(n) + h(n)
where g(n) = actual distance from start state to state n
h(n) = heuristic estimated distance from n to goal

In this case, lowest f is best.

Algorithm A - Best-first search with distance from start

If you implement best-first with distance from start you get a best-first which has more of a breadth-first flavour.

The g component of f prevents the search being misled by an (inevitably) inaccurate heuristic h.
If h continually returns good evaluations for a path that never gets to a goal, g will grow to dominate f and the search will backtrack to look for a path that actually works.
Inaccuracy of h is adapted to at run-time.

Example of Algorithm A

The 8-puzzle problem.
Heuristic h(n) = no. of tiles out of place.

Luger Fig 4.15 (See goal state at bottom)
e.g. middle choice has 2,8,1 out of place, h(n) = 3, g(n) = 1, f(n) = 4

How this would direct search:

Image courtesy of Ralph Morelli.
See also Luger Fig 4.16

Exercise: Put in all the h values.

Progression of OPEN and CLOSED: See Luger Notes

In step 3, state e is followed. Its child h has same h(n) value as state f, but higher f(n) value, caused by g(n) increasing by 1.
So best-first leaves it on the list and returns to look at f (step 4).
Note each state has other children not shown - namely their parents! We only show new child states.

4.3 Admissibility

We said designing heuristics is an empirical problem. How do we study when one heuristic is better than another?

A heuristic is said to be admissible if it provably finds the (joint) shortest path to the goal where it exists.
Breadth-first search is admissible, but impractical.

Algorithm A

Algorithm A: Best-first heuristic search with this heuristic evaluation function:

f(n) = g(n) + h(n)
where g(n) = distance from start state to state n along current, known path (haven't yet searched other paths, may find there are multiple different ways to get to n)
h(n) = heuristic estimated distance from n to goal

Consider:

f^*(n) = g^*(n) + h^*(n)
where g^*(n) = minimum distance from start state to state n along any path
h^*(n) = actual, minimum distance from n to goal along any path

Best-first search with f^* is admissible.
But we do not know f^* (it would be an "oracle").
We want f to be as close to f^* as possible.

Note that g(n) may be too high - it may not have found the shortest path to n.

For all A algorithms: g(n) ≥ g^*(n) for all n.

A* algorithms

A* search algorithm

An A^* algorithm is algorithm A where h(n) ≤ h^*(n) for all n.

i.e. All states have a worse distance to goal than predicted, or equal, but never better.
h is always too optimistic.
h(n) = 0 for all n, for example.

Theorem: All A^* algorithms are admissible.

Proof: See here.

Rough proof:

When A* terminates, it has by definition found a path whose actual cost is lower than (or equal to) the estimated cost of any path through any unsearched node.
But since those estimates are all optimistic (real cost will be equal or higher), A* can ignore those nodes.
If h was pessimistic, we have a problem. Maybe the goal is hidden right under some high-up unsearched nodes.