Admissible heuristic

What are Admissible heuristics?

Admissible heuristics are used to estimate the cost of reaching the goal state in a search algorithm. Admissible heuristics never overestimate the cost of reaching the goal state. The use of admissible heuristics also results in optimal solutions as they always find the cheapest path solution.

For a heuristic to be admissible to a search problem, needs to be lower than or equal to the actual cost of reaching the goal.

‍

Here is an example:

In the A* search algorithm, the evaluation function (where {\displaystyle n}n is the current node) is:

f(n)=g(n)+h(n)

where

f(n) = evaluation function.

g(n) = cost from start node to current node

h(n) = estimated cost from current node to goal

Here, h(n) gets calculated with the use of the heuristic function. If a non-admissible heuristic was used, it is possible that the algorithm would not reach the optimal solution because of an overestimation in the evaluation function.

‍

What is non-admissible heuristic?

Non-admissible heuristics may overestimate the cost of reaching the goal state. There is no guarantee that they will reach an optimal solution.

What happens when a heuristic is not admissible?

When a non-admissible heuristic is used in an algorithm, it may or may not result in an optimal solution. 

But, sometimes non-admissible heuristics expand a smaller amount of nodes. As a result, it is possible that the total cost (search cost + path cost) could end up being lower than an optimal solution that would be found by using an admissible heuristic.

‍

What is the difference between admissible heuristics & consistent heuristics?

A heuristic is considered to be consistent if the estimated cost from one node to the successor node, added to the estimated cost from the successor node to the goal is less than or equal to the estimated cost from the current node to the goal state.

In an admissible heuristic, the estimated cost from the current node to the goal state is never greater than the actual cost.

All consistent heuristics are admissible heuristics, however, all admissible heuristics are not necessarily consistent heuristics.

How does an admissible heuristic ensure an optimal solution?

If the heuristic function isn’t admissible, then it is possible to have an estimation that is larger than the actual path cost from some node to a goal node. If this higher path cost estimation is on the least cost path (that you are trying to find), the algorithm will not explore it and it may find another (not the cheapest) path to the goal. 

Consider this example:

Say 𝐴  and 𝐺 are the starting and goal nodes respectively. Now let ℎ(𝑁) be an estimate of the path's length from node 𝑁 to 𝐺, ∀𝑁 in the graph. Say 𝑐(𝑁,𝑋𝑖) is the step cost function from node 𝑁 to its neighbor 𝑋𝑖, ∀𝑁 and 𝑖=1..𝑚, where 𝑚 is the number of neighbors of 𝑁 (i.e., a function that returns the cost of the edge between node 𝑁 and one of its neighbors).

Let the heuristics be

• ℎ(𝐵)=3
• ℎ(𝐶)=4

This heuristics function 𝐻 will not be admissible, because

ℎ(𝐶)=4>𝑐(𝐶,𝐺)=2

If the 𝐴∗ algorithm starts from node 𝐴, it will then select the node 𝐵 for the purpose of expansion and, after this, it will proceed to node 𝐺 from there. And the path will be 𝐴→𝐵→𝐺 with cost 4, instead of 𝐴→𝐶→𝐺 with cost 3. If the heuristic function was admissible this would not have happened.

if the heuristic had been admissible A->B could be chosen for the next node to expand, but after that, the A* would select A->C instead of A->B->G. And in the end, it would end up with A->C->G.

This is because of the way in which  A* works. It expands the node that has the least sum of the distance to that node + heuristic estimation from that node. d(A,G) + h(G) = 4 + 0 = 4 and d(A,C) + h(C) = 1 + something<=2 (because it is admissible). C has the lower sum and hence A* will pick it. In the same way, it will then expand G and identify the least path.

Admissible heuristics make sure to find the shortest path with the least cost. The solution itself will be optimal if the heuristic is consistent.

Here is an alternative explanation:

The fact that the heuristic is admissible means that it does not overestimate the effort to reach the goal. i.e., ℎ(𝑛)≤ℎ∗(𝑛) for all 𝑛 in the state space (in the 8-puzzle, which means is that just for any permutation of the tiles and the goal you are currently considering) where ℎ∗(𝑛) is the optimal cost to reach the target.

The most logical reason why 𝐴∗ offers optimal solutions if ℎ(𝑛) is admissible is due to the fact that it sorts all nodes in OPEN in ascending order of 𝑓(𝑛)=𝑔(𝑛)+ℎ(𝑛) and, also, because it does not stop when generating the goal but when expanding it.

Due to the fact that nodes are expanded in ascending order of 𝑓(𝑛) you know that no other node is more promising than the current one. ℎ(𝑛)  is admissible so that having the lowest 𝑓(𝑛) means that it has an opportunity to reach the goal via a cheaper path that the other nodes in OPEN have not. This holds true unless you can manage to prove the opposite, i.e., by expanding the current node.

Because 𝐴∗ will only stop when it proceeds to expand the goal node (instead of stopping when generating it) you can be absolutely sure that no other node leads to it via a cheaper path.