# RJA-Star Algorithm for UAV Path Planning Based on Improved RSDOS Model
## 2 Materials and Methods
### Improved Path Planning Algorithm  
According to Sections 2.1-2.4, RJA star path planning Algorithm 1 is as follows:  
1. Detects obstacles in the path between the UAV current position and the target point. 2. If there is an obstacle, consider the one closest to the UAV as a coercive neighbor. If there is no obstacle, end the search and fly directly to the target point. 3. Consider the Vertex of the forcing neighbor and its closest boundary point as the jump point. 4. Repeat steps 2-3 until all hops are searched. 5. Compute the cost functions for all hops, compare them, and choose the best path. 6. The UAV chooses the jumping body to move in turn, and the moving path is on the plane formed by the adjacent jumping points. 7. Move in sequence until you reach the target point. The pseudo-code of RJA-star is:  
```
1 algorithmRJA-star (start point, current_node, child node, goal point)
2\(\mathrm{F_{\text{\scriptsize{cot}}}}(\text{current\_node})=\mathrm{G}( \text{current\_node})+\mathrm{H}(\text{current\_node})\)
3 if current_node = goal point found the feasible path; break
4 Generate child node that come after current_node
5 for child node of current_node
6 if\(R(A_{i},B,C)= \begin{pmatrix}0&0&0&1\\ 1&1&0&1\end{pmatrix} \)then Jumbody:f \(\leftarrow\)\(\mathcal{O}\)
7 if\(R(A_{i},B,C)= \begin{pmatrix}0&1&0&1\\ 1&1&0&1\end{pmatrix} \)then open \(\leftarrow\) Jump bodys
8 else closed \(\leftarrow\) Jump bodys
9 end if
10 end if
11 closed \(\leftarrow\) current_node
12 ifPath(current_node) and RJAPath(current_node) then
13 final \(\leftarrow\) closed
14 end if
15 end for
16 end
17 return
18 if(current_node! = goal point) exit with error (the open list is empty)The algorithm flow is shown in Figure 6.

## 3 Results

We simulated maps of different map sizes in Matlab. The starting point is (0,0,0), aand the target point is the point farthest from the origin under the current dimension, 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. In order to discuss the advantages of RJA star algorithm more intuitively, we simulate A-star algorithm and RJA star algorithm on maps of different sizes. Calculate the running time of the algorithm to evaluate the effectiveness of the RJA star algorithm.The running time starts from the map generation and ends when the UAV reaches the target point

Our simulation environment is as follows:

CPU:Intel(r) Core(tm) i7-8750H;

GPU:NVIDIA GTX 1060 Max-Q 6 GB. We repeated the average value of 100 simulation experiments as the result. We fixed the height of the experimental map at 15 m and set several scenarios, as shown in Table 1.

We simulate the RJA star algorithm and A-star algorithm in scenario 11, as shown in Figure 7a-d. \begin{table}
\begin{tabular}{c c c c} \hline
**Scenario Name** & **Map Size** & **Scenario Name** & **Map Size** \\ \hline scenario 1 & 20 \(\times\) 20 \(\times\) 15 & scenario 7 & 80 \(\times\) 80 \(\times\) 15 \\ scenario 2 & 30 \(\times\) 30 \(\times\) 15 & scenario 8 & 90 \(\times\) 90 \(\times\) 15 \\ scenario 3 & 40 \(\times\) 40 \(\times\) 15 & scenario 9 & 100 \(\times\) 100 \(\times\) 15 \\ scenario 4 & 50 \(\times\) 50 \(\times\) 15 & scenario 10 & 110 \(\times\) 110 \(\times\) 15 \\ scenario 5 & 60 \(\times\) 60 \(\times\) 15 & scenario 11 & 30 \(\times\) 90 \(\times\) 15 \\ scenario 6 & 70 \(\times\) 70 \(\times\) 15 & & \\ \hline \end{tabular}
\end{table} 
Table 1: Scenario Names of Different Map Sizes. Figure 6: Work flow diagram of RJA star algorithm. Figure 7: _Cont._

To compare the experimental results, we use Equation (2) to calculate the results of RJA star algorithm and A-star algorithm in computing time, exploration nodes, and path length. \[\frac{\left(I_{A}-I_{RJA}\right)}{I_{A}}\times 100\%,I_{A/RJA}=\{computing\ time,\ exploration\ nodes,\ path\ length\} \tag{2}\]

Through Equation (2), we can calculate the reduced computation time, probe node and path length of the RJA star algorithm.