An introduction to A* Search Algorithm in Artificial Intelligence

Table of Content

• What is A* Search Algorithm?
• Why A* Search Algorithm?
• Explanation
• A* Terminologies
• Heuristics
• Manhattan Distance
• Admissibility and Consistency
• Basic Concepts of A*
• Example
• Limitation
• Applications
• Conclusion

 What is A* Search Algorithm?

The algorithm to calculate shortest distance in real-life situations, like -maps and games.

A-Star is essentially the best search algorithm and popular technique used for graph traversals and path-finding. This technique is used in a lot of games and web-based maps for finding the shortest path effectively.

Why A* Search Algorithm?

A* search algorithm is needed because it has “brains” in comparison to other traversal techniques. It means, this technique is really smart and that separates it from other conventional algorithms.

A* Algorithm Works-

• To maintain a tree of paths originating at the start node.
• To extend those paths (one edge at a time).
• Continues till the termination criterion is satisfied.

 Explanation

In daily life, we search for the shortest route to reach our destination. A* search algorithm  in artificial intelligence is the most successful path-finding algorithm that is capable of finding the shortest path between graphs and nodes. The algorithm is an informed search and uses info about the cost of path and heuristics to find a solution to a problem.

Terminologies: 

Before moving forward, let’s have a look at some of the terminologies of A* algorithm:

•    Node: Potential position with a unique identification
•    Transition: Act of moving between nodes
•    Starting Node: Start point of searching
•    Goal Node: Stop point of searching
•    Search Space: Collection of nodes
•    Cost: Numeric Values like time or distance between two nodes
•    g(n): Symbol that represents the exact cost of the path from starting node
•    h(n):It is a heuristic estimated cost from node n to the goal node.
•    f(n): the Lowest point in neighboring node n

Suppose you need to reach from the starting point to the endpoint defined in a square grid. Here, comes the A* search algorithm.

At each step, A* will pick the node according to the value “f”. It is a parameter equal to the sum of the other two parameters “g” & “h”. 

This process is known as heuristic and that is a kind of smart guess only, where we are not aware of the actual distance until we find the path.

Heuristics

The heuristic is derived from the Greek word “to discover”.  It is a method of problem-solving in the quickest way possible and delivers a satisfactory result that is sufficient enough to be useful in given time constraints. It’s like a mental shortcut that allows people to solve complex problems and make judgments quickly. Such a strategy allows people without thinking about the next course of action. Basically, it’s a flexible technique for quick decision making, mostly used when working with complex data structures. 

Manhattan Distance

Manhattan distance is the sum of absolute values of difference between current goal and target goal respectively. This heuristic can be used in an algorithm when you are allowed to move in four directions (left, right, top, bottom) only. 

Admissibility and Consistency

A given function h(n) will be admissible if it doesn’t overestimate the real distance between goal node and n.

So, the formula for every node will be –

h(n)≤h∗(n)h(n)≤h∗(n)

h*(n) = distance between n and goal node

A given function h (n), will be consistent if the estimate is always >= estimated distance between the goal n and any neighbor, plus the estimated cost of reaching neighbor. It will be demonstrated by –

c(n,m)+h(m)≥h(n)c(n,m)+h(m)≥h(n)

c (n,m) = distance between nodes n and m.

Basic Concepts of A*

As discussed above also, A* uses heuristic methods to achieve optimality and completeness. These are the two valuable properties of the search algorithm.

Optimality – It is the guarantee to find the best possible solution, i.e. to find the shortest path.

Completeness – It means if a solution to the given problem exists, the algorithm will find it.

Whenever, A-star (A*) will enter in a state, it will calculate the cost denoted by f(n), to travel in all the neighboring nodes and then lastly it will enter the node having lowest f(n).

It is calculated by –

f(n)=g(n)+h(n)

Example:

Use A* to find the shortest path from the green square to the yellow square in the grid below.

Start by choosing the admissible heuristic. In this case, Manhattan heuristic can also be used. After this, we can move forward to starting the cell. This will be the current cell and then we will start looking for all its neighbors and compute f(n), g(n), h(n) for each of them. After that, we need to select a neighbor with the lowest f(n).

This lowest one will be our new current cell and the above process will be repeated until we don’t reach the goal cell. In the below images you can understand which is out the current cell and where we need to reach.

Image source: brilliant.org/wiki/a-star-search

Image Source: brilliant.org/wiki/a-star-search

Limitations

Although, A* is the best path-finding algorithm it doesn’t come up with the shortest path always due to its heavy reliance on heuristics.

Applications

Do you know, where A* search algorithm mostly used? It’s in games!

Have you played Tower Defense Games?

It’s a type of strategy video game in which a player has to defend a territory by obstructing enemies. This is done by placing defensive structures on their attack path.

So, in such games, A* search algorithm is used to find the shortest path between two points. It can be used for each enemy specifically to find a path to the goal.

Conclusion

A* star is a mighty algorithm in AI that has a wide range of usage. Due to its heuristic function, it is very popular. For being reasonably flexible in nature A-star (A*) is the most popular choice for path-finding. As discussed, it has various applications, like in software systems and machine learning and game development.