Consistent Heuristic

search

Definition

Consistent Heuristic

A heuristic is called consistent if, for every node $n$, every successor $n^{\prime }$ of $n$ and every operator $a$

$$h(n)\le c(n,a,n^{\prime })+h(n^{\prime })$$

holds, where $c(n,a,n^{\prime })$ are the path costs for $a$.

Non-Decreasing

Non-Decreasing

If $h$ is consistent, then $f$ (the evaluation function) is non-decreasing along every path:

$$\begin{array}{rl}f(n^{\prime })& =g(n^{\prime })+h(n^{\prime })\\ & =g(n)+c(n,a,n^{\prime })+h(n^{\prime })\\ & \ge g(n)+h(n)=f(n)\end{array}$$

Optimal Graph Search

Optimal Graph Search

If $h$ is consistent, then A* search using graph search is optimal.