Wikipedia / Consistent heuristic
Wikipedia / Consistent heuristic
In the study of path-finding problems in artificial intelligence, a heuristic function is said to be consistent, or monotone, if its estimate is always less than or equal to the estimated distance from any neighbouring vertex to the goal, plus the cost of reaching that neighbour.
Formally, for every node N and each successor P of N, the estimated cost of reaching the goal from N is no greater than the step cost of getting to P plus the estimated cost of reaching the goal from P. That is:
and
where
h is the consistent heuristic function
N is any node in the graph
P is any descendant of N
G is any goal node
c(N,P) is the cost of reaching node P from N
Informally, every node i will give an estimate that, accounting for the cost to reach the next node, is always lesser than or equal to the estimate at node i+1.
A consistent heuristic is also admissible, i.e. it never overestimates the cost of reaching the goal (the converse, however, is not always true). Assuming non negative edges, this can be easily proved by induction.
, so any consistent heuristic is also admissible since it is upperbounded by the true cost.
.
Consequences of monotonicity
. It's necessary and sufficient for a heuristic to obey the triangle inequality in order to be consistent.
to be monotonically non-decreasing under a consistent heuristic is as follows:
. Then we have that
.
In the A* search algorithm, using a consistent heuristic means that once a node is expanded, the cost by which it was reached is the lowest possible, under the same conditions that Dijkstra's algorithm requires in solving the shortest path problem, then A* is equivalent to best-first search on that graph using Dijkstra's algorithm.
.
In the unusual event that an admissible heuristic is not consistent, a node will need repeated expansion every time a new best (so-far) cost is achieved for it.
is admissible but not consistent, one can artificially force the heuristic values along a path to be monotonically non-decreasing by using
. This idea is due to László Mérō and is now known as pathmax. Contrary to common belief, pathmax does not turn an admissible heuristic into a consistent heuristic. For example, if A* uses pathmax and a heuristic that is admissible but not consistent, it is not guaranteed to have an optimal path to a node when it is first expanded.
Relation to Local Admissibility
Modifying the consistency condition to h(N)−h(P) ≤ c(N,P) establishes a connection to local admissibility, where the heuristic estimate to a specific node remains less than or equal to the actual step cost. This ensures optimality when selecting local nodes, akin to how admissible heuristics ensure global optimality. By maintaining this property, the search process improves efficiency by making locally optimal decisions that contribute to the globally optimal solution.