Dynamic Collision Avoidance Strategy for Unmanned Aerial Vehicles Formation Flight

Abstract

Unmanned aerial vehicles (UAV) have been widely used in many fields. UAV formation flight can complete more assignments than single UAV. Collision avoidance is an important part of UAV formation flight. In this paper, we put forward a three-dimensional method of dynamic collision avoidance for UAV formation flight based on the theory of velocity obstacle. The collection of all possible accelerations of the UAV can be obtained by the input of UAV. Considering that the relative velocity between the UAV and obstacle must be out of the collision cone, we can obtain the collection of feasible accelerations next moment. Then we choose the acceleration which is able to let the UAV closest to the target next moment in the collection as the real acceleration. The maximum and minimum velocity should also be set up. Each UAV can determine the best acceleration next time for itself. In addition to formation keeping, this paper also presents how to split the formation on the basis of the direction of each UAV. Numerical simulation is used to test the performance of this method at the end of this paper.

1 Introduction

The technology of single unmanned aerial vehicle (UAV) has become relatively mature after decades of development. It plays an important role in military and civilian affairs, such as fire monitoring, search and rescue and reconnaissance. The formation flight can accomplish more tasks than single UAV. Cooperative operation of multi-UAVs can not only carry equipment separately to complete the transportation of larger equipment, but also fulfil the missions such as high-precision positioning, 3D modelling and multiangular imaging. Formation flight can expand the scope of reconnaissance, monitoring and search in the case of aerial photography and aerial monitoring. In addition, the formation design can make the impact of wreck of single UAV reduce to the bottom, which greatly improves the reliability.

UAVs must have the ability to avoid obstacles for almost any tasks. Static obstacles include trees, buildings and so on. Dynamic obstacles include birds, other airplanes, kites and so on. At low altitude, humans and animals may become obstacles. In order to complete missions successfully, UAVs should be able to discover obstacles and then avoid collision. Especially in civilian affairs, safety is the first.

Nowadays, there are already many researches on collision avoidance for single UAV and collision avoidance for UAV formation flight in static environment. For single UAV, conventional proportional navigation guidance method [1], reference point guidance [2], velocity obstacle [3] and some other methods [4, 5] are used for collision avoidance. For UAV formation flight, most collision avoidance strategy are for static obstacles. A* algorithm and model predictive control are widely used in this situation [6, 7].

However, there are not yet enough methods of collision avoidance for UAV formation flight in dynamic environment. Recently, Seo et al. put forward a strategy of collision avoidance for UAVs formation flight based on geometry [8]. This strategy only changes the velocity direction of UAV and doesn’t change the magnitude of velocity, which obviously cannot achieve optimal results. In addition, while avoiding the obstacle, UAVs doesn’t consider the target. It is necessary to judge whether to complete obstacle avoidance all the time.

Velocity obstacle was put forward early [9]. It is a very useful method and has been used widely in collision avoidance of robots. After decades of development, there are some variants, such as selective velocity obstacle (SVO) [10], reciprocal velocity obstacle [11] and probabilistic velocity obstacle (PVO) [12].

In this paper, we put forward a three-dimensional method of dynamic collision avoidance for UAV formation flight based on the theory of velocity obstacle and collision cone. In addition to formation keeping, this paper also presents how to split the formation on the basis of each UAV. Collision avoidance among UAVs in the same formation is also considered. Numerical simulation is used to test the performance of this method at the end of this paper.

2 Collision Avoidance Strategy

2.1 Velocity Obstacle

Velocity obstacle is generally two-dimensional in the past.

We can first consider a UAV and an obstacle in a 2-D plane. This method assumes that the UAV is a point and the obstacle is a sphere. In Fig. 1a, the position of UAV u is $\left[ {x_{\text{u}} ,y_{\text{u}} } \right]$ and the position of obstacle o1 is $\left[ {x_{\text{o1}} ,y_{\text{o1}} } \right]$. $v_{\text{o1}}$ is the velocity of obstacle and $v_{\text{u}}$ is the velocity of UAV. The relative velocity is $v_{\text{ou1}} (v_{\text{ou1}} = v_{\text{u}} - v_{\text{o1}} )$. CC_uo1 is the collision cone between UAV and obstacle, namely the shadow in Fig. 1a. We can define it mathematically:

