# RJA-Star Algorithm for UAV Path Planning Based on Improved RSDOS Model
## 2 Materials and Methods
### Jump Point Search Algorithms  
A-star requires a lot of unnecessary computation and memory space [29], to improve this an adaptive JPS algorithm was introduced. JPS algorithm is a special search strategy, which only accesses special nodes in the calculation process [30]. This can be thought of as a pre-processing method. After pre-processing, the remaining nodes to be searched are called jump points. As shown in Figure 3, the current node is dotted in blue. From the blue node A5 to the orange node G5, we can ignore the grey node B4, C4, B6, C6 and so on, because the cost of going through B5 to G5 is minimal. When extending to node G5, since node G6 is an obstacle, G5 is the forced neighbor of hop G6. This will greatly increase computing time while reducing computing efficiency. In this paper, we will add a preprocessing process to all nodes based on the A-star algorithm to obtain a batch of special hops. In this way, the improved RJA star algorithm can reduce a lot of unnecessary analysis and calculation. This article defines it according to the actual situation. Take the three-dimensional view of Figure 4a and the cross-section of Figure 4b as an example, assuming that the grey area is an obstacle. The connecting line between UAV and target is defined as \(L_{ut}\), the length as \(d_{ut}=\sqrt{\left(x_{t}-x_{u}\right)^{2}+\left(y_{t}-y_{u}\right)^{2}+\left( z_{t}-z_{u}\right)^{2}}\), and the direction vector as \(\overset{\rightarrow}{L}_{ut}=\left(\frac{\left(x_{t}-x_{u}\right)}{d_{ut}},\frac{\left(y_{t}-y_{u}\right)}{d_{ut}},\frac{\left(z_{t}-z_{u}\right)}{d_{ut }}\right)\). Taking the connection line \(L_{ut}\) as the central axis of the detection area B, the length of the UAV body is r, and in order to ensure that the UAV can safely avoid obstacles without being affected by other factors, we set the diameter of B as 3r, to determine if there is an obstacle \(A_{i}\), \((i=1,2,\cdots)\) and B intersecting, that is, the topological relationship is \(R(A_{i},B,C)= \begin{pmatrix}0&1&0&1\\ 1&1&0&1\end{pmatrix} \), where B represents the detection area and C represents the UAV body Area. If such an obstacle exists, the nearest obstacle to the UAV is considered as the forcing neighbor, the vertices and boundary points with special distance on the obstacle are regarded as the next round of search nodes, namely, that is, the yellow nodes in the Figure 4a,b. When the algorithm executes the JPS algorithm once, it repeats the above steps until no obstacle intersects with \(L_{ut}\) in Figure 5b, and then completes the JPS. Note:  
\[\left\{ \begin{aligned} & J_{0},\ \text{ the coordinates of the starting point of the UAV}\\ & J_{i}(i=1,2,\cdots,n-1),\text{ the coordinates of the jump point}\\ & J_{n},\ \text{ the coordinates of the target point}\end{aligned} \right.\]  
Figure 3: The shortest path selection example of JPS algorithm. During the implementation of the A-star algorithm, the path is not smooth enough because there are many corners, which does not conform to the movement mode of the UAV. To ensure that the UAV can move smoothly and be safe enough, first, we filter out all the jumping points. Then consider expanding a sphere with a diameter of 3r at each node and call it a \"jumping body\". At the same time, the moving target of UAV is not the selected  
Figure 4: (**a**) Schematic diagram of obstacles and UAV. (**b**) Cross sectional sketch of obstacles and UAV. Figure 5: Path Selection for UAV Obstacle Avoidance. jumping point, but the jumping body corresponding to each jumping point. Starting from the origin, every time the UAV moves to the next jump body, we will obtain the coordinates of the current node and the next two jump points of the UAV. In the three-dimensional plane the two jumping bodies will intersect on the corresponding spherical tangent plane. There are two types of UAV paths:  
1. When flying from the starting point, move the tangent line from the current position to the circle. 2.