How do we know that $c(n,a,G) = h^{\ast}(n)$, in the proof that if a heuristic is consistent then it is admissible?

Question

I found a proof that if a heuristic $h$ is consistent, then it is admissible, but I'm confused by one of the steps in the proof.

The proof is by induction on $k$, the number of actions from a node $n$ to the goal node $G$.

Base step: $k = 1$, i.e., node $n$ is one step from $G$. Since the heuristic function $h$ is consistent,

$$h(n) \leq c(n, a, G) + h(G)$$

Since $h(G) = 0$,

$$h(n) \leq c(n, a, G) = h^{\ast}(n)$$

Therefore, $h$ is admissible.

Induction step: Assume: If $h(n′)$ is consistent, then $h(n′)$ is admissible, for all nodes $n′$ that are $k$ steps from $G$.

$$h(n) \leq c(n, a, n') + h(n')$$

Since $n′$ is $k$ steps from $G$ and $h$ is admissible for node $n′$ that is $k$ steps from $G$,

$$h(n') \leq h^{\ast}(n')$$ $$\implies c(n,a,n') + h(n') \leq c(n, a, n') + h^{\ast}(n')$$ $$\implies h(n) \leq c(n, a, n') + h^{\ast}(n') = h^{\ast}(n)$$

hence, $h$ us admissible for node n.

I'm specifically confused about these lines:

$$h(n) \leq c(n, a, G) = h^{\ast}(n)$$

and

$$h(n) \leq c(n, a, n') + h^{\ast}(n') = h^{\ast}(n)$$

How do we know that $c(n,a,G) = h^{\ast}(n)$? Wouldn't it depend on the action $a$ chosen?

Also, how do we know: $c(n, a, n') + h^{\ast}(n') = h^{\ast}(n)$?

Answer 1

$c(n, a, G) = h^*(n)$ is true because $h^*$ is the optimal heuristic, i.e. it gives you the minimal/optimal cost from $n$ to the goal $G$, which, in that base case, is exactly $c(n, a, G)$, i.e. the edge distance from $n$ to $G$.

Now, I understand the confusion arises from the parameter $a$, the action.

Here, $a$ is arbitrary, but, in this case, there's only one action that should lead to $G$, which I suppose is a reasonable assumption, otherwise you would have multiple arrows from $n$ to $G$ (which are neighbours), which I've never seen.

I don't even know why they use this parameter $a$. I think you can safely ignore it, unless you want to consider cases where there are more than one edge between two neighbours $n$ and $n'$, which is useless because you can always consider the cheapest edge.