Fig. 1

Collision cone between UAV and obstacle

$$ {\text{CC}}_{\text{ou1}} = \left\{ {v_{\text{ou1}} |\exists t > 0,\left( {x_{\text{u}} + v_{\text{ou1}} \vec{i} \times t,y_{\text{u}} + v_{\text{ou1}} \vec{j} \times t} \right) \in {\text{o}}} \right\} $$

(2.1)

where o is the obstacle, $\vec{i}$ and $\vec{j}$ are the unity vectors of x and y directions.

The Velocity Obstacle VO is defined as:

$$ {\text{VO}} = {\text{CC}}_{\text{ou1}} \oplus v_{\text{o1}} $$

(2.2)

where $\oplus$ is the Minkowski vector sum operator.

If there are more than one obstacle, VO can be defined as:

$$ {\text{VO}} = \bigcup\limits_{i = 1}^{n} {{\text{VO}}_{i} } $$

(2.3)

where n is the number of obstacles.

When it comes to three-dimensional, the definition is similar. As shown in Fig. 1b, the collision cone turns into three-dimensional and can be defined as:

$$ {\text{CC}}_{\text{ou1}} = \left\{ {v_{\text{ou1}} |\exists t > 0,\left( {x_{\text{u}} + v_{\text{ou1}} \vec{i} \times t,y_{\text{u}} + v_{\text{ou1}} \vec{j} \times t,z_{\text{u}} + v_{\text{ou1}} \vec{k} \times t} \right) \in o} \right\} $$

(2.4)

where o is the obstacle, $\vec{i}$, $\vec{j}$ and $\vec{k}$ are the unity vectors of x, y and z directions.

The Velocity Obstacle (VO) is defined in the same way:

$$ {\text{VO}}_{i} = {\text{CC}}_{{{\text{ou}}i}} \oplus v_{{{\text{o}}i}} ,\quad {\text{VO}} = \bigcup\limits_{i = 1}^{n} {{\text{VO}}_{i} } $$

(2.5)

where $v_{{{\text{o}}i}}$ is the velocity of the i-th obstacle and n is the number of obstacles.

When the velocity of UAV $v_{\text{u}}$ belongs to VO, it must satisfy the following formula:

$$ \vec{v}_{\text{ou}} \bullet \vec{l}_{\text{ou}} > 0\,{\text{and}}\,{\text{d}}\left( {\vec{v}_{\text{ou}} ,{\text{o}}} \right) < r_{\text{o}} $$

(2.6)

where $\vec{v}_{\text{ou}} = \vec{v}_{\text{u}} - \vec{v}_{\text{o}}$, $\vec{l}_{\text{ou}} = {\text{pos}}_{\text{o}} - {\text{pos}}_{\text{u}}$ (${\text{pos}}_{\text{o}} ,{\text{pos}}_{\text{u}}$ are the position of obstacle and UAV). $\bullet$ represents dot product between vectors. ${\text{d}}\left( {\vec{v}_{\text{ou}} ,{\text{o}}} \right)$ is the distance between the line of $\vec{v}_{\text{ou}}$ and the centre of obstacle. $r_{\text{o}}$ is the ratio of obstacle.

2.2 Acceleration Selection for Single UAV

Considering the input of the UAV, we can get the collection of all of the feasible acceleration which is recorded as $A_{\text{u}}$. For example, the input of quadrotor is the rotate speed of the four rotors and then the acceleration can be acquired through the dynamic model. The collection of velocity of UAV at $t + \Delta t$ can be acquired.

$$ V_{t + \Delta t} = v_{{{\text{u}}t}} \oplus (A_{\text{u}} \times \Delta t) $$

(2.7)

where $v_{{{\text{u}}t}}$ is the velocity of UAV at time t and $\Delta t$ represents a very short period of time.

In consideration of Velocity Obstacle and the limit of velocity, the feasible velocity collection at $t + \Delta t$ is $V_{{{\text{u}},t + \Delta t}}$:

$$ V_{{{\text{u}},t + \Delta t}} = \left\{ {v_{{{\text{u}},t + \Delta t}} |v_{{{\text{u}},t + \Delta t}} \in V_{t + \Delta t} ,v_{{{\text{u}},t + \Delta t}} \notin {\text{VO}},v_{ \hbox{min} } \le v_{{{\text{u}},t + \Delta t}} \le v_{ \hbox{max} } } \right\} $$

