A* Algorithm
As promised I am presenting a blog on the A* algorithm as a follow up on my blog on Dijkstra's shortest path first algorithm. The algorithm was developed by Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968. During the time in which I wrote this blog Nils Nilsson passed away on April 23, 2019. I was never fortunate enough to take a course from Prof. Nilsson but through studying his work I would like to thank him for making me a better engineer. Rip Prof. Nilsson.
The A* algorithm A* achieves better performance than Dijkstra's SPF by using heuristics to guide its search. Isn't it amazing that some of the most relevant algorithms today were developed some fifty years ago?
For this algorithm it can be best displayed by using a fuller graph such as that depicted in Figure 1. Each small box or cell is a grid location. At each grid the options are to move in one of eight directions N, S, E, W, NW, NE, SW, or SE. In the example shown the starting grid is 15 and the ending grid is 9. In this problem there are barriers at grids 12 and 17 that block those from being occupied. The problem is to move from starting grid to target grid in an optimum manner. Movement is also blocked outside of the overall rectangle of grids. As example from grid '0' motion can only occur to grid '5', '1' or '6'. All others are blocked.
This problem could be thought of as a strategy to move a robot within a warehouse to minimize total travel time or distance. If the layout is known a priori to starting out then this would be path planning.
Figure 1 - Graph
The problem could be formulated exactly the same as the Dijkstra code using a dictionary. The dictionary in this case would have 24 keys, one for each node. The entries for each key would be up to 8 neighboring nodes with the cost of that edge. While this works the code and the data entry for each problem becomes cumbersome and is prone to error. We can make use of the rectilinear grid layout and treat a move as being in a vector direction (1,0), (-1,0), (0,1), (0,-1), (1,1), (1,-1), (-1,1) and (-1,-1) from the current grid (x,y). In this formulation the weight on each move is the vector length either 1 or sqrt(2).
The entry for a given problem will be a list of rows similar to figure 1. The row entries will contain a '0' depicting non-occupied and 'x' depicting occupied. For the example in figure 1 we would have 5 rows with 5 entries per row. This list we will call our 'Grid' structure which defines the specific problem.
Like the Dijkstra algorithm there will be a cost to move from the current location to the adjacent location but in this case there will a heuristic h(n) added to the cost to move, f(n) = g(n) + h(n). The cost to move from the current location to adjacent location n is g(n) and the heuristic h(n) is the minimum cost from location n to the end target. If the move is in a direction away from the target then the cost of the move is penalized by h(n). This helps eliminate some searching and improves the overall algorithm efficiency. The cost g(n) could have various weights but as explained in this development will be +1 to adjacent cells vertically and horizontally and sqrt(2) to adjacent diagonal cells. If h(n) is set to zero the solution is the Dijkstra algorithm.
As in the SPF algorithm there will initially be a list Q of all non-visited grids and a list S of already visited grids. The grids not available will start out in the list Q but will be moved as encountered. There will be a list v of costs for each grid location. Initially v will have all entries set to infinity except for the starting grid which is initialized to 0. In the python code S and Q will be a list of strings.
A restriction on the heuristic h(n) is that the cost must not be greater than the cost to move from n to the end cell. For the rectilinear grid we can choose the diagonal distance from n to the end target.
The iterative algorithm is as follows:
- Initialize list of grids not visited, Q, and visited or unavailable, S.
- while Q is not empty or until the end grid is visited:
- from the current grid visit each neighboring grid
- for each neighbor compute the cost f(n) = g(n) + h(n)
- Remove the current grid from Q and add it to the S
- Continue until the end is visited or Q is empty.
Python Code
The beginning of the code has comments that show the algorithm in pseudo code (lines 8-31). I tried to keep the actual Python code as close as possible to the pseudo code
The full code listing is given below. The input, A, is given as a list of rows. Each row has an entry for every grid in the row. Unoccupied cells are denoted with a int 0 and occupied cells are denoted with an 'x'.
The heavy lifting is done in the function 'astar' (line 35) with inputs A, start and end, where start and end are the starting and ending grids.
Listing 1 astar_algo.py
Output
The output is the list A with the cells chosen along the solution path with a '1'. The cost to move from start to end is displayed as the distance value. The number of nodes visited is displayed as the value total. Outputs are shown for two examples.
Here is the path for example 1, starting in the green grid, 15, and proceeding to the yellow grid, 9.
Results Example 1 Path
Of the 25 grid locations 22 are available to search and 21 were actually visited. For the Dijkstra algorithm 22 grids were visited. The distance traveled on the optimal path is 4.828 units.
Example 2 is a 10 x 10 grid. Of the 100 grid locations 90 are available to search and 63 were actually visited. For the Dijkstra algorithm 88 grids were visited. The distance traveled on the optimal path is 11.899 units.
Results Example 2 Path
Summary
In summary the A* algorithm is an improvement on the Dijkstra algorithm. It achieves this improvement by penalizing moves that are away from the final target location. The improvement is realized as fewer nodes that need to be visited before the optimum is found.