Skip to main content

A* search algorithm

A* 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.

A* search algorithm 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 openListINIT LIST closedListstartNode.f = 0ADD startNode TO openListWHILE 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    ENDFORENDWHILE

Usage in NetworkX#

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

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 nximport 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()

The output is:

Path: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]Path length: 6

Astar matplotlib

The first output represents the shortest path from point (0,0) to point (2,2). The second output is the length of the shortest path.