# Global Path Planning for Differential Drive Mobile Robots Based on Improved BSGA* Algorithm
## 4 Simulation and Experiments  
### Performance Comparison of Different Algorithms  
In order to verify the performance of the improved BSGA* algorithm, the 15 \(\times\) 15 and 30 \(\times\) 30 grid maps constructed in Section 3.3 were used to compare the improved BSGA* algorithm with the ACO algorithm [40,41], D* lite algorithm [42], and GA [43]. The ACO algorithm [44] uses pheromone as the medium to transmit the information learned by ants in the process of moving, so that ants can move to the area with high pheromone concentration spontaneously. The parameter settings of the ACO algorithm are shown in Table 5. The GA [45] retains individuals according to their fitness by simulating the biological evolution process and updates the population through genetic and mutation operations. The parameters settings of GA are shown in Table 6. The D* lite algorithm uses the same heuristic function as the A* algorithm to guide the search [46], but the difference is that the D* lite algorithm first takes the target point as the starting point for reverse search to obtain the shortest path information, and can use the previously obtained information to reduce the search scope when it is necessary to re-plan during a later process. Figure 13a,b shows the paths generated by the above-mentioned various algorithms on the 15 \(\times\) 15 and 30 \(\times\) 30 grid maps, respectively. It can be seen that, compared with the ACO algorithm, GA, and the D* lite algorithm, the path generated by the improved BSGA* algorithm is smoother and the total turning angle is smaller. It is worth noting that, due to the randomness of the paths generated by the ACO algorithm and GA, the results of each execution may be different. For better comparison, these three algorithms were executed \begin{table}
\begin{tabular}{c c} \hline \hline
**Parameters** & **Value** \\ \hline Population size & 500 \\ Number of generations & 200 \\ Crossover probability & 0.8 \\ Mutation probability & 0.2 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Setting of genetic algorithm parameters. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Map Size** & **Algorithm** & **Average Calculation Time/ms** & **Number of Searched Nodes** & **Total Angle/\({}^{\circ}\)** & **Path Length** \\ \hline \multirow{3}{*}{\(15\times 15\)} & A* & 975.49 \(\pm\) 16.29 & 95 & 360 & 21.55 \\  & BSGA* & 321.92 \(\pm\) 7.27 & 63 & 270 & 21.55 \\  & Improved BSGA* & 366.31 \(\pm\) 8.35 & 63 & 36.87 & 20.42 \\  & A* & 12,316.77 \(\pm\) 99.37 & 388 & 540 & 44.52 \\
30 \(\times\) 30 & BSGA* & 886.42 \(\pm\) 12.69 & 131 & 360 & 44.52 \\  & Improved BSGA* & 950.80 \(\pm\) 14.47 & 131 & 65.42 & 42.19 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Comparison of paths generated by A*, BSGA*, and improved BSGA* algorithms under \(15\times 15\) and 30 \(\times\) 30 grid maps; the values of average calculation time are reported as mean \(\pm\) standard deviation for 50 executions. \begin{table}
\begin{tabular}{c c} \hline \hline
**Parameters** & **Value** \\ \hline Maximum number of iterations & 200 \\ Number of ants & 50 \\ The expectation heuristic factor & 1.5 \\ The pheromone heuristic factor & 7 \\ The evaporation coefficient of pheromone & 0.3 \\ Initial amount of pheromone concentration & 1 \\ The constant coefficient & 1 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Setting the parameters of ant colony algorithm. 50 times, respectively, on the above two grid maps; the results are shown in Table 7. It can be seen that, on the 15 \(\times\) 15 grid map, the improved BSGA* algorithm is 69.84%, 5.81%, and 85.97% lower than the ACO algorithm, 69.76%, 92.50%, and 6.20% lower than the GA, and 89.45%, 5.26%, and 86.34% lower than the D* line algorithm in terms of calculation time, path length, and total turning angle, respectively.