Advanced
Nonlinear Model Predictive Control for Multiple UAVs Formation Using Passive Sensing
Nonlinear Model Predictive Control for Multiple UAVs Formation Using Passive Sensing
International Journal of Aeronautical and Space Sciences. 2011. Mar, 12(1): 16-23
Copyright ©2011, The Korean Society for Aeronautical Space Science
  • Received : March 26, 2010
  • Accepted : March 16, 2011
  • Published : March 30, 2011
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Hyo-Sang Shin
Min-Jea Thak
mjtahk@fdcl.kaist.ac.kr
Hyoun-Jin Kim

Abstract
In this paper, nonlinear model predictive control (NMPC) is addressed to develop formation guidance for multiple unmanned aerial vehicles. An NMPC algorithm predicts the behavior of a system over a receding time horizon, and the NMPC generates the optimal control commands for the horizon. The first input command is, then, applied to the system and this procedure repeats at each time step. The input constraint and state constraint for formation flight and inter-collision avoidance are considered in the proposed NMPC framework. The performance of NMPC for formation guidance critically degrades when there exists a communication failure. In order to address this problem, the modified optimal guidance law using only lineof-sight, relative distance, and own motion information is presented. If this information can be measured or estimated, the proposed formation guidance is sustainable with the communication failure. The performance of this approach is validated by numerical simulations.
Keywords
1. Introduction
Over the last decade, formation flight technology has become more important with the increasing number of commercial and military applications on multiple unmanned aerial vehicles (UAVs). Formation of multiple UAVs includes two major problems of: (i) how to guide each UAV to a formation position (Kim et al., 2002; Tahk et al., 2005), and (ii) how to maintain tight formation (Pachter et al., 2001; Ryoo et al., 2005; Verma et al., 2003).
If there are fixed obstacles such as mountains and enemy defense sites, path planning by trajectory optimization may be performed first. However, the possibility of collision with other members in the formation is high if there are large external disturbances or if the change of formation pattern is associated. Due to unexpectedness of collision with other mobile objects, it is difficult to construct a guidance law for formation flying of multiple UAVs. Ryoo, C. K. (2005) propsoed an optimal closed-form solution for formation guidance without collision avoidance is obtained first, and a command term for collision avoidance is added.
Because most autonomous formation flight methods require an active communication link between the vehicles, damage to the receiver or the transmitter and communication delay are critical to mission success. For the prediction of future state values, nonlinear model predictive control (NMPC) must know the acceleration of the other vehicles along all the future time horizons, and this problem is more critical. Passive detection of another vehicle would be much preferred to the methods for the formation guidance.
One possible method for passive sensing target information is to use visual sensors. Vision-based formation control has been actively studied in robotics (Das et al., 2002). The guidance laws for approaching and forming the formation using only line-of-sight (LOS) angles is proposed in Tahk et al. (2005). In Sattigeri et al. (2004), an adaptive approach to vision-based UAV formation control assumes that LOS range can be estimated by the visual sensors. Each vehicle in formation can measure its speed, heading, LOS range, and angle to other vehicles. The developed formation control assumes that the neighboring vehicles are stationary in formation and dynamic model inversion errors are adaptively approximated by a neural network. Another passive method for sensing the vehicles is to use the wake produced by the leading aircraft (Sutton and Bitmead, 2000). A neural network is used to estimate the relative position from the leader and the initial training phase of the neural network requires the follower to receive a relative position from the leader.
MPC refers to a class of control algorithms that use a process model to predict the output along a future time horizon of the system (Bhattacharya et al., 2001; Kouvaritakis et al., 2001) and calculates a control input sequence to optimize future system behavior using the receding horizontal concept at each step (Mayne et al., 2000; Michalska and Mayne 1993). Then, the MPC algorithm implements only the first control signal to the system and optimization is repeated at subsequent control intervals in real time. NMPC, the MPC for a nonlinear model and/or nonlinear constraints, can deal with explicit constraints on the inputs and the states. Therefore, the optimal formation guidance in consideration of collision avoidance can be constructed by using NMPC. One issue is that, in formation, each follower usually uses the relative distance, LOS angle, own motion information, and the acceleration intent along all time horizons for multiple vehicles in the formation flight. This requires communication between the vehicles. In this paper, the modification is made to use only the relative distance, LOS angle, and own motion information. The acceleration of the other vehicles is unnecessary in this modification, and the modified approach can solve sub-optimal formation problems in consideration of collision avoidance without data communication.
The leader-follower structure, which is a common formation structure, is considered in our paper. While the leader generates a formation trajectory for a common mission, each follower follows the trajectory generated by the leader and keeps its position within a specific distance in the leader-wingmen structure. Thus, in our paper, each wingman solves the optimal control problem including collision avoidance.
This paper is organized as follows. In the next section, NMPC for formation guidance is first introduced. After the formation guidance using NMPC is developed, the modification that uses only the estimation of other vehicle’s acceleration is introduced. The stability of the error dynamics between the modification and NMPC is also investigated. Simulation for three UAVs converging to a formation while avoiding danger of collision is presented to verify the performance of the proposed methods. Conclusions are provided in the final section.
2. NMPC for Formation Flight
- 2.1 Equations of motion for formation flight
Consider the planar motion of two vehicles shown in Fig. 1 . The two-dimensional point mass model is used in formation of a group of UAVs for simplicity.
In this figure, subscript F means the motion information of the follower and L denotes the information of the leader’s motion. ρ denotes the relative distance, λ and γ represent the LOS angle and the flight path angle, respectively. Furthermore, V represents the velocity of the vehicles. The I-frame is an inertial reference frame and all information of the motions of vehicles is described with respect to the inertia reference frame.
From the formation guidance geometry shown in Fig. 1 , the relative distance of the follower with respect to the leader and LOS angle are given by
Lager Image
Lager Image
Lager Image
Formation guidance geometry.
where ρ X =ρcos λ, ρ Y =ρsin λ.
Then, the first and second time derivatives of the relative distance and the LOS angle are obtained as
Lager Image
Lager Image
Lager Image
Lager Image
where α FT , α FN are the follower’s acceleration and α LT , α LN are the acceleration of the leader applied tangential and normal to the velocity of the each vehicle shown in Fig. 1 , respectively.
Here γ L can be obtained by applying simple algebra to Eqs. (3) and (4):
Lager Image
Therefore, the flight path angle of the leader can be calculated using the relative distance, LOS angle, and the velocity of the follower.
The equations of relative motion of the follower with respect to the leader can be described as
x˙=f c (x, u):
Lager Image
where
Lager Image
Lager Image
The discrete-time versions of Eq. (8) are considered in implementing NMPC,
Lager Image
where x(i)∈R 4 denotes the state vector at time step i, u (i)∈R 2 denotes the control input vector.
Discrete-time equations of motion are represented as follows;
Lager Image
where ΔT represents sampling time.
To guide and keep the formation, the proper desired output should be determined. Let us define the output and desired output, respectively, as follows
Lager Image
Lager Image
where θ=γ L ?λ. This desired output can be determined according to the formation shape, and vehicles can make and maintain formation when the output of the follower tracks the desired output.
An NMPC algorithm calculates a control sequence to optimize the future system behavior at each event (x, k) (i.e. for initial state x at time k). The initial values of the state vector of each event are defined as
Lager Image
- 2.2 Problem formulation
The optimal control problem considered in this paper is as follows.
NMPCF: Find a control input sequence u s which minimizes
Lager Image
subject to Eq. (10), with the input constraints of
Lager Image
where u s ={u(k), u(k+1), …, u(k+N?1)}, y?=y d ?y, u max =2g, g is gravity (9.81 m/sec), and S j (x(i)) denotes state inequality constraints.
In this paper, collision avoidance is considered as the state constraints. We set the state constraints as follows
Lager Image
where R c denotes the radius of collision, and ρ j (i) represents the relative distance between our own vehicle and the j-th wingman at time step i. When the distance between the UAVs is less than or equal to R c , the danger of collision exists.
- 2.3 Open-loop optimization for NMPCF
It is difficult or impossible to find the analytic solution of an NMPC problem. Therefore, numerical optimization is necessary and we have considered the approach of Sutton and Bitmead (2000) to solve the NMPC problem.
As shown in Bryson and Ho (1975), an augmented cost function of Eq. (16) can be derived using the vector Lagrange Multiplier sequence {λ k ∈R 4 : k=1, …, N} and integral penalty functions:
Lager Image
where n s denotes the number of state constraints, μ j is a constant weighting factor of the j-th state constraint, and
Lager Image
In this paper, input constraints (input saturation) are addressed by bounding the input with the maximum control value when computing the new control input sequence during the optimization process by setting
Lager Image
where
Lager Image
The Hamiltonian function is defined as
Lager Image
Then the variations of the augmented cost function is obtained as
Lager Image
By defining the Lagrange multiplier as
Lager Image
Lager Image
we can simplify the variations of the augmented cost function dJ’ as
Lager Image
and we have
Lager Image
where
Lager Image
At each time step, the online optimization process at a given initial state is Kim et al. (2002):
Lager Image
To reduce computation time, the initial control input sequence at each time step is taken as {u k+1 , …, u k+N?1' u k+N?1 }which is obtained in the previous time step.
3. Modification of NMPC Formation Guidance Law
As shown in Eqs. (8) and (10), we must know the normal and tangential acceleration intent of the leader along the future time horizon to predict the relative motion of the follower. If the follower does not know the acceleration intent of the leader and other followers, i.e., data communication between the vehicles is impossible, the performance of the proposed NMPC degrades significantly. In this section, we propose a modification to the proposed NMPC framework to overcome this problem. The proposed modification uses only the LOS angle, the relative distance, and the motion of the follower. Therefore, data communication between UAVs is unnecessary to guide and maintain formation with the proposed modification.
- 3.1 Modification procedure
Now, let us describe the modification of the formation guidance using the NMPC procedure using the above approach.
Define a as
Lager Image
where χ 3 (k), χ 4 (k) are the initial relative distance and LOS angle rate of the follower at time k, respectively. χ + 3 (k), χ + 4 (k) denote the k-th optimal relative distance and LOS angle rate resulting at (k?1)-th optimization step, where k=0 at the first optimization step. It is assumed that a(0)=[0 0] T for simplicity.
We define a L (k) as follows:
Lager Image
Lager Image
Next, we modify the discrete dynamic equation by substituting a L (k) for the leader’s acceleration intent at the k-th optimization step,
Lager Image
Then, the NMPCF problem is modified as follows:
NMPCF-M: Find control input sequence u s which minimizes
Lager Image
Lager Image
Lager Image
subject to the modified discrete dynamic equation, with the same input and state constraints as NMPCF ones.
Note that any information of the leader’s motion is not used in the proposed modification. Therefore, the communication between the vehicles is unnecessary in the modification for formation guidance.
- 3.2 Stability of the modified NMPC law
In this section, we mention the stability of the error dynamics between the NMPC for formation and the modification. To refer to this stability, it is assumed that the acceleration of the leader is bounded and converges to a constant. As usual, the acceleration of the leader and other vehicles are assumed to be bounded in magnitude. Therefore, the assumptions are reasonable.
From Eqs. (8), (29), and (30), we have
Lager Image
For a stationary solution dJ’=0 for arbitrary integer k; this can happen only if
Lager Image
Then, the optimal command can be obtained
Lager Image
Note that the matrix R should be nonsingular for the existence of solution.
From Eqs. (8), (12), (25), and (26), it is clear that the performance of the formation guidance depends on the accuracy of the estimation and prediction of the leader’s acceleration. Therefore, the solution of the modified NMPC will differ from that of full-information NMPC. However, the difference will be continuously reduced if the acceleration of the leader is bounded and converges to a constant.
The desired output for the optimal formation guidance represents the desired position of the follower about the leader shown in Eq. (14). The cost function of the two proposed NMPC for formation is defined to guide and maintain the formation and to minimize the guidance command. At every k-th optimization step, the difference of the desired positions of the two NMPC for formation is bounded and reduced to zero due to the assumption that the acceleration of the vehicles is bounded and converges to a constant.
The boundedness of the error dynamic system is deduced from the above facts. Therefore, the error dynamic system between the modified NMPC and the full-information NMPC for formation is stable. Moreover the modified formation guidance system is stable when the proposed formation guidance system using NMPC is stable.
4. Numerical Example
In this section, the modifications for formation are applied to three missions described in Table 1 for verification. The desired output is represented in this table, time is zero when the optimization procedure is started and F1, F2 denote the follower 1 and the follower 2, respectively. If UAVs achieve three missions, UAVs change the formation pattern. The performance of the proposed modification is analyzed from three points of view: (i) performance depredation from the lack of the acceleration information of others; (ii) performance analysis of the proposed modification and NMPC for formation; (iii) boundedness of the error dynamics output mentioned in Section 3.2.
Leader’s acceleration vector is as follows:
Lager Image
This leader’s acceleration pattern is depicted in Fig. 2 . The acceleration of the leader is oscillated, but the amplitude of
Mission table for UAVs in the L-frameUAVs: unmanned aerial vehicles.
Lager Image
Mission table for UAVs in the L-frame UAVs: unmanned aerial vehicles.
Lager Image
Leader’s acceleration profile.
Initial state of each UAVUAVs: unmanned aerial vehicles.
Lager Image
Initial state of each UAV UAVs: unmanned aerial vehicles.
Weighting factors
Lager Image
Weighting factors
oscillation decreases until the leader’s acceleration converges to a constant. This satisfies the assumption that the leader’s acceleration is bounded and converges to a constant. The initial states of the UAVs, which are described by the velocity vectors and positions of each UAV in the inertial reference frame, are given in Table 2 .
The NMPC algorithm could fail to achieve formation due to a finite horizon and limitations of the input/state. In that case, the command input is likely to be saturated because it try to make formation as much as possible at a given future horizon. To avoid this problem, the variable weighting factor is taken in numerical example as in Table 3 . In Table 3 , ρ(k) is the initial relative distance at the k-th optimization step.
- 4.1 Performance degradation
The modification of NMPC for formation does not use the leader’s acceleration. Therefore, the only performance degradation of NMPC for formation from the lack of leader’s acceleration is addressed in this section.
If there is the communication or measurement failure, it is assumed that the acceleration of the leader is zero. Figure 3 shows the history of the error between the desired output
Lager Image
Output errors of nonlinear model predictive control for formation and the modification.
for formation and the output of NMPC for formation. All the followers display the output error in NMPC for formation, because they do not know the acceleration vector of the leader. NMPC compensates for the missed distance to a certain extent.
- 4.2 Performance analysis
In this paper, the radius of collision is 30 m. The UAVs can form the formation and avoid collision when the terminal relative distance errors are close to zero and the minimum distance from each other satisfies the state constraints for collision avoidance. The results of optimization are represented in Table 4 and Figs. 4 and 5 . As shown in the optimal results, two methods can make formation and avoid collision for every mission and the performance of the modification is similar to that of the formation guidance using NMPC with full information. The optimal commands of NMPC for formation and the modification are different at the beginning but this difference diminishes by 40 seconds.
- 4.3 Boundedness of the error dynamics output
To check the stability of the error dynamics represented in Section 3.2, we compare the outputs of the modification
Terminal relative distances and the minimum distance between UAVs
Lager Image
Terminal relative distances and the minimum distance between UAVs
Lager Image
The output error history resulting from the lack of leader’s acceleration.
Lager Image
Optimal acceleration history of the follower.
Lager Image
Output error history.
and the formation guidance using NMPC. As shown in Fig.6 , the output error between the two approaches oscillates at the beginning but this error remains bounded. Moreover, this error decreases and goes to zero.
5. Conclusions
In this paper, an online optimal control method for formation of multiple UAVs has been proposed. The main idea of this paper is to solve the optimal formation guidance problem with collision avoidance using LOS information, the relative distance, and own motion information for the online optimization. Under the assumption that each vehicle exchanges all estimated states and acceleration with each other every moment, the formation guidance using NMPC is proposed firstly. If this assumption holds, the solution of NMPCF can be applied to formation guidance with a collision avoidance problem in real time. However, there are many operations in which this assumption is inappropriate due to communication failure or delay. The modification of NMPC for formation guidance has been constructed and the stability of error dynamics between outputs of the formation and the modification is derived. Each follower uses the relative distance, LOS angle, and own motion information to solve the optimal formation problem in this modification. The modification is successfully tested on a three-vehicle formation and changing formation pattern. The performance of the modification has been validated by comparing the optimization results of the full-information NMPC for formation and those of the modified NMPC. The method suggested in this paper can be easily applied to various problems related to formation flight of multiple UAVs. Especially, the proposed approach will be helpful when a minimum communication profile is required between the formation vehicles and there is the danger of collision.
Acknowledgements
This work was supported by Flight Vehicle Research Center at Seoul National University under the sponsorship of Agency for Defense Development.
References
Bhattacharya R , Balas G. J , Kaya A , Packard A 2001 Nonlinear receding horizon control of F-16 aircraft Proceedings of the American Control Conference ArlingtonVA 518 - 522
Bryson A. E , Ho Y. C 1975 Applied Optimal Control:Optimization Estimation and Control. Hemisphere Publishing Corporation. Washington DC: 212 - 245
Das A. K , Fierro R , Kumar V , Ostrowski J. P , Spletzer J , Taylor C. J 2002 A vision-based formation controlframework. IEEE Transactions on Robotics and Automation 18 813 - 825    DOI : 10.1109/TRA.2002.803463
Kim H. J , Shim D. H , Sastry S 2002 Nonlinearmodel predictive tracking control for rotorcraft-basedunmanned aerial vehicles Proceedings of the AmericanControl Conference Anchorage AK. 3576 - 3581
Kouvaritakis B , Cannon M Institution of ElectricalEngineers. 2001 Nonlinear Predictive Control: Theory andPractice. Institution of Electrical Engineers. London: 3 - 32
Mayne D. Q , Rawlings J. B , Rao C. V , Scokaert P.O. M 2000 Constrained model predictive control: stability and optimality. Automatica 36 789 - 814    DOI : 10.1016/S0005-1098(99)00214-9
Michalska H , Mayne D. Q 1993 Robust receding horizon control of constrained nonlinear systems. IEEE Transactions on Automatic Control 38 1623 - 1633    DOI : 10.1109/9.262032
Pachter M , D’Azzo J. J , Proud A. W 2001 Tight formation flight control. Journal of Guidance Control andDynamics 24 246 - 254    DOI : 10.2514/2.4735
Ryoo C. K , Kim Y. H , Tahk M. J 2005 An optimal formation guidance law for multiple unmanned aerial vehicles. 24th IASTED International Conference on ModelingIdentification and Control Innsbruck 445 - 450
Sattigeri R , Calise A. J , Evers J. H 2004 An adaptive vision-based approach to decentralized formation control. AIAA Guidance Navigation and Control Conference Providence RI. 2575 - 2798
Sutton G. J , In F. Allgower and A. Zheng eds. , Bitmead R. R , In F. Allgower and A. Zheng eds. 2000 Computational implementation of NMPC to nonlinear submarine. Birkhauser Verlag. Boston MA In F. Allgower and A. Zheng eds. Nonlinear Model Predictive Control Vol 26. 461 - 471
Tahk M. J , Park C. S , Ryoo C. K 2005 Line-of-sight guidance laws for formation flight. Journal of Guidance Control and Dynamics 28 708 - 716    DOI : 10.2514/1.9605
Verma A , Wu C. N , Castelli V 2003 Autonomous command and control system for UAV formation. AIAA Atmospheric Flight Mechanics Conference Austin TX