## 2 Preliminaries  
### Problem Formulation  
UAV needs to plan a safe and short flying path from starting position to target position. However, numerous obstacles and no-fly zones fulfill complex environments, such as urban, indoor, or forest area. It is crucial to take the constraints of nonlinear dynamics and unstructured environment into account. Further, the fly speed and altitude changing need to be also considered. In the paper, we model the above planning problems as a mixed objective optimization problem with constraints on UAV dynamic and threats, and assume that UAVs satisfy following dynamics.  
\[\left[\begin{array}{c}\dot{\theta}\\ \dot{\phi}\\ \dot{\psi}\end{array}\right]=\left[\begin{array}{c}q\cos\phi-r\sin\phi\\ p+(r+\cos\phi+q\sin\phi)\tan\theta\\ \frac{1}{\cos\theta}(r\cos\phi+q\sin\phi)\end{array}\right] \tag{1}\]  
\[\left[\begin{array}{c}\dot{x}\\ \dot{y}\\ \dot{z}\end{array}\right]=\left[\begin{array}{c}u\cos\theta\cos\psi+v(\sin \phi\sin\theta\cos\psi-\cos\phi\sin\psi)+w(\sin\phi\sin\psi+\cos\phi\sin\theta \cos\psi)\\ u\cos\theta\cos\psi+v(\sin\phi\sin\theta\sin\psi+\cos\phi\sin\psi)+w(-\sin\phi \sin\psi+\cos\phi\sin\theta\sin\psi)\\ u\sin\theta-v\sin\theta\cos\theta-w\cos\phi\cos\theta\end{array}\right] \tag{2}\]  
where \(\eta=\left[\begin{array}{cc}\theta&\phi&\psi\\ \end{array}\right]\) are Euler angles; and \(\Omega=\left[\begin{array}{cc}p&q&r\\ \end{array}\right]\) are angular velocities; \(X=\left[\begin{array}{cc}x&y&z\\ \end{array}\right]\) and \(V=\left[\begin{array}{cc}u&v&w\\ \end{array}\right]\) are position and linear velocities respectively in the North-East-Down inertial reference.  
Further, the threats in the environment are simplified as cylinders that denoted by distinct vectors, including position coordinates \((x_{k},y_{k},z_{k})\), radius \(r_{k}\), and corresponding threat levels \(t_{k}\). Threat level \(t_{k}\) is used to indicate the impact degree of threats on the UAV path.  
By taking fly time, path length, and security requirements into account, the UAV path planning problem can be established as the following optimization problem:  
\[\min J=c_{1}l_{l}+c_{2}I_{t}+c_{3}J_{a}c_{1}+c_{2}+c_{3}=1 \tag{3}\]  
The cost function \(J\) is consisted of \(J_{l}\), \(J_{a}\), and \(J_{t}\), which represent path length cost, the altitude cost and the threat cost, respectively. The path length cost and altitude cost can be directly obtained by  
\[J_{l}=\sum\limits_{i=1}^{n}l^{2}, \tag{4}\]  
\[J_{a}=\sum\limits_{i=1}^{n}h_{i}, \tag{5}\]  
where \(n\) is the amount of path segments; \(l_{i}\) and \(h_{i}\) are the length and the average altitude above the sea level of the \(i\)-th path segment, respectively. To simplify the total threat cost model, an efficient approximation is adopted to the exact solution. In our work, threat cost, which can be obtained by five points, of each edge connects two discrete points along the edge [16].  
\[J_{t}=\frac{L_{ij}}{5}\sum\limits_{k=1}^{N_{t}}t_{k}\Bigg{(}\frac{1}{d_{0,1,k}^{4 }}+\frac{1}{d_{0,3,k}^{4}}+\frac{1}{d_{0,5,k}^{4}}+\frac{1}{d_{0,7,k}^{4}}+\frac {1}{d_{0,9,k}^{4}}\Bigg{)}, \tag{6}\]  
where \(d_{0,1,k}\) is the length between the \(1/10\) point and the \(k\)-th threat center. We divide the line segment between two discrete points \((x_{i-1},y_{i-1},z_{i-1})\), \((x_{i},y_{i},z_{i})\) into five segments of the same length, and select five of them. The threat cost of the line segment between two discrete points is approximately equal to the total cost of the selected five points. Threat computation model is shown in Figure 1.