Artificial Intelligence – A* Search Algorithm

We will try to improve the efficiency of the Uniform Cost Search algorithm by using heuristics which we discussed in the previous post. By improving the efficiency I mean that the algorithm will expand less of the search tree and will give the optimal result faster. We start with the same search problem and search tree that we used for Uniform Cost Search. If you don’t know what search problems are or how search trees are created, visit this post.

searchProblem
searchTree
A* Search Algorithm

We saw that Uniform Cost Search was optimal in terms of cost for a weighted graph. Now our aim will be to improve the efficiency of the algorithm with the help of heuristics. If you don’t know what heuristics are, visit this post. Particularly, we will be using admissible heuristics for A* Search.

A* Search also makes use of a priority queue just like Uniform Cost Search with the element stored being the path from the start state to a particular node, but the priority of an element is not the same. In Uniform Cost Search we used the actual cost of getting to a particular node from the start state as the priority. For A*, we use the cost of getting to a node plus the heuristic at that point as the priority. Let n be a particular node, then we define g(n) as the cost of getting to the node from the start state and h(n) as the heuristic at that node. The priority thus is f(n) = g(n) + h(n). The priority is maximum when the f(n) value is least. We use this priority queue in the following algorithm, which is quite similar to the Uniform Cost Search algorithm:

Insert the root node into the queue
While the queue is not empty
      Dequeue the element with the highest priority
      (If priorities are same, alphabetically smaller path is chosen)
      If the path is ending in the goal state, print the path and exit
      Else
            Insert all the children of the dequeued element, with f(n) as the priority

Now let us apply the algorithm on the above search tree and see what it gives us. We will go through each iteration and look at the final output. Each element of the priority queue is written as [path,f(n)]. We will use h1 as the heuristic, given in the diagram below.

heuristic

Initialization: { [ S , 4 ] }
Iteration1: { [ S->A , 3 ] , [ S->G , 12 ] }
Iteration2: { [ S->A->C , 4 ] , [ S->A->B , 10 ] , [ S->G , 12 ] }
Iteration3: { [ S->A->C->G , 4 ] , [ S->A->C->D , 6 ] , [ S->A->B , 10 ] , [ S->G , 12] }
Iteration4 gives the final output as S->A->C->G.

Things worth mentioning:

->The creation of the tree is not a part of the algorithm. It is just for visualization.
->The algorithm returns the first path encountered. It does not search for all paths.
->The algorithm returns a path which is optimal in terms of cost, if an admissible heuristic is used(this can be proved).

The above example illustrates that A* Search gives the optimal path faster than Uniform Cost Search. This is, however, true only if the heuristic is admissible. In general, the efficiency of the algorithm depends on the quality of the heuristic. The nearer the heuristic is to the actual cost, the better is the speed of the algorithm. Trivially, the heuristic can be taken to be 0, which gives the Uniform Cost Search algorithm.

With this, I have completed all the popular search algorithms in Artificial Intelligence. In the next post I will be writing about Feature Detection in Computer Vision.

Advertisements

19 comments

  1. I do agree with all of the concepts you have presented in your post.
    They’re really convincing and can definitely work. Nonetheless, the posts are very short for novices. May you please extend them a bit from subsequent time? Thanks for the post.

    1. Thanks for the comment. It would be great if you could tell me what details you are looking for, I will definitely extend as required.

  2. I’ve used several of the entries on your site to help me with my AI class at college. Thanks. 🙂

    1. Thanks a lot for appreciating my work. 😀

  3. Avishek Seal · · Reply

    i didn’t get here… why the heuristic value of A is 2… it should be 1 + 2 =3 .. isn’t it??

    1. Heuristics are made so that they give us an approximate cost of reaching the goal. If the heuristic value gives us the actual cost, then there is no point in searching for the shortest path, because we already know all the costs. For more detail, read my post on ‘Search Heuristics’

  4. Avishek Seal · · Reply

    So we can take any value ?? either equal or less than the actual cost of the path???

    1. Yes, that’s right. Trivially, even the constant ‘0’ is a heuristic. In that case, A* Search is the same as Uniform Cost Search.

  5. A compelling blog. Well done. Just FYI, the Jeffrey Epstein VI Foundation just launched its new website on artificial intelligence covering robotics to virtual software platforms to explore cognition: http://www.jeffreyepstein.net

  6. we have to assign heuristics manually for each node?? is ther any heuristic function like something…..which do it automatically while coding..??

    1. No, a heuristic is a mathematical function, which you include in your code for computation. For example, if you are playing Pacman, the distance to a food particle maybe a heuristic.

  7. 00la wallter · · Reply

    Thanks alot for the post, i really need to know how admissible heuristic work

  8. I have been preparing for an AI exam in college and this really help a lot.

  9. thanks for clarification. This example helped mi alot

  10. sri krishna · · Reply

    helped me big time !!!!thanks

  11. What's Ap · · Reply

    Its really informative to help my to solve labrtory task

  12. Initially i had no clue where to start as i am preparing for an AI exam. Of all the post i came upon online, this has really been the most helpful. Thank you.

  13. The concept about a* search is amazing because, it’s easy to understand as well as the way of style that you present 🙂

  14. thanks for the blog, i liked it

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: