Mixing heuristic functions in A*

Question

I have applied a custom heuristic to my A* search. It is admissible, but it is not consistent (monotonic). As such, I am not guaranteed to find the shortest path.

I had assumed I could use a hybrid approach that calculates both the euclidian distance heuristic and my custom heuristic and choses the tightest consistent value of the two (where euclidian will always be consistent).

However, when I attempted this, I found instances where even the euclidian distance is not consistent in the presence of the parent node. That is, given edge uv, custom-heuristic(u) - euclidian-distance(v) > edge(uv).

To solve this, I attempted to detect this & default to a heuristic value of h(u) - e(uv) but that resulted in some truly terrible paths.

Is it possible to mix heuristic methods effectively and still have consistency? Under what circumstances will it work?

Answer 1

Any admissible heuristic can be made consistent using the following:

h*(p) = Max(h(p), h*(n)-c(np))
where
h is the admissible heuristic
h* is the new consistent heuristic
n is any node
p is any child of n
c is the cost of going from n to p
Note: h*(start) = h(start)

Using this the total cost estimate either stays the same in the h*(n)-c(np) case or increases in the h(p) case and therefore is non-decreasing which is what you need for consistency.

Consistent Heuristic

As far as combining heuristics you just add them to the max.

h*(p) = Max(h(p), h*(n)-c(np), h'(p))

Again the h*(n)-c(np) keeps the total cost estimate from decreasing, so as long as all your heuristics are admissible you can add as many as you want to the Max function.

To be clear though the max wouldn't necessarily work without the h*(n)-c(np). if you are combining an inconsistent heuristic with a consistent one because if the inconsistent one is consistently greater than the consistent one then the max will have no effect. A heuristic that always says 0 is consistent.