# Salp Swarm Algorithm Optimized A* Algorithm and Improved B-Spline Interpolation in Path Planning
## 2 Path Planning Algorithm
### Improvement of the A* Algorithm
#### 2.2.2 Optimization Using the SSA
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Map ID**} & \multirow{2}{*}{**Algorithm**} & \multicolumn{3}{c}{**Cluster Maps**} & \multicolumn{3}{c}{**Random Maps**} \\ \cline{3-8}  & & **SN** & **Length** & **Time (ms)** & **SN** & **Length** & **Time (ms)** \\ \hline \multirow{4}{*}{\(10\)} & SSA-A* & 42 & 52.18 & 1.45 & 58 & 56.43 & 0.99 \\  & A* & 251 & 52.18 & 3.96 & 300 & 55.60 & 2.37 \\  & Dijkstra & 653 & 52.18 & 4.42 & 995 & 55.60 & 3.83 \\  & JPS-A* & 17 & 62.73 & 1.38 & 89 & 80.63 & 2.26 \\  & ACO & 220 & 52.18 & 31.52 & 273 & 60.67 & 29.63 \\ \hline \multirow{4}{*}{\(11\)} & SSA-A* & 52 & 55.36 & 1.53 & 53 & 53.84 & 0.89 \\  & A* & 239 & 54.53 & 3.84 & 319 & 51.60 & 2.55 \\  & Dijkstra & 586 & 54.53 & 3.91 & 994 & 51.60 & 3.9 \\  & JPS-A* & 19 & 60.04 & 1.29 & 35 & 60.63 & 0.88 \\  & ACO & 177 & 56.18 & 35.74 & 233 & 53.84 & 25.41 \\ \hline \multirow{4}{*}{\(12\)} & SSA-A* & 44 & 54.18 & 1.41 & 51 & 52.18 & 0.85 \\  & A* & 251 & 53.36 & 4.02 & 353 & 51.60 & 2.99 \\  & Dijkstra & 657 & 53.36 & 4.55 & 977 & 51.60 & 3.91 \\  & JPS-A* & 17 & 69.21 & 1.38 & 43 & 63.56 & 1.23 \\  & ACO & 192 & 55.01 & 36.54 & 242 & 54.18 & 24.47 \\ \hline \multirow{4}{*}{\(13\)} & SSA-A* & 52 & 53.36 & 1.47 & 45 & 52.43 & 0.83 \\  & A* & 227 & 51.6 & 3.72 & 362 & 51.60 & 3.51 \\  & Dijkstra & 627 & 51.6 & 4.18 & 965 & 51.60 & 4.42 \\  & JPS-A* & 23 & 67.31 & 1.49 & 30 & 62.14 & 0.83 \\  & ACO & 169 & 53.84 & 33.62 & 239 & 54.67 & 26.32 \\ \hline \multirow{4}{*}{\(14\)} & SSA-A* & 57 & 57.94 & 1.67 & 43 & 51.60 & 1.03 \\  & A* & 188 & 56.28 & 3.28 & 194 & 49.84 & 2.05 \\  & Dijkstra & 609 & 56.28 & 4.36 & 971 & 49.84 & 4.55 \\  & JPS-A* & 19 & 62.63 & 2.5 & 25 & 58.63 & 0.74 \\  & ACO & 171 & 58.77 & 36.19 & 187 & 52.08 & 26.83 \\ \hline \multirow{4}{*}{\(15\)} & SSA-A* & 45 & 54.77 & 1.5 & 43 & 51.60 & 0.98 \\  & A* & 229 & 52.77 & 3.86 & 346 & 51.60 & 3.53 \\ \cline{1-1}  & [PERSON] & 630 & 52.77 & 4.73 & 968 & 51.60 & 4.61 \\ \cline{1-1}  & JPS-A* & 20 & 68.63 & 2 & 26 & 60.97 & 0.74 \\ \cline{1-1}  & ACO & 189 & 57.6 & 32.46 & 251 & 52.43 & 25.72 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: _Cont._Table 3 presents a comparison of the average performance of the SSA-A* against other algorithms across different map sizes. Figure 6: Comparison of running time between the SSA-A* and Classical A* Algorithms. (**a**) corresponds to the 20 \(\times\) 20 grid map, (**b**) corresponds to the 35 \(\times\) 35 grid map, and (**c**) corresponds to the 50 \(\times\) 50 grid map. Based on the simulation experimental results, for the high-density clustered map, the SSA-A* reduces the running time by an average of 56.17% compared to [PERSON]'s Algorithm, by 50.35% compared to the A* algorithm, and by 95.26% compared to ACO. The SSA-A* reduces the number of search nodes by an average of 91.41% compared to [PERSON]'s Algorithm, by 75.97% compared to the A* algorithm, and by 73.91% compared to ACO. Figure 7: Comparison of search node count and path length between the SSA-A* and Classical A* Algorithms. (**a**) corresponds to the 20 \(\times\) 20 grid map, (**b**) corresponds to the 35 \(\times\) 35 grid map, and (**c**) corresponds to the 50 \(\times\) 50 grid map. For the low-density random map, the SSA-A* reduces the running time by an average of 73.77% compared to [PERSON]'s Algorithm, by 55.80% compared to the A* algorithm, and by 96.90% compared to ACO. The SSA-A* reduces the number of search nodes by an average of 94.31% compared to [PERSON]'s Algorithm, by 80.57% compared to the A* Algorithm, and by 77.34% compared to ACO. With the increase in map size, the advantages of the SSA-A* become more apparent. For example, on the 50 \(\times\) 50 low-density random map, the SSA-A* reduces the running time by 67.75% compared to [PERSON]'s Algorithm and by 84.12% compared to the A* algorithm. Additionally, the number of search nodes is reduced by 96.73% compared to [PERSON]'s Algorithm and by 86.10% compared to the A* algorithm.