1

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$.

John Doucette
  • 9,147
  • 1
  • 17
  • 52
calveeen
  • 1,251
  • 7
  • 17

1 Answers1

2

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.
nbro
  • 39,006
  • 12
  • 98
  • 176
John Doucette
  • 9,147
  • 1
  • 17
  • 52
  • if c(n,m) edge is removed how would you know that h(n) < c(n,m) + h(m) ? since we don't know how long it takes to go from n to m ? I understand intuitively why h is still consistent but how would the inequality for consistency apply for node n and m ? does c(n,m) need to be a direct edge ? – calveeen Mar 26 '20 at 01:35
  • 1
    @calveeen It ends up that if the heuristic is locally consistent (between all neighbors of states) then it is also globally consistent (where n and m are not directly connected and c(n, m) represents the cost of the shortest path between them). This can be proven by induction. Removing the edge between n and m can only make c(n, m) larger, in which case the inequality still holds. – Nathan S. Mar 26 '20 at 05:24