(2.8)

where $v_{ \hbox{min} }$ and $v_{ \hbox{max} }$ are the minimum and maximum value of velocity.

For each $v_{{{\text{u}},t + \Delta t}} \in V_{{{\text{u}},t + \Delta t}}$, we can get the correspondent position ($p_{{{\text{u}},t + \Delta t}}$) of UAV at time $t + \Delta t$.

$$ p_{{{\text{u}},t + \Delta t}} = \left[ {x_{{{\text{u}},t + \Delta t}} ,y_{{{\text{u}},t + \Delta t}} ,z_{{{\text{u}},t + \Delta t}} } \right] = p_{{{\text{u}}t}} + \frac{{\left( {v_{{{\text{u}},t + \Delta t}} + v_{{{\text{u}}t}} } \right)}}{2} \times \Delta t $$

(2.9)

where $p_{{{\text{u}}t}}$ is the position of UAV at time t: $p_{{{\text{u}}t}} = \left[ {x_{{{\text{u}}t}} ,y_{{{\text{u}}t}} ,z_{{{\text{u}}t}} } \right]$.

The position of target is given at first. Then we can acquire the distance at time $t + \Delta t$ between UAV and the target for each $v_{{{\text{u}},t + \Delta t}} \in V_{{{\text{u}},t + \Delta t}}$. Finally, we will choose the velocity corresponding to the shortest distance. Then we will get the selected acceleration in the end. Figure 2 shows the flow chart of the process of selection.

Fig. 2

Flow chart of acceleration selection

2.3 Formation Keeping and Splitting

For formation flight of UAVs, we must consider formation splitting and configuration while avoiding collision. While considering formation splitting, we should first divide the obstacle into four parts based on the xy and yz plane fixed on the obstacle as shown in Fig. 3. The four parts can be marked as I,II,III and IV.

Fig. 3

Four parts divided based on the obstacle

Figure 4 shows the formation keeping and splitting strategy. The formation consists of five UAVs. UAV1 is in the middle of the formation and others are around it. Each UAV can acquire its best acceleration next time according to the method in Sects. 2.1 and 2.2. If the formation must be unchanged, all the UAVs should choose the same acceleration that allows the velocity of each UAV outside collision cone among the five best accelerations. The condition of formation keeping is shown in Fig. 4a. While considering formation splitting, the UAVs should be divided into groups according to the direction of velocity next time and the four parts of the obstacle as shown in Fig. 4b.

Fig. 4

Formation keeping and splitting strategy a Formation keeping b Formation splitting

While formation keeping, the final acceleration of the whole formation is selected from the selected acceleration of the UAVs. The selection rule is that the final acceleration can let each UAV in the formation complete collision avoidance. Figure 5 shows the flowchart of selection.

Fig. 5

Flow chart of acceleration selection for formation keeping

While formation splitting, UAVs in the formation can be divided into four parts at most. In the same part, UAVs must keep in a new formation, the acceleration selection is the same as formation keeping. In fact, after formation splitting we can set different targets to complete formation reconfiguration based on the mission.

Then we should judge which part the UAV belongs to. Firstly we should define some angles. As shown in Fig. 6, $V_{{{\text{uo}}1}}$ is the relative velocity next moment on the basis of the selected acceleration. $\beta$ is the angle between the tangent line and the connected line of the center of UAV and obstacle. $\beta$ is always defined as nonnegative. $\theta$ is the angle between the horizontal axis and the connected line. $\theta_{v}$ is the angle between the horizontal axis and the line of $v_{\text{ou}}$. $\theta$ and $\theta_{v}$ both belong to the scope $\left[ { - \pi ,\pi } \right]$. They are positive while above the horizontal axis and negative while under the horizontal axis. $\Delta \theta$ is defined as:

Fig. 6

Definition of angles

$$ \Delta \theta = \theta_{\text{v}} - \theta $$

(2.10)

While in three-dimensional space, we consider xy and yz plane. The horizontal axis is the x axis in xy plane and y axis in yz plane. Then we can get $\Delta \theta_{xy} ,\Delta \theta_{yz} ,\beta_{xy} ,\beta_{yz}$. The division is shown in Table 1.

