# Cooperative Multi-UAV Collision Avoidance Based on a Complex Network
## 3 Core Algorithm Analysis
### Direction of Collision Avoidance  
Most of the CA systems use the upward or downward strategy to avoid collision. The sense selection can reduce the domino effect. For instance, two new encounters will occur if the key UAV descends, and three will occur if it climbs. The implementation of airborne CA systems II (ACAS II) [39] indicates that it is effective and safe to perform resolution in the vertical direction; therefore, the method of this paper only considered the vertical change in direction. As shown in Figure 3, the key node direction choosing method was as follows. To generate a suitable direction for CA, we expect the UAV cluster system to minimize the cost and to choose the fastest method to reach the target, and we expect the domino effect to be as small as possible in the CA process. The objective function for direction choosing should include three elements:  
(1) The Number of Intruder UAV Designated Directions  
\[Z_{k}(m)=\sum_{i=i}^{n}\text{sgn}(x_{k}(i)),\ x_{k}(i)=\left\{ \begin{array}[] {c}1,\ z_{i}>z_{k}\\ -1,\ z_{i}\leq z_{k}\end{array} \right. \tag{15}\](2) Network Robustness  
Complex networks rely on their robustness, i.e., the ability of a network to maintain its connectivity when a fraction of its vertices is damaged, for their function and performance [40]. In the context of this new conflict model, it is important to improve reliability as much as possible. The robustness of the edge connection is defined as follows:  
\[R_{k}(m)=R\Big{(}\frac{I_{m}}{N_{m}}\Big{)}=\frac{M_{m}}{N_{m}-1},\ M=\frac{ \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\omega_{ij}}{2},\ \omega_{ij}=\frac{v_{ij}}{d_{ij}} \tag{16}\]  
(3) Connected Component of the Network  
\[C_{k}(m)=C(\frac{I_{m}}{N_{m}})=\frac{C_{m}}{N_{m}-I_{m}} \tag{17}\]  
\(N_{m}\) stand for N nodes in the network at time \(m\), \(I_{m}\) is the number of nodes that are rejected in the network at time \(m\), and \(C_{m}\) represents the number of sub-maps of the network. In summary, the objective function at time \(m\) consists of three elements and is represented as follows:  
\[O_{k}(m)=\omega_{1}Z_{k}(m)+\omega_{2}R_{k}(m)+\omega_{3}C_{k}(m) \tag{18}\]  
In this formula, \(\omega_{1}\), \(\omega_{2}\), and \(\omega_{3}\) are the corresponding weight coefficients of the three indicators. Different weights satisfy the requirements of different scenarios of CA. For instance, if \(\omega_{2}<\omega_{3}\), it is implied that the connected component is more important than the robustness of the network. It is noteworthy that a normalization process is required in this computation. Assuming that the direction is amended to avoid the collision in the period \([m,m+N-1]\) and the corresponding position and pitch angle sequences of UAV\({}_{k}\) are, respectively,  
\[p_{k}=[p_{k}(m),p_{k}(m+1),\ldots,p_{k}(m+N-1)]^{T}\]  
\[\psi_{k}=[\psi_{k}(m),\psi_{k}(m+1),\ldots,\psi_{k}(m+N-1)]^{T}\]  
the following constraints of the optimization process should be satisfied:  
\[q(\varphi_{k}(m+\Delta t))=\left[ \begin{array}{c}1\\ -1\end{array} \right](\varphi_{k}(m+\Delta t)-\varphi_{k}(m+\Delta t))-\left[ \begin{array}{c}B\\ -A\end{array} \right]\leq 0\]  
\[e_{k}(p_{k}(m+\Delta t))=\left[ \begin{array}{c}x_{k}(m+\Delta t)-[x_{k}(m)+ v_{k}\cos(\varphi_{k}(m))\cos\theta_{k}\cdot\Delta t]\\ y_{k}(m+\Delta t)-[y_{k}(m)+v_{k}\cos(\varphi_{k}(m))\sin\theta_{k}\cdot\Delta t ]\\ z_{k}(m+\Delta t)-[z_{k}(m)+v_{k}\sin\varphi_{k}\cdot\Delta t]\\ \varphi_{k}(m+\Delta t)-[\varphi_{k}(m)+\omega_{k}(m)\cdot\Delta t]\\ \end{array} \right]=0 \tag{19}\]  
Figure 3: Conceptual graph for sense selection. In the formula above, \(q(\rho_{k}(m+\Delta t))\) implies that the direction change should be in the range of (A,B). \(e_{k}(p_{k}(m+\Delta t))\) indicates that the pitch angle at time \(m+\Delta t\) is determined by the global information at time \(m\) and the constrains of the CA system. By repeating the optimization procedure, the complete amending trajectory is generated. The goal of this new model is to decompose the network as quickly as possible.