## 3 Path-Planning Design and Dynamic-Obstacle Avoidance Strategy
### Trajectory Optimization Based on the Resultant Path of 3D JPS Algorithm
#### 3.2.1 An Any-Angle Path-Planning Strategy Based on the Parent Node Transfer Law
Since the parent-child relationship between node \(x_{1}\) and \(x_{start}\) is not modified, it is only necessary to perform LOS reachability detection with \(x_{start}\) from node \(x_{2}\) to node \(x_{end}\) in order to verify whether the visibility between nodes holds. 4. If visibility holds, the node between the current node and \(x_{start}\) will be deleted and added to the deletelist without changing the parent node relationship. 5. If visibility does not hold, the parent node for the current node needs to be found again in the deletelist, and the parent node of the remaining nodes without LOS detection is replaced with the parent node of the current node to continue the detection. Figure 11: Comparison between the actual spatial shortest path and the path obtained by JPS algorithm. (a) Comparison of the actual spatial shortest path and the path obtained by the 2D-JPS algorithm. (b) Comparison of the actual spatial shortest path and the path obtained by the 3D-JPS algorithm. When the parent node of \(x_{end}\) is passed, the algorithm ends and the shortest path is output. In this paper, the pseudocode of the parent-node-passing rule is shown as follows (Algorithm 1). ```
Input: The complete set of nodes of the path obtained by 3D-JPS algorithm \(\{pathlist:=[x_{end},x_{n},x_{n-1},...,x_{i},...,x_{i},x_{start}]\}\) Output: Optimized set of nodes \(\{pathlist\}\)
1\(length(pathlist)>2\)then
2 initial\(closist\);
3\(parentnode=parent(x_{1})=x_{start}\);
4\(parent(x_{end})=parent(x_{n})=...=parent(x_{i})...=parent(x_{2})=parentnode\);
5 for\(i=2\) to length(pathlist)do
6\(LineOfSight(x_{i},parentnode)\)then
7 remove all nodes between \(x_{i}\) and \(parentnode\), as well as adding \(closist\);
8
9 else
10 initial\(flag:=0\);
11 for\(j=1\) to length(\(closist\))do
12 if\(LineOfSight(x_{i},closist(j))\) AND \(dist(x_{i},closist(j),+j(closist(j),x_{end})<g(x_{i},x_{end})\)then
13\(parent(x_{i})=closist(j)\);
14 remove all nodes between \(x_{i}\) and \(closist(j)\), as well as adding \(closist\);
15\(flag=1\);
16
17 end if
18 if\(flag\) equals \(0\)then
19\(parent(x_{i})=x_{i-1}\);
20
21 end if
22\(parentnode=parent(x_{i})\);
23
24 end if
25
26 end if
27
28 end for
29 return\(pathlist\);
```  
**Algorithm 1**Parent Node Passing  
2.2 Optimization of Trajectory Smoothing Based on Minimum-Snap Seventh-Order Polynomial Interpolation  
For drones performing near-ground missions, path planning should fully take into account the feasibility constraints that arise during the actual flight of the drones. To be precise, the path obtained by the path planning algorithm of drone should meet the path space node state continuous and smooth, to achieve the shortest path. The full-state space of the drone is 12 dimensions, which are position, velocity, attitude angle, and angular velocity, as shown in Equation (6). \[\mathrm{x}=\left[x,y,z,\phi,\theta,\psi,\dot{x},\dot{y},\dot{z},p,q,r\right]^{\top} \tag{6}\]  
However, in the process of drones' path planning, it is not possible to plan for the full dimensional space because it would be very complex and difficult to compute. In their paper [38], [PERSON] et al. demonstrated that the 12-dimensional full state of a drone can be represented by a flat output space composed of four-dimensional variables, as shown in Equation (7). \[\sigma=[x,y,z,\psi]^{\top} \tag{7}\]  
There are only four-dimensional variables in this space, namely, the positions of the \(x\)-axis, \(y\)-axis, \(z\)-axis, and yaw angle \(\psi\). The remaining states can be represented by the algebra of these four variables and their finite order derivatives. Therefore, in this paper, based on the four-dimensional flat-output space of UAV, the seventh-order polynomial based on minimum snap is selected for trajectory optimization. Additionally, for the possibility of recollision of the optimized path, the node expansion interval is used and the flight safety corridor is set by applying the inequality constraint. \[snap_{m}(t)=\Big{(} \begin{array}{cccccccc}0&0&0&0&24&\cdots&\frac{kt}{(k-4)!}t^{k-4 }\end{array} \Big{)}\big{(}