Skip to main content

A* search algorithm

A* search algorithm is a graph traversal and path search algorithm often used in many fields of computer science. Starting from the starting node, it aims to find the path to the target node having the smallest cost.

It was made as a part of the Shakey project. The goal of the project was to build a mobile robot that could plan its own action. It yielded in the making of Shakey the Robot, the first general-purpose robot made in 1966. A* search algorithm was developed to help Shakey solve the pathfinding problems so it could move around.

How does it work?​

A* search algorithm combines information from Dijkstra’s algorithm and the Greedy Best-First-Search algorithm. Dijkstra’s algorithm favours vertices that are closer to the starting point, while the Greedy Best-First-Search algorithm favours vertices that are closer to the goal.

A* search algorithm uses heuristics to determine the path it will take. The heuristic function provides an estimate of the minimum cost between the current vertex and the target vertex. The algorithm will combine the actual cost from the start vertex with the estimated cost to the target vertex. It will use the result to select the next vertex to evaluate.

The difference from other shortest path algorithms​

The difference from other shortest path algorithms Unlike other traversal techniques, A* search algorithm has “brains”. It is a really smart algorithm that uses heuristic methods to guide itself. A* search algorithm is more efficient as its use of heuristics allows the algorithm to make a better choice about what path to take next.

While Dijkstra’s algorithm will always find the shortest path between the starting vertex and every other vertex in the graph, A* search algorithm will find the shortest path between the starting vertex and target vertex. In a graph with a small number of nodes, Dijkstra’s algorithm will suffice. However, in a real-life situation, we are dealing with the problem of an enormous number of combinations. For that, we need to use a “guided” algorithm that can decide the optimal route quickly and accurately. A* search algorithm only performs steps if it seems promising and reasonable, unlike other shortest path algorithms. It runs toward the goal and doesn’t consider any non-optimal steps if it doesn’t have to consider them.

A* search algorithm is very useful for artificially intelligent systems such as machine learning and game development where characters navigate complex terrains and obstacles to reach players.

Pseudocode​

Before starting with the pseudocode, we need to explain the node structure. Each node has three attributes f, g, and h. Those attributes are parameters of the following equation:

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

Where:

  • f is cost of the transversal
  • g is the actual cost of transversal from the starting node
  • h is the estimate cost of transversal to the target node 
INIT LIST openList
INIT LIST closedList
startNode.f = 0
ADD startNode TO openList
WHILE openList is not empty
    currentNode = node with the least f value
    REMOVE currentNode FROM penList
    ADD currentNode TO closedList
    IF currentNode = goal THEN
        FINISHED
    ENDIF
    children = list of nodes adjacent to currentNode
 
    FOR EACH child in children
        IF child is in closedList
            CONTINUE
        ENDIF
        child.g = currentNode.g + distance between child and current
        child.h = distance from child to target
        child.f = child.g + child.h
        IF child.position is in the openList's nodes positions
            IF the child.g is higher than the openList node's g
                CONTINUE
        ENDIF
          ENDIF
        ADD the child TO the openList
    ENDFOR
ENDWHILE

Usage in NetworkX​

astar_path(G, source, target, heuristic=None, weight='weight')

Not fast enough? Find 100x faster algorithms here.

Method input​

The first input parameter of the method, G, is a NetworkX graph. The second parameter, source, is the source node of the shortest path. The third parameter, target, is the target node of the shortest path. The fourth parameter, heuristic, is a function to evaluate the estimate of the distance from the a node to the target. The function takes two node arguments and must return a number. The fifth parameter, weight, represents the edge attribute that should be used as the edge weight. If it’s not specified, the weight of all edges will be 1.

Method output​

The output of the method is a list of nodes.

Example​

Using A* search algorithm in Python allows us to use custom methods and function as heuristics. In the following example, we designed the distance heuristic which calculates geometrical distances between the points. 

import networkx as nx
import matplotlib.pyplot as plt


def dist(a, b):
    (x1, y1) = a
    (x2, y2) = b
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5


G = nx.grid_graph(dim=[3, 3])  # nodes are two-tuples (x,y)
nx.set_edge_attributes(G, {e: e[1][0] * 2 for e in G.edges()}, "cost")
path = nx.astar_path(G, (0, 0), (2, 2), heuristic=dist, weight="cost")
length = nx.astar_path_length(G, (0, 0), (2, 2), heuristic=dist, weight="cost")
print("Path: ", path)
print("Path length: ", length)

pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color="#f86e00")
edge_labels = nx.get_edge_attributes(G, "cost")
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.show()

Where to next?​

There are many graph algorithms libraries out there, with their own implementations of A* search algorithm. NetworkX's algorithms are written in Python, and there are many other libraries that offer faster C++ implementations, such as MAGE, a graph algorithms library developed by Memgraph team.

Memgraph for NetworkX developers