Are heuristic functions that produce negative values inadmissible?

Question

As far as I understand, admissibility for a heuristic is staying within bounds of the 'actual cost to distance' for a given, evaluated node. I've had to design some heuristics for an A* solution search on state-spaces and have received a lot of positive efficiency using a heuristic that may sometimes returns negative values, therefore making certain nodes who are more 'closely formed' to the goal state have a higher place in the frontier.

However, I worry that this is inadmissible, but can't find enough information online to verify this. I did find this one paper from the University of Texas that seems to mention in one of the later proofs that "...since heuristic functions are nonnegative". Can anyone confirm this? I assume it is because returning a negative value as your heuristic function would turn your g-cost negative (and therefore interfere with the 'default' dijkstra-esque behavior of A*).

Disject

Do you have an example of a heuristic function that does this? At face value, it seems like returning a negative value is an indicator that you overestimated the distance to the goal at some point in the past, but I might be overlooking something. – Harpoon

I represent my state spaces as individual sets of items. There is a goal set of items that must be satisfied in any order. As I continue to generate new states (within the constraints of the problem) my 'best' heuristic adds the weights for all items missing from the goal set and subtracts the weights for all items that match, favoring closely formed goal states. If you look at the values for H produced at runtime, most are positive in the beginning, but become negative later (more potential goals). The F and G values never dip below zero, however. – Disject

So is each edge representing the addition of an item, and its weight is the cost of that edge? – Harpoon

Yes, that's correct. – Disject

As Nikola Benes points out, the counterexample is not really a counter-example since the A* will still return the path Start -> A -> B -> End. – Odey

Answer 1

Conclusion: Heuristic functions that produce negative values are not inadmissible, per se, but have the potential to break the guarantees of A*.

Interesting question. Fundamentally, the only requirement for admissibility is that a heuristic never over-estimates the distance to the goal. This is important, because an overestimate in the wrong place could artificially make the best path look worse than another path, and prevent it from ever being explored. Thus a heuristic that can provide overestimates loses any guarantee of optimality. Underestimating does not carry the same costs. If you underestimate the cost of going in a certain direction, eventually the edge weights will add up to be greater than the cost of going in a different direction, so you'll explore that direction too. The only problem is loss of efficiency.

If all of your edges have positive costs, a negative heuristic value can only over be an underestimate. In theory, an underestimate should only ever be worse than a more precise estimate, because it provides strictly less information about the potential cost of a path, and is likely to result in more nodes being expanded. Nevertheless, it will not be inadmissible.

However, here is an example that demonstrates that it is theoretically possible for negative heuristic values to break the guaranteed optimality of A*:

In this graph, it is obviously better to go through nodes A and B. This will have a cost of three, as opposed to six, which is the cost of going through nodes C and D. However, the negative heuristic values for C and D will cause A* to reach the end through them before exploring nodes A and B. In essence, the heuristic function keeps thinking that this path is going to get drastically better, until it is too late. In most implementations of A*, this will return the wrong answer, although you can correct for this problem by continuing to explore other nodes until the greatest value for f(n) is greater than the cost of the path you found. Note that there is nothing inadmissible or inconsistent about this heuristic. I'm actually really surprised that non-negativity is not more frequently mentioned as a rule for A* heuristics.

Of course, all that this demonstrates is that you can't freely use heuristics that return negative values without fear of consequences. It is entirely possible that a given heuristic for a given problem would happen to work out really well despite being negative. For your particular problem, it's unlikely that something like this is happening (and I find it really interesting that it works so well for your problem, and still want to think more about why that might be).

Harpoon

Really fabulous answer. I'm curious why you have H(n)=1 for your starting node. – Disject

Thanks! The h(n) value for the starting node was completely arbitrary. I just chose something low so it would be sure to be admissible and consistent. In retrospect, 3 would probably have been a less confusing choice. – Harpoon

In fact, this heuristics is not consistent. A consistent heuristics should satisfy for all u, v: h(u) <= d(u,v) + h(v). However, in your example, h(start) = 1, h(C) = -2, d(start, C) = 2 and 1 > 2 + (-2). Even if you corrected this (e.g. by setting h(start) = 0), it is still not a counterexample. You are forgetting the heuristics value of end, which must be at least 0 (due to h(b) = 1). End will be added to the open set with g(end) = 6, f(end) = 6; however, before it is extracted from the open set, it is added again with g(end)=3, f(end) = 3. – Publisher

Classic mistake: seeing the goal for first time is not same is reaching the goal. Not in A*, not in Djikstra. So all correct A* implementations will give correct answer. Important point is H(goal)=0 always. – Zoochemistry

Question is about definition of admissibility, I would like to see some references in the answer instead of just a numerical example showing it could lead non-optimal results. – Nolie