# Global Path Planning for Differential Drive Mobile Robots Based on Improved BSGA* Algorithm
## 3 Improved BSGA* Algorithm
### Improved Heuristic Functions  
The heuristic function determines the quality of the A* algorithm [37]. As shown in Figure 5, the A* algorithm, using Euclidean distance as the heuristic function, can search a feasible path, but there are too many search nodes and the calculation time is too long. Therefore, this study addresses the above shortcomings by improving the heuristic function. When \(h(n)=0\), the A* algorithm is transformed into a Dijkstra algorithm, and a large number of nodes will be searched. Although the total cost in the planning process is the same as the actual cost, it is inefficient [38]. When \(g(n)=0\), the A* algorithm is transformed into the Breadth-First Search (BFS) algorithm, which has high planning efficiency but not an optimal path [39]. In order to make the path planning process both efficient and qualitative, \(h(n)\) should usually occupy a larger weight in the beginning of the planning, so that the algorithm can search near the target point more quickly. At the end of the planning process, \(g(n)\) should occupy a larger weight, so as to avoid repeated searches of nodes that may occur near the target point and reduce the total turning angle of paths. Since Euclidean  
Figure 4: Program flow of A* algorithm. distance is used as the heuristic function in this study, \(h(n)\) tends to be slightly smaller than the actual cost from the current node to the target node. As the current node gradually approaches the target node, this gap will become smaller and smaller. In the optimal case, \(h(n)\) is always the same as the actual cost, so the algorithm can always select the optimal node. But this is often difficult to achieve. Therefore, this study combined with the Gaussian function to construct the attenuation coefficient \(D(n)\) for dynamically adjusting the weight ratio of the heuristic function; the heuristic function was rewritten as the following equation:  
\[\left\{ \begin{array}{l}f(n)=g(n)+\mathrm{h}(n)\,/\,D(n)\\ D(n)=\frac{1}{\sigma\sqrt{2\pi}}e^{-\frac{(h(n)-\mu)^{2}}{2\sigma}}\end{array} \right. \tag{8}\]  
Let \(\mu=0\) and \(\sigma=1/\sqrt{2\pi}\). At the beginning of the algorithm, the current node is far from the target point, at this time \(\,D(n)\to 0^{+}\,\), so the weight ratio of \(h(n)\) increases, thus improving the search efficiency. As the algorithm runs, the current node gradually approaches the target point, \(D(n)\) gradually increases, and the weight ratio of \(h(n)\) gradually decreases to reduce the total turning angle of the path. In order to verify the performance of the Gaussian-A* (GA*) algorithm, Matlab2020a software was used to write the algorithm program. The Intel workstation running the program was equipped with an i9-10900 processor, with 64 GB RAM and 3.70 GHz main frequency. The subsequent simulation was also run based on this workstation. As shown in Figures 5 and 6, 50 executions were carried out on grid maps with sizes of 10 \(\times\) 10, 20 \(\times\) 20 and 30 \(\times\) 30, respectively. Table 1 shows the states represented by the different colored grids. It can be seen that, compared with the A* algorithm, the path generated by the GA* algorithm has fewer turning points and the number of nodes searched is also less. According to Table 2, it can be seen that, on the 10 \(\times\) 10 grid map, the calculation time, the number of search nodes, and the total turning angle of the GA* algorithm are, respectively, reduced by 64.43%, 40.00%, and 37.5% relative to the A* algorithm. On the 20 \(\times\) 20 grid map, the calculation time, number of search nodes, and the total turning angle of the GA* algorithm are, respectively, reduced by 80.98%, 56.38%, and 25% relative to the A* algorithm. On the 30 \(\times\) 30 grid map, these three were reduced by 84.09%, 70.91%, and 41.67%, respectively. Although the length of the path generated by the GA* algorithm is not much different from that of the A* algorithm, it has higher efficiency, and with the gradual exp  
Figure 5: Simulation results of traditional A* algorithm under different map environments.