A* heuristic, overestimation/underestimation?

Question

I am confused about the terms overestimation/underestimation. I perfectly get how A* algorithm works, but i am unsure of the effects of having a heuristic that overestimate or underestimate.

Is overestimation when you take the square of the direct birdview-line? And why would it make the algorithm incorrect? The same heuristic is used for all nodes.

Is underestimation when you take the squareroot of the direct birdview-line? And why is the algorithm still correct?

I can't find an article which explains it nice and clear so I hope someone here has a good description.

Answer 1

As far as I know, you want to typically underestimate so that you may still find the shortest path. You can find an answer quicker by overestimating, but you may not find the shortest path. Hence why overestimation is "incorrect", whereas underestimating can still provide the best solution.

I'm sorry that I cannot provide any insight as to the birdview lines...

Answer 2

You're overestimating when the heuristic's estimate is higher than the actual final path cost. You're underestimating when it's lower (you don't have to underestimate, you just have to not overestimate; correct estimates are fine). If your graph's edge costs are all 1, then the examples you give would provide overestimates and underestimates, though the plain coordinate distance also works peachy in a Cartesian space.

Overestimating doesn't exactly make the algorithm "incorrect"; what it means is that you no longer have an admissible heuristic, which is a condition for A* to be guaranteed to produce optimal behavior. With an inadmissible heuristic, the algorithm can wind up doing tons of superfluous work examining paths that it should be ignoring, and possibly finding suboptimal paths because of exploring those. Whether that actually occurs depends on your problem space. It happens because the path cost is 'out of joint' with the estimate cost, which essentially gives the algorithm messed up ideas about which paths are better than others.

I'm not sure whether you will have found it, but you may want to look at the Wikipedia A* article. I mention (and link) mainly because it's almost impossible to Google for it.

Answer 3

From the Wikipedia A* article, the relevant part of the algorithm description is:

The algorithm continues until a goal node has a lower f value than any node in the queue (or until the queue is empty).

The key idea is that, with understimation, A* will only stop exploring a potential path to the goal once it knows that the total cost of the path will exceed the cost of a known path to the goal. Since the estimate of a path's cost is always less than or equal to the path's real cost, A* can discard a path as soon as the estimated cost exceeds the total cost of a known path.

With overestimation, A* has no idea when it can stop exploring a potential path as there can be paths with lower actual cost but higher estimated cost than the best currently known path to the goal.