## 3 Path-Planning Design and Dynamic-Obstacle Avoidance Strategy
### Global Path-Planning Design Based on 3D JPS Algorithm
#### 3.1.2 3D Extension of JPS Algorithm  
In order to ensure that the drone maintains excellent static-obstacle-avoidance capability during the search mission in low-altitude airspace, this paper extends the JPS algorithm in three dimensions. In the traditional 2D space, the JPS algorithm uses a single grid node as the smallest unit and the current node and contains all eight neighboring nodes as the smallest set  
Figure 5: JPS algorithm’s neighbor-pruning rule and forced-neighbor judgment method. (**a**) Neighbor pruning in the linear extension state. (**b**) Neighbor pruning in the diagonal expansion state. (**c**) Forced neighbors in the linear extension state. (**d**) Forced neighbors in diagonally extended states. Figure 6: Minimum set of JPS algorithm in 2D and 3D space. (**a**) 2D JPS path search minimum set. (**b**) 3D JPS path search minimum set. for path-planning search and judgment. The number of neighbors and the orientation of the current node play a crucial role in the search direction of the JPS algorithm, as shown in Figure 6a. The minimum set of the current node and all its neighbors included in the expansion process of 3D JPS is different from the traditional JPS algorithm. The neighboring nodes of the current node are expanded in 3D space as 26 belonging grid nodes directly connected to the current node, as shown in Figure 6b. In Figure 6b, only the expansion direction of the same plane and the expansion of one edge of each of the upper and lower planes are given; all other directions can be obtained by rotation. The result of the change in the minimum set in the 3D space is a difference in the direction of the expansion of the JPS algorithm during the path-planning process. The different expansion directions are determined by the neighbor-pruning method of the JPS algorithm. Therefore, this paper makes further modifications to the neighbor-pruning rule for 3D JPS as follows. 1. The parent node \(parent(x)\) of the current node \(x\) satisfies the two-dimensional pruning rule when it is in the same plane as the current node with linear extension and does not involve other planes, as shown in Figure 7a. The current node needs to prune off any neighbor node in the same plane that satisfies the following constraint \(n\): \[len(<parent(x),\ldots,n>\setminus x)\leq len(<parent(x),x,n>)\] (1) where the \(len\) function represents the distance between nodes, and \(<parent(x),\ldots,n>\setminus x\) represents the set of all nodes that reach \(n\) from the \(parent(x)\) node without the current node \(x\). 2. The parent node \(parent(x)\) of the current node \(x\) and the current node in the same plane diagonal expansion also satisfies the two-dimensional pruning rule, and does not involve other planes, as shown in Figure 7b. That is, it is necessary to prune off any neighbor node \(n\) in the same plane that satisfies the following constraint: \[len(<parent(x),\ldots,n>\setminus x)<len(<parent(x),x,n>)\] (2)
3. If the parent node \(parent(x)\) of the current node \(x\) and the current node for the body diagonal expansion, the need to expand along the diagonal direction to the upper level while satisfying the formula (b), as shown in Figure 7c. From another point of view, forced neighbors and jump points are a relative set of concepts in the 3D JPS algorithm. The number and location of forced neighbors has an intuitive effect on jump points. We assume that the set of pruned neighbors is \(P=<x_{1},x_{2},x_{3}\ldots,x_{n}>\) in a minimal set with the current grid \(x\) as the core. There exists an obstacle \(x_{ob}\in P\); if there exists any neighbor grid \(x_{i}\in P,x_{i}\
eq x_{ob}\) of \(x_{ob}\) satisfying the following condition, then \(x_{i}\) is called a forced neighbor of the current node \(x\). Additionally, \(x\) is called the jump point. Figure 7: Three-dimensional JPS algorithm neighbor-pruning law. (**a**) Pruning rule under the linear extension direction in the same plane. The expansion direction of the 3D JPS algorithm is restricted to the original expansion direction in the unique plane.