Yang YUAN，Yimin DENG，Sida LUO，Haibin DUAN?，3

1State Key Laboratory of Virtual Reality Technology and Systems，School of Autonomous Science and Electrical Engineering，Beihang University，Beijing 100083，China

2School of Mechanical Engineering&Automation，Beihang University，Beijing 100191，China

3Peng Cheng Laboratory，Shenzhen 518000，China

Abstract: We investigate a distributed game strategy for unmanned aerial vehicle (UAV) formations with external disturbances and obstacles.The strategy is based on a distributed model predictive control (MPC) framework and Levy flight based pigeon inspired optimization (LFPIO).First，we propose a non-singular fast terminal sliding mode observer (NFTSMO) to estimate the influence of a disturbance，and prove that the observer converges in fixed time using a Lyapunov function.Second，we design an obstacle avoidance strategy based on topology reconstruction，by which the UAV can save energy and safely pass obstacles.Third，we establish a distributed MPC framework where each UAV exchanges messages only with its neighbors.Further，the cost function of each UAV is designed，by which the UAV formation problem is transformed into a game problem.Finally，we develop LFPIO and use it to solve the Nash equilibrium.Numerical simulations are conducted，and the efficiency of LFPIO based distributed MPC is verified through comparative simulations.

Key words: Distributed game strategy;Unmanned aerial vehicle (UAV);Distributed model predictive control (MPC);Levy flight based pigeon inspired optimization (LFPIO);Non-singular fast terminal sliding mode observer (NFTSMO);Obstacle avoidance strategy

1 Introduction

Unmanned aerial vehicles (UAVs) have attracted wide attention with their advantages of low cost，simple operation，and high reliability (Wang B et al.，2020).Compared with manned aerial vehicles (MAVs)，UAVs are more suitable for boring，harsh，and dangerous tasks.For these reasons，they are popular in cargo transportation，aerial photography，and other civil and military fields (Labbadi and Cherkaoui，2019;Zheng and Cai，2021).In recent years，the UAV swarm has become an important topic in academia and industry(Huo et al.，2021;Li W et al.，2021;Luo et al.，2021).Studies have indicated that the UAV swarm can expand the field of application for UAVs，and has more reliable，more robust，and more durable task execution capabilities (He et al.，2018).Formation control is a key technology for UAVs to realize the collaborative work of a swarm system，and there has already been a wealth of work on the topic.Common formation control methods include the leader–follower strategy，the behavior-based method，and game theory(Dong et al.，2016;Ran et al.，2019;Yang J et al.，2019).

In the leader–follower formation framework，the leader tracks a predetermined trajectory，while the follower interacts with the leader to maintain a relative position.Wang AJ et al.(2018)studied the tracking consistency of the second-order system by designing a fractional observer，and the event-triggered control strategy of periodic sampling was used for the leader–follower formation by using relative position information.However，the structure is not robust enough to guarantee the formation if the leader breaks down or if the communication is unstable.He et al.(2018) proposed a multi-implicit leader formation control algorithm to solve the above problems，adopting a consensus protocol applicable to both the leader and follower.As there was no explicit leader，the damage of a single node had little effect on the stability of the whole swarm.Trinh et al.(2021) studied the bearing-constrained leader–follower formation control problem depending on displacement and bearing vectors，where the relative velocity，bearing rate，and information exchange were not required.Xia et al.(2022) transformed the leader–follower formation problem of heterogeneous systems with time-varying output into a conventional tracking control problem，where a resilient observer was used to eliminate the effect of a cyber-attack.

In the behavior-based method，each UAV has an equal status，and damage to a single UAV node does not affect the normal work of the entire system.Based on the Reynolds rule，Olfati-Saber (2006) proposed three distributed clustering algorithms that can realize a self-organizing formation.Lee G and Chwa (2018)developed a decentralized，behavior-based formation controller considering obstacle avoidance for multiple robots.Qiu and Duan (2020) designed a distributed UAV-formation control framework based on biological behavior，where the UAV control problem was transformed into an object-optimization problem.Tan et al.(2021) proposed the hybrid behavior-based coordination–control method for multiple unmanned surface vehicles，which was effective in a dynamically changing or unknown environment.Liu et al.(2021)studied a behavior-based cooperative target tracking strategy for a dual robotic-dolphin system，and achieved high-level decision-making by the combination of the behavior-based approach and a centralized architecture.

However，the above research considers only the performance of the formation，and the target of a single UAV is ignored.For example，the fuel consumption，preset speed，and attitude requirements of a UAV should be concerned with in some situations.When each UAV has its own objective，UAV formation can be regarded as a game problem in the case of different individual objectives.Gu (2008) proposed a differential game method for the formation control of robots，where the formation control was expressed as a linear quadratic Nash differential game by means of graph theory.Jond and Nabiyev (2019) discussed the coupled Riccati differential equation of the solvability of the differential game method for the formation control problem，and proved the existence of the Nash equilibrium in the discrete formation control problem.Li JQ et al.(2021) studied a distributed game strategy for multi-spacecraft formation control under nonlinear dynamics and perturbation，proposed a worst-case Nash equilibrium strategy，and proved the existence of an open-loop Nash equilibrium.Li YB and Hu (2022) addressed the non-cooperative formation control problem of a multi-agent system by differential game strategy，and studied the Nash equilibria of the finite horizon and infinite horizon games.

Formation control based on a distributed model predictive control (MPC) framework and the optimization algorithm has also been a focus of research in game theory.To solve the formation control problem of UAVs，Zhao et al.(2022) designed a coordinated control scheme based on a distributed MPC.The cost functions of heterogeneous roles such as the leader，coordinator，and follower have been established，and solved by the particle swarm optimization (PSO) algorithm.Yu et al.(2021) defined the tracking task as a distributed MPC problem，and proposed a Nashcombined adaptive differential evolution(ADE)method by combining the ADE algorithm with Nash optimization.Wang YX et al.(2020) proposed a distributed MPC method based on swarm intelligence to solve the local finite time domain optimal control problem using the chaotic gray-wolf optimization (CGWO)method，and adopted an event-triggered strategy to reduce the computation burden.

However，the influence of disturbance on formation was not considered in the above-mentioned research.Keeping the original formation when avoiding obstacles does not guarantee optimal energy for all individuals in large clusters.Based on the above problems，we propose a distributed UAV formation control framework in complex scenarios with external disturbances and obstacles.First，a non-singular fast terminal sliding mode observer(NFTSMO)is proposed to observe the disturbance，and a non-disturbance UAV model is obtained.Second，a distributed UAV obstacle avoidance strategy is proposed with topology reconstruction.Finally，the cost function of each UAV is established in the distributed MPC framework，and a Levy flight based pigeon inspired optimization(LFPIO) algorithm is proposed to solve the distributed cost function to achieve the Nash equilibrium.

The contributions of this study can be summarized as follows:(1)The robustness against disturbance is provided by NFTSMO and fast convergence of the observer is achieved;(2) More energy of a single UAV can be retained during the process of obstacle avoidance by the developed obstacle avoidance strategy;(3) High precision formation with an unknown disturbance can be guaranteed with the proposed NFTSMO and LFPIO based distributed MPC.

2 UAV model and problem formulation

In this study，to design the formation controller of UAVs，we adopt the representative UAV model widely used in much of the literature(Lin，2014;Wei et al.，2021)，in which the dynamic model can be described as

wherexi，yi，andzirepresent the location under the inertial system of coordinates，Vi，χi，andγiindicate the ground speed，heading angle，and flight path angle，respectively，Li，Di，andTiare lift，drag，and engine thrust，respectively，φiis the banking angle，mis the mass of the UAV，gis gravitational acceleration，dVi，dχi，anddγiare the external disturbances ofVi，χi，andγi，respectively，and the control inputs of the model areLi，Ti，andφi.

Defining，and taking the derivative ofvi，we can obtain

Defining，we can further obtain

Remark 1In this paper we focus on formation control and assume thatuican be ideally controlled.

The schematic of the proposed distributed game strategy is shown in Fig.1.

Fig.1 Schematic of the distributed game strategy

To compensate for the effects of disturbance，we propose an NFTSMO to estimate the disturbance value and then obtain a UAV model without disturbance.By usingudito compensate for the disturbance，the control inputuican be redefined asui=udi+uni，whereuniis used to achieve the goal of formation.Eq.(4)can be further derived as

Whenudi+diconverges to zero，it can be approximated that=Azi+Buni.

Graph theory is used to represent the information exchange among UAVs.We defineG={V，ε}，where UAVi∈Vrepresents a UAV node，andeij∈εindicates the information transmission from UAVjto UAVi.The adjacent matrix ofGis defined asH=[hij]∈RNUAV×NUAV，whereNUAVis the number of UAVs in the formation，and elementhijis defined

Remark 2To guarantee formation consistency，there is at least one directed spanning tree in graphG.

The distributed MPC framework is applied to achieve a formation with the Nash equilibrium strategy.Each UAV is configured with MPC and MPC is applied to determine its own behavior according to the information exchanged，independent of each other.The performance index for each UAV in the framework is designed as

subject tozi∈Z，uni+udi∈U，whereδis the time step，is the final relative state between UAViand UAVj，which is determined by formation shapezd，(t) is the preset speed to complete the task，q，r，m，andnare the weights of the costs，andNis the number of prediction steps.The performance indices consist of four parts:the desired formation configuration in 0–(N－1) steps，the energy consumption in the process，the terminal state penalty function in theNthstep，and the penalty function for the predetermined velocity.

The Nash equilibrium strategy of the UAV formation is defined as follows(Lee SM et al.，2015):

fori=1，2，…，NUAV.When the system reaches the Nash equilibrium，no UAV can further optimize its cost by changing its own strategy under the condition that all the other UAVs remain unchanged.

Due to the state variables，and because the control inputs of multiple UAVs are coupled together in the cost function，it is difficult to find a Nash equilibrium strategy to ensure stability by optimizing the control input sequence within a limited prediction range in a distributed MPC framework.Therefore，heuristic optimization algorithms are used to solve the problem，and some studies have shown that evolutionary algorithms are effective.In an LFPIO-based distributed MPC framework，each UAV has its own population to optimize the cost function value，and the local optimization problem is solved with LFPIO according to the Nash equilibrium strategy.

3 Distributed game strategy for UAV formations

3.1 Non-singular fast terminal sliding mode observer

For the particle model of this paper，we consider the system

wherez∈Rn×1is the state，A∈Rn×nis the state matrix，andB∈Rn×mis the input matrix，u∈Rm×1is the control input，andd∈Rn×1is the external disturbance.

Sliding mode observers with different forms have been developed to solve various problems (Xiong and Saif，2001;Kalsi et al.，2010;Yang HY et al.，2022).For fast convergence，NFTSMO is developed in this study to achieve high precision formation with unknown disturbances.The non-singular fast terminal sliding surface can be defined as follows (Labbadi and Cherkaoui，2020;Wang X et al.，2022):

wheree=z-，is the observed state，λ1andλ2are positive numbers larger than 1，Π1=diag(λ11，λ12，…，λ1n)，Π2=diag(λ21，λ22，…，λ2n)，andλij＞0 (i=1，2，j=1，2，…，n).

Motivated by the observer forms designed in previous studies (Kalsi et al.，2010;Czy?niewski and ?angowski，2022)，the disturbance observer is designed as follows:

whereis the estimated value ofd，ηis a positive constant larger than the bound of，ρis a small positive scalar.

We pick the differential of the observed state error as

The derivative ofscan be calculated by

We define the Lyapunov function asVo=0.5sTs，of which the derivative is

Lemma 1(Bhat and Bernstein，2000) Lyapunov functionVis defined in the neighborhoodΩ(Ω∈R)of the origin.If(x) +lVμ(x)≤0，x∈Ω，wherel＞0，0＜μ＜1，the statexconverges to the original neighborhood in a fixed time，whereV(x0) is the initial value ofV(x).

Lemma 1 indicates that NFTSMO is fixed-time convergent.We then divideuinto two parts，unandud，and Eq.(4)is reformed as

We defineud=B+，whereB+is the Moore-Penrose generalized inverse matrix ofB，and substitute it into Eq.(14).We can obtain

Sinceconverges toBdin a fixed time，the model is considered as=Az+Bunwhen designing the formation controller.

3.2 Obstacle avoidance strategy

In this study，we propose an obstacle avoidance method based on topology reconstruction.As shown in Fig.2，a safe circle with radiusRiis set to ensure a safe distance.There are two cases in which the UAV formation encounters obstacles，and the three dashed lines in the figure are in the same direction as the ideal speed of the formation.In the first case，the UAV formation is on one side of the middle，dashed line，and the UAVs avoid the obstacle while keeping formation.In the second case，UAVs are on either side of the middle，dashed line.The UAV formation is split into two parts and flies over the obstacle on either side.

The specific obstacle avoidance strategy can be divided into the following steps:

Step 1:UAVijudges whether UAVjis within the obstacle range shown in Fig.2.If so，go to the next step;otherwise，exit.

Fig.2 Two cases in which UAVs encounter obstacles:(a)first case;(b)second case

Step 2:The distance between UAViand the obstacle is detected.If the distance is less thando，go to the next step;otherwise，exit.

Step 3:A new adjacency relationship with other UAVs based on the position information is established，as shown in Fig.2b，and the new sub-formationΣkis fully connected.The UAVs in the obstacle range inΣkare defined as setΣkd，and UAVjclosest to the obstacle is located.

Step 4:The reference speed(t) of UAVjwhen avoiding obstacles is calculated.As shown in Fig.3，the ideal speed of UAVjisat pointP1，wherel1is in the tangent line of UAVjto the safety circle，and the angle betweenvj(t) andl1is smaller than the angle betweenvj(t) andl2.As UAVjmoves to pointP2，the tangent line of UAVjto the safety circle isl3，and the ideal speed changes as

Fig.3 Ideal speed for obstacle avoidance

Step 5:(t)is transmitted to sub-formationΣk.

The trajectory created by(t) can be divided into curvesC1，C2，andC3.In the first stage，UAVjapproaches the safety circle along curveC1as its velocityvj(t) is in the right hand of the desired velocity(t).In the second stage，UAVjmoves along the safety circle until velocityvj(t) is in line with the preset velocity.In the final stage，UAVjsuccessfully avoids the obstacle and moves by the rules of UAV formation.

Due to the strategy of selecting UAVjinΣkdclosest to the obstacle to generate the obstacle avoidance speed of the sub-formation，the safe distance from the obstacle can be guaranteed.In case 1，the formation remains fully connected during obstacle avoidance.If there is a single individual on one side in case 2，the cost function of the individual retains the control assumption term and velocity term.The preset reference speed is restored when the obstacle is passed.

3.3 Levy flight based pigeon inspired optimization

Pigeon inspired optimization (PIO) is a novel heuristic optimization algorithm proposed by Duan and Qiao (2014)，and has been widely used in many fields (Ruan and Duan，2020).PIO simulates the biological mechanism of the homing navigation of pigeons，and different operators are designed according to navigation tools in different stages.In the first stage，the pigeons use the geomagnetic field and the sun as navigation tools，and a map and compass operator is established.In the second stage，a landmark operator is designed to simulate the effect on pigeons of landmarks near the destination.

We set the swarm size of pigeons toNp，and the maximum numbers of iterations of the first stage and the second stage areNc1maxandNc2max，respectively.The initial position of theithpigeon is，and the velocity is.In the first stage，the updating rules of position and speed are as follows:

wherelindicates the generation number，Rrepresents the map and compass factor，Xgis the global best position，and rand is a random number between 0 and 1.When generationlexceedsNc1max，the updating rules are transformed as follows:

wheref() represents the fitness of，which is the reciprocal ofJi.In the landmark operator phase，half of the pigeons with poor performance in each generation are eliminated，which can accelerate the convergence of pigeon swarm.However，it is also easy to fall into the local optima(Zhang et al.，2017).

To solve the problem of premature convergence of the population，we propose a Levy flight based PIO，which combines two operators in one stage.The improved updating rules of position and speed are as follows:

wherer1is the scaling factor，sis the Levy flight operator，and ⊕is the dot product operator.The Levy flight model is an optimal random walk model with a heavy tail probability distribution (Feng et al.，2021)，which can be described as follows:

whereδ∈(0，2]is a constant，συ=1，andN(0，σ2)represents the normal distribution.

3.4 LFPIO based Nash equilibrium strategy for distributed MPC

There is a separate cost function for each UAV，and a separate pigeon flockSiis designed for each cost function for optimization.The control input sequence at timetobtained by solving the distributed MPC can be expressed asUni(t)=[uni(0|t)，…，uni(NUAV-1|t)]，anduni(0|t)is used as the control input for the UAV model.We defineSi，j∈{1，2，…，Np}，which represents the position of thejthpigeon at generationlin swarmSicorresponding to UAVi，and the velocity of thejthpigeon is.The solution process is shown in Fig.4.

Fig.4 LFPIO based Nash equilibrium strategy for distributed MPC

Step 1:The control input sequenceUni(t-δ) at the previous moment is inherited at timet，and it is used as the initial input sequence of the current moment after the following processing:

It can be seen thatUni(t) inherits the predicted value ofUni(t-δ) from step 1 to stepN-1，and the predicted value at stepN-1 is also assigned touni(NUAV-1|t).

Step 2:The received neighbor information is processed according to step 1，and the cost function of UAViis calculated.We determine whether the costJi(t) is greater than the triggered thresholdTJ.If it is，the current input does not meet the requirement，and LFPIO is triggered to optimize the input sequence.If not，Uni(t)will be output.

Step 3:Using LFPIO to optimize the cost function，Uni(t)from step 1 is taken as the initial global optimal position.The updated global optimal position is output as the control input sequenceUni(t) after optimization.

Step 4:The output sequenceUni(t) is sent to the neighbor and executed as the first control input in the sequence.

4 Simulation results

In this section，the numerical simulation conducted for the two cases is shown.The simulation stepδwas 0.2 s，and the prediction horizon of MPC was[t，t+4δ].A swarm of five UAVs was used for the simulation，of which the initial speeds were all set as 20 m/s，and the position of each UAV was generated randomly.In both cases，the UAVs were subject to external interference，and the disturbance of UAViwas set as

The initial adjacent matrix and formation shapezdwere set as

andis the result of thejthcolumn ofzdminus theithcolumn.

Four different methods were used to generate control inputs，PIO (PIO without using NFTSMO)，LFPIO (LFPIO without using NFTSMO)，PIO with NFTSMO，and LFPIO with NFTSMO.The parameters of PIO and LFPIO are given in Table 1.

Table 1 Parameters of PIO and LFPIO

To reduce the computational burden，the total number of iterations of PIO and LFPIO was set as 30.Rwas set to 0.1 to obtain a good search capability.Settingr1to 0.01 increased its development capability after exploration，and the ability was poor whenr1was large.

The desired speed was set as

There were two obstacles in the flight path of the UAVs，of which the coordinates were (300，0)Tand (1050，400)T，and the radius of the obstacles was 30 m.

The simulation results of the trajectories are shown in Fig.5.First，the UAV formation can successfully complete the task and navigate through all obstacles with the obstacle avoidance strategy proposed in this study.When crossing the first obstacle (Fig.2b)，the UAVs were automatically divided into two subformations.When facing the second obstacle (Fig.2a)，the UAVs chose to keep the formation，flying from one side.The effectiveness of the obstacle avoidance strategy proposed is clearly shown.Second，the ideal trajectory generated in each time period with the desired velocity was a straight line in the case of no obstacles.However，we can see that the velocity directions of the UAVs in Figs.5a and 5b deviated significantly from the predetermined one with the influence of a disturbance.It is apparent that the methods with NFTSMO had better performance than the others.The simulation results in Figs.5c and 5d were straighter than those in Figs.5a and 5b.The observation results of the disturbance are shown in Fig.6，in which the observed value and the actual value were essentially the same in three channels.

Fig.5 Simulation results of trajectories:(a)PIO;(b)LFPIO;(c)PIO with NFTSMO;(d)LFPIO with NFTSMO

Fig.6 Observed values of disturbance

The velocities of UAV1 with different methods are shown in Fig.7.The velocity trends obtained by the four methods were essentially consistent.At the beginning of the curves in Figs.7a and 7b，the velocity obtained by PIO fluctuated the most，followed by LFPIO and PIO with NFTSMO，and finally LFPIO with NFTSMO.When encountering an obstacle，the speed of UAV1 showed a strong variation.As depicted in the local figure，the speed obtained by LFPIO with NFTSMO was closer to the reference most of the time.The PIO and LFPIO methods had greater velocity deviations than PIO with NFTSMO and LFPIO with NFTSMO，which demonstrates the effectiveness of NFTSMO.

Fig.7 Velocity of UAV1 with different methods:(a)velocity along the X axis;(b)velocity along the Y axis

We averaged the cost function for each UAV to obtainJmean，and took log base 10 ofJmeanto obtain Fig.8.At the initial moment，the values ofJmeanof all the four methods were large due to the large difference between the relative position and the ideal relative value.After a period of time，the mean cost value stabilized within a certain range.The UAVs detected obstacles and carried out topology reconstruction at 10 s，and the cost function increased suddenly due to the change of the UAVs’ adjacent matrix.The UAVs completed the obstacle avoidance，and the formation topology was restored to the initial state at 13.6 s.At the time，the UAVs were located on both sides of the obstacle and the distance between the two subgroups was the largest，thus the cost function mutated again.The cost function increased suddenly as the UAVs’preset speed changed at 50，100，and 150 s.The cost function changed suddenly at 66.2 s because the UAVs encountered obstacles again.We can also see that LFPIO performed better than PIO most of time with or without NFTSMO，indicating that LFPIO has stronger search ability than PIO and can acquire a better solution.

Fig.8 Average cost with different methods

Fig.9 shows the triggered times of UAV5 with different methods.The triggered threshold was set as 10，indicating that it will not be triggered in the case ofJi(t)≤10.The effects of the disturbance cannot be ignored，for which PIO and LFPIO were still triggered at every moment.Corresponding to Fig.5，the control input updated less without encountering obstacles and changing direction，and the triggered times were reduced(Fig.9).

Fig.9 Triggered times of UAV5 with different methods

The details of triggered times of UAVs with different methods are shown in Table 2.The UAVs need to calculate the control input at every moment in the absence of NFTSMO.The triggered time of LFPIO with NFTSMO was only 455 for UAV1，and the average time was only 498.6，which means that the computing burden was halved.Compared with PIO with NFTSMO，the triggered times of LFPIO with NFTSMO were reduced by 12.8%.

Table 2 Triggered times of UAVs with different methods

Through the above analysis，we can see that the obstacle avoidance strategy and disturbance observer were very effective，and the optimization ability of LFPIO was greatly improved compared with PIO.

5 Conclusions

In this study，considering the problem of distributed UAV formation，we designed a non-singular fast terminal sliding mode observer to observe the influence of disturbance，and feedforward compensation was conducted to obtain a non-disturbance model.When the UAVs encountered obstacles，topology reconstruction was used to ensure that each UAV can take a small output to avoid obstacles.Based on the above work，a cost function was established in the distributed model predictive control framework，and a Nash equilibrium strategy was adopted.Then，the original pigeon inspired optimization was improved，and a Nash equilibrium can be obtained by Levy flight based pigeon inspired optimization.The simulation results showed that the distributed game strategy is effective.

Contributors

Haibin DUAN and Yang YUAN designed the research.Yang YUAN and Yimin DENG processed the data.Yang YUAN drafted the paper.Sida LUO helped organize the paper.Haibin DUAN and Yang YUAN revised and finalized the paper.

Compliance with ethics guidelines

Yang YUAN，Yimin DENG，Sida LUO，and Haibin DUAN declare that they have no conflict of interest.