a* algorithm in ai
Updated on 23rd Feb, 24 9.1K Views

This blog will provide you with all that you need to know about the A* algorithm, its working principles, advantages, disadvantages, and various applications in artificial intelligence. Furthermore, this blog will give you an in-depth guide to the working steps of A* algorithms.

Table of Contents

Watch this artificial intelligence video tutorial for beginners:

What is an A* Algorithm in AI?

A* algorithm is a popular and effective algorithm used in artificial intelligence for finding optimal paths and graph traversal. It efficiently searches for the shortest path between nodes in a graph by maintaining the cost to reach each node. Each node represents a specific position in the grid.

A* algorithm combines the advantages of Dijkstra’s algorithm (which guarantees the shortest path) and greedy best-first search (which uses heuristics to prioritize nodes likely to lead to the goal). It uses a heuristic function (often denoted as h(n)) that estimates the cost from a given node to the goal that leads to the most optimal path to the desired node.

The algorithm maintains two lists: the open list and the closed list. It evaluates nodes based on the sum of the costs to reach the node from the start (denoted as g(n)) and the heuristic estimate to the goal (h(n)). The node with the lowest total cost (f(n) = g(n) + h(n)) is selected from the open list for expansion. This process continues until the goal node is reached or there are no more nodes to explore.

Thinking of getting a master’s degree in AI? Enroll in Master’s in Artificial Intelligence in Europe.

Why is an A* Algorithm Preferred?

The A* algorithm stands out among other searching algorithms due to its unique blend of optimality and efficiency. Unlike Dijkstra’s algorithm, which explores all nodes uniformly, A* utilizes heuristics to guide its search, significantly reducing the number of nodes evaluated while ensuring the shortest path. Compared to greedy best-first search, A* strikes a balance by considering both the actual cost to reach a node and an estimated cost to the goal, guaranteeing an optimal solution, unlike Greedy Search, which might not ensure optimality. Its adaptability, versatility across different graph types, and ability to efficiently navigate complex spaces make A* the preferred choice for optimal pathfinding in various real-world scenarios.

Components of A* Algorithm

The algorithm is implemented on a graph consisting of nodes (or vertices) connected by edges (or links). Each node represents a state or a position in a space.

  • Cost Functions: A* uses two cost functions.
    • g(n): The actual cost to reach a node from the start node
    • h(n): The heuristic function estimating the cost from a node to the goal

The total cost for a node is given by the sum of these two functions:

F(n)=G(n)+H(n)

  • Open and Closed Lists: The algorithm maintains two lists: the open list and the closed list.
    • The open list stores nodes that are candidates for evaluation.
    • The closed list keeps track of nodes that have already been evaluated.
Graph of A Star Algorithm

How Does A* Algorithm Work?

To implement the A* algorithm in code, one must first understand how A*  algorithm works in the background. Here is a step-by-step guide on the working of A* algorithm:

Step 1: Initialization

  • First, define the starting node and the goal node within the graph.
  • Then, create two empty sets.
    • Open Set: Stores nodes to be explored, initially containing only the starting node.
    • Closed Set: Stores explored nodes.

Step 2: Start Iterating the Graph

  • While the open set is not empty, select the node with the lowest f-score from the open set.
  • This node will be the most eligible to reach the goal.
  • Move the selected node from the open set to the closed set.
  • Expand the current node: explore all its neighbors and their connections.
  • For each neighbor, calculate g(n) and h(n), and then calculate the f-score for the starting node using the formula: f(n) = g(n) + h(n).

f(n): Initial f-score of the starting node

g(n): g-score of the starting node (always 0 for the starting node)

h(n): A heuristic estimate of the cost to reach the goal node from the starting node

A* algorithm iterates the whole graph by following the following steps:

  • If the neighbor is not in the closed set
  • If the neighbor is not in the open set, add it with its f-score.
  • If the neighbor is already in the open set
  • Update the neighbor’s g-score and f-score if the new ones are lower.
  • If the neighbor is the goal node
  • Reconstruct and return the shortest path from the starting node to the goal node by tracing back through the g-score values.

Step 3: Termination

  • If the open set becomes empty and the goal node is not found, there is no path from the starting node to the goal node.
  • By repeatedly selecting the node with the lowest f-score for expansion, the A* algorithm efficiently explores the graph and ultimately finds the shortest path to the goal.

Interested in learning Artificial Intelligence? Register for our Artificial Intelligence Training in Sydney!

Pseudocode of the A* Algorithm

Using the following pseudo algorithm, you can easily implement the A* algorithm into your code:

function AStar(start, goal):

    openSet := {start}

    closedSet := {}

    cameFrom := an empty map

    gScore[start] := 0

    fScore[start] := heuristic_estimate(start, goal)

    while openSet is not empty:

        current := node in openSet with lowest fScore

        if current equals goal:

            return reconstruct_path(cameFrom, current)

        remove current from openSet

        add current to closedSet

        for each neighbor of current:

            tentative_gScore := gScore[current] + distance_between(current, neighbor)

            if neighbor in closedSet and tentative_gScore >= gScore[neighbor]:

                continue

            if neighbor not in openSet or tentative_gScore < gScore[neighbor]:

                cameFrom[neighbor] := current

                gScore[neighbor] := tentative_gScore

                fScore[neighbor] := gScore[neighbor] + heuristic_estimate(neighbor, goal)

                if neighbor not in openSet:

                    add neighbor to openSet

    return "No path found”

