A* Search

A* Search is an informed best-first search algorithm that efficiently determines the lowest cost path between any two nodes in a directed weighted graph with non-negative edge weights. This algorithm is a variant of Dijkstra’s algorithm. A slight difference arises from the fact that an evaluation function is used to determine which node to explore next.

Evaluation Function

The evaluation function, f(x), for the A* search algorithm is the following:

f(x) = g(x) + h(x)

Where g(x) represents the cost to get to node x and h(x) represents the estimated cost to arrive at the goal node from node x.

For the algorithm to generate the correct result, the evaluation function must be admissible, meaning that it never overestimates the cost to arrive at the goal node.

The Algorithm

The A* algorithm is implemented in a similar way to Dijkstra’s algorithm. Given a weighted graph with non-negative edge weights, to find the lowest-cost path from a start node S to a goal node G, two lists are used:

• An open list, implemented as a priority queue, which stores the next nodes to be explored. Because this is a priority queue, the most promising candidate node (the one with the lowest value from the evaluation function) is always at the top. Initially, the only node in this list is the start node S.
• A closed list which stores the nodes that have already been evaluated. When a node is in the closed list, it means that the lowest-cost path to that node has been found.

To find the lowest cost path, a search tree is constructed in the following way:

1. Initialize a tree with the root node being the start node S.
2. Remove the top node from the open list for exploration.
3. Add the current node to the closed list.
4. Add all nodes that have an incoming edge from the current node as child nodes in the tree.
5. Update the lowest cost to reach the child node.
6. Compute the evaluation function for every child node and add them to the open list.

Just like in Dijkstra’s algorithm, the lowest cost is updated as the algorithm progresses in the following way:

current_lowest_cost = min(current_lowest_cost, parent_node_cost + edge_weight)

All nodes except for the start node start with a lowest cost of infinity. The start node has an initial lowest cost of 0.

The algorithm concludes when the goal node G is removed from the open list and explored, indicating that a shortest path has been found. The shortest path is the path from the start node S to the goal node G in the tree.

Note: The algorithm ends when the goal node G has been explored, NOT when it is added to the open list.

Example

Consider the following example of trying to find the shortest path from S to G in the following graph:

Each edge has an associated weight, and each node has a heuristic cost (in parentheses).

An open list is maintained in which the node S is the only node in the list. The search tree can now be constructed.

Exploring S:

A is the current most promising path, so it is explored next:

Exploring D:

Exploring F:

Notice that the goal node G has been found. However, it hasn’t been explored, so the algorithm continues because there may be a shorter path to G. The node B has two entries in the open list: one at a cost of 16 (child of S) and one at a cost of 18 (child of A). The one with the lowest cost is explored next:

Exploring C:

The next node in the open list is again B. However, because B has already been explored, meaning a shortest path to B has been found, it is not explored again and the algorithm continues to the next candidate.

The next node to be explored is the goal node G, meaning the shortest path to G has been found! The path is constructed by tracing the graph backward from G to S:

Using the A* Algorithm

This algorithm is guaranteed to find a shortest path if one exists. One of the main uses of this algorithm is route planning. However, there are many other uses.