#4567 Pathplanner A* heuristic underestimates path cost in certain situations

[Nicholas Walczak]

Currently, the A* heuristic estimates the remaining path cost as the sum of three terms: the hex distance between the current location and the goal location, the difference in facing between the current position and the goal, and the elevation difference between the current elevation and the goal elevation.

This heuristic does not take into account the current level that a unit is at, and hence can under estimate. For instance, if the path has the option of going around a hill and going over a hill, it will pick going over a hill, because level changes for the current location aren't considered. I'll attach two screenshots with an example.

The sub_optimal path gets picked because the comparison between the [F] movepath and the [R,F,F] movepath is equal (because the heuristic doesn't account for the downwards level change that will be required from the current position in [R,F,F]). In a tie, the path with more steps gets picked, so [R,F,F] gets picked and the [F] path never gets expanded, and gets ignored, even though it leads to the shortest path.

[Nicholas Walczak]

Fixed in [r11969].

I added another term to the heuristic that computes the level difference between the current hexes' level and the goal hexes' level, but only if the current elevation in the path is non-zero (since a non-zero elevation implies that the unit off the ground somehow, generally VTOL or WiGE movement).

This fixes the reported case, however I think that it's still possible in some extreme cases for the heuristic to under estimate. Essentially, if there are a lot of level changes between the current hex and the goal hex, then I think the heuristic still under estimates, but I can't think of any way to compute this in closed-form; I can only think of iterative ways of computing it and I don't want to use an iterative term for performance reasons. My thought is that these situations are pretty rare so it's not worth it.