# Formation Control Technology of Fixed-Wing UAV Swarm Based on Distributed Ad Hoc Network
## 4 Waypoint-Based Formation Obstacle Avoidance Algorithm
### Formation Obstacle Avoidance Algorithm  
To obtain multiple formation passage paths, firstly, it was necessary to determine the entry points and the exit points according to the SECP determination method; secondly, to determine the formation obstacle avoidance path in combination with the A* search method; and finally, to determine the obstacle avoidance waypoint of the UAV swarm. The algorithm flow is shown in Figure 5; the specific steps were as follows:  
Step 1. Determine entry and exit points. As shown in Figure 6, we connected the center points of circles two by two to get the connecting line set \(\mathit{CirSeg}=\{\mathit{CirSegment}_{k}|k=1,2\cdots,Nk\}\), and obtained the entry and exit line segments according to the SECP determination method, and further obtained the in-point set \(\mathit{EntPoint}\) and the out-point set \(\mathit{ExPoint}\). The specific process of the algorithm was as follows Algorithm 1:  
Figure 4: Determination method.  
Figure 5: Principle flow chart of obstacle avoidance algorithm.  
Step 2. Determine formation avoidance path.  
As shown in Figure 7, we combined the entry and exit points set \(EnPoint\)\(ExPoint\) from Algorithm 1 and the processed channel segment \(CirSeg\) (e.g., \(M\) in Figure 7) to find the obstacle avoidance path set \(AvoidPath\) with the A\({}^{\star}\) method. The specific process of the algorithm was as follows Algorithm 2:  
Figure 6: Determination of entry and exit points.  
Figure 7: Determination of the formation avoidance path.  
Step 3. Determining the UAV formation obstacle avoidance waypoint.  
As shown in Figure 8, we extended _AvoidPath_ to the boundary of the obstacle avoidance area (e.g., \(P\) in Figure 8), deleted the formation obstacle avoidance path that did not meet the UAV dynamic constraints, and calculated the number of UAVs that the path of the \(i\)th entry point could pass through:  
\[n_{i\to j}=\min(\Big{\lfloor}\omega\times\frac{L_{(i\to j),d}-2\times d_{ safe}}{d}\Big{\rfloor}+1)\ q=1,2,\cdots,Nq \tag{15}\]  
\[\left\{\begin{array}{l}n_{i}=\max n_{i\to j}\ j=1,2,\cdots,Nj\\ jmax=\operatorname*{argmax}(n_{i})\\ N_{pass}=\sum\limits_{i=1}^{Ni}n_{i}\end{array}\right. \tag{16}\]  
where \(d\) is the vertical interval distance of the UAV, \(d_{safe}\) is the safe distance of the UAV, \(L_{(i\to j),d}\) is the length of the \(q\)th formation channel segment from the \(i\)th formation path to  
Figure 8: Determining the UAV formation obstacle avoidance waypoint.  
\(j\)th formation path, \(n_{j}\) is the number of UAV that can be passed by the \(j\)th formation path, \(\omega\) is the scaling scale, and \(0<\omega\leq 1\) is to adjust the number of UAVs through the channels.  
Then, we calculated the obstacle avoidance waypoint \(PathPoint\) of UAV\({}_{i}\) based on _AvoidPath_ obtained from \(n_{i}\) and Algorithm 2; the specific process was as follows Algorithm 3:  
```
Input:\(O\), \(S\), \(\mathbf{X}(0)\), AvoidPath, \(v\) Output:\(PathPoint=\{PathPoint_{\_}{uxi}|uxi=1,\cdots,N\}\)
1: extent \(AvoidPath_{\_}{i\to j}\) to \(S\)'s boundary (e.g., \(P\) in Figure 8)
2:if\(AvoidPath_{\_}{i\to j}\) do not satisfy constraints \(R_{\_}{res}\) and \(d_{\_}{s}\)then erase
3:endif
4: calculate \(n_{\_}{i}\) by Equation (15)
5: \(\mathit{CirLine}_{\_}{k}\leftarrow\mathit{CirSegment}_{\_}{k}\)
6: split UAV swarm into \(Ni\) sub-forms
7:\(PathPoint_{\_}{\leftarrow}\) calculate \(PathPoint_{\_}{uxi}\) based \(AvoidPath_{\_}{(i\to jmax),d}\)
8:if\(N_{\_}{pass}\leq N\)then
9:\(PathPoint_{\_}{\leftarrow}\left\{N-N_{\_}{pass}\right\}\) UAV fly around the obstacle area
10:endif
11:for\(uxi=1\)to\(N\)
12:\(T_{\_}{uxi}=|PathPoint_{\_}{uxi}|/v\)
13:endfor
14:\(PathPoint_{\_}{\leftarrow}\) use formation conversion algorithm with \(T_{\_}{uxi}\) and \(PathPoint\)
15:return\(PathPoint\)
```  
**Algorithm 3** Get fly path point