Understanding A* Path Algorithms and Implementation with Python



Original Source Here

Understanding A* Path Algorithms and Implementation with Python

The A* algorithm is one of the most effective path finding algorithms used to find the shortest path between two points. It was first published in 1968 by Peter Hart, Nils Nilsson and Bertram Raphael [1]. Although it initially can be seen as an extension of Dijkstra’s algorithm, it has become one of the most frequently used pathfinding algorithms today.

Via Pixabay

The A* algorithm basically reaches the optimum result by calculating the positions of all the other nodes between the starting node and the ending node. In addition, it is faster than Dijkstra’s algorithm due to the heuristic function[2].

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

f(n) : Calculated total cost of path

g(n): The cost of path between the first node and the current node

h(n): Heuristic function

If we want to find the shortest path on Figure 2 using the above function;

Figure 2. Sample route

Let’s say we are trying to get from point X to point Y. Since the point X is not moved to a different node, the g(n) cost does not occur and its value is 0. The heuristic value of this point is the value 5 written on the node in red. In such problems, the heuristic value in general is the air distance between the current node and the desired node. There are two points to go from point X.
In case of going to point A, g(n) = 5 (path cost) because it moves to a new node. The heuristic is set to h(n) = 1. The f(n) value of point A is found as 5+1 = 6. If we want to find the f(n) values ​​of all points using this method,

X— A => g(A) + f(A) = 5 + 1 = 6,

A — Y=> g(Y) + f(Y) = 6+ 0= 6,

X— B => g(B) + f(B) = 1+ 4= 5,

B — C => g(C) + f(C) = 3+ 2= 5,

C — Y=> g(Y) + f(Y) = 5 + 0= 5,

As seen in the simple example above, the shortest path is the X-B-C-Y route. The cost of this road is 5 units, while the cost of the alternative X-A-Y route is 6 units. The example in Figure 3 can be examined in more detail once we have fully understood how to use the above equation.

Figure 3. Sample route v2

Let’s say we want to reach node A from node J. There are 2 points (B and F), that can be reached from point A. Calculating the overhead costs, we get f(B) = 8 + 6 = 14 and f(F) = 3+6 =9.Since the least cost is at point F, the A* algorithm continues from here. There are 2 paths at point F. f(G) = 4 +5 = 9 and f(H) = 10 + 3 = 13. Since the least cost is at point G, we can do it from that point. Then, following the I and J nodes, we get f(I) = 7 + 1 = 8 , f(J) = 10. Since all the values ​​obtained after going to the F node are less than the f(B) node, it was not returned to the B node. But in a different scenario, let’s assume that f(I) is greater than f(B) after nodes F and G (f(I) > 14). In this case, according to the A* algorithm, the process is interrupted here and the path is continued with the B node. Here, as soon as f(C) > f(I), the path determination process continues again from the I node.

Implementation with Python

All of the codes below are available at https://github.com/ademakdogan/Implementation-of-A-Algorithm-Visualization-via-Pyp5js-

First, the grid structure is created. Some nodes here are marked as obstacles. Then the start and end nodes are determined and the shortest path between these two points is found with the A* algorithm [3]. The working logic of the algorithm is basically based on two lists named open_set and closed_set. While there are nodes that can be processed in open_set, there are node paths that are processed in closed_set and therefore should not be repeated (In some approaches, obstacles are also thrown directly into the closed_set list, while in some approaches, it can be added as one of the qualifying properties of each node produced as an object.). As a result of various processes, these lists are filled and emptied, and the final result is reached.

Pseudocodes of all stages can be viewed on wikipedia.

Figure 4. Sample of A* algorithms-link

Github

Figure 4 shows the python implementation of the A* algorithm. Pyp5js library was used to visualize in this work. In addition, the A* algorithm can work according to the obstacle list to be given specifically, the coordinates of the start and end nodes and the size of the grid structure. Thus, this project can also be used against specific problems.

python AStar.py -c 25 -r 25 -s 1 -q 3 -e 23 -t 21 -l True

As a result,

The way found!!!
23 20
23 19
23 18
23 17
23 16
23 15
23 14
23 13
23 12
23 11
23 10
23 9
23 8
23 7
23 6
23 5
23 4
23 3
22 3
21 3
20 3
19 3
18 3
17 3
16 3
15 3
14 3
13 3
12 3
11 3
10 3
9 3
8 3
7 3
6 3
5 3
4 3
3 3
2 3
1 3

Pyp5js

Pyp5js is a framework for visualizing python codes on the browser. It enables the use of p5.js javascript library via Transcrypt with Python. After the necessary installations are made, it is simply run with the following command.

$ SKETCHBOOK_DIR='~/my-custom-sketchbook' pyp5js serve

Afterwards, the necessary config settings are made by accessing the interface section via http://localhost:5000/ . In the specified folder (SKETCHBOOK_DIR), operations are performed according to the codes in the python file that is the same name as the project name. If you want to examine this project in detail, https://berinhard.github.io/pyp5js/ can be visited.

As a result, the A* algorithm is one of the most frequently used path finding algorithms. In this article, the working principles of this algorithm and its coding with python are discussed. All codes can be found at github. The pyp5js library was used to visualize the algorithm. In the next articles, comparisons of different path determination algorithms with the A* algorithm will be discussed.

Github : https://github.com/ademakdogan

Linkedin : https://www.linkedin.com/in/adem-akdo%C4%9Fan-948334177/

References

[1] Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”. IEEE Transactions on Systems Science and Cybernetics. 4 (2): 100–107.

[2] Zeng, W.; Church, R. L. (2009). “Finding shortest paths on real road networks: the case for A*”. International Journal of Geographical Information Science. 23 (4): 531–543.

[3] Hetland, Magnus Lie (2010), Python Algorithms: Mastering Basic Algorithms in the Python Language, Apress, p. 214, ISBN 9781430232377.

AI/ML

Trending AI/ML Article Identified & Digested via Granola by Ramsey Elbasheer; a Machine-Driven RSS Bot

%d bloggers like this: