Imagine three states: A
, B
, and G
, where the start state is A
and the goal state is G
.
Suppose you have the heuristic $h(n)$ that maps state $n$ to an estimated numerical cost of going from state n
to the goal state. So you input $n$ into the function and it returns an estimated cost $h(n)$.
Now, for this heuristic function to be deemed "consistent" or "monotonic", it needs to meet one criterion that you may consider logical and geometrical if you will. And that is, in simplified terms:
- The heuristic "distance" from
A
to G
"directly" must be shorter than or equal to the sum of: a step to a third state B
and the heuristic distance from that state B
to the goal state G
.
Only then, a heuristic function is consistent in the estimates it's providing. It needs to adhere to the triangle inequality.
Formally, the inequality defines the relationship between $h(n)$, $h(n')$, and $c(n, n')$, or three sides of a triangle if you draw vertices as states or nodes and label the edges as appropriate. So you end up with $h(n) \leq c(n, n') + h(n')$ where $c(n, n')$ is the cost of going from state n
to state n'
.
