## A* algorithm - Why should the heuristic be an underestimate?

### A* algorithm - Why should the heuristic be an underestimate?

Hi all,

In the A* algorithm, F = G + H where H is the result returned by the
heuristic function. In many articles that I read about A*, the one
thing I can't understand is: why should the heuristic function return
an underestimate figure?

How do we know it is an underestimate in the first place, because at
any given node N, we do not know the actual (real) distance to the
goal, so how can we say underestimate if we don't know the real
figure?

Can someone please explain it in simple terms, or give me a hint.
Something is blobked for me here ...

Cheers,

Dave

[ comp.ai is moderated.  To submit, just post and be patient, or if ]

### A* algorithm - Why should the heuristic be an underestimate?

Quote:>Hi all,
>In the A* algorithm, F = G + H where H is the result returned by the
>heuristic function. In many articles that I read about A*, the one
>thing I can't understand is: why should the heuristic function return
>an underestimate figure?

A* explores nodes in order of increasing total estimated cost F.
If the heuristic H is guaranteed never to overestimate then F is
a lower bound on the actual cost of a path via a given node, ie
the actual cost via that node must always be >= the estimate.
A* may then "waste time" expanding a node whose distance to the
goal is underestimated, but it will eventually discover that the
actual cost is greater than the estimate and immediately switch
to more promising nodes, hence ensuring that it finds an optimal
path (if one exists) before finding a suboptimal one.

If the heuristic overestimates then A* may find a suboptimal
path to the goal before it finds an optimal one, because an
overestimate causes it to defer exploring some node actually on
an optimal path, choosing instead to expand some more promising
node on a suboptimal path.

Quote:>How do we know it is an underestimate in the first place, because at
>any given node N, we do not know the actual (real) distance to the
>goal, so how can we say underestimate if we don't know the real
>figure?

Finding heuristics that never overestimate is certainly possible
even when we don't know the distance from a node to the goal.
For example, the constant function H=0 never overestimates,
although it provides no guidance in the search.  In a 4-connected
grid the "Manhattan Distance" (sum of the absolute values of the
differences in X and Y values between the node and the goal) also
never overestimates, and does provide useful guidance.

Quote:>Can someone please explain it in simple terms, or give me a hint.
>Something is blobked for me here ...
>Cheers,
>Dave

If it's still not clear I suggest you try it out by hand on a
small example, it should rapidly become obvious what's going on.

David

[ comp.ai is moderated.  To submit, just post and be patient, or if ]

### A* algorithm - Why should the heuristic be an underestimate?

Quote:>Hi all,

>In the A* algorithm, F = G + H where H is the result returned by the
>heuristic function. In many articles that I read about A*, the one
>thing I can't understand is: why should the heuristic function return
>an underestimate figure?

>How do we know it is an underestimate in the first place, because at
>any given node N, we do not know the actual (real) distance to the
>goal, so how can we say underestimate if we don't know the real
>figure?

>Can someone please explain it in simple terms, or give me a hint.
>Something is blobked for me here ...

Assuming F(N) = distance from node N to a goal node, G(N) = known
smallest distance from the start to node N, H(N) = estimate of
distance from N to goal node.

If H(N) is an overestimate then if the algorithm reaches the goal
node by some other path with distance < F(N) then it will never
look at node N, because H(N) is then seemingly worse than an already
established path.  And so even if the _actual_ distance via N is
optimal this path will then be overlooked.  Which is incorrect.

If, on the other hand, H(N) is an underestimate then if the algorithm
reaches the goal node by some path with distance D, and the actual
distance via N is less than D, then it is guaranteed that F(N) will
also be less than D, so the algorithm will continue to look at N
(and perhaps find a path shorter than D).

Hth.,

- Alf  (novice helper mode)

[ comp.ai is moderated.  To submit, just post and be patient, or if ]

### A* algorithm - Why should the heuristic be an underestimate?

> >In the A* algorithm, F = G + H where H is the result returned by the
> >heuristic function. In many articles that I read about A*, the one
> >thing I can't understand is: why should the heuristic function return
> >an underestimate figure?

> A* explores nodes in order of increasing total estimated cost F.
> If the heuristic H is guaranteed never to overestimate then F is
> a lower bound on the actual cost of a path via a given node, ie
> the actual cost via that node must always be >= the estimate.
> A* may then "waste time" expanding a node whose distance to the
> goal is underestimated, but it will eventually discover that the
> actual cost is greater than the estimate and immediately switch
> to more promising nodes, hence ensuring that it finds an optimal
> path (if one exists) before finding a suboptimal one.

> If the heuristic overestimates then A* may find a suboptimal
> path to the goal before it finds an optimal one, because an
> overestimate causes it to defer exploring some node actually on
> an optimal path, choosing instead to expand some more promising
> node on a suboptimal path.

It might be worth noting that very often an overestimated heuristic makes the
algorithm find the way faster, even thou the solution is suboptimal.
So if you have an aplication where the path needs to be found _fast_ you might
consider an overestimated heuristic a valid option.

Quote:>> (...)

[ comp.ai is moderated.  To submit, just post and be patient, or if ]

Q from a beginner in AI on the heuristic search algorithm that
uses a heuristic evaluation function f(n) = g(n) + h(n) to
decide which node to expand.  This is where g(n) is the cost
(say distance) from the origin to the node n, and h(n) is our
heuristic, in this case the straight line distance from the
node n to the destination (goal) node.

This is "A* Search" as per p. 97 of the great work by Russell
and Norvig.  They prove that this search is optimal, i.e. it
will find the shortest path, since our heuristic is admissable.

I think I can come up with a example that this algorithm will
not find the shortest path in, so I must be missing something.
I am pulling out my hair with this -- where am I going wrong?

Consider a pair of routes in the plane between an origin O and
a goal point G.  The first route goes from the origin to a node
n which is very close to G.  However, from here it goes through
many nodes and a long circuitous path finally terminating iat
G.  The second route goes from the origin to another node that
is not as close to G.  Then, it goes straight to the goal.

At the first node, deciding which path to expand:

For the first path, f(n) would be nearly equal to the straight
line distance between G and O, because the first node on that
path is very close to G.

For the second path, it is quite easy to imagine a place to
put the first node relative to G such that f(n) is greater than
in the first possible route above.  Just put it off to the side.

So the first path gets expanded (the first node on the first
path).  Since this path eventually leads to the goal state,
it is returned as a solution.  It however is not optimal
because the second path is shorter and also reaches the goal
state.

So where am I going wrong in my logic??

Thanks,
Taavo.

[ comp.ai is moderated.  To submit, just post and be patient, or if ]