Does a consistent heuristic have value 0 on a goal state?

Question

I was studying AI when a question came to my mind.

In the context of search problems, a heuristics is a non-negative real-valued function on the space of states. A heuristic is said to be consistent if it satisfies the triangle-equality-like condition kindly stated in an answer below.

I'm attempting to prove that a consistent heuristic is admissible, as stated in AIMA. It seems an easy induction proof by induction of the length of an optimal path, but the base case is giving me some trouble: how one can prove that a consistent heuristic has value 0 on a goal state?

Answer 1

A heuristic is said to be consistent if its value on a state is less or equal than the cost of an optimal path from the state to a goal.

No, that is the definition of an admissable heuristic. A consistent heuristic is one which satisfies the triangle inequality:

$$ h(N) \le c(N,P) + h(P)\\ h(G) = 0 $$

how one can prove that a consistent heuristic has value 0 on a goal state?

It's part of the definition of a consistent heuristic, given above. It's also trivially true of admissable heuristics, but that's not necessary to show in order to prove that consistent heuristics are admissable. To show that, you can use induction against the above equations (a full proof can be found in the Wikipedia page)

Answer 2

Though AIMA doesn't explicitly state $h(G)=0$ for the heuristic function value at the goal node, however, it does claims this in a previous section, whether it's admissible or consistent or neither:

Most best-first algorithms include as a component of f a heuristic function, denoted $h(n)$:
$h(n)$ = estimated cost of the cheapest path from the state at node $n$ to a goal state...

For now, we consider them to be arbitrary, nonnegative, problem-specific functions, with one constraint: if $n$ is a goal node, then $h(n)=0$.

Answer 3

How one can prove that a consistent heuristic has value 0 on a goal state?

I think that a consistent heuristic $h$ doesn't necessarily need to have $h(G) = 0$, but you can assume it. If you assume something, you don't have to prove it, otherwise you go in circles (unless you're proving by contradiction).

Now, is the assumption $h(G) = 0$ reasonable?

In the book "Artificial Intelligence: A New Synthesis", Nils Nilsson (who is one of the inventors of A*) does not explicitly assume $h(G) = 0$. It simply defines a consistent heuristic as

$$h(n) - h(n') \leq c(n, n') \iff h(n) \leq c(n, n') + h(n'),$$

where $n'$ is a successor of $n$, that is, our current estimate must be smaller or equal to the estimate from the successor plus the cost to get to the successor.

If $h(G) > h^*(G)$, where $h^*$ is the optimal heuristic (i.e. it gives you the true cost to the goal), then the heuristic is not admissible because it overestimates the cost to the goal (this is just the definition of admissibility). Now, if we assume $h^*(G) = 0$ (which is a reasonable assumption), then we must have $h(G) \leq 0$ for $h$ to be admissible, so are 2 possible cases $h(G) = 0$ or $h(G) < 0$ for $h$ to be admissible.

Nilsson states (to prove a theorem on p. 152)

Here, we use the fact that if the $\hat{h}$ function is consistent it will also never be greater than the true function $h$ function

and then cites a Judea Pearl's book (1984, p. 83). (Note that in Nilsson's $h$ is actually $h^*$).

If you check Pearl's proof of theorem 9 which Nilsson references, you will see that he actually assumes that $h(G) = 0$ in order to prove that consistent heuristics are also admissible, although he also doesn't explicitly include this condition as part of the definition of a consistent heuristic

Now, since $h(\gamma) = 0$ and $k(n, \gamma) = h^*(n)$ for some goal node $\gamma$...

If $h(G) > h^*(G)$, I think you can prove that $h$ is still consistent, but it's not admissible, which means that consistent heuristics would not be a subset of admissible heuristics, which is actually what Pearl proves in theorem 9, p. 83.

So, in conclusion, assuming that a consistent heuristic is also defined to meet $h(G) = 0$ is reasonable. Here, consistency refers to how the heuristic also has the same properties as the optimal heuristic, i.e. it's consistent with it. If you accept this, then $h(G) = 0$ is more than reasonable.

(I hope the changes of notation don't confuse you too much).