## 3 UAV Path Planning Method Based Modified Fruit Fly Optimization Algorithm
### MSFOA-Based Path Planning
#### 3.2.2 Application of MSFOA to Multi-UAVs Path Planning  
(1) Collision detection method  
Collision avoidance is an important part of multi-UAVs path planning. Due to the huge space in the 3D map, this method only detects the possibility of collision after the path is generated. When the \(n\)-th UAV's flight path is going to check for collision, this method will check it in pairs with the previous \(n-1\) UAV's flight path. The \(n\)-th path is called the path to be detected, and the previous \(n-1\) is called the \(air\_path_{n-1}\). For each point on the detection path, the distance from each point between the detection path and \(air\_path_{n-1}\) is calculated. If the distance is less than the minimum safe distance, the two points will be called a possible collision point, and the path will be punished. The mathematical descriptions are as follows:  
\[ \begin{array}{c}JP=\sum\limits_{m=1}^{n}\sum\limits_{i=1}^{n}JP_{i}\\ \text{with}\\ \Delta_{time\_k}=\begin{cases}C*t_{crash}^{3},&t_{crash}<0.5\\ 0,&t_{crash}\geq 0.5\end{cases}\end{array}  \tag{29}\]  
where \(JP_{i}\) is the collision risk between the \(i\)-th UAVs and the \(m\)-th UAVs, the parameter \(C\) is the time penalty factor, and \(t_{crash}\) is the time difference between the two UAVs at the point of possible collision, determined by the following formula:  
\[t_{crash}=v/(dis_{1}-dis_{2}) \tag{30}\]  
(2) MSFOA based multi-UAVs path planning  
In order to further explain the MSFOA based path planning, the specific steps of multi-UAVs path planning for MSFOA is elaborated. The algorithm records the location of the \(d\)-th control point of the \(i\)-th individual fruit fly in swarm \(g\) with \(X_{i}^{(g),\ d}\) and \(Y_{i}^{(g),\ d}\), \(d=1,\ldots,D\), where \(D\) denotes the number of control points. \[S_{i}^{(g),\ d}=\sqrt{(X_{i}^{(g),d})^{2}+(Y_{i}^{(g),d})^{2}} \tag{31}\]  
where \(S_{i}^{(g),\ j}\) is the smell concentration judgment. The path is generated by  
\[\left\{ \begin{array}{c}path_{i}^{(x)}[k]=S_{i}^{(g),\ k}*p_{max}^{(x)}\\ path_{i}^{(y)}[k]=S_{i}^{(g),\ k+D}*p_{max}^{(y)}\\ path_{i}^{(z)}[k]=S_{i}^{(g),\ k+2D}*p_{max}^{(z)}\end{array} \right. \tag{32}\]  
where \(P_{max}^{(x)}\), \(p_{max}^{(y)}\), \(p_{max}^{(z)}\) is the boundary of the map in three dimensions. \(path_{i}^{(x)}\) is the coordinate on the X axis of all the control points in the path, \(path_{i}^{(y)}\) is the coordinate on the Y axis of all the control points in the path, and \(path_{i}^{(z)}\) is the coordinate on the Z axis of all the control points along this path. \(k\) represents the number of control points, where \(k\) values range from 2 to \(D\)-1. Then add the starting and ending points:  
\[\left\{ \begin{array}{c}path_{i}^{(x)}[1]=X_{S,N}\\ path_{i}^{(y)}[1]=Y_{S,N}\\ path_{i}^{(z)}[1]=Z_{S,N}\\ path_{i}^{(x)}[D+2]=X_{T}\\ path_{i}^{(y)}[D+2]=Y_{T}\\ path_{i}^{(z)}[D+2]=Z_{T}\end{array} \right. \tag{33}\]  
where \(X_{S,N}\), \(Y_{S,N}\), \(Z_{S,N}\) is the beginning of the path of the \(N\)-th UAV, and \(X_{T},\ Y_{T},\ Z_{T}\) is the end of the path of the UAV. There is no essential difference between the multi-origin and multi-destination model in this paper. The MSFOA for multi-UAVs path planning is implemented as follows:  
**Step 1:** Determine information of the UAVs mission, including starting coordinates \((X_{S,N},Y_{S,N},Z_{S,N})\) and ending coordinates \((X_{T},Y_{T},Z_{T})\). The number of UAVs required for the mission _Num_, maximum velocity \(v_{max}\), maximum turn overload \(n_{max}\), and minimum altitude \(h_{min}\). Mission map information \(p\), boundary \(P^{x}_{max},\ P^{y}_{max},\ P^{z}_{max}\), and the number \(D\) of control points that each UAV needs to plan out. **Step 2:** Identify enemy ground weapons, including threat types such as radar, missiles, anti- aircraft guns, weapon positions (\(X_{threat,\ j}\), \(Y_{threat,\ j}\)), and their respective threat ranges.