Searching the “Intelligent” way!

Recently while cleaning my room, I came across a box containing my college memorabilia, (Read “stuff that I never even knew existed”) Digging deeper into the dusty pile of uselessness , I found something rather interesting. I found my notes from the Artificial Intelligence lectures or as google translate calls it “Intelligentia Artificialis Corpus“! I can say for sure this was one of the classes that I did attend and with diligence. I grew up watching TV shows like the “Jetsons” and “Dexter’s Laboratory” and movies like “The Matrix” and “I,Robot”, so the diligence and the excitement for the AI lectures is self-explanatory. The part that was legible in the “Corpus” , helped me in revisiting some of the simpler topics in AI and in this post I will be talking about one of those topics – Heuristic Search.

In computer science, we have come across various search algorithms that follow a brute force methodology of finding all the possible solutions and then selecting the best one (example, British Museum Search).But these methods are time consuming and prone to error. Other methods like Depth First Search(DFS) or Breadth First Search (BFS) somewhat improve the searching techniques but still does not address the urge of finding a sophisticated and optimal search technique. This is where admissible heuristics steals the limelight. Admissible Heuristics ensures that any instant the cost to reach the goal is never overestimated. This is the property that eliminates failed search paths and ensures a fast and efficient search path.

The A* (read A-star) algorithm is a classic heuristic search algorithm that extensively uses this admissible heuristics property.

Concept

The A*Algorithm scans through a set of nodes that would lead us to the goal and picks the node that looks most promising instead of blinding selecting any node.It then calculates the partial path cost and picks the path with the least cost. This process is repeated till the final node is reached. This sounds like any ordinary path-finding algorithms!! This was supposed to be an intelligent algorithm, right ?  Well, the intelligence lies in the way the cost of the node is calculated. The cost is calculated based on the formula :

\huge f(x) = g(x) + h(x)

Here, the g(x) or G-cost is the cost of the path from the start node to the current node x.The “Heuristic Cost (H-cost)” or h(x) is the admissible heuristic estimate from the current node x to the goal node. The lowest estimate to reach a goal from the start node via the path chosen is referred to as f(x) or the F-cost.

In the first step, the start node is explored and the neighboring nodes (8 in number) are evaluated based on their F-costs and the lowest F-cost node is selected. In the next step,the new node’s neighbors are evaluated. The lowest F-cost node is selected and this process is repeated till we get to our goal node (if possible). Also, a situation may arise where the evaluated neighboring nodes overlap. In such a scenario, the g-cost and eventually the f-cost for that neighboring node gets updated only if the g-cost for reaching that node via the current path is smaller than the current g-cost of that node (figure 1).

p11
Figure 1 : The overlapping node(in yellow) can be reached using 2 paths. The g-cost calculated earlier (via path-1) is lower than the new g-cost (via path-2). Hence the costs will not be updated in this step.

Properties

Admissibility

The H-cost function is admissible if the estimated distance between the current node nad the goal is less than or equal to the actual distance between the current node,x and the goal. Mathematically, it can be written as:

\huge H(x,G) \le D(x,G)

Consistency

The H-cost function is consistent if the absolute difference between the estimated distance between two nodes (x and y) and the goal node [(x,G)  and (y,G)] is less than or equal to the actual distance between x and y . Mathematically, it can be written as:

\huge |H(x,G) - H(y,G)| \le D(x,y)

Result

This slideshow requires JavaScript.

 

Codehttps://github.com/sukhoi/Artificial-Intelligence

References

  1. Wiki (A* algorithm)
  2. MIT OCW course on AI
  3. World of Computing article on  AI

This slideshow requires JavaScript.

Advertisements

One thought on “Searching the “Intelligent” way!

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