Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
Could someone give the intuition behind consistency of heuristic function in the A* algorithm?
From wikipedia:
Every node i will give an estimate that, after accounting for the cost to reach i + 1, is always lesser than the estimate at node i + 1.
I understand what this means, but is there any intuitive meaning behind it? And how does this lead to monotonicity of the evaluation function = f(n) = g(n) + h(n)?
A consistent heuristic must not overestimate the true cost to get to the goal from a particular node - the heuristic estimate is always less than or equal to the cost to get to another node plus the estimated cost from that node to the goal (which itself cannot be an overestimate).
Basically, a consistent heuristic will not spuriously discard truly good options because it overestimates their cost and treats them as bad options. An inconsistent heuristic might overestimate the cost of some path, and instead explore another, costlier path and miss the optimal solution. A consistent heuristic allows paths to turn out longer than expected (since you can explore them and then go elsewhere if needed), but it does not allow paths to turn out shorter than expected (since you may miss them entirely if you get to the goal first).
With a consistent heuristic, the estimated final cost of of a partial solution (f(n) = g(n) + h(n)) is monotonically non-decreasing along the best path. The consistent heuristic can't overestimate costs, so true the cost must always be as large or larger than the estimated cost. If you move along the best path closer to the goal, the estimated final cost must not decrease - if you get closer to the goal and find your estimated final cost has decreased, it must mean that you overestimated the remaining cost somewhere along the way, which means the heuristic is not consistent.
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:
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'.