Thinking of competition between humans and AI, grab an interesting read on Will AI Replace Programmers via our blog.

Code for the A* Algorithm

Here is the code of A* algorithm in Python:

class Node:

    def __init__(self, position, parent=None):

        self.position = position

        self.parent = parent

        self.g = 0

        self.h = 0

        self.f = 0

    def __eq__(self, other):

        return self.position == other.position

    def __lt__(self, other):

        return self.f < other.f

def astar(start, goal, grid):

    open_set = []

    closed_set = set()

    start_node = Node(start)

    goal_node = Node(goal)

    heapq.heappush(open_set, start_node)

    while open_set:

        current_node = heapq.heappop(open_set)

        if current_node == goal_node:

            path = []

            while current_node is not None:

                path.append(current_node.position)

                current_node = current_node.parent

            return path[::-1]

        closed_set.add(current_node)

        for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]:

            new_position = (current_node.position[0] + dx, current_node.position[1] + dy)

            if (new_position[0] < 0 or new_position[0] >= len(grid) or

                new_position[1] < 0 or new_position[1] >= len(grid[0]) or

                grid[new_position[0]][new_position[1]] == 1):

                continue

            neighbor = Node(new_position, current_node)

            if neighbor in closed_set:

                continue

            neighbor.g = current_node.g + 1

            neighbor.h = abs(neighbor.position[0] - goal_node.position[0]) + abs(neighbor.position[1]  

            - goal_node.position[1])

            neighbor.f = neighbor.g + neighbor.h

            if any(neighbor == node and neighbor.g > node.g for node in open_set):

                continue

            heapq.heappush(open_set, neighbor)

    return None

Become a master of data science and AI by going through this PG Diploma in Data Science and Artificial Intelligence!

Advantages of the A* Algorithm in AI

The A* algorithm offers several advantages in the field of artificial intelligence (AI) for searching for an optimal solution. Here are the key advantages of A* algorithm:

  • Optimal Searching: A* algorithm ensures to obtain the shortest path between two points by following an appropriate heuristic function. 
  • Versatility: It can be applied in various domains, such as robotics, gaming, logistics, and more, and that makes it a versatile algorithm for finding the shortest path in different cases.
  • Heuristic Approach: A* works on a heuristic approach for searching that helps in exploring the optimal path for the destination node. This significantly reduces the number of nodes that need to be evaluated as compared to other uninformed search algorithms.
  • Adaptability: A* is adaptable and can be modified with the help of different heuristic functions that allow developers to alter it according to specific problem domains or requirements.

Disadvantages of the A* Algorithm in AI

While the A* algorithm is widely used and highly efficient, there are some disadvantages that we have listed here:

  • Memory Intensive: In certain scenarios, A* might consume more memory due to its need to store information about explored nodes and paths, especially in larger search spaces or grids.
  • Heuristic Dependency: A* heavily relies on heuristic functions for guiding its search. If the heuristic is poorly chosen or unable to find the right estimated cost, it might not be able to find the optimal path or might take longer to calculate.
  • Doesn’t Adapt to Dynamic Environments: A* assumes a static environment during the search process. If the environment changes dynamically, the previously calculated path may become invalid and require re-computation of the path.
  • Not Always Efficient with High Costs: In scenarios where the cost function between nodes is non-uniform or irregular, A* may explore a large number of unnecessary nodes before finding the optimal path, which will make unnecessary computations that ultimately increase the time to calculate the optimal path.

Applications of the A* Algorithm in AI

There are various applications of A* algorithm in artificial intelligence (AI) due to its effectiveness in finding optimal paths. Some of the most popular applications are as follows:

  • Robotics and Autonomous Vehicles: A* is used for planning paths in robotics to help robots navigate environments, avoid obstacles, and reach destinations efficiently. In self-driving vehicles, A* algorithm assists in route planning for optimal and safe navigation.
  • Game Development: A* is widely used in game development for creating intelligent NPC (non-playable character) behaviors, generating game maps, etc.
  • GPS and Navigation Systems: Many GPS and navigation systems utilize A* to calculate the shortest or fastest routes between locations, ensuring efficient travel planning for users.
  • Logistics and Supply Chain Management: A* aids in optimizing delivery routes, warehouse management, and logistics planning by finding the most efficient paths for transporting goods and managing inventory.
  • Network Routing and Traffic Management: In network routing protocols and traffic management systems, A* helps determine the best paths for data transmission or traffic flow to minimize congestion and optimize network efficiency.

Conclusion

In summary, the A* algorithm stands as a cornerstone in AI, offering an optimal pathfinding solution across diverse applications. Its blend of optimality, adaptability, and efficiency makes it a pivotal tool in robotics, gaming, logistics, and more. While it exhibits limitations, its widespread usage showcases its paramount role in advancing AI, enhancing navigation, and optimizing decision-making in complex environments.
For more information on artificial intelligence, visit our AI Community.

Course Schedule

Name Date Details
Data Scientist Course 02 Mar 2024(Sat-Sun) Weekend Batch
View Details
Data Scientist Course 09 Mar 2024(Sat-Sun) Weekend Batch
View Details
Data Scientist Course 16 Mar 2024(Sat-Sun) Weekend Batch
View Details

Leave a Reply

Your email address will not be published. Required fields are marked *

Speak to our course Advisor Now !

Related Articles

Subscribe to our newsletter

Signup for our weekly newsletter to get the latest news, updates and amazing offers delivered directly in your inbox.