Heuristic

A heuristic is a function $h(s)$ used to estimate how close a state $s$ is to a goal. They’re problem-specific, and can help us approximate computationally difficult problems. This makes them useful for NP-complete problems in artificial intelligence.

Good heuristics have the properties:

• Non-negative.
• $h(n)=0$ if $n$ is a goal node.
• Can compute $h(n)$ efficiently and without search, so that we don’t affect the underlying time complexity of the algorithm.

Some algorithms that rely on heuristics to search:

• Greedy best-first search
• A-star algorithm

An admissible heuristic is one that never overpredicts the cost to a goal node, i.e., it never estimates a cost to the goal greater than the actual cost to the goal. For the cost of an optimal path $h^{\ast }(n)$:

$$h(n)\le h^{\ast }(n)$$

They basically ensure that the search won’t miss any promising paths.

A consistent (or monotone) heuristic is one that never overpredicts the action cost, i.e., the heuristic predicts the action cost less than the actual cost for each action.

$$h(A)-h(C)\le c_{A\to C}$$

The consequence of consistency is that the $f$ value along a path never decreases.

By theorem, consistency implies admissibility. That is:

$$(\forall n_1,n_2,a)h(n_1)\le C(n_1,a,n_2)+h(n_2)⟹(\forall n)h(n)\le h^{\ast }(n)$$

where $a$ is the edge between $n_1,n_2$.