What does a consistent heuristic become if an edge is removed in A*?

Question

For the A* algorithm, a consistent heuristic is defined as follows: if, for every node $n$ and every successor $m$ of $n$ generated by any action $a$, $h(n) \leq c(n,m) + h(m)$.

Suppose the edge $c(n,m)$ is removed, how do we define consistency for nodes $n, n'$ ? Since the $n'$ is not generated from $n$.

Answer 1

Consistency is a property of heuristics. You can think of consistency as the common sense idea that our guess at the time to go from $A \rightarrow B \rightarrow C$ cannot be more than the time to go from $A \rightarrow B$, plus our guess of the time to go from $B \rightarrow C$.

Supposing we remove a given edge $c(n,m)$ from our graph, but that our heuristic function gives the same value for $h(n)$ as before. Can the function be inconsistent? Let's try a proof sketch:

1. Since the function was consistent before we removed this edge, it must already be the case that $h(n) < c(n, m') + h(m')$ for every other node $m'$ adjacent to $n$.
2. Removing the edge $c(n,m)$ doesn't change these relationships, because the other edges still have the same costs as before, and the heuristic function still gives the same value for every node.
3. The same argument may be applied to node $m$.
4. Since none of these relationships have changed, $h$ is still consistent.