# UAV Path Planning Model Based on R5 DOS Model Improved A-Star Algorithm
## 2 Materials and Methods
### Improved A-Star Algorithm  
The A-star algorithm is a global planning algorithm that requires all the information on maps and obstacles to perform a good job. However, for UAVs, because of the limitation of detection range, the full information of the map cannot be obtained while working, causing the A-star algorithm to work poorly. The map information of the three-dimensional space is too complex and the larger the map the greater the amount of computation. We improved the A-star algorithm based on the R5 DOS model. The hop-point search algorithm is a special search strategy that ignores unnecessary search nodes during the search process; the points that the algorithm searches for after ignoring processing are called hop points. As shown in Figure 4, the three paths from the P node can be selected to reach the Q node:  
Figure 4: Path selection during search. Figure 3: Motion directions of the UAV. During the search process, the A-star algorithm compares the estimates of each node and calculates the \(B_{2}\) lowest cost of the nodes through comparison. The algorithm will then traverse each adjacent node \(B_{1}\), \(B_{2}\), \(B_{3}\). The operation of searching for \(B_{1}\), \(B_{3}\) is unnecessary because the moving cost of path 2 is always the lowest in this case. To further improve the search efficiency and speed, you can search directly according to the location and direction of the target node; this is the search method of a jump-point search. A hop-point search improves the search efficiency by searching for specific nodes and ignoring unnecessary nodes in the process of expanding nodes; these specific nodes are called hop points. The Q node in the figure is a hop point. The other nodes between the two hop paths will be ignored, which will greatly reduce the amount of computation and storage. This effectively solves the problem of large amounts of computation and memory consumption caused by the A-star algorithm in larger map sizes. In this article, a search requires access to 26 nodes, which will greatly increase the computational difficulty and time required, so we have improved the A-star algorithm based on the hop-point search algorithm. In this paper, preprocessing for nodes is added to the A-star algorithm to filter out a batch of jump points in advance, which can greatly reduce the access and computation of the A-star algorithm to a large number of intermediate unnecessary nodes. The improved A-star algorithm does not traverse each node but calculates special nodes over long distances and jumps. Preprocessing is essentially the process of filtering the jump points in a raster map, which is defined in this article according to the situation. The UAV cannot obtain the information of the full map while working, but the UAV has a detection area and can obtain local information. For UAVs, the UAV does not set up nodes when it does not detect obstacle A \(R(A,B,C)= \begin{pmatrix}0&0&0&1\\ 1&1&0&1\end{pmatrix} \). When the UAV detection area detects obstacle A \(R(A,B,C)= \begin{pmatrix}0&1&0&1\\ 1&1&0&1\end{pmatrix} \), the local map is rasterized and all 26 nodes around it are removed, as shown in Figure 5.  
Figure 5: When the UAV detects an obstacle. Set the node coordinates to \((x_{i},y_{i},z_{i})i=1,2\cdots 26\). The coordinates of the UAV are \((x_{u},y_{u},z_{u})\), the distance from the node to the UAV is \(d_{ui}=\sqrt{\left(x_{i}-x_{u}\right)^{2}+\left(y_{i}-y_{u}\right)^{2}+\left(z _{i}-z_{u}\right)^{2}}\) and the direction unit vector from the node to the UAV is \(\overset{\rightarrow}{V}_{ui}(x_{vi},y_{vi},z_{vi})=\left(\frac{\left(x_{i}- x_{u}\right)}{d_{ui}},\frac{\left(y_{i}-y_{u}\right)}{d_{ui}},\frac{\left(z_{i}- z_{u}\right)}{d_{ui}}\right)\). Target point coordinates are \((x_{t},y_{t},z_{t})\).