# RJA-Star Algorithm for UAV Path Planning Based on Improved RSDOS Model
## 2 Materials and Methods
### Improved Path Planning Algorithm
Figure 8 is the results of a simulation run under scenario 11. Compared with A-star algorithm, RJA star algorithm reduces 94.4% rotation angle, 99.87% calculation time and 10.05% path length. It can be seen from the results in Figure 9 that the path of the JPS algorithm will stick to the obstacle, which will threaten the safety of the UAV. The RJA star path is smoother and safer than the JPS algorithm, and it can avoid obstacles to reach the destination in many cases. We can see that the RJA-star algorithm avoided obstacles well. Figure 8: Comparison of path length between the two algorithms. Figure 7: **(a)** The fitting results and details of RJA star algorithm on scenario 11. **(b)** Fitting result of XY plane of RJA star algorithm in scenario 11. **(c)** Fitting result of XZ plane of RJA star algorithm in scenario 11. **(d)** Fitting result of YZ plane of RJA star algorithm in scenario 11. After 100 simulation experiments, we fit the two algorithms into the scenario 1--scenario 10. We limit the random range within the current map, and generate disjoint obstacles based on the xoy plane. The number of obstacles is 8/10 of the projected area of the current map on the xoy plane, and then a random height is given. We compare the two algorithms on a 20 m long map and a 10 m long map. We can obtain the path lengths (as shown in Figure 8), exploration nodes (as shown in Figure 9), computation time (as shown in Figure 10) and the number of corners (as shown in Figure 11) for the A-star algorithm and the RJA-star algorithm. The maximum number of corners are shown in Figure 11.

Figure 10: Comparison of the average time of the two algorithms. Figure 9: Comparison of two algorithms for exploring nodes. The result shows that the path length of the RJA star algorithm is not much different from that of the A-star algorithm. It can be seen from the results in the Figure that the number of nodes of RJA star algorithm is far less than that of A star algorithm. The y-axis on the left of Figures 9 and 10 respectively represents the number of exploration nodes and average time, and the y-axis on the right represents the percentage reduction of RJA star algorithm compared with A-star algorithm,, which can be calculated by Equation (2). We may know from the Figure that RJA star algorithm has the advantage of short computing time. The five sizes of the map are compared in Table 2. \begin{table}
\begin{tabular}{c c c c c} \hline \hline \multirow{2}{*}{**Map Size**} & \multirow{2}{*}{**Path Parameters**} & \multirow{2}{*}{**Traditional A-Star**} & \multirow{2}{*}{**RJA-Star**} & **RJA-Star Reduced** \\  & & & & **Proportion** \\ \hline \multirow{6}{*}{20 \(\times\) 20} & Average running time/s & 2.56 & 1.068 & 58.28\% \\  & Average number of nodes & 4710 & 9 & 99.81\% \\  & Total distance/s & 36.806 & 34.806 & 4.80\% \\  & Max turning & 90\({}^{\circ}\) & 11.286\({}^{\circ}\) & 96.59\% \\  & Number of turns & 11 & 1 & 87.46\% \\  & Average running time/s & 28.742 & 4.213 & 85.34\% \\  & Average number of nodes & 20,806 & 20 & 99.90\% \\
40 \(\times\) 40 & Total distance/s & 64.847 & 62.113 & 4.22\% \\  & Max turning & 90\({}^{\circ}\) & 29\({}^{\circ}\) & 67.78\% \\  & Number of turns & 21 & 1 & 95.24\% \\  & Average running time/s & 91.83 & 6.211 & 93.24\% \\  & Average number of nodes & 39,546 & 29.5 & 99.93\% \\
60 \(\times\) 60 & Total distance/s & 93.131 & 90.931 & 2.36\% \\  & Max turning & 90\({}^{\circ}\) & 25.51\({}^{\circ}\) & 71.66\% \\  & Number of turns & 31 & 2 & 93.55\% \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Comparison of experimental data of three different specifications of network diagrams. Figure 11: Comparison of the number of corners and the maximum angle between the two algorithms. ### Discussion

We select scenario 1, 4, 7, 9. Make the number of obstacles equal to 5/10 of the area of the xoy plane, run the algorithm 20 times on each map, and conduct statistical analysis on the algorithm.