Admissible heuristic

Table of contents

Automate your business at $5/day with Engati

REQUEST A DEMO
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.

Admissible heuristic
Source: Computer Science Stack Exchange


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.

3x Your Revenue With Chatbot And Live Chat
Schedule a demo


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:

example of admissible heuristic


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.

Close Icon
Request a Demo!
Get started on Engati with the help of a personalised demo.
Thanks for the information.
We will be shortly getting in touch with you.
Oops! something went wrong!
For any query reach out to us on contact@engati.com
Close Icon
Congratulations! Your demo is recorded.

Select an option on how Engati can help you.

I am looking for a conversational AI engagement solution for the web and other channels.

I would like for a conversational AI engagement solution for WhatsApp as the primary channel

I am an e-commerce store with Shopify. I am looking for a conversational AI engagement solution for my business

I am looking to partner with Engati to build conversational AI solutions for other businesses

continue
Finish
Close Icon
You're a step away from building your Al chatbot

How many customers do you expect to engage in a month?

Less Than 2000

2000-5000

More than 5000

Finish
Close Icon
Thanks for the information.

We will be shortly getting in touch with you.

Close Icon

Contact Us

Please fill in your details and we will contact you shortly.

Thanks for the information.
We will be shortly getting in touch with you.
Oops! Looks like there is a problem.
Never mind, drop us a mail at contact@engati.com