Monotonicity and A*. Is it optimal?

Question

Is A* an optimal search algorithm (ie. will it find the best solution) even if it is non-monotonic? Why or Why not?

Answer 1

A* is an optimal search algorithm as long as the heuristic is admissible.

But, if the heuristic is inconsistent, you will need to re-expand nodes to ensure optimality. (That is, if you find a shorter path to a node on the closed list, you need to update the g-cost and put it back on the open list.)

This re-expansion can introduce exponential overhead in state spaces with exponentially growing edge costs. There are variants of A* which reduce this to polynomial overhead by essentially interleaving a dijkstra search in between each A* node expansion.

This paper has an overview of recent work, and particularly citations of other work by Martelli and Mero who detail these worst-case graphs and suggest optimizations to improve A*.

Answer 2

A* is an optimal search algorithm if and only if the heuristic is both admissible and monotonic (also referred to as consistent). For a discussion of the distinction between these criteria, see this question. Effectively, the consistency requirement means that the heuristic cannot overestimate the distance between any pair of nodes in the graph being searched. This is the necessary because any overestimate could result in the search ignoring a good path in favor of a path that is actually worse.

Let's walk through an example of why this is true. Consider two nodes, A and B, with heuristic estimates of 5 and 6, respectively. If the heuristic is admissible and consistent, the shortest path that could possibly exist goes through A and is no shorter than 5. But what if the heuristic isn't consistent? In order for a heuristic to be admissible but inconsistent, it must always underestimate the distance to the goal but not result in there being a clear relationship between heuristic estimates at nodes within the graph. For a concrete example, see my answer to this question. In this example, the heuristic function randomly chooses between two other functions. If the heuristic estimates at A and B were not calculated based on the same function, we don't actually know which one of them currently has the potential to lead to a shorter path. In effect, we aren't using the same scale to measure them. So we could choose A when B was actually the better option. This might result in us finding the goal through a sub-optimal path.