# Global Path Planning for Differential Drive Mobile Robots Based on Improved BSGA* Algorithm
## 3 Improved BSGA* Algorithm
### Multi-Layer Turning Point Filtering Strategy  
In order to further reduce the total turning angle and improve smoothness, this study proposed an optimization strategy based on turning point filtering. The specific procedures are as follows:  
1. Store the path points \(Grid\_node_{i}(i=1,2,\ldots)\) obtained by BSGA* algorithm in the \(CloseList\_Path\) and store the obstacles and environment boundaries in the \(Obstacle\_nodes\). Store the \(Start\_node=(X_{s},Y_{s})\) and the \(target\_node=(X_{e},Y_{e})\) in the \(Opt\_path\). 2. Calculate the slope \(k_{1}\) and \(k_{2}\) of \(Start\_node\) and \(Grid\_node_{1}\), \(Start\_node\) and \(Grid\_node_{2}\) respectively. If \(k_{1}=k_{2}\), then \(Grid\_node_{1}\) is not a turning point, continue to calculate the slope \(k_{i}\) of \(Start\_node\) and \(Grid\_node_{i}\) in turn until \(k_{1}\
eq k_{i}\), then \(Grid\_node_{i-1}\) is the turning point. \(Grid\_node_{i}\) will be stored in the set of \(Turn\_nodes\), then repeat the above process from \(Grid\_node_{i}\) until it reaches the target point. 3. Connect the previous node \(Grid\_node_{i-2}\) of the \(Grid\_node_{i-1}\) with the next node \(Grid\_node_{i}\). If the connection between them passes through the obstacle, then \(Grid\_node_{i-1}\) will be stored in \(Opt\_path\). If the connection does not pass through the obstacle, \(Grid\_node_{i-1}\) will be deleted in \(Turn\_nodes\). Judge all the turning points in \(Turn\_nodes\) in turn according to this step. 4. Repeat steps (2) and (3) until the connection between the previous node and the next node of any of the turns in \(Turn\_nodes\) passes through the obstacle and connects the nodes in \(Opt\_path\) to generate the optimized path, then the algorithm stops. To verify the effectiveness of the turning point filtering strategy, as shown in Figures 11 and 12, 50 executions were conducted, respectively, to compare the A*, BSGA*, and improved BSGA* algorithms under grid maps with sizes of 15 \(\times\) 15 and 30 \(\times\) 30. The \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Map Size** & **Algorithm** & \
\begin{tabular}{c} **Average Calculation** \\ **Time/ms** \\ \end{tabular} &
\begin{tabular}{c} **Number of** \\ **Searched Nodes** \\ \end{tabular} & **Total Angle/\({}^{c}\)** & **Path Length** \\ \hline \multirow{4}{*}{\(10\times 10\)} & A* & 574.94 \(\pm\) 12.27 & 64 & 450 & 19.49 \\  & GA* & 280.79 \(\pm\) 4.48 & 51 & 270 & 20.07 \\  & BSGA* & 221.71 \(\pm\) 2.42 & 46 & 360 & 20.66 \\  & A* & 1593.84 \(\pm\) 18.83 & 186 & 450 & 39.63 \\  & GA* & 1099.21 \(\pm\) 7.24 & 142 & 450 & 42.56 \\  & BSGA* & 645.77 \(\pm\) 7.24 & 102 & 360 & 46.66 \\  & A* & 6192.52 \(\pm\) 38.80 & 392 & 810 & 56.11 \\
30 \(\times\) 30 & GA* & 3898.71 \(\pm\) 27.79 & 274 & 405 & 62.46 \\  & BSGA* & 1180.20 \(\pm\) 4.77 & 138 & 360 & 66.66 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Comparison of the paths generated by the A*, GA*, and BSGA* algorithms under different grid maps, the values of average calculation time are reported as mean \(\pm\) standard deviation for 50 executions. purple nodes in Figures 11c and 12c are the filtered turning points. As can be seen from Table 4, the calculation time of improved BSGA* is reduced by 62.45% compared with the A* algorithm and improved by 13.79% compared with the BSGA* algorithm in the 15 \(\times\) 15 grid map. This is because improved BSGA* is implemented by re-performing the turning point filtering on the paths planned by the BSGA* algorithm, so the calculation time is slightly longer. Compared with the A* and BSGA* algorithms, the total turning angle of paths planned by improved BSGA* is reduced by 89.76% and 86.34%, respectively, the path length is reduced by 1.13. In the 30 \(\times\) 30 grid map, compared with A* and BSGA*, the calculation time of improved BSGA* is reduced by 92.28% and that of BSGA* is improved by 7.26%, the total turning angle of the path is reduced by 87.89% and 81.83%, the path length is reduced by 2.33, respectively.