## 3 Path-Planning Design and Dynamic-Obstacle Avoidance Strategy
### Global Path-Planning Design Based on 3D JPS Algorithm
#### 3.1.1 Traditional JPS Algorithm  
The JPS algorithm was proposed by [PERSON] and [PERSON] in 2011 [34]. The main idea of the JPS algorithm is to further optimize the process of finding subsequent path nodes by the A* algorithm based on the heuristic function of the A* algorithm through the neighbor-pruning rule and the forced-neighbor judgment method. The JPS algorithm drastically reduces the number of nodes that need to be accessed in the openlist list, reducing the time and space costs of the algorithm, as shown in Figure 4. The light-gray grid indicates the nodes that have been visited by the openlist, and the purple grid indicates the remaining nodes in the current openlist.  
The direction of expansion of the JPS algorithm during path planning depends on the orientation of the natural neighbors given by the neighbor-pruning rule. When JPS extends the path in a particular direction, it identifies a set of natural neighbors among the neighboring nodes evaluated by the neighbor-pruning rule. If the extension direction is a straight line, the natural neighbor of the current grid is defined as the next node in the same direction, as shown in Figure 5a. That is, JPS will continue searching along the direction of the current natural neighbor. When the extension direction is diagonal, the natural neighbors of the current grid are the next node along the extension diagonal and the vertical and horizontal nodes in the extension direction, as shown in Figure 5b. JPS will start expanding along the natural neighbors in the vertical and horizontal directions until they are blocked or a jump point is found before considering the search in the diagonal direction. If there is an obstacle among the pruned neighbors, this will make it impossible to prune all unnatural neighbors. The grids that are forced to become natural neighbors as a result of this phenomenon are called forced neighbors, as shown in Figure 5c,d.  
In essence, JPS is a heuristic search algorithm that relies on jump points for path planning. The efficiency of the JPS algorithm is inextricably linked to the choice of jump points. Usually, the identification of jump points for the JPS algorithm relies on the judgment of forced neighbors. The current node is the jump point if it is the start point, the target point, or if there is at least one forced neighbor. If the current node is a diagonal search and there  
Figure 4: Comparison between A* algorithm and JPS algorithm for accessing nodes in the search process. (**a**) A* algorithm path-planning process. (**b**) JPS algorithm path-planning process.  
is a jump point in its horizontal or vertical direction, the current node is also the same as the jump point.  
The JPS algorithm is much lower than the A* algorithm in terms of time complexity. The fundamental reason is that the openlist list of the JPS algorithm no longer stores all the natural neighbors of the current node, but the jump nodes that play a key role in the final generated path. Although the JPS algorithm and the A* algorithm generate paths of equal length, the A* algorithm requires far more nodes to be computed and visited than the JPS algorithm, which explains why the JPS algorithm is more efficient than A*. In particular, the efficiency of the JPS algorithm is more significant in complex environments. Just as the results tested by [PERSON] are consistent, the search speed of the JPS algorithm is an order of magnitude higher than that of the A* algorithm [34]. Therefore, choosing the JPS algorithm to perform the drone path planning has a general advantage in meeting the requirements of efficiency.