Table 1 Parts division while formation splitting

2.4 Collision Avoidance Within the Formation

When the formation is split, we must consider the case that UAVs in the formation may collide among themselves. Thus, we must add collision avoidance strategy among UAVs.

In this paper, we also use the method in Sects. 2.1 and 2.2 to avoid collision among UAVs in formation.

First, we should set up a minimum safe distance $d_{\text{safe}}$. When $d < d_{\text{safe}}$ (where d is the distance between two UAVs), the collision between UAVs occurs. The minimum safe distance is dependent on the size of UAV and some other factors. Then we need to set up a threshold of distance $d_{\text{th}}$. When $d < d_{\text{th}}$, the UAVs treat each other as obstacle. The selection of the threshold is important. The threshold must meet the requirement: $d_{\text{th}} > d_{\text{safe}}$. In addition, it cannot be too large considering the formation keeping.

3 Numerical Simulation

In order to verify the effectiveness of the algorithm, we use Matlab & Simulink to simulate.

3.1 Simulation Conditions

The obstacle detection distance of UAV is set as 500 m. Since rotor drone can hover, the minimum velocity of UAV is set as zero. The maximum velocity is set as 20 m/s. The starting point and target of the five UAVs are shown in Table 2.

Table 2 The starting point and target of the UAVs

3.2 Formation Keeping with Two Obstacles

In this condition, the formation is kept while avoiding obstacle. The radio of obstacle1 is 10 metres and the radio of obstacle2 is 12 metres. The acceleration range of the UAV is: ${ - 3} \le a_{x} \le 3, - 3 \le a_{y} \le 3, - 3 \le a_{z} \le 3$. The entire simulation lasts 50 s. Communication delay is 0.1 s.

Figure 7 shows the distance between UAVs and the centre of obstacle1 and Fig. 8 show the distance between UAVs and the centre of obstacle2. Figure 9 shows trajectories of UAVs in the case of formation keeping with two obstacles. We can see from Figs. 7and 8 that the minimum distance between UAVs and the centre of obstacle is bigger than the ratio of obstacle. Therefore, the collision avoidance is successful.

Fig. 7

Distance between UAVs and the centre of obstacle1

Fig. 8

Distance between UAVs and the centre of obstacle2

Fig. 9

Trajectories of UAVs in the case of formation keeping with two obstacles

3.3 Formation Splitting

In this condition, the formation can be split while avoiding collision. The radio of obstacle is 10 metres. The acceleration range of the UAV is: ${ - 10} \le a_{x} \le 10, - 10 \le a_{y} \le 10, - 10 \le a_{z} \le 10$. The entire simulation lasts 50 s.

The minimum safe distance $d_{\text{safe}} = 1 {\text{m}}$ and the threshold $d_{\text{th}} = 4 {\text{m}}$

We can see from Fig. 10 that the minimum distance between UAVs and the centre of obstacle is bigger than the ratio of obstacle. Figure 11 shows the trajectories of UAVs in the case of formation splitting. In Fig. 12, the distance between UAVs in the formation is greater than 2 m, which is obviously bigger than the safe distance.

Fig. 10

Distance between UAVs and the centre of obstacle

Fig. 11

Trajectories of UAVs in the case of formation splitting

Fig. 12

Distance between UAVs in the formation

3.4 Analysis of the Simulation

As shown in Figs. 7, 8 and 10, we can see that this method has a good performance on collision avoidance with external obstacles and can tolerate little communication delay.

While applied in collision avoidance among UAVs in the formation, the distance is much more shorter. This means UAVs need higher acceleration to get good performance. This method is good at obstacles which can be discovered far away from UAVs. When the obstacle is close, the relative size of acceleration and the communication delay has bigger influence on final performance.

4 Conclusion

This paper presents a strategy of collision avoidance between UAV formation and moving obstacles based on the theory of velocity obstacle. The maximum and minimum velocity and acceleration collection can be set up according to the dynamic model and inputs of UAVs. The condition of formation keeping and splitting are both considered. At last, the result of numerical simulation is presented to prove the performance of this method.

Currently, we just give the collection acceleration directly and don’t involve a specific model. In addition, we just choose the best acceleration by a simple regulation. In the future, we will combine it with a type of rotor UAV and try to optimise the method of selection based on some other theories to reduce the amount of calculation.