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.
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 :
Here, the or G-cost is the cost of the path from the start node to the current node .The “Heuristic Cost (H-cost)” or is the admissible heuristic estimate from the current node to the goal node. The lowest estimate to reach a goal from the start node via the path chosen is referred to as 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).
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:
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: