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.

Solution 1

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.

Solution 2

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.

Solution 3

Short answer

@chaos answer is bit misleading imo (can should be highlighted)

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

as @AlbertoPL is hinting

You can find an answer quicker by overestimating, but you may not find the shortest path.

In the end (beside the mathematical optimum), the optimal solution strongly depends on whether you consider computing resources, runtime, special types of "Maps"/State Spaces, etc.

Long answer

As an example I could think of an realtime application where a robot gets faster to the target by using an overestimating heuristic because the time advantage by starting earlier is bigger than the time advantage by taken the shortest path but waiting longer for computing this solution.

To give you a better impression, I share some exemplary results that I quickly created with Python. The results stem from the same A* algorithm, only the heuristic differs. Each node(grid cell) has got edges to all eight neighbors except walls. Diagonal edges cost sqrt(2)=1.41

The first picture shows the returned paths of the algorithm for an simple example case. You can see some suboptimal paths from overestimating heuristics (red and cyan). On the other hand there are multiple optimal paths (blue, yellow, green) and it depends on the heuristic which one is found first.

The different images show all expanded nodes when the target is reached. The color shows the estimated path cost using this node (considering the "already taken" path from start to this node as well; mathematically it's the cost so far plus the heuristic for this node). At any time the algorithm expands the node with lowest estimated total cost (described before).

1. Zero (blue)

• Corresponds to the Dijkstra algorithm
• Nodes expanded: 2685
• Path length: 89.669

2. As the crow flies (yellow)

• Nodes expanded: 658
• Path length: 89.669

3. Ideal (green)

• Shortest path without obstacles (if you follow the eight directions)
• Highest possible estimate without overestimating (hence "ideal")
• Nodes expanded: 854
• Path length: 89.669

4. Manhattan (red)

• Shortest path without obstacles (if you don't move diagonally; in other words: cost of "moving diagonally" is estimated as 2)
• Overestimates
• Nodes expanded: 562
• Path length: 92.840

5. As the crow flies times ten (cyan)

• Overestimates
• Nodes expanded: 188
• Path length: 99.811

Solution 4

Intuitive Answer

For A* to work correctly (always finding the 'best' solution, not just any), your estimation function needs to be optimistic.

Optimism here means that your expectations are always better than reality.

An optimist will try many things that might disappoint in the end, but they will find all the good opportunities.

A pessimist expects bad results, and so will not try many things. Because of this, they may miss some golden opportunities.

So for A*, being optimistic means to always underestimate the costs (i.e. "it's probably not that far"). When you do that, once you found a path, then you might still feel excited about several unexplored options, that could be even better. That means you won't stop at the first solution, and still try those other ones. Most will probably disappoint (not be better), but it guarantees you will always find the best solution. Of course trying out more options takes more work (time).

A pessimistic A* will always overestimate cost (e.g. "that option is probably pretty bad"). Once it has found a solution and it knows the true cost of the path, every other path will seem worse (because estimates are always worse than reality), and it will never try any alternative once the goal is found.

The most effective A* is one that never under-estimates, but estimates either perfectly or just slightly over-optimistic. Then you'll not be naive and try too many bad options.

A nice lesson for everyone. Always be slightly optimistic!

Solution 5

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...

View more solutions

Comments

[Eric]

Point taken, but the part I quoted is correct and relevant for my answer.

[chtz]

With an overestimating heuristic, the algorithm should tend to find a (suboptimal) solution faster than with an underestimating heuristic, shouldn't it? With an extremely underestimating heuristic (like always returning 0), one would get the optimal solution, but essentially just doing a breadth-search.

[Ayush]

@chtz Yes, that's true. You'll get a solution faster albeit a sub-optimal one. Conversly, it is also why Djisktra's in general is slower than the A* algorithm, as the heuristic is always 0(I know, 3 years late but might help someone else reading this in the future).

[VimNing]

@chtz: No, It's underestimated that makes searching of possibly suboptimal solution faster.

[VimNing]

If one overestimate the potential cost, it means the predicted cost of that branch is larger and less possible to be chosen. Are you sure this will speed up the search?

[Ayush]

I wasn't pinged when Rainning made the comment but revisited this today. Underestimation doesn't 'make searching of suboptimal solution faster'. Underestimation actually provides the optimal solution.