Artificial Intelligence – Search Heuristics

Search heuristics are important in improving the efficiency of a search problem. This post will describe what heuristics are and why they are used in artificial intelligence applications. I will cover some of the standard topics in heuristics which are admissible and consistent heuristics.

What are heuristics?

Heuristics can be said to be estimates of how far the goal state is. Heuristics basically predict how far the goal state maybe or how much it will cost to get to the goal state from a particular node. Now the question that arises is, when we know the cost of getting to the goal state from every node why do we have to search at all? We don’t know the cost of getting to the goal state, we have an estimate or prediction for it which may or may not be correct.

Let us take an example to demonstrate how we can estimate costs of reaching a goal state. Consider the maze below:

maze

Let the opening at the left of the maze be the start state, and the one at the top be the goal state. We consider the maze to be split into blocks having (x,y) co-ordinates, with the width of a path being 1 block. It is quite difficult for us to say how many steps a person may have to move to get to the goal state, since we will have to solve the search problem to find that. It makes no sense to solve a search problem to find out a heuristic, since heuristics are meant for the efficient solving of search problems.

Now imagine the maze without any walls or obstacles. What would be the shortest path then? It would be a steps to the right and b steps to the top. This is called the Manhattan distance between two points and can be used as a heuristic for the given maze. Another obvious heuristic is the Euclidean distance between the two points.

It can also be clearly seen that heuristics don’t give the actual cost of the path. In this particular example, if we use the Euclidean distance as a heuristic, there are points that are far from the goal state as compared to the start state, but the actual cost of getting to the goal state from these points is smaller than the actual cost from the start state.

Admissible Heuristics

A heuristic is said to be admissible if the value of the heuristic is always smaller than or equal to the actual cost of getting to the goal state.

Consistent Heuristics

A heuristic is said to be consistent if the heuristic value for every edge is smaller than or equal to the actual cost of the edge. The heuristic value for an edge might be defined as h(AB) = h(A) – h(B). The heuristic of an edge AB is the heuristic value at A minus the heuristic value at B.
It is an obvious statement to say that if a heuristic is consistent then it is also admissible.

Let us take the following diagram as an example for admissible and consistent heuristics:

heuristic

Clearly h1 is an admissible heuristic. But it is not consistent since the heuristic value for edge SA is 2 whereas the true value is 1. Also h2 is both admissible as well as consistent.

In this post we have laid the base for heuristics which will be used to increase the efficiency of Uniform Cost Search algorithm. This will give the A* Search algorithm which will be discussed in the next post.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: