Formation Flight and Collision Avoidance for Multiple UAVs using Concept of Elastic Weighting Factor

  • cc icon
  • ABSTRACT

    In this paper, the guidance law for formation flight and collision avoidance of multiple Unmanned Aerial Vehicle (UAV)s is proposed. To construct the physically comprehensible guidance law for formation flight, the virtual structure approach is used. To develop a guidance law for collision avoidance considering both other UAVs and unknown static obstacles, a geometric approach using information such as a relative position vector is utilized. Through the Lyapunov theorem, the stability of the proposed guidance law is proved. To combine guidance commands, the concept of the elastic weighting factor inspired by the elastic behavior of shape memory polymer, which tends to regain its original shape after deformation, is introduced. By using the concept of elastic weighting factor, multiple UAVs are able to cope actively with the situation of a collision between both UAVs and static obstacles during the formation flight. To verify the performance of the proposed method, numerical simulations are performed.


  • KEYWORD

    Unmmaned Aerial Vehicle , Formation Flight , Collision Avoidance , Elastic Weighting Factor

  • 1. Introduction

    Recently, the use of UAVs has been expanded in both military applications and civil operations [1-3]. When a UAV performs a mission such as surveillance, it is more advantageous to utilize multiple UAVs rather than a single UAV [4]. The task can be performed in a group of multiple UAVs, which can deal with the failure due to the loss of a UAV from an enemy attack or hardware/software fault. In addition, the range of operations can be extended.

    To make UAVs move in formation, it is required that a proper method for formation flight which has physical reasonability be proposed and the proposed method should have a definite performance in terms of exactness of formation configuration. Formation flight of UAVs can be accomplished by several methods, which include the leader-follower approach, virtual structure approach, behavioral approach, and so on [5]. Among those methods, the virtual structure approach is more physically comprehensible compared to the others and can easily construct a formation shape.

    To make UAVs cope with collision threats instantly, it is required that a proper method for collision avoidance which is simple and effective be proposed. Collision avoidance for a UAV can be accomplished by various methods such as the potential field method, geometric approach, grid based method, generic algorithm, and so on [6-7]. Among those methods, the potential field method is quite attractive in that it is easy to understand intuitively and its potential function, which is used to generate commands, can be made freely according to specific objectives. The geometric approach is also easy to understand and can be used simply.

    For the operation of multiple UAVs, it is important to consider both formation flight and collision avoidance. In Ref. [8], formation flight and collision avoidance were considered separately and changed the modes according to the flight situation. In Refs. [9] and [10], formation flight and collision avoidance were considered at the same time with weighted sum of certain functions. Those works [8-10] lack effort for considering formation flight and collision avoidance simultaneously. Especially, in Refs. [9] and [10], weighting values used in the consideration were defined as constants, which may lead to inefficiency in coping with unexpected collision threats. Also, there is no convincing explanation for the reason why the weighting values were chosen. Thus, it is strongly required to develop the proper methods for formation flight and collision avoidance regarding multiple UAVs and connect those methods with an appropriate weighting value. The value should be defined reasonably and vary with the situation continuously.

    In this thesis, a physically appropriate method for formation flight based on the decentralized virtual structure approach and a simple method for collision avoidance using the geometric approach are proposed separately. Both methods are connected by a concept of elastic weighting factor that is inspired by the behavior of the material which exists in nature. Using the concept, UAVs can deal with the collision threats including the other UAVs in formation and unknown obstacles during flight simultaneously.

    This paper is organized as follows. Section 2 proposes the formation flight method based on the virtual structure approach. The stability of the proposed method is analyzed using the Lyapunov Stability Theorem. Section 3 gives the collision avoidance method based on the geometric approach, and stability analysis on the proposed method is also performed using the Lyapunov Stability Theorem. Section 4 introduces the concept of elastic weighting factor for the integration of heading commands. Section 5 provides numerical simulation results in which a performance of the proposed method is verified. Finally, section 6 is devoted to the summary of the main results and the future work.

    2. Formation Flight

    A formation flight method proposed in this section is based on the following assumptions.

    Assumption 2.1. There is a certain range in which UAVs can communicate.

    Assumption 2.2. UAVs can obtain information which includes the position and velocity of other UAVs within the range.

       2.1 Coordinate System and Kinematics for Guidance

    All geometric information used in this study is based on a two dimensional cartesian coordinate system. Two coordinate frames are considered; the inertial coordinate frame and body fixed coordinate frame. Position information is expressed in terms of the inertial coordinate frame. Heading angle and speed of UAVs are represented in terms of body fixed frame. Let us consider a position of a UAV expressed as follows:

    image

    Note from Eq. (1) that the position is expressed in the inertial coordinate frame only, and therefore subscript I will be omitted in the remaining sections for simplicity. To visualize the coordinate system as shown in Fig. 1, let us consider the flight situation of a single UAV with the following velocity command:

    image

    where θc and Vc denote heading angle command and speed command of a UAV, respectively. Let us denote

    image

    as the current position vector of UAV, and θ and V the current heading angle and velocity, respectively. According to the given guidance commands, a future position of UAV can be obtained from the following kinematics:

    image
    image

    where Vc is bounded between the minimum speed and maximum speed of a UAV as follows:

    image

       2.2 Heading Command and Speed Command

    Formation flight is performed in a way that each UAV pursues its formation position that is defined through the virtual structure. To construct the virtual structure, let us define the geometric center of UAVs as follows [11]:

    image

    where

    image

    and

    image

    denote the position vector of the geometric center and a ith UAV, respectively, and n represents the total number of UAVs in group. Using PGC, the virtual structure can be made with a proper geometric condition. The formation position of each UAV can be generated in terms of PGC according to the number of UAVs or a flight situation. For example, when the number of UAVs in group is 3, that is n=3, a triangular shaped virtual structure and the formation position can be made as shown in Fig. 2. The whole virtual structure moves towards the goal point, and the kinematics of the formation position can also be written as:

    image
    image

    where Vref is a speed of the formation position and its value should be in the range between Vmin and Vmax, and θr is an angle between the formation position and goal position. To consider a formation error between the UAV and the formation position, a look-ahead factor, K is introduced. Considering K, the UAV watches the look-ahead position and generates the heading commands using the relative position between itself and the position that reflects the movement of the formation position as shown in Fig. 3.

    Using the look-ahead factor K, the heading vector command of each UAV can be generated as follows:

    image

    Where r is a direction vector from the UAV to the lookahead position, and ?·? represents the Euclidean norm of the vector p=(x, y) on

    image
    image

    From Eq. (9), the heading command can be expressed as

    follows.

    image

    where (rx, ry) are the components of the vector r.

       2.3 Stability Analysis and Speed command

    2.3.1 Stability Analysis

    To guarantee that a position of a UAV converges to the formation position with the heading command defined in Eq. (11), a stability analysis using the Lyapunov stability theorem is performed and the detailed procedure is explained in Ref. [12].

    From Ref. [12], a condition for the time derivative of the Lyapunov candidate function to be negative can be obtained as follows.

    image

    Eq. (12) is an important condition for deciding the lookahead factor and Vc of a UAV, which will be analyzed in the following section.

    Note from Ref. [12] that the time derivative of the Lyapunov candidate function has a negative value except the case when the position of a UAV and the formation position are coincident. This means that the value of the Lyapunov candidate function is decreasing and converges to zero asymptotically. As the Lyapunov candidate function is defined as a distance from the UAV position to formation position, it means that the distance is decreasing and become zero eventually.

    2.3.2 Look-Ahead Factor and Speed Command

    To make the heading command appropriate for the formation flight and generate a proper speed command, Eq. (12) should be considered. Two unknown variables, K and Vc, have to be confirmed to generate the heading command in Eq. (9). The speed command should be within a certain bound according to the specifications of a UAV as follows:

    image

    Using Eq. (12), the constraint condition on the speed command can be expressed as follows:

    image

    With the properly pre-defined constant value of K, the flight situation of the UAV can be divided into two main cases using Eq. (14) as follows:

    Case 1. For the case that Eq. (14) is satisfied. : A UAV is in the stable region where the convergence to the formation position is assured.

    Case 2. For the case that Eq. (14) is not satisfied. : A UAV is outside the stable region.

    The descriptions of each case are shown well in Fig. 4.

    Case 2 can be categorized again into two sub-cases.

    Case. 2.1 Pursuing case

    image

    : As a projected position of a UAV is farther from the goal point than the formation position, the UAV needs to pursue the formation position.

    Case. 2.2 Pursued case

    image

    : As a projected position of a UAV is closer from the goal point than the formation position, the UAV needs to be pursued by the formation position.

    In Fig. 4, d1 is a distance between the formation position and goal position, d2 is a distance between a projected position of the UAV which is the foot of perpendicular drawn from the UAV on the reference trajectory of the formation position and the goal position, and dform-ver represents a distance from the formation position to the projected position of the UAV.

    Variables K and Vc corresponding to the above cases can be decided as follows:

    Case 1:

    image

    Case 2:

    image

    where dver, dform-ver and e are defined in Fig. 4, and e≪1.

    With Eq. (9), Eq. (17) and Eq. (18), guidance commands for formation flight including the heading command and the speed command are generated. As case 2 is always turned into case 1 eventually, which means that the UAV moves towards the stable region and enters the region in the end, the convergence of the UAV to the formation position is assured in all flight situations.

    3. Collision Avoidance

       3.1 Heading command

    The collision avoidance method proposed in this section is based on the following assumptions.

    Assumption 3.1. Assumptions of section 2 are still valid.

    Assumption 3.2. All obstacles are static.

    Assumption 3.3. There exists a ‘safety range’ and ‘sensing range’ between the UAV and static obstacle.

    Assumption 3.4. There exists a ‘safety range’ and ‘sensing range’ between the UAV and other UAVs.

    The safety range means a minimum distance which a UAV should have for the collision avoidance of the threat. Also, the sensing range means a distance in which the UAV recognizes a threat.

    The proposed method in this section deals with the procedures of generating the command for the collision avoidance of a single threat. And the method will be extended to multiple threats with a proper weighting value in section 4.

    The direction of the relative position vector can be used to increase a distance between the UAV and the threat. Another vector is also considered by defining sub-vectors which are perpendicular to the relative position vector as shown in Fig. 5. In Fig. 5, PU-T is a relative position vector from the collision threat to the UAV and subscript U and T are the UAV and the collision threat, respectively. Psub1 and Psub2 denote sub-vectors which are perpendicular to PU-T in +90° and -90°, respectively. And Pcmd1 and Pcmd2 are heading vector commands which give directions for the UAV to move, which are obtained by adding Psub1 or Psub2 to PU-T' respectively. The collision threat can be both another UAV and an obstacle. The goal position is a formation position of the UAV when the collision threat is another UAV in the group. On the other hand, if the collision threat is an obstacle, the goal position is a final destination or way point of the UAV.

    The heading command can be generated by using vectors which are defined in Fig. 4 as follows:

    image

    In Eq. (19), Pcmd1 and Pcmd2 can be written as follows:

    image

    In Eq. (20), i denotes the mode of the sub-vector, and decides the direction, i.e., +90° for i=1 and -90° for i=2. And PU-T and Psubi and be written as follows:

    image
    image

    In Eq. (22), Ti denotes a rotation matrix expressed as:

    image

    Using Eq. (21) and Eq. (23), Pcmd can be rewritten as follows:

    image

    Using Eq. (27), the heading vector which the UAV should follow can be written as:

    image

    Finally, the heading command can be generated by using Eq. (25) as:

    image

    where rc,x and rc,y denote a x-component and a y-component of the heading vector, rc, respectively.

    A stability analysis for the proposed heading commands is performed using the Lyapunov stability theorem. The analysis assures that the UAV always moves in the direction away from the threat and avoids the collision threat surely whether it is another UAV or a static obstacle. Ref. [12] contains a detailed procedure of the analysis.

    4. Combined Guidance Law for Formation Flight and Collision Avoidance

       4.1 Inspiration and Concept

    In general, the virtual structure approach deals with a fixed shape of formation. In other words, the structure is notionally treated as a rigid body. In this type of structure, the group of UAVs cannot react effectively to unexpected situations including a collision. This problem can be solved by giving the elastic property to the structure using the Elastic Weighting Factor (EWF). A main idea of the EWF is to provide an elastic property to the virtual structure as shown in Fig. 6. Using this concept, the structure of the formation is deformable during flight, and therefore UAVs can easily cope with the collision threat.

    Among many materials in the real world, SMP (Shape Memory Polymer) has properties of the deformable formation structure. The SMP has the shape memory effect and the elastic behavior which can be applied to the structure. Depending on the external stimulus like temperature, the shape or length of the SMP is variable. When the external stimulus returns to the certain condition, the SMP recovers its permanent or original shape. Using this property, the formation structure can be deformed considering an effect from the collision threat and return to its original state. The formation structure can have a soft phase or a state like a rubber band for the collision avoidance as well as a hard phase or a rigid state for maintaining the formation structure.

    When adapting the SMP to the formation structure, the elastic modulus of the SMP corresponds to the material property of the structure and the temperature which is an external stimulus corresponds to a distance from a UAV to the collision threat. In other words, the structure’s property varies according to an interaction between the UAV and all the threats within the sensing range in which the UAV recognizes the risk of collision.

       4.2. Shape Memory Polymer Modeling

    In this section, the model of SMP is represented. The elastic weighting factor, E, is a value that describes the elasticity of the virtual structure and contributes to combining commands of formation flight and collision avoidance. Based on Ref. [13], E can be defined mathematically as follows

    Definition 4.1 (Elastic Weighting Factor, E) E is a value such that

    image

    where

    image

    Note that subscript s represents the sensing range where a transition from a rigid to elastic state starts, and subscript f represents the safety range where the transition terminates, subscript g represents the point where an elastic property becomes predominant over a rigid property, and T represents the difference between dsense and dU-T.

    E decreases as the distance is getting closer, which means that the elastic modulus of the structure decreases. This makes the structure more flexible. On the other hand, as the distance becomes farther, the structure becomes rigid with increase in E.

       4.3. Combination of Heading Commands

    To adapt E to the combination of heading commands for formation flight and collision avoidance, let us redefine E for ith UAV with considering all the threats.

    Definition 4.2 (E for ith UAV) The elastic weighting factor for the ith UAV which is in danger of collision with several UAVs and static obstacles is defined as:

    image

    where the value of p represents the number of all UAVs within the range in which communication is possible. The value of q is the number of static obstacles detected by ith UAV, and Ej and ek are portions of Euav_i which are related to the jth UAV and the kth obstacle within the sensing range, respectively, as follows:

    image

    In Eq. (30), dU-Uj is a distance from the ith UAV to the jth UAV and dU-Ok is a distance from the ith UAV to the kth obstacle. Using definition 2, the heading vector which the ith UAV should have can be written as follows:

    image

    In Eq. (31), rform and rCA are the heading vector commands for the formation flight and the collision avoidance, respectively, i.e., Eq. (9) and Eq. (25). Using Eq. (31), the combined heading command for the ith UAV can be written as:

    image

    where rc_i,x and rc_i,y represent the x-component and the y-component of rc_i' respectively. Since Eq. (31) considers all the collision threats within the sensing range, the UAV can always consider the multiple collision threats during the formation flight. Especially, when UAVs fly in an unknown region, they can cope with the abrupt obstacles continuously and actively using Eq. (29).

    5. Numerical Simulation

       5.1 Simulation Environment

    The two-dimensional point mass model of UAV is used in the simulations. To consider the time delay of UAV dynamics and autopilot, heading angle θ and speed V are modeled as follows:

    image

    where τv and τθ represent time constants of the speed and the heading angle, respectively.

    To check the performance of the proposed method, a situation of collision avoidance during the formation flight is simulated. That is, UAVs encounter unknown static obstacles during the formation flight. It is required for UAVs to avoid the collision threats by deforming the formation. After the avoidance is finished, UAVs have to recover their formation.

    The parameters and initial conditions of the simulation environment are summarized in Table 1.

       5.2 Simulation Result

    Figure 7 shows the trajectories of each UAV. It can be seen that the collision avoidance during the formation flight is performed successfully. The elastic behavior of the formation structure is shown in Fig. 8. When UAVs recognize the collision threats, the formation structure varies elastically so that UAVs can avoid the threats effectively, and then recover its original formation after the avoidance. In Fig. 9, fluctuations are observed in the speed of UAVs,

    because UAVs repeatedly come in and out of the region where the stability is assured as the collision avoidance and the formation flight are considered simultaneously. Heading angles vary quite smoothly as shown in Fig. 9. In Fig. 10, it also can be seen that the concept of elastic weighting factor is used well in the presence of unknown obstacles. In addition, elastic weighting factors change continuously considering both other UAVs and unknown obstacles. In Fig. 11, all UAVs converge to their formation position after the avoidance.

    To see the performance of collision avoidance with threats

    including other UAVs and obstacles, the minimum distances among all UAVs are summarized in Table 2 and minimum distances from each UAV to the unknown obstacles are summarized in Table 3. As it can be seen in Tables 2 and 3, all UAVs maintain their distance farther than the safety range from other UAVs and obstacles. Thus, it can be said that collision avoidance during the formation flight is well performed.

    6. Conclusion

    Guidance laws for decentralized formation flight and collision avoidance are proposed. The stability of the each guidance law is proved using the Lyapunov Stability Theorem. By introducing the concept of elastic weighting factor, heading angle commands of formation flight and collision avoidance are integrated. The integrated guidance law makes UAVs perform formation flight and collision avoidance simultaneously. It is shown that UAVs can cope with the collision threats including other UAVs in the formation and unknown obstacles. The guidance command

    for UAVs can be generated by a simple calculation at every moment, and therefore the proposed method can be utilized for real time applications.

  • 1. 2000 Development and Operation of UAVs for Military and Civil Applications, RTO Education NOTE google
  • 2. Sarris Z. 2001 “Survey of UAV Applications in Civil Markets(June 2001)” [the 9th IEEE Mediterranean Conference on Control and Automation] google
  • 3. Srinivasan S., Latchman H., Shea J., Wong T., McNair J. 2004 “Airborne Traffic Surveillance Systems-Video Surveillance of Highway Traffic” [Proceedings of the ACM 2nd International Workshop on Video Surveillance & Sensor Networks] google
  • 4. Booth C.E. 2009 Surveillance Using Multiple Unmanned Aerial Vehicles google
  • 5. Scharf D. P., Hadaegh F. Y., Ploen S. R. 2004 “A Survey of Spacecraft Formation Flying Guidance and Control(Part II) : Control” [American Control Conference] P.2976-2985 google
  • 6. Gardiner B., Ahmad W., Cooper T., Haveard M., Holt J., Biaz S. 2011 “Collision Avoidance Techniques for Unmanned Aerial Vehicles Technical Report #CSSE11-01”, Technical Report google
  • 7. Ruchti J., Senkbeil R., Carroll J., Dikinson J., Holt J., Biaz S. 2011 “UAV Collision Avoidance Using Artificial Potential Fields Technical Report #CSSE11-03,” Technical Report google
  • 8. Wang X., Yadav V., Balakrishnan S. N. 2007 “Cooperative UAV Formation Flying with Obstacle/Collision Avoidance” [IEEE Transactions on Control Systems Technology] Vol.15 P.672-679 google doi
  • 9. Zhou C., Lei M., Zhou S., Zhang W. 2011 “Collisionfree UAV Formation Flight Control based on Nonlinear MPC” [Electronics, Communications and Control (ICECC) International Conference] google
  • 10. Ricardo B., Mariam F., Joao S., Anouck G. 2011 “Formation Control with Collision Avoidance” [IEEE Conference on Decision and Control and European Control Conference] google
  • 11. Lee J. 2009 Design of UAV Formation Flight Controller based on Formation Geometry Center Concept google
  • 12. Kang S. 2013 Formation Flight and Collision Avoidance for multiple UAVs using Concept of Elastic Weighting google
  • 13. Zhou B., Lin Y., Lan X., Leng J. S., Yoon S. H. 2009 “A Glass Transition Model For Shape Memory Polymer And Its Composite” [International Journal of Modern Physics B] Vol.23 P.1248-1253 google doi
  • [Fig. 1.] Coordinate system
    Coordinate system
  • [Fig. 2.] Shape of virtual structure and formation positions for n=3
    Shape of virtual structure and formation positions for n=3
  • [Fig. 3.] Heading command defined by the position ahead of current formation position
    Heading command defined by the position ahead of current formation position
  • [Fig. 4.] Flight situations of a UAV
    Flight situations of a UAV
  • [Fig. 5.] Collision avoidance scheme
    Collision avoidance scheme
  • [Table 1.] Parameters and initial values
    Parameters and initial values
  • [Fig. 6.] Conceptual diagram of the formation structure with elasticity.
    Conceptual diagram of the formation structure with elasticity.
  • [Fig. 7.] Trajectories of UAVs.
    Trajectories of UAVs.
  • [Fig. 8.] Elastic behavior of the formation structure.
    Elastic behavior of the formation structure.
  • [Table 2.] The minimum distances among all UAVs
    The minimum distances among all UAVs
  • [Fig. 9.] Speed and heading angle histories of UAVs
    Speed and heading angle histories of UAVs
  • [Fig. 10.] Elastic weighting factor histories of UAVs
    Elastic weighting factor histories of UAVs
  • [Table 3.] The minimum distances from each UAV to unknown obstacles
    The minimum distances from each UAV to unknown obstacles
  • [Fig. 11.] Distance from each UAV to its formation position.
    Distance from each UAV to its formation position.