Formation Control Technology of Fixed-Wing UAV Swarm Based on Distributed Ad Hoc Network

Abstract

The formation control technology of the unmanned aerial vehicle (UAV) swarm is a current research hotspot, and formation switching and formation obstacle avoidance are vital technologies. Aiming at the problem of formation control of fixed-wing UAVs in distributed ad hoc networks, this paper proposed a route-based formation switching and obstacle avoidance method. First, the consistency theory was used to design the UAV swarm formation control protocol. According to the agreement, the self-organized UAV swarm could obtain the formation waypoint according to the current position information, and then follow the corresponding rules to design the waypoint to fly around and arrive at the formation waypoint at the same time to achieve formation switching. Secondly, the formation of the obstacle avoidance channel was obtained by combining the geometric method and an intelligent path search algorithm. Then, the UAV swarm was divided into multiple smaller formations to achieve the formation obstacle avoidance. Finally, the abnormal conditions during the flight were handled. The simulation results showed that the formation control technology based on distributed ad hoc network was reliable and straightforward, easy to implement, robust in versatility, and helpful to deal with the communication anomalies and flight anomalies with variable topology.

1. Introduction

The fixed-wing UAV swarm has essential application prospects and has become a current research hotspot. Completing combat missions such as coordinated reconnaissance, early warning, strike, and evaluation in the military field; and realizing disaster emergency, geological survey, and pesticide-spraying tasks in the civilian field [1,2,3,4]. Formation control is one of the key issues to achieve UAV swarm flight [5,6]. Its primary con-tents include formation maintenance, formation switching, formation obstacle avoidance, and exception handling. The distributed wireless ad hoc network [7] is the core of realizing the cluster unmanned system [8]. The formation control based on the distributed ad hoc network can better reflect the distributed, networked, and centerless characteristics of the cluster system, which is the future development trend of cluster control.

The formation control technology for UAV swarm behavior has been extensively studied. Wang [9] proposed the leader–follower method. Its basic idea is that other UAVs follow a leader UAV as followers. Luo et al. [10] and Gu et al. [11] also adopted the leader–follower method to design a control method for the leader and followers in the formation. CamPa et al. [12], based on the leader–follower method, proposed a virtual leader method. Its main idea was to treat the formation of a multi-UAV formation as a rigid virtual structure. When the formation moved as a whole, the UAV only needed to track the movement of the fixed point corresponding to the rigid body. Li and Liu [13] designed a synchronized position tracking controller to improve the effectiveness of using a virtual structure method to maintain formation geometry. Yun and Albayrak [14] applied behavior-control methods to study the formation of multiplatform formations, such as linear formation and circular formation. Chen and Luh [15] applied behavior-control methods to achieve the purpose of object transportation. Ginlietti et al. [16] used behavior methods to define the concept of the formation geometric center. When flying in formation, each aircraft needs to maintain a prescribed distance from the geometric center, and be able to perceive the movements of other aircraft and reconstruct the formation, similar to the behavior of migratory birds in nature. Joongbo et al. [17] proposed a feedback linearization method based on consistency for multi-UAV systems to maintain a specific time-varying formation flight geometry. Glavas et al. [18] applied the consistency research strategy to study the situation when there were random communication noise and information packet loss constraints in the network, and used the polygon method based on information exchange to achieve formation control. Yasuhiro and Toru [19] studied the cooperative control problem of multi-UAV systems, and proposed a cooperative formation control strategy with collision-avoidance capability using decentralized model predictive control (MPC) and consensus-based control. Zhao et al. [20] studied the problem of formation control of multiaircraft formation with time-varying formation characteristics when there was a spanning tree in the network topology based on the consistency theory, and obtained the stability conditions of the system. Dong et al. [21] designed a distributed formation controller based on the consistency theory, proving that as long as the network topology was guaranteed to have directional strong connectivity, even if the aircraft was lost during the formation flight, the multiaircraft system could still achieve stable formation control. Seo et al. [22] designed a consistent control protocol for the situation in which the network topology had fixed connectivity, and studied the problem of cooperative formation control of multiaircraft systems forming geometric formations. Tang et al. [23] used evolutionary control theory to complete distributed collaborative control of UAV formations. He and Lu [24] proposed a decentralized design method based on a UAV distributed-formation maintenance controller, decomposing the UAV formation model into decoupled parts and associated parts using robust control methods, and improved the distributed control method of the associated system designs of the controller to control the UAV formation flying. However, most of the research content was based on the formation controller design coupled with the UAV’s underlying control system. It was assumed that the UAV had a three-channel autopilot and had the ability of instantaneous response [25]. These assumptions made it difficult to apply the formation algorithm to an actual UAV swarm control. Furthermore, the research content was insufficient in the control algorithm of real flight environments such as network topology jump, communication delay, and even weak communication.

Based on the consistency theory, this paper proposes a method for formation switching and obstacle avoidance based on waypoint planning for the problem of formation control of a fixed-wing UAV swarm in a distributed ad hoc networks. The organizational structure of the paper is as follows. The first part gives a general description of the problem of a fixed-wing UAV swarm formation in a distributed ad hoc network; the second part proposes a method for switching the formation of the UAV swarm based on the consistency theory; the third part designs a UAV swarm formation obstacle avoidance algorithm; the fourth part deals with the problems of flight abnormality and communication abnormality of the UAV swarm during the flight; the fifth part simulates and verifies the formation switching of the UAV swarm, the formation obstacle avoidance, and handling of anomalies during the flight; the sixth part analyzes and discusses the results; and finally, the seventh part summarizes the article.

2. Problem Formulation

This paper focuses on two critical problems of formation switching and formation obstacle avoidance in a distributed ad hoc network for UAV swarm formation control.

Definition 1.

Formation switch in distributed ad hoc network.

For $n$ UAV, given an initial position $X_i(0)$ of ${\mathrm{UAV}}_i$, a UAV swarm forms a communication topology in the ad hoc network (as shown in Figure 1). Plan the waypoint $P_i=\{P_{i1},\cdots ,P_{ik},\cdots \}$ of the ${\mathrm{UAV}}_i$ under the dynamic constraints of the maximum turning angle constraint ${\beta }_{\max }$ and minimum route length constraint $d_s$, so that the distance between ${\mathrm{UAV}}_i$ and other UAVs reaches the expected value $\mathsf{\Delta }{X}_{jiref}$ within the time $T$:

$$|X_j(t)-X_i(t)-\mathsf{\Delta }{X}_{jiref}|\to 0i=1,2,\cdots ,n$$

(1)

Definition 2.

Formation obstacle avoidance in distributed ad hoc network.

For $n$ UAV, given an initial position $\mathrm{X}$ of ${\mathrm{UAV}}_i$, intelligently split the UAV swarm into $N_c$ formation; the number of UAVs in the $p\mathrm{th}$ subformation is $N_p$. Plan the waypoint $P_i=\{P_{i1},\cdots ,P_{ik},\cdots \}$ of the ${\mathrm{UAV}}_i$ under the dynamic constraints of the maximum turning angle ${\beta }_{\max }$ and the minimum direct flying distance $d_s$, so that the UAVs will not collide through the rectangular obstacle avoidance area $S$ containing the circular obstacle $O$, and the distance between ${\mathrm{UAV}}_i$ the and other UAVs will eventually reach the expected value $\mathsf{\Delta }{X}_{\mathit{jiref}}$; namely, reconstructed into the required formation.

Where $n={\displaystyle \sum _{p=1}^{N_c}{N}_p}$, $O$ is a collection of obstacles, and $O=\{o_1,o_2,\cdots ,o_{oN}\}$, $oN$ is the number of obstacles, each obstacle $o_m$ can be described as a dyadic array $<R_{\mathit{om}},R_m>$; $R_{om}$ is the center point of the $m\mathrm{th}$ circle; $R_m$ is the radius of the $m\mathrm{th}$ circle; $S$ is the rectangular obstacle avoidance area described as a ternary array $<S_o,L,W>$, where $S_o$ is the center point of the rectangular obstacle avoidance area; $L$ is the length of the rectangle; and $W$ is the width of the rectangle.

A reasonable formation-switching control method requires that the UAV can perform online formation switching based on the neighboring UAV information, and can meet the UAV dynamic constraints and can handle communication delays and flight anomalies, eliminating track deviation. Formation obstacle avoidance requires that a UAV swarm can effectively avoid obstacles, and can form a desired formation after the avoidance is completed. The UAV studied in this paper was a highly dynamic fixed-wing UAV with a uniform speed. The dynamic constraints were required to satisfy the minimum turning radius constraints and minimum track length constraints. The research space of this paper was the two-dimensional Euclidean horizontal plane.

3. Waypoint-Based Formation-Switching Method

The UAV studied in this paper was a highly dynamic fixed-wing UAV. Due to its high speed, it was difficult for the control system to update flight parameters in real time, and the errors were relatively large. Therefore, this article mainly considered the waypoint-based formation switching, and the online design of a small number of waypoints to complete the flight process of the UAV swarm formation, without the need to participate and change the design of the aircraft control system.

3.1. Consensus-Based Design for UAV Swarm Formation Control Protocol

The algebraic graph theory was used to describe the UAV swarm system and its behavior. Assume that the ad hoc network UAV swarm system has $n$ UAVs, and each UAV is regarded as a node, then the communication relationship is seen as an edge. An undirected graph $G=(V,E,A)$ represents the UAV swarm system, where $V=\{s_1,s_2,\cdots ,s_n\}$ is a collection of nodes, $E=\{(s_i,s_j)\in s\times s,i\ne j\}$ is a collection of edges, and $A={[a_{ij}]}_{n\times n}$ represents an adjacency matrix with weights. The edge of the graph is indicated by $e_{ij}=(s_i,s_j)$. For an undirected graph, ${\mathrm{UAV}}_i$ and ${\mathrm{UAV}}_j$ can receive the information sent by each other, namely $(s_i,s_j)\in E\iff (s_j,s_i)\in E$. The adjacency matrix is defined as $a_{ii}=0$, and $a_{ij}=a_{ji}\ge 0$, when $e_{ij}\in E$, $a_{ij}>0$. The neighbor set of the node $s_i$ is defined as $N_i=\{s_i\in V|(s_i,s_j)\in E\}$.

An undirected graph $G_n$ was used to describe the communication topology relationship in the UAV swarm. At each moment $t$, the communication connection between the ad hoc network and UAV swarm forms a communication topology. For the vertex $i$ of graph $G$, let $x_i(t)\in R^q$ and $u_i(t)\in R^q$ denote the state variable and state information input variable of the UAV swarm, respectively, at the time $t$. The classic first-order continuous-time consistency protocol [26] is:

$${\dot{x}}_i(t)=u_i(t)i=1,2,\cdots ,n$$

(2)

$$u_i(t)=-{\displaystyle \sum _{j=1}^n{a}_{ij}}(t)\left(x_i(t)-x_j(t)\right)$$

(3)

For any ${\mathrm{UAV}}_i$, the initial state is $x(0)\in R^P$, when $t\to \infty$, there is $|x_i(t)-x_j(t)|\to 0$, which is called the state of UAV swarm system reaching consensus.

In this paper, the consensus algorithm needed to be applied to the formation switching of the UAV swarm. The distance between UAVs needed to reach the expected value eventually. Therefore, to improve the classic first-order consistency protocol, the first-order consistency protocol with reference location information was proposed, and the specific form was as follows:

$${\dot{x}}_i(t)=u_i(t)=\frac{{\displaystyle \sum _{j=1}^m(a_{ij}(t)[(X_j(t)-X_i(t))-X_{\mathit{jiref}}]})}{{\displaystyle \sum _{j=1}^m{a}_{ij}(t)}}i=1,2,\cdots ,n$$

(4)

where $X_{\mathit{jiref}}$ is the expected formation relative distance between ${\mathrm{UAV}}_j$ and ${\mathrm{UAV}}_i$.

3.2. Consensus-Based Waypoints Planning

3.2.1. Formation Waypoints

The UAV speed studied in this paper was constant, and the UAV swarm formation was controlled based on the route. Therefore, the consistency control protocol in Equation (4) needed to be discretized. First, the communication time of the UAV swarm was discretized, then the position status of each UAV was updated in real time according to the difference equation, and the discrete consistency control protocol can be given by:

$$X_i[k+1]=X_i[k]+\mathsf{\Delta }{X}_i[k]+D$$

(5)

$$\mathsf{\Delta }{X}_i[k]=\frac{{\displaystyle \sum _{j=1}^m(a_{ij}[k]((X_j[k]-X_i[k])-X_{jiref})})}{{\displaystyle \sum _{j=1}^m{a}_{ij}[k]}}$$

(6)

where $k$ represents a communication event, which is a formation process of the UAV swarm formation waypoint; $D$ is the distance required to switch the formation, and is selected according to actual needs; $X_j[k]$ and $X_i[k]$ are the position status of the ${\mathrm{UAV}}_j$ and ${\mathrm{UAV}}_i$ at time $k$, also called formation waypoint; $a_{ij}[k]\in R\times R$ is the adjacency weight matrix of the communication topology, and its elements are defined as:

$$a_{ij}=\{\begin{array}{ll}1\hfill & \left(v_j,v_i\right)\in E\hfill \\ 0\hfill & \left(v_j,v_i\right)\notin E\hfill \end{array}$$

(7)

The undirected graph in this article did not allow self-loops, so $a_{ij}=0$.

During the flight, ${\mathrm{UAV}}_i$ established a communication connection with other UAVs in the ad hoc network, forming a formation waypoint $X_i[k]$ within each communication event $k$ according to Equations (5) and (6).

According to the consistency theory, it can be proved that for any ${\mathrm{UAV}}_i$ with an initial value $X_i[0]\in R^P$, the time-varying communication topology union is fully connected in a formation transformation [27], namely ${\displaystyle \sum _{k=0}^{Nk}{a}_{ij}[k]>0}(i\ne j)$, when $k\to Nk$, there is $|\mathsf{\Delta }{X}_{ji}[k]-\mathsf{\Delta }{X}_{\mathit{jiref}}[k]|\to 0$; that is, the relative distance between the UAV swarm reached the desired value, and the formation switch was realized. If the initial state of the communication topology $a_{ij}[0]$ was full connectivity; namely, the communication was in the normal state, the formation fly could be achieved as the expected formation when $k=0$.

3.2.2. Flying to Formation Waypoint in Consistent Time

Once the formation waypoints were obtained, only local waypoints from the current position of the ${\mathrm{UAV}}_i$ to its formation waypoint needed to be designed so that the flight time of each UAV was equal. In this section, a distributed UAV swarm flying method based on time consistency is proposed, and local waypoints are designed under dynamic constraints to achieve UAV swarm formation switching when flying at a constant speed.

(1)

Dynamic constraints

Maximum turning angle constraint: when the UAV turns according to the waypoint, the turning angle $\beta$ (as shown in Figure 2) needs to be lower than the maximum turning angle ${\beta }_{\max }$:

$$\beta \le {\beta }_{\max }$$

(8)

Minimum route length constraint [28]: assuming that the UAV was flying under the available overload at the turn, the turning radius $R$ was a fixed value. As shown in Figure 2, the turning angle of the UAV in this section of the route was $\beta$. For the UAV to make two consecutive turns, the route of this section needed to be lower than the minimum track length constraint $d_s$:

$$d_s=2\times R\times \tan \frac{\beta }{2}$$

(9)

(2)

Waypoint design

When a UAV flew to formation waypoint, we first took the UAV that was going to fly the longest path as the time base, and then planned for other UAVs to fly around in the horizontal plane so that the final time to reach the formation waypoint was consistent.

The longest path $C_{\max }$ is:

$$C_{\max }=\max (C_i)+d_y$$

(10)

where $d_y$ is the vertical flight distance margin to ensure that the vertical distance meets the constraint of the minimum route length $d_s$. The turning angle of this method is a fixed value $\beta =90°$, so we set $d_y=2\times d_s=4\times R$, $C_i$ as the route distance that the ${\mathrm{UAV}}_i$ needed to fly:

$$C_i=\mathsf{\Delta }{x}_i+\mathsf{\Delta }{y}_i+\mathsf{\Delta }{t}_i\times V$$

(11)

where $\mathsf{\Delta }{x}_i$ and $\mathsf{\Delta }{y}_i$ are the horizontal distance and vertical distance of ${\mathrm{UAV}}_i$ from the current position to the formation waypoint; $V$ is the flight speed of the UAV; and $\mathsf{\Delta }{t}_i$ is the waiting time of ${\mathrm{UAV}}_i$, which can be selected according to the actual project. If it was a formation switch scenario, $\mathsf{\Delta }{t}_i=0$. If it was a formation assembly scenario, $\mathsf{\Delta }{t}_i$ was the launch interval of ${\mathrm{UAV}}_i$ from the first UAV.

The dynamic constraints of the flight plan needed to consider the maximum turning angle constraint and the minimum route length constraint. The flight project was divided into the following sections:

As shown in Figure 3, the flight project was composed of four right-angle turning sections. The solid line is the planned route, which was sections ①, ②, ③, ④, and ⑤. The dashed line is the actual flight route considering the UAV turning process. The solid point is the UAV waypoint. To make the flying distance the same, the length of the distances of ①, ②, ③, ④, and ⑤ were designed as:

$$\{\begin{array}{l}{L}_{1x,i}=L_{5x,i}=r\\ L_{3x,i}=\mathsf{\Delta }{x}_i-4\times r\\ L_{2y,i}=L_{4y,i}=\frac{C_{\max }-\mathsf{\Delta }{x}_i-\mathsf{\Delta }{y}_i}{2}\end{array}$$

(12)

where $L_{1x,i}$, $L_{3x,i}$, and $L_{5x,i}$ are the horizontal distances of ${\mathrm{UAV}}_{\mathrm{i}}$ in segments ①, ③, ⑤; and $L_{2y,i}$, $L_{4y,i}$ are the vertical distances of ${\mathrm{UAV}}_{\mathrm{i}}$ in segments ② and ④, respectively.

The local waypoints of the ${\mathrm{UAV}}_{\mathrm{i}}$ could be calculated according to the starting waypoint and the distance lengths of ①, ②, ③, ④, and ⑤:

$$\{\begin{array}{l}{P}_{i1}(x_{i1},y_{i1})=P_{i0}(x_{i0}+L_{1x,i},y_{i0})\\ P_{i2}(x_{i2},y_{i2})=P_{i1}(x_{i1},y_{i1}+L_{2y,i})\\ P_{i3}(x_{i3},y_{i3})=P_{i2}(x_{i2}+L_{3x,i},y_{i2})\\ P_{i4}(x_{i4},y_{i4})=P_{i3}(x_{i3},y_{i3}-L_{4y,i})\end{array}$$

(13)

At this point, all local route points could be obtained. The UAVs could arrive at the formation waypoints at the same time, thus forming the expected formation.

In this section, a waypoint-based distributed ad hoc network formation-switching control method, derived from the consistency theory, only needed to obtain the formation waypoint from the position information of the UAVs, and then plan the local waypoint from the current waypoint to the formation waypoint under dynamic constraints. The UAV only needed to reach the online planned waypoint under the control of its flight control system. It did not need to call the UAV’s control system to track flight parameters in real time, and only required the design of four local waypoints. This method has a small amount of calculation, is practical and straightforward, and is conducive to implementation in engineering. It can also realize dynamic formation control of UAVs when some communication networks are lost and the topology structure changes.

4. Waypoint-Based Formation Obstacle Avoidance Algorithm

The traditional formation obstacle avoidance method uses an artificial potential field method for obstacle avoidance or an intelligent algorithm to search for waypoints. Still, considering the real-time nature of obstacle avoidance and engineering applications, the artificial potential field method needs to participate in the design of the control system. When facing a high-dynamics UAV, it is challenging to update flight parameters in real time, as it presents significant errors and low reliability. Using the intelligent algorithm to plan trajectories, if high precision is required, planning the trajectory of a single UAV is still too slow, and if there are many planned waypoints, it cannot meet the dynamic constraints of the UAV.

In this paper, the intelligent path search algorithm was used to search for obstacle avoidance channels through which UAVs could pass, and the UAV swarm was divided into multiple smaller formations according to the number of UAVs that could pass through the avoidance channel.

4.1. Consensus-Based Design for UAV Swarm Formation Control Protocol

Obstacle-avoidance principles include the A* algorithm and the smallest enclosing convex polygon of a set of points (SECP) decision principle.

(1)

A* algorithm

The A* algorithm [29,30] is the most effective direct search method for solving the shortest path in a static road network. We only needed to search for the formation channel between the obstacle circles, and there was no need to search for high-precision track points, so we could use the traditional A* algorithm:

$$f(o)=g(o)+h(o)$$

(14)

where $f(n)$ is the cost estimate from the initial state to the target state via state $n$; $g(n)$ is the actual cost from the initial state to state $n$ in the state space; and $h(n)$ is the estimated cost of the best path from state to the target state. The shortest path could be determined by searching from the starting point according to the valuation function in Equation (14) to the ending point.

(2)

SECP determination method

Given a plane point set $A=\{(x_i,y_i)|x_i,y_i\in R\}$, we determined the smallest enclosing convex polygon of a set of points $A_i$ (SECP): we connected the points two by two to form a line segment set $S=\{(A_i,A_j)|A_i,A_j\in A,i\ne j\}$. If all the other line segments were on the side of the line where a line segment $S_{\mathit{convex}}$ was located, then the line segment $S_{\mathit{convex}}$ where this line (e.g., the dotted line in Figure 4) lay was a side of the required convex polygon SECP.

4.2. 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}=$$\left\{{\mathit{CirSegment}}_k\right|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{EnPoint}$ and the out-point set $\mathit{ExPoint}$. The specific process of the algorithm was as follows Algorithm 1:

Algorithm1. Get the entry points and exit points

Input: $O$: Obstacle collection $S$: Obstacle avoidance area

Output:$ExPoint=\left\{ExitPoin{t}_j\right|j=1,2\cdots \}$ $EnPoint=\left\{EntryPoin{t}_i\right|i=1,2\cdots \}$

1: $CirSeg$$\leftarrow$ connect the two-point in $R_o=\left\{R_{om}\right|m=1,\cdots ,n\}$ 2: $MidLine$$\leftarrow$ connect the maximum and minimum of point $R_{om}$ in $y$-direction 3: for $k=1$ to $Nk$ do 4:  $CirLin{e}_k$$\leftarrow$$CirSegmen{t}_k$ 5:  if $\{\mathrm{CirSeg}-CirSegmen{t}_k\}$ in the same side of $CirLin{e}_k$ then

6:   $CirSegmen{t}_k\in SCEP$ (e.g., $\mathrm{SCEP}$ in Figure 6) 7:   $PathSegement$$\leftarrow$ $\{CirSegmen{t}_k-CirSegmen{t}_k\cap O\}$ 8:   if $PathSegement$ on the left side of $MidLine$ then 9:     $EnPoint$$\leftarrow$ the middle point of $PathSegement$ (e.g., $A$ in Figure 6) 10:    else $ExPoint$$\leftarrow$ the middle point of $PathSegement$ (e.g., $B$ in Figure 6) 11:    end if 12:  end if 13: end for 14: return $EnPoint$, $ExPoint$

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* method. The specific process of the algorithm was as follows Algorithm 2:

Algorithm 2. Get the avoidance path

Input: $O$, $S$, $ExPoint$, $EnPoint$

Output: $AvoidPath=\left\{AvoidPat{h}_{(i\to j),q}\right|q=1,2,\cdots ,Nq\}$ 1: for $k=1$ to $Nk$ do 2:  if $CirSegmen{t}_k\cap O$ then erase $CirSegmen{t}_k$ 3:  else if $CirSegmen{t}_k\cap \{\mathrm{CirSeg}-CirSegmen{t}_k\}$ then erase $CirSegmen{t}_k$ 4:  end if 5: end for 6: use $O$ and $S$ initialize A* map 7: for $i=1$ to $Ni$ do 8:   for $j=1$ to $Nj$ do 9:   search $Pat{h}_{i\to j}$ from $EntryPoin{t}_i$ to $ExitPoin{t}_j$ by A* (e.g., $S$ in Figure 7) 10:   for $k=1$ to $Nk$ do 11:    if $Pat{h}_{i\to j}\cap CirSegmen{t}_k$ then 12:     $Pathsegement$$\leftarrow$ $\{Csegmen{t}_k-Csegmen{t}_k\cap O\}$

13:     $AvoidPat{h}_{(i\to j),q}$$\leftarrow$ the middle point of $Pathsegement$ 14:    end if 15:   end for 16:  end for 17: end for 18: return $AvoidPath$ (e.g., the blue line in Figure 7)

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\mathrm{th}$ entry point could pass through:

$$n_{i\to j}=\min (\lfloor \omega \times \frac{L_{(i\to j),q}-2\times d_{safe}}{d}\rfloor +1)q=1,2,\cdots ,Nq$$

(15)

$$\{\begin{array}{l}{n}_i=\max n_{i\to j}\hspace{1em}j=1,2,\cdots ,Nj\\ jmax=\mathrm{argmax}(n_i)\\ N_{pass}={\displaystyle \sum _{i=1}^{Ni}{n}_i}\end{array}$$

(16)

where $d$ is the vertical interval distance of the UAV, $d_{safe}$ is the safe distance of the UAV, $L_{(i\to j),q}$ is the length of the $q\mathrm{th}$ formation channel segment from the $i\mathrm{th}$ formation path to $j\mathrm{th}$ formation path, $n_j$ is the number of UAV that can be passed by the $j\mathrm{th}$ formation path, $\omega$ is the scaling scale, and $0<\omega \le 1$ is to adjust the number of UAVs through the channels.

Then, we calculated the obstacle avoidance waypoint $PathPoint$ of ${\mathrm{UAV}}_i$ based on $AvoidPath$ obtained from $n_i$ and Algorithm 2; the specific process was as follows Algorithm 3:

Algorithm 3. Get fly path point

Input: $O$, $S$, $X(0)$, $AvoidPath$, $v$

Output: $PathPoint=\left\{PathPoin{t}_{uavi}\right|uavi=1,\cdots ,N\}$ 1: extent $AvoidPat{h}_{i\to j}$ to $S$ ’s boundary (e.g., $P$ in Figure 8) 2: if $AvoidPat{h}_{i\to j}$ do not satisfy constraints $R_{res}$ and $d_s$ then erase 3: end if 4: calculate $n_i$ by Equation (15) 5:   $CirLin{e}_k$$\leftarrow$$CirSegmen{t}_k$ 6: split UAV swarm into $Ni$ sub-forms 7: $PathPoint$$\leftarrow$ calculate $PathPoin{t}_{uavi}$ based $AvoidPat{h}_{(i\to jmax),q}$ 8: if $N_{pass}\le N$ then 9: $PathPoint$$\leftarrow$$\{N-N_{pass}\}$ UAV fly around the obstacle area 10: end if 11: for $uavi=1$ to $N$ 12:  $T_{uavi}$ = $\left|PathPoin{t}_{uavi}\right|/v$ 13: end for 14: $PathPoint$$\leftarrow$ use formation conversion algorithm with $T_{uavi}$ and $PathPoint$ 15: return $PathPoint$

5. Handling Exceptions

This paper dealt with two kinds of abnormal situations: flight abnormity and communication abnormalities during the formation flight of distributed ad hoc network UAV swarm. The processing methods of each category were shown in Figure 9, and the detailed processing methods were shown below.

5.1. Flight Abnormity

For the abnormal situation in which the tracking error was too large, the above-mentioned distributed ad hoc network online formation switch algorithm could be used for dynamic adjustment, and had the characteristics of not being related to the initial position of the UAV. In response to the falling of the UAV during the flight, the remaining UAVs switched formation online using the formation switch algorithm; that is, formation reconstruction.

5.2. Communication Abnormalities

Communication abnormalities mainly considered three situations. First, the excessive communication delay included two cases, which were the entire UAV swarm’s delay and some members’ delay of the UAV swarm. Second, the communication was completely disconnected; that is, the other UAV communication links in the UAV swarm were completely disconnected and could not be restored. Third, the communication was partially interrupted; that is, the UAV communication link of other parts of the UAV swarm was temporarily disconnected, and it could be restored after some time.

If the communication of some UAVs was completely disconnected, this could be regarded as the situation of UAV formation to reconstruct the formation. If there was a delay in communication, the offset error could be eliminated according to the online formation-switching algorithm. If the communication of some UAVs was temporarily interrupted, multiple iterative formation flights could be performed based on the distributed ad hoc network online formation-switching algorithm.

6. Simulation Analysis

In this paper, 12 UAVs were used for formation assembly, switching, and formation flight simulation under abnormal flight and communication environments, and 8 UAVs were used for formation obstacle avoidance simulation. In the simulation experiment, the algorithm was programmed in the C++ language, the platform tool was Microsoft Visual Studio 2016, and the hardware environment was a PC with an inter-core i5-4210 CPU, 2.60 GHz dual-core processor, and 8 GB memory.

6.1. Formation Assembly and Formation Switching

The 12 UAVs took off in succession. After each UAV passed the assembly point A, the formation-switching algorithm began to take over the UAV, planning the trajectory of the UAV; the formation was assembled into an inverted V-shape; and then the formation-switching algorithm was enabled again to change the swarm into a V-shaped formation, as shown in Figure 10. The simulation parameters that had to be set are shown in

Table 1. Simulation parameters.

UAV Swarm Attributes	Parameter Value
Number of UAVs $n$	12
Launch interval	5 s
UAV speed $V$	30 m/s
Maximum turning angle constraint ${\beta }_{\max }$	90°
Turning radius $R$	300 m
Minimum track length constraint $d_s$	600 m
Assembly point A	(0 m, 2000 m)
Communication topology	Fully Connected
Assembled formation	Inverted V-Shape
Switch formation	V-Shape
Formation interval in x direction	100 m
Half vertex angle of V-shaped	45°
Formation-switching distance D	Adaptive (met the minimum switching distance)

. The simulation results of formation assembly and formation switching in the horizontal plane are shown in Figure 11 and Figure 12.

The assembly formation was V-shaped, the formation switching was changed from V-shaped to column formation, the vertical formation interval in the y-direction was 100 m, and other parameters remain unchanged. The simulation is shown in Figure 13 and Figure 14.

It can be seen in Figure 12 and Figure 14 that when the communication topology of UAV swarm was fully connected, formation aggregation and formation switching could make the distance between each UAV meet the desired requirements after a formation interval correction; namely, the communication event was $k=0$. If the communication topology was partially interrupted, the formation interval had to be corrected again. This method could simply and quickly converge to the final expected formation interval value. It can be seen in Figure 11 and Figure 13 that this formation method could quickly plan the route to the formation waypoints under the constraints of the UAV dynamics, and has a high engineering application value.

6.2. Formation Obstacle Avoidance

The obstacle avoidance area was rectangular, and the relevant parameters are shown in

Table 2. Obstacle avoidance area parameters.

Obstacle Avoidance Area Properties	Parameter Value
Rectangle center point	(7000 m, 5000 m)
Rectangular area length	10,000 m
Rectangular area width	10,000 m

. Eight UAVs formed a column formation to enter the obstacle avoidance area. The obstacle information is shown in

Table 3. Obstacle parameters.

Obstacle Index	X/m	Y/m	Radius/m
1	3000	7000	500
2	4000	3000	500
3	6500	5000	500
4	11,000	3000	900
5	11,000	6000	600

. The initial position information of UAVs is shown in

Table 4. Initial position of UAV.

UAV Index	X/m	Y/m
1	1000	3000
2	1000	6500
3	1000	3500
4	1000	6000
5	1000	4000
6	1000	5500
7	1000	4500
8	1000	5000

. The maximum turning angle constraint was 90°, and the minimum direct flight distance constraint was calculated according to Equation (9). The UAV swarm passed through the obstacle and was reconstructed into a V-shape. Other parameters of UAV swarm are shown in Table 1. The horizontal plane simulation results are shown in Figure 15.

We reset obstacles for simulation, and the obstacle information is shown in

Table 5. Obstacle parameters—scene 2.

Obstacle Index	X/m	Y/m	Radius/m
1	3000	5000	700
2	6000	14,000	1000
3	6500	5000	700
4	7000	8500	1300
5	11,000	4000	900

. Other parameters remain unchanged; the horizontal plane simulation results are shown in Figure 16.

As can be seen in Figure 15 and Figure 16, the UAV swarm could be intelligently divided into multiple smaller formations to pass obstacles or fly around to avoid obstacles. Finally, it could be reconstructed into the expected formation. The simulations showed that the algorithm could quickly and flexibly plan the cooperative obstacle avoidance path and had the ability of online formation to avoid obstacles.

6.3. Handle Exceptions

6.3.1. Flight Abnormity

Suppose the number of UAV swarm was 12, and the assembly formation was an inverted V-shaped formation. After the formation assembly, four UAVs were randomly dropped or lost. Then, the remaining eight UAVs were reconstructed into a column formation. Other simulation parameters were still as shown in Table 1, and the simulation results are shown in Figure 17 and Figure 18:

It can be seen in Figure 17 and Figure 18 that after the UAV flight abnormally fell, then the required formation could be reconstructed according to this plan.

6.3.2. Communication Abnormity

In actual flight, the communication topology may be temporarily interrupted. At this time, a communication event, $k=0$, is insufficient to meet the expected formation, and formation interval distance correction is required again.

In this simulation, a formation switch was performed from an inverted V-shape to a V-shape. It was assumed that in the initial communication event, namely $k=0$, the communication failure rate reached 18%, and in the second communication event, namely $k=1$, the communication failure rate reached 9%. Other parameters were as shown in Table 1, and the results are shown in Figure 19 and Figure 20.

It can be seen in Figure 19 and Figure 20 that in the case in which some UAVs and other UAVs were lost in the communication network, the first formation interval distance correction could not obtain the desired formation. In the second correction, the communication network still had local faults, but eventually formed the expected formation. So, the formation-switching algorithm was effective in dealing with communication abnormity.

6.4. Simulation Comparison

6.4.1. Formation-Switching Method

The formation-switching control method proposed in this paper mainly dealt with the communication abnormalities of the UAVs during the flight. Therefore, the classic consistency control method [31], which could handle changes in the communication topology, was selected to compare to illustrate the effectiveness of the algorithm.

We selected six UAVs for simulation, and used the simulation scenario in Section 6.3.2 to set the consistency control step to meet the minimum algorithm stability requirement, which was 0.2 s. The simulation of the classical consistency control method is shown in Figure 21, and the method proposed in this paper is shown in Figure 22.

The algorithm performance during the simulation process was recorded, as shown in

Table 6. Simulation comparison.

Method	Classical Consistency Control Method	Proposed Method
Number of communication requests	200 times	2 times
Average solution time per communication	125 ms	53 ms
Total running time of the algorithm	1521 ms	131 ms

.

The simulation results showed that when the step length was 0.5 s, in the case of abnormal communication, the classic consistent formation control method needed to communicate with neighboring UAVs 200 times before the formation could be changed from an inverted V to a V-shape. The route-based formation-switching method proposed in this paper only needed two communications to obtain the required formation waypoints, which greatly reduced the pressure on the airborne communication system.

In addition, the classic consensus algorithm obtained the coordinated route of the UAV by controlling the deflection angle of the track. The average solution time per communication took a longer time, and required high control system performance, which could not guarantee the real-time performance of online formation flying. The solution proposed in this paper was time-consuming, and only required the UAV to perform direct flight and turning maneuvers. It was easy to control during the flight and easy to implement in engineering. However, the disadvantage was that the planned path distance was relatively long.

6.4.2. Formation Obstacle Avoidance Method

The sparse A * algorithm [30] was selected and compared with the formation obstacle avoidance algorithm proposed in this paper to illustrate the effectiveness of the algorithm. The simulation scenario used scenario 2 as given in Section 6.2. The sparse A* simulation results are shown in Figure 23.

In order to analyze the complexity of the two algorithms, the number of UAVs in the formation was increased successively, and the two algorithms were used to simulate the formation obstacle avoidance simulation. The relationship between the algorithm running time and the number of drones was obtained as shown in Figure 24.

We concluded from Figure 16 and Figure 24 that the sparse A* algorithm was basically the same as the obstacle avoidance path planned by the algorithm in this paper, but the running time of the sparse A* algorithm was much longer than that of the algorithm in this paper, and it doubled with the increase in the number of UAV formations. However, the obstacle avoidance algorithm proposed in this paper based on geometry had a shorter running time and did not change significantly with the increase in the number of UAVs. It could meet online real-time trajectory planning, and has strong engineering applicability.

7. Conclusions

This paper proposed a method of fixed-wing UAV swarm formation control based on distributed ad hoc networks. This method included the formation switching of UAVs, formation obstacle avoidance, and handling of abnormal conditions during flight.

Simulation results showed that in formation switching, the ad hoc network, high-dynamics, fixed-wing UAV could form formation switching only by position information. The method was not sensitive to the initial position information of the UAV, which could eliminate errors during flight, and handle temporarily interrupted communication topologies and UAV drop, as well as other abnormal flight situations. In formation obstacle avoidance, the UAVs could be clustered into multiple subformations to pass through the obstacle avoidance area, and could be reconstructed as required formation. The formation technology was designed based on the waypoints, which was versatile, simple, and reliable, and is easy to realize in engineering.

Compared with the classic consistent formation control algorithm and obstacle avoidance algorithm, it was shown that the formation technology method proposed in this paper had lower complexity and higher timeliness, and is suitable for online formation flying of highly dynamic UAVs in an ad hoc network. However, the route planned by the method did not consider optimality, and it was only suitable for high-speed and constant-speed formation missions. For obstacle avoidance algorithms, the obstacle model is too simple, and there may be scenarios for obstacle avoidance that are not covered by the algorithm. Next, we will consider the optimal route planning problem and extend the algorithm to three-dimensional flight scenes to increase its practicability.

8. Patents

Suo, W.B., Zhang, D., and Wang, M.Y. “A distributed unmanned aerial vehicle flying around formation method based on time consistency”, C.N. Patent, 202010226440.4, issued 10 July 2020.

Zhang, D., Suo, W.B., and Wang, M.Y. “A distributed unmanned aerial vehicle dynamic formation switching method based on waypoints”, C.N. Patent, 202010226439.1, issued 10 July 2020.