What is A* Search Algorithm?

Intelligence is the strength of the human species; we have used it to improve our lives. Then, we created the concept of artificial intelligence to amplify human intelligence and to develop and flourish civilizations like never before. A* Search Algorithm is one such algorithm that has been developed to help us. In this blog, we will learn more about what the A* algorithm in artificial intelligence means, the steps involved in the A* search algorithm in artificial intelligence, its implementation in Python, and more.

1. What is A* Search Algorithm?
2. A* Search Algorithm Steps
3. Why is A* Search Algorithm Preferred? 
4. A* Search Algorithm and Its Basic Concepts
5. What is a Heuristic Function?
6. Admissibility of the Heuristic Function
7. Consistency of the Heuristic Function
8. Implementation with Python
9. FAQs Related to A* Search Algorithm

AI helps us solve problems of various complexities. Computational problems like path search problems can be solved using AI. Search problems where you need to find a path from one point to another, say, point A to point B. Sometimes you need to solve it by mapping those problems to graphs, where nodes represent all the possible outcomes. A* algorithm comes up as an answer to these problems. 

Created as part of the Shakey project aimed to build a mobile robot that has artificial intelligence to plan its actions, A* was initially designed as a general graph traversal algorithm. It is widely used in solving pathfinding problems in video games.  Because of its flexibility and versatility, it can be used in a wide range of contexts. A* is formulated with weighted graphs, which means it can find the best path involving the smallest cost in terms of distance and time. This makes A* algorithm in artificial intelligence an informed search algorithm for best-first search. Let us have a detailed look into the various aspects of A*. 

What is A* Search Algorithm?

A* search algorithm is an algorithm that separates it from other traversal techniques. This makes A* smart and pushes it much ahead of conventional algorithms. 

Let’s try to understand Basic AI Concepts and comprehend how does A* algorithm work. Imagine a huge maze that is too big that it takes hours to reach the endpoint manually. Once you complete it on foot, you need to go for another one. This implies that you would end up investing a lot of time and effort to find the possible paths in this maze. Now, you want to make it less time-consuming. To make it easier, we will consider this maze as a search problem and will try to apply it to other possible mazes we might encounter in due course, provided they follow the same structure and rules.

As the first step to converting this maze into a search problem, we need to define these six things.

1. A set of prospective states we might be in
2. A beginning and end state
3. A way to decide if we’ve reached the endpoint
4. A set of actions in case of possible direction/path changes
5. A function that advises us about the result of an action 
6. A set of costs incurring in different states/paths of movement

To solve the problem, we need to map the intersections to the nodes (denoted by the red dots) and all the possible ways we can make movements towards the edges (denoted by the blue lines).
A denotes the starting point, and B denotes the endpoint. We define the starting and endpoints at nodes A and B, respectively.
If we use an uninformed search algorithm, it would be like finding a path that is blind, while an informed algorithm for a search problem would take the path that brings you closer to your destination. For instance, consider Rubik’s cube; it has many prospective states that you can be in, making the solution very difficult. This calls for the use of a guided search algorithm to find a solution. This explains the importance of A*.  
Unlike other algorithms, A* decides to take up a step only if it is convincingly sensible and reasonable as per its functions. This means it never considers any non-optimal steps. This is why A* is a popular choice for AI systems that replicate the real world – like video games and machine learning. 

A* Search Algorithm Steps

Step 1: Add the beginning node to the open list
Step 2: Repeat the following step

In the open list, find the square with the lowest F cost, which denotes the current square. Now we move to the closed square.

Consider 8 squares adjacent to the current square and Ignore it if it is on the closed list or if it is not workable. Do the following if it is workable.

Check if it is on the open list; if not, add it. You need to make the current square as this square’s a parent. You will now record the different costs of the square, like the F, G, and H costs. 

If it is on the open list, use G cost to measure the better path. The lower the G cost, the better the path. If this path is better, make the current square as the parent square. Now you need to recalculate the other scores – the G and F scores of this square. 

– You’ll stop:

If you find the path, you need to check the closed list and add the target square to it.

There is no path if the open list is empty and you cannot find the target square.

Step 3. Now you can save the path and work backward, starting from the target square, going to the parent square from each square you go, till it takes you to the starting square. You’ve found your path now.  

Why is A* Search Algorithm Preferred? 

It’s easy to give movement to objects. But pathfinding is not simple. It is a complex exercise. The following situation explains it. 

The task is to take the unit you see at the bottom of the diagram to the top of it. You can see that nothing indicates that the object should not take the path denoted with pink lines. So it chooses to move that way. As and when it reaches the top, it has to change its direction because of the ‘U’ shaped obstacle. Then it changes direction and goes around the obstacle to reach the top. In contrast to this, A* would have scanned the area above the object and found a short path (denoted with blue lines). Thus, pathfinder algorithms like A* help you plan things rather than waiting until you discover the problem. They act proactively rather than reacting to a situation. The disadvantage is that it is a bit slower than the other algorithms. You can use a combination of both to achieve better results – pathfinding algorithms give a bigger picture and long paths with obstacles that change slowly, and movement algorithms for a local picture and short paths with obstacles that change faster. 

Read how artificial intelligence will create more jobs by 2025.

A* Search Algorithm and Its Basic Concepts

A* algorithm works based on heuristic methods, and this helps achieve optimality. A* is a different form of the best-first algorithm. Optimality empowers an algorithm to find the best possible solution to a problem. Such algorithms also offer completeness; if there is any solution possible to an existing problem, the algorithm will definitely find it.  

When A* enters into a problem, firstly, it calculates the cost to travel to the neighboring nodes and chooses the node with the lowest cost. If The f(n) denotes the cost, A* chooses the node with the lowest f(n) value. Here ‘n’ denotes the neighboring nodes. The calculation of the value can be done as shown below:

f(n)=g(n)+h(n)f(n)=g(n)+h(n)
g(n) = shows the shortest path’s value from the starting node to node n
h(n) = The heuristic approximation of the value of the node

The heuristic value has an important role in the efficiency of the A* algorithm. To find the best solution, you might have to use different heuristic functions according to the type of the problem. However, the creation of these functions is a difficult task, and this is the basic problem we face in AI. 

What is a Heuristic Function?

A heuristic is simply called a heuristic function that helps rank the alternatives given in a search algorithm at each of its steps. It can either produce a result on its own or work in conjugation with a given algorithm to create a result. Essentially, a heuristic function helps algorithms to make the best decision faster and more efficiently. This ranking is based on the best available information and helps the algorithm decide the best possible branch to follow. Admissibility and consistency are the two fundamental properties of a heuristic function.

Admissibility of the Heuristic Function

A heuristic function is admissible if it can effectively estimate the real distance between a node ‘n’ and the end node. It never overestimates; if it ever does, it will be denoted by ‘d’, which also denotes the accuracy of the solution.

Consistency of the Heuristic Function

A heuristic function is consistent if the estimate of a given heuristic function turns out to be equal to or less than the distance between the goal (n) and a neighbor and the cost calculated to reach that neighbor.

A* is indeed a very powerful algorithm used to increase the performance of artificial intelligence. It is one of the most popular search algorithms in AI. The sky is the limit when it comes to the potential of this algorithm. However, the efficiency of an A* algorithm highly depends on the quality of its heuristic function. Wonder why this algorithm is preferred and used in many software systems? There is no single facet of AI where the A*algorithm has not found its application. From search optimization to games, robotics, and machine learning, the A* algorithm is an inevitable part of a smart program.

Implementation with Python

In this section, we are going to find out how the A* search algorithm can be used to find the most cost-effective path in a graph. Consider the following graph below.

The numbers written on edges represent the distance between the nodes, while the numbers written on nodes represent the heuristic values. Let us find the most cost-effective path to reach from start state A to final state G using the A* Algorithm.

Let’s start with node A. Since A is a starting node, therefore, the value of g(x) for A is zero, and from the graph, we get the heuristic value of A is 11, therefore 

g(x) + h(x) = f(x)
0+ 11 =11
Thus for A, we can write
A=11
Now from A, we can go to point B or point E, so we compute f(x) for each of them
A → B = 2 + 6 = 8
A → E = 3 + 6 = 9

Since the cost for A → B is less, we move forward with this path and compute the f(x) for the children nodes of B
Since there is no path between C and G, the heuristic cost is set to infinity or a very high value
A → B → C = (2 + 1) + 99= 102
A → B → G = (2 + 9 ) + 0 = 11
Here the path A → B → G has the least cost but it is still more than the cost of A → E, thus we explore this path further
A → E → D = (3 + 6) + 1 = 10
Comparing the cost of A → E → D with all the paths we got so far and as this cost is least of all we move forward with this path. And compute the f(x) for the children of D
A → E → D → G = (3 + 6 + 1) +0 =10
Now comparing all the paths that lead us to the goal, we conclude that A → E → D → G is the most cost-effective path to get from A to G.

Next, we write a program in Python that can find the most cost-effective path by using the a-star algorithm.

First, we create two sets, viz- open and close. The open contains the nodes that have been visited, but their neighbors are yet to be explored. On the other hand, close contains nodes that, along with their neighbors, have been visited.

def aStarAlgo(start_node, stop_node): open_set = set(start_node) closed_set = set() g = {} #store distance from starting node parents = {}# parents contains an adjacency map of all nodes #ditance of starting node from itself is zero g[start_node] = 0 #start_node is root node i.e it has no parent nodes #so start_node is set to its own parent node parents[start_node] = start_node while len(open_set) > 0: n = None #node with lowest f() is found for v in open_set: if n == None or g[v] + heuristic(v) < g[n] + heuristic(n): n = v if n == stop_node or Graph_nodes[n] == None: pass else: for (m, weight) in get_neighbors(n): #nodes 'm' not in first and last set are added to first #n is set its parent if m not in open_set and m not in closed_set: open_set.add(m) parents[m] = n g[m] = g[n] + weight #for each node m,compare its distance from start i.e g(m) to the #from start through n node else: if g[m] > g[n] + weight: #update g(m) g[m] = g[n] + weight #change parent of m to n parents[m] = n #if m in closed set,remove and add to open if m in closed_set: closed_set.remove(m) open_set.add(m) if n == None: print('Path does not exist!') return None # if the current node is the stop_node # then we begin reconstructin the path from it to the start_node if n == stop_node: path = [] while parents[n] != n: path.append(n) n = parents[n] path.append(start_node) path.reverse() print('Path found: {}'.format(path)) return path # remove n from the open_list, and add it to closed_list # because all of his neighbors were inspected open_set.remove(n) closed_set.add(n) print('Path does not exist!') return None #define fuction to return neighbor and its distance
#from the passed node
def get_neighbors(v): if v in Graph_nodes: return Graph_nodes[v] else: return None
#for simplicity we ll consider heuristic distances given
#and this function returns heuristic distance for all nodes
def heuristic(n): H_dist = { 'A': 11, 'B': 6, 'C': 99, 'D': 1, 'E': 7, 'G': 0, } return H_dist[n] #Describe your graph here Graph_nodes = { 'A': [('B', 2), ('E', 3)], 'B': [('C', 1),('G', 9)], 'C': None, 'E': [('D', 6)], 'D': [('G', 1)], }
aStarAlgo('A', 'G') 

Output:

Path Found: [ 'A','E','D','G']

Further Reading

1. Best First Search Algorithm in AI | Concept, Implementation, Advantages, Disadvantages
2. Alpha Beta Pruning in AI
3. Decision Tree Algorithm Explained with Examples
4. Data Structures & Algorithm using Java a Beginners Guide

Source: GreatLearning Blog