Automatic Separation Management Between Multiple Unmanned Aircraft Vehicles in Uncertain Dynamic Airspace Based on Trajectory Prediction

Page:

171-180

DOI:

https://doi.org/10.18280/ria.330302

OPEN ACCESS

Abstract:

In an uncertain dynamic airspace, the future trajectories of noncooperative aircrafts (obstacles) are very uncertain. Multiple unmanned aircraft vehicles (UAVs) must avoid colliding into noncooperative obstacles and keep a safe distance between each other. This poses a huge challenge to the unmanned aircraft system traffic management (UTM). To cope with the challenge, this paper puts forward an automatic separation management method for a formation of multiple UAVs based on trajectory prediction in 3D dynamic airspace. Firstly, the uncertain trajectories of each obstacle in a time horizon were predicted based on the reachable set, producing an ellipsoidal reachable region. Next, a safe and efficient double-layer separation management strategy was proposed based on the improved artificial potential field (APF) method, considering the safe distance between cooperative UAVs and that between cooperative and noncooperative UAVs. The distance-based traditional APF method was adopted to manage the conflicts according to the reachable region of each obstacle, maximizing the safety between the UAV and the obstacle. The APF method based on relative motion state was employed to manage the conflicts, and adaptively adjust the dynamic safe separation between the UAVs. Experimental results prove that our method can effectively prevent the conflicts between a UAV and other UAVs in the formation or noncooperative obstacle. Besides, the collision-free trajectory generated by our method is smooth and stable, and close to the planned trajectory. The proposed method provides a solid guarantee to UAV flight safety, while minimizing the impacts on nearby aircrafts. The research findings shed new light on the UTM of highly uncertain low-altitude airspaces.

Keywords:

*unmanned aircraft vehicle (UAV), separation assurance, collision avoidance, conflict resolution, unmanned aircraft system traffic management (UTM)*

1. Introduction

In recent years, unmanned aircraft vehicles (UAVs) have been widely used in various field of the civilian sector, ranging from cargo transport to road patrol [1]. The joint flight of multiple UAVs becomes increasingly popular, because multi-UAV cooperation can complete operations that are difficult to be done by a single UAV. For safe and efficiency integration of UAVs into low-altitude airspace, many countries, namely, the US, Japan and Singapore, have explored the concept of unmanned aircraft system traffic management (UTM). The core issue of the UTM is to keep a safe separation between a UAV and other cooperative or noncooperative aircrafts, which is critical to the safety of the airspace [2]. However, it is a challenging task to design a robust management system for the separation assurance of the UAV. The challenge mainly arises from the following factors: Unlike traditional traffic management systems, the UTM handles multiple UAVs in a strict and crowded airspace. During conflict resolution, a UAV is very likely to cause a cascade effect, inducing even more conflicts. Moreover, the future trajectories of noncooperative aircrafts (obstacles) are uncertain, under the effects of pilot reaction, aircraft performance, wind and many other factors. In such a dense and uncertain airspace, it is not an easy task for a UAV to avoid conflicts with a noncooperative obstacle, while keeping a safe separation with cooperative UAVs. In other words, it is difficult for the UAV to strike a balance between safety and efficiency.

For a UAV formation, the management of safe separation requires a good collision avoidance method to keep the safe distance and resolve conflicts. There are many recent studies on collision avoidance algorithms. Kuchar and Yang [3] conducted a detailed investigation on collision detection and avoidance algorithms. Jenie et al. [4] summarized and classified the conflict detection and resolution methods for UAVs in integrated airspace. Many reviews have been completed on relevant issues in the past two years [5-8]. Popular collision avoidance algorithms include geometric method [9-11], sampling-based method [12-14], numerical optimization [15-19], and artificial potential field (APF) [20-28]. The geometric method considers the geometric representation of the collision scene in the search for collision avoidance maneuvers. This method is simple and efficient, yet not suitable for multi-UAV situations. The sampling-based method divides the airspace into different nodes for spatial search. Common sampling-based methods are rapid-exploring random trees (RRT), RRT star (RRT*), A-star (A*), etc. However, the sampling-based method requires prior knowledge of the airspace, making it not suitable for dynamic collision avoidance, and faces a high complexity in 3D space search. The numerical optimization converts collision avoidance into the minimization of the objective function, and adopts techniques like intelligent evolutionary algorithm, linear programming and optimal control. The problem of this method lies in the high computing complexity and large computing overhead. To sum up, the above three methods are not desirable tools for real-time collision avoidance of multiple UAVs in a 3D dynamic airspace.

Compared with the above methods, the APF is the most widely used collision avoidance method for 3D dynamic airspace, because it is simple in mathematic meanings, easy to implement, and highly efficient, robust and adaptive to environment changes. For example, Chang et al. [20] combined APF with rotational vectors for collision avoidance in dynamic 3D airspace with multiple UAVs. Targeting a dynamic airspace, Zhu et al. [21] improved the APF for the UAV to realize emergency collision avoidance against suddenly emerging moving obstacles, ensuring that the collision-free trajectory is feasible under the physical constraints of the UAV. Sun et al. [22] proposed an improved APF method that generate collision-free trajectories for multiple cooperative UAVs in a 3D dynamic airspace. Nie et al. [23] controlled the UAV formation with the APF based on speed state in a dynamic airspace. Sun et al. [24] improved the APF to generate collision-free trajectories cooperatively in a 3D dynamic space with multiple UAVs. The APF and its variants mentioned above can quickly avoid obstacles in real time in a dynamic airspace. However, there are two imperfections with these methods. First, the moving obstacles are generally treated as instantaneously static or motionless, while the future trajectories of obstacles are uncertain under the effects of wind, pilot reaction and aircraft performance. Second, these methods often produce excessive collision avoidance maneuvers, which may disrupt the normal operation of the surrounding traffic in the airspace. To promote the safety of the entire airspace, it is necessary to consider the uncertainty of future trajectories of obstacles during the safe separation assurance and collision avoidance of the UAV formation in a dynamic airspace.

This paper aims to develop a method to generate safe, stable and efficient collision-free trajectories for UAVs in an uncertain and dynamic airspace to keep safe separation between each other and from obstacles. Based on our previous research [23], the uncertainty in the future trajectories of obstacles was taken into account. Our research mainly makes two contributions. Firstly, to cope with the uncertainty of the airspace, all the possible future trajectories of a noncooperative obstacle were expressed by the reachable set. Secondly, to deal with the dynamicity of the airspace, the collision-free trajectories were generated by different APF methods, such that the UAVs will not collide into each other or into an obstacle. The safe distance between UAV and obstacle was maintained by the static APF based on trajectory prediction, while that between UAVs was kept by the dynamic APF based on relative motion.

2. Problem Formulation

It is assumed that the multiple UAVs in the formation fly along the planned trajectory. The cooperative UAVs in the formation know the real-time positions of obstacles via the automatic dependent surveillance-broadcast (ADS-B) technology. The real-time positions of noncooperative obstacles can be tracked by ground radars. However, the UTM does not know the future trajectories of the obstacles. Targeting an uncertain, crowded airspace, our research has two main purposes: avoid the conflicts between a formation of cooperative UAVs and the noncooperative obstacles in a safe and efficient manner; prevent the cascade of conflicts between the UAVs within the formation.

**2.1 Motion equations**

Small UAVs have a wide range of uses in the civilian sector. This paper mainly considers the small UAVs (<55lbs) that are widely applied in low-altitude airspace, such as rotary UAVs and unmanned helicopters. Each UAV was considered as a particle in a 3D space described by the north-east-down (NED) system. Let *x _{i}(t)* be the motion state of UAV

$\dot{x}_{i}(t)=A x_{i}(t)+B a_{i}(t)+S_{w}$ (1)

$y_{i}(t)=C \dot{x}_{i}(t)+S_{v}$ (2)

where, $A=\left[\begin{array}{cc}{I} & {\Delta T \cdot I} \\ {0} & {I}\end{array}\right]$; $B=\left[\begin{array}{cc}{\frac{\Delta T^{2}}{2}} {I} & {\Delta T \cdot I}\end{array}\right]^{T}$; *a _{i}(t)*=

2.1.1 System noise

In the formation, each UAV acquires its current motion state via the onboard sensors, and sends it to the other UAVs in the formation. In fact, the acquired information is always biased due to the performance constraints of the sensors. The bias is also known as measurement noise, denoted as Sv. The noise obeys a zero-mean multidimensional normal distribution.

According to the above motion equations, we have *x _{i}*(

2.1.2 Maximum velocity

During UAV operations, the maximum velocity is one of the most important physical constraints. Throughout the flight, no UAV in the formation should surpass its maximum velocity ‖*V _{max}*‖:

$v_{i}(t) \leq\left\|V_{\max }\right\|$ (3)

At a sampling instant, the traction force *F* of a UAV is generated by the APF, thus producing the acceleration at that moment *a(t)*={*a _{x}(t)*,

$F(t) \leq \frac{m\left(V_{\max }-v(t)\right)}{\Delta T}$ (4)

**2.2 Definition of UAV formation**

Formation control aims to keep a group of UAVs to fly in a formation along the planned trajectory. There are three main strategies for formation control: leader-following method, virtual leader method and behavior method. In leader-following method, the leader flies along the planned trajectory, while the followers fly in the light of their relative positions to the leader. In the virtual leader method, the formation is viewed as a rigid virtual structure, and each UAV as a point with a relative fixed position in the structure. This paper adopts the behavior method for formation control.

In the leader-following method or the virtual leader method, each UAV flies after a physical or an abstract individual. In the behavior method, however, there is no such an information source for reference. All UAVs in the formation are of equal status and directly obtains information from the other UAVs in the formation. The formation pattern is based on the average of the instantaneous states of the UAVs $x_{o}=\left[p_{o}^{T}, v_{o}^{T}\right]^{T}$.

$x_{o}(t)=\frac{1}{N} \sum_{i}^{N} x_{i}(t)$ (5)

As shown in Figure 1, the formation coordinate system (*O _{f}X_{f}Y_{f}Z_{f}*) was defined as a Cartesian coordinate system, in which the origin

**Figure 1.** The formation coordinate system

For the flight controller to control the formation, it is necessary to identify the ideal positions of the UAVs in the NED system. To this end, the coordinates of the formation should be transformed from the formation coordinate system to the NED system:

$C=\operatorname{RotaZ} \cdot \operatorname{RotaX}=\left[\begin{array}{ccc}{\cos \theta} & {\sin \theta} & {0} \\ {-\sin \theta} & {\cos \theta} & {0} \\ {0} & {0} & {1}\end{array}\right] \cdot\left[\begin{array}{ccc}{1} & {0} & {0} \\ {0} & {\cos \varphi} & {-\sin \varphi} \\ {0} & {\sin \varphi} & {\cos \varphi}\end{array}\right]$ (6)

Through the above conversion matrix, the NED coordinates of the ideal position of the formation can be obtained as:

$p_{i}^{d}(t)=C \cdot p_{i}^{r}(t)+p_{o}(t)$ (7)

Therefore, the real-time target position of each UAV in the NED system can be described as $D(t)=\left\{p_{1}^{d}(t), p_{2}^{d}(t), \cdots, p_{N}^{d}(t)\right\}$.

3. Methodology

**3.1 Trajectory prediction under uncertainties based on reachable set **

Currently, the future trajectories of obstacles are generally predicted under linear motion assumption. The obstacle is assumed to fly at a constant speed along a straight line. Then, the future position of the obstacle in a time horizon can be deduced based on the current velocity. This approach applies to the forecast of future trajectories, if the obstacle has little change in motion state in the short term. Nevertheless, a moving obstacle cannot fly along a straight line in the long run. The pilot may change the course, and the obstacle may deviate from the planned trajectory under the wind.

Considering the uncertainty in the future trajectories of moving obstacles, this paper decides to predict the possible future motion states of an obstacle with reachable set, rather than linear prediction. The reachable set refers to the scope of region that can be reached by the obstacle in the next time horizon, under its own kinematic constraints (maximum turning radius and maximum turning velocity). Once the future trajectories of the obstacle are predicted based on the reachable set, the conflicts can be detected by judging whether the UAV trajectory intersects with reachable region of the obstacle. For noncooperative obstacles, this detection approach is much more robust than the linear prediction.

3.1.1 Reachable set on 2D plane

Suppose the obstacle flies according to Dubin’s car model. Then, the obstacle flies at a constant velocity and faces a limit on the maximum turning velocity:

$v=$ Const

$\varphi \leq w_{\max }$ (8)

where, *v* is the horizontal velocity of the obstacle; *φ* is the heading angle (*φ _{max}* is the upper limit of the steering angle);

$S_{1}(\theta, t)=\left[\begin{array}{c}{-\rho(1-\cos \theta)+(v t+\rho \theta+r) \sin \theta} \\ {-\rho \sin \theta+(v t+\rho \theta+r) \cos \theta}\end{array}\right]$ (9)

$S_{2}(\theta, t)=\left[\begin{array}{c}{\rho(1-\cos \theta)+(v t-\rho \theta+r) \sin \theta} \\ {\rho \sin \theta+(v t-\rho \theta+r) \cos \theta}\end{array}\right]$ (10)

The domains of *S _{1,2}*(

$S_{1}: \max \left(-\varphi_{\max },-\pi\right) \leq \theta \leq 0$ (11)

$S_{2}: 0 \leq \theta \leq \min \left(\varphi_{\max }, \pi\right)$ (12)

Similarly, *S _{3,4}*(

$S_{3}(\theta, t)=S_{1}\left(-\varphi_{\max }, t\right)+\left[\begin{array}{l}{r \sin \theta} \\ {r \cos \theta}\end{array}\right]$ (13)

*$S_{4}(\theta, t)=S_{2}\left(\varphi_{\max }, t\right)+\left[\begin{array}{l}{r \sin \theta} \\ {r \cos \theta}\end{array}\right]$ *(14)

The domains of *S _{3,4}*(

*$S_{3}:-\pi \leq \theta \leq-\varphi_{\max }$ *(15)

*$S_{4}: \cdot \varphi_{\max } \leq \theta \leq \pi$ *(16)

where, *θ* is the normal unit vector of each point. The normal unit vector of point *(x,y)* is $\vec{n}$=(*n _{x}, n_{y}*)，

According to formulas (9), (10), (13) and (14), *W _{max}*,

**Figure 2.** The boundaries of the reachable set

If *φ _{max}*>

For convenience, the region enclosed by the boundaries of *RS _{xy}* was approximated as an ellipse (Figure 3), where the length of the major axis

*$\left\{\begin{array}{l}{x=a \cos \alpha} \\ {y=b \sin \alpha}\end{array}\right.$ * (17)

where, *α* is the angle between any boundary point (*x, y*) of the elliptical reachable set $R S_{x y}^{e l l i}$ and the *x* axis, *α**∈*(*0*, *2**π*).

**Figure 3.** The elliptical reachable set on the 2D plane

3.1.2 Reachable set in 3D space

When the obstacle is moving in a 3D space, the reachable set can be approximated as an ellipsoid both on plane *xy* and plane *xz*. Suppose the ellipsoid on plane *xz* has the same major and minor axes as that on plane* xy*, that is, the lengths of major and minor axes are *a* and *b*, respectively. As for plane *yz*, the reachable set can be roughly considered as a circle, whose diameter equals the length of the major axis *a*. Then, the entire reachable region in the 3D space can be approximated as an ellipsoid (Figure 4). Let *k(x,y,z)* be a point on the ellipsoid $R S_{x y z}^{e l l i}$. The 3D ellipsoidal reachable set $R S_{x y z}^{e l l i}$ can be defined as:

$x=a \cos \alpha \sin \beta$

$y=b \sin \alpha \sin \beta$

$z=b \cos \beta$ (18)

where, *α* is the angle between the projection of the normal unit vector of *k(x,y,z)* on plane *xy* and the *x* axis, α∈[0,2π); *β* is the angle between the normal unit vector of *k(x,y,z)* and its projection on plane *x-z*, *β**∈**[0,π]*.

**Figure 4.** The 3D ellipsoidal reachable set

**3.2 Two-layer safe separation management based on improved APF**

The APF method has received extensive attention, because of its fast speed, simple expression and physical significance. In this method, it is assumed that the trajectory of a robot depends on the forces in the virtual potential field: the attractive force from the destination that pulls the robot towards the destination, and the repulsive force on the obstacle that pushes the robot away from the obstacle and threat source. In the virtual potential field, a path can be set up to connect the origin and the destination along the direction of the resultant force of the attractive force and the repulsive force. In this paper, the APF method is improved and adopted for the aircrafts in the UAV formation to realize the safe separation control and obstacle avoidance.

3.2.1 Attractive force

Under the attractive force of the APF, the UAVs move from the original positions to the preset positions of the formation, forming the required formation pattern. The attractive force can be divided into position attractive force *F _{p}* and velocity attractive force

$F_{p}^{i}(t)=K_{g}\left(p_{g}-p_{o}(t)\right)+K_{p}\left(p_{i}^{d}(t)-p_{i}(t)\right)$ (19)

$F_{v}^{i}(t)=K_{v}\left(v_{i}^{d}(t)-v_{i}(t)\right)$ (20)

where, *K* is the weight coefficient; *p _{g}* is the destination of the entire formation, a key point on the planned trajectory.

When a UAV flies towards the destination, it is continuously subjected to the acceleration generated by the resultant force. As a result, the UAV may still fly at a high velocity even if it comes close to the destination. Chances are that the UAV might fly over the destination. Since the attractive force always points towards the destination, the UAV will eventually oscillate repeatedly about the destination. This phenomenon often occurs when a UAV tries to return to the planned trajectory after successful collision avoidance. To weaken the oscillation, a damping force *F* pointing to the opposite direction of velocity can be introduced:

$F_{d a m p}^{i}(t)=-K \cdot v_{i}(t)$ (21)

Then, the overall attractive force can be depicted as:

$F_{a t t}^{i}(t)=F_{p}^{i}(t)+F_{v}^{i}(t)+F_{d a m p}^{i}(t)$ (22)

3.2.2 Repulsive force

The repulsive force keeps the UAVs outside the safe distance. In this paper, the repulsive force of UAV i consists of two parts: the repulsive force $F_{r e p_{-} o b s}^{i}$ that keeps the safe distance from a noncooperative obstacle, and the repulsive force $F_{r e p{-i n n e r}}^{i}$ that keeps the safe distance between cooperative UAVs in the formation.

(1) Repulsive force between a UAV and a noncooperative obstacle. The reachable region of an obstacle after the time horizon Ks can be computed by formula (18). Meanwhile, the position of the UAV in Ks can be determined based on its current position and velocity. If the UAV will enter the reachable region of the obstacle in Ks, the UAV should perform collision avoidance maneuvers under the traditional distance-based potential field force. Otherwise, the UAV should fly forward in the original motion state.

Based on the reachable region, the repulsive force between UAV i and a noncooperative obstacle can be calculated by:

$F_{r e p_{-} o b s}^{i}=\left\{\begin{array}{cc}{K_{o b s} \cdot\left(\frac{1}{r_{s a f e}^{o b s}-o b s}-\frac{1}{\|\vec{d}\|}\right) \frac{\vec{d}}{\|\vec{d}\|},} & {\text { for }\|\vec{d}\|<r_{s a f e}^{o b s}} \\ {0,} & {\text { otherwise }}\end{array}\right.$ (23)

where, $\vec{d}$ is the distance from the UAV to the reachable region of the obstacle; $r_{\text {safe }}^{\text {obs }}$ is the safe distance between the UAV and the reachable region of the obstacle. If $\vec{d}$ is smaller than $r_{\text {safe}}^{o b s}$, then the repulsive force will act on the UAV to push it away from the reachable region. As shown in Figure 5, $r_{\text {safe}}^{o b s}$ is dependent on the size of the reachable region and the boundaries of the safe region of the UAV:

$r_{s a f e}^{o b s}=\left\{\begin{array}{c}{r_{s a f e}^{\operatorname{min}}+r_{e l l i}+K \cdot v_{i} \cdot \cos \delta, i f \delta \in\left[0, \frac{\pi}{2}\right]} \\ {r_{s a f e}^{\min }+r_{e l l i}, e l s e}\end{array}\right.$ (24)

where, *δ* is the angle between the velocity direction of the UAV and the connecting line between the UAV and the obstacle; *v _{i}* is the UAV velocity;

$r_{\text {elli }}=\sqrt{(a \sin \beta \cos \alpha)^{2}+(b \sin \beta \sin \alpha)^{2}+(b \cos \beta)^{2}}$ (25)

**Figure 5.** Safe distance between a UAV and an obstacle

(2) Repulsive force between cooperative UAVs in the formation. Traditionally, the repulsive force is only related to relative position. When the UAV moves at a high velocity, such a repulsive force cannot guarantee successful avoidance of collision. To adapt to the real-time dynamic requirements of the UAV formation, this paper modifies the traditional function of the repulsive force. The UAV velocity was included as an influencing factor of the repulsive force. In the revised function, both the direction and magnitude of velocity can be adjusted by the repulsive force. In other words, the repulsive force between cooperative UAVs in the formation *F _{rep_inner}* depends both on relative position and the direction of relative velocity. Let $F_{r e p}^{i j}$ be the repulsive force of UAV

$F_{_{rep\_inner//}}^{{}}=\left\{ \begin{matrix} K\cdot (\frac{1}{r_{_{safe}}^{inner}}-\frac{1}{\left\| {\vec{d}} \right\|})\cdot ({{{\vec{v}}}_{j}}-{{{\vec{v}}}_{i}})\cdot \cos \delta ,\text{ }for\text{ }\left\| {\vec{d}} \right\|<r_{_{safe}}^{inner} \\ 0,otherwise \\\end{matrix} \right.$ (26)

$F_{_{rep\_inner\bot }}^{{}}=\left\{ \begin{matrix} K\cdot (\frac{1}{r_{_{safe}}^{inner}}-\frac{1}{\left\| {\vec{d}} \right\|})\frac{\vec{d}\cdot \left\| {{{\vec{v}}}_{j}}-{{{\vec{v}}}_{i}} \right\|\cos \delta }{\left\| {\vec{d}} \right\|}-{{F}_{rep\_inner//}},\text{ }for\text{ }\left\| {\vec{d}} \right\|<r_{_{safe}}^{inner} \\ 0,otherwise \\\end{matrix} \right.$(27)

$F_{r e p_{-} i n n e r}^{i j}=\alpha F_{r e p_{-} i n n e r \perp}+\beta F_{r e p_{-} i n n e r / /}$ (28)

where, *α* and *β* are weight factors; $\left\|\vec{v}_{j}-\vec{v}_{i}\right\| \cos \delta$ is the approaching velocity between UAVs *i* and *j* (the greater the approaching velocity, the larger the repulsive force); $\vec{v}_{j}$ is the obstacle velocity during collision avoidance; $r_{\text {safe}}^{\text {inner}}$ is the safe distance between a UAV and its surrounding UAVs. If two UAVs are closer than the $r_{\text {safe }}^{\text {inner }}$, the repulsive force will emerge to keep the two UAVs outside the safe distance. Considering the velocity states of relevant UAVs, the $r_{\text sa f e}^{\text {inner }}$ can be defined as:

$r_{\text {safe}}^{\text {inner}}=\left\{\begin{array}{c}{2 \cdot r_{\text {safe}}^{\min }+K_{\text {safe}} \cdot\left(v_{i}-v_{j}\right) \cdot \cos \delta, \text {if } \delta \in\left[0, \frac{\pi}{2}\right]} \\ {2 \cdot r_{\text {safe}}^{\min }, \text {else}}\end{array}\right.$ (29)

When two UAVs are approaching each other, the increases with the relative velocity.

If UAV *i* senses N UAVs in the formation to be avoided from at time t, then the total repulsive force needed to complete the collision avoidance can be described as:

$F_{r e p_{-} i n n e r}^{i}=\sum_{j}^{N} F_{r e p_{-} i n n e r}^{i j}$ (30)

The total repulsive force acting on UAV i can be determined as:

$F_{r e p}^{i}=F_{r e p_{-} o b s}^{i}+F_{r e p_{-} i n n e r}^{i}$ (31)

According to the states of each UAV and the information of the airspace, the resultant force of the potential field can be obtained as:

$F_{\text {total}}^{i}=F_{a t t}^{i}+F_{r e p}^{i}$ (32)

4. Simulation and Results Analysis

This section simulates the encounter between a three-UAV formation and a noncooperative obstacle. First, the 3D reachable region of the moving obstacle was visually presented. After that, the authors verified whether our method can effectively keep a UAV in safe distance from other UAVs and the obstacle, minimize the deviation of the collision-free trajectory from the planned trajectory, and mitigate the violent changes in UAV velocity and acceleration.

**4.1 Reachable region**

Figure 6 shows the ellipsoidal reachable region of the moving obstacle in the time horizon of 10s. As shown in the figure, planes *xz* and *xy* are ellipses, while plane *zy* is a circle. The moving obstacle may appear in any point in the region after 10 s.

**Figure 6.** The ellipsoidal reachable region of the noncooperative obstacle

**4.2 Encounter scenes**

In the 3D airspace (Figure 6), three UAVs set out from different positions, each with a unique acceleration and velocity. As shown in Figure 7(a), the three UAVs soon reached basically the same direction and magnitude of velocity, and flied at relatively fixed positions, indicating that the formation had been established. The formation pattern is $x_{1}^{r}$=[-20,0,0,0,0,0]^{T}, $x_{2}^{r}$ =[20,0,0,0,0,0]^{T}, and $x_{3}^{r}$=[0,0,0,0,0,0]^{T}. Meanwhile, an obstacle (the red dot) flied across the trajectories of the three UAVs. The reachable region and trajectory of the obstacle are respectively displayed as a red ellipsoid and a blue dotted line. When the three UAVs encountered the obstacle, the UAV3 at the middle detected the entry into the reachable region of the obstacle, and performed collision avoidance maneuvers, without violating the safe distance with the other two UAVs.

(a) Before conflict

(b) Conflict resolution

(c) After resolution

**Figure 7.** Collision avoidance process between the UAV formation and the noncooperative obstacle

**4.3 Safety analysis**

Figure 8 shows the safe distance between each UAV and the obstacle in the conflict resolution process. The red dotted line stands for the collision distance. Obviously, the safe distances between all three UAVs and the obstacle were greater than the collision distance throughout the process. This means all UAVs in the formation successfully avoided colliding into the obstacle. It can also be seen that the UAV formation maintained a large safe distance from the obstacle.

The real-time distances between the three UAVs are plotted in Figure 9. It can be seen that, at around 120s, UAV3 moved closer to UAV2 and away from UAV1, when the UAV took collision avoidance measures. This is because UAV3 moved towards UAV2 during conflict resolution. In addition, the distances between the three UAVs were greater than the collision distance, indicating that no conflict occurred between them.

**Figure 8.** Variation in safe distance between each UAV and the obstacle

**Figure 9.** Variation in safe distances between UAVs in the formation

**4.4 Performance comparison**

To verify its stability and safety, the proposed method, i.e. the safe distance management based on trajectory prediction, was compared with the safe distance management based on motion state [23] and the traditional APF method, in terms of the deviation of conflict resolution trajectory from the planned trajectory, and the fluctuation of velocity and acceleration. The safe distance management based on motion state was referred to as the previous method, because it was proposed previously by the authors.

4.4.1 Comparison of trajectory deviation

As shown in Figures 10 and 11, the UAV formation encountered the obstacle after flying for 120s. In the formation, UAV3 and UAV2 moved away from the planned trajectories after the encounter. The trajectory deviation was mainly observed in the vertical direction (z axis). The trajectory deviation of UAV3 was greater than that of UAV2. The trajectory deviation of our method (Figure 10) was obviously smaller than the previous method (Figure 11). Therefore, our method could generate relatively stable conflict resolution trajectories, making the collision avoidance maneuvers gentle and elegant, with limited impact on nearby traffic in the airspace.

In Figure 10, UAV3 started to move away from the planned trajectory at 103 s, successfully resolved the conflict at 122 s, and returned to the planned trajectory at 130 s. The entire conflict resolution took 27s. In Figure 11, the corresponding time points were 110 s, 121s and 148s, and the conflict was resolved fully in 38 s. Compared with that of the previous method, the conflict resolution by our method takes effect early, restores the planned path rapidly, and ensures the safety of the UAVs.

4.4.2 Comparison of velocity and acceleration fluctuations

In 102 s, the three UAVs encountered the obstacle and started to make conflict resolution maneuvers. The velocity and acceleration fluctuations of our method, the previous method and the traditional APF method are displayed in Figures 12-14, respectively. Judging by the acceleration fluctuations, UAV3 mainly maneuvered along the vertical direction (z axis), with limited fluctuations in horizontal velocity and acceleration. By the traditional APF method, sudden fluctuations appeared on the velocity and acceleration in the vertical direction, which may surpass the physical constraints of the UAV, making the maneuvers inexecutable. By contrast, the velocity and acceleration by our method and the previous method fluctuated rather gently in conflict resolution, and our method boasts the gentlest changes of velocity and acceleration in the vertical direction.

**Figure 10.** Trajectory deviations of our method

**Figure 11. **Trajectory deviations of the previous method

**Figure 12.** Velocity and acceleration fluctuations of our method

**Figure 13.** Velocity and acceleration fluctuations of the previous method

**Figure 14. **Velocity and acceleration fluctuations of the traditional APF method

5. Conclusions

Focusing on uncertain, crowded airspaces, this paper puts forward a separation management method based on trajectory prediction, aiming to maintain the safe distance between each UAV and the other UAVs in the formation, and between each UAV and a noncooperative obstacle. Firstly, the region that a noncooperative obstacle may fly to within a time horizon was predicted based on the reachable set, for the future trajectory of the obstacle is uncertain under the effects of pilot reaction, wind and other external factors. Next, the possibility of conflict was judged according to the reachable region of the noncooperative obstacle, and the affected UAVs in the formation need to perform collision avoidance maneuvers by the distance-based APF method. In this way, the conflict resolution measure is taken early, maximizing the safety of the UAVs, and the UAVs could avoid the risk of collision by moving slightly away from the planned trajectory. Since a UAV in conflict resolution inevitably affects the surrounding UAVs, this paper designs the APF method based on relative motion state to generate the collision avoidance trajectory. In our method, the approaching velocity between the UAVs is positively correlated with the safe distance and the deviation from the planned trajectory; the UAVs in the formation could adjust their safe distances in real time, and adapt to the flexibly changing patterns of the formation. The simulation results show that our method can effectively maintain the safe distance and prevent the collisions between UAVs and between UAVs and a noncooperative obstacle, and outperform the existing methods in safety, stability and robustness.

Acknowledgment

This work is supported by the State Key Program of National Natural Science of China (Grant No. 71731001).

References

[1] Jiang, T., Geller, J., Ni, D., Collura, J. (2016). Unmanned aircraft system traffic management: Concept of operation and system architecture. International Journal of Transportation Science and Technology, 5(3): 123-135. https://doi.org/10.1016/j.ijtst.2017.01.004

[2] Kopardekar, P., Rios, J., Prevot, T., Johnson, M., Jung, J. Robinson III, J.E., (2016). UAS traffic management (UTM) concept of operations to safely enable low altitude flight operations. 16th AIAA Aviation Technology, Integration, and Operations Conference, Washington, D.C. https://doi.org/10.2514/6.2016-3292

[3] Kuchar, J.K., Yang, L.C. (2000). A review of conflict detection and resolution modeling methods. IEEE Transactions on Intelligent Transportation Systems, 1(4): 179-189. https://doi.org/10.1109/6979.898217

[4] Jenie, Y.I., Van Kampen, E.J., Ellerbroek, J., Hoekstra, J.M. (2017). Taxonomy of conflict detection and resolution approaches for unmanned aerial vehicle in an integrated airspace. IEEE Transactions on Intelligent Transportation Systems, 18(3): 558-567. https://doi.org/10.1109/TITS.2016.2580219

[5] Zhang, X., Du, Y., Gu, B., Xu, G., Xia, Y. (2018). Survey of safety management approaches to unmanned aerial vehicles and enabling technologies. Journal of Communications and Information Networks, 3(4): 1-14. https://doi.org/10.1007/s41650-018-0038-x

[6] Aggarwal, S., Kumar, N. (2020). Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges. Computer Communications, 149: 270-299. https://doi.org/10.1016/j.comcom.2019. 10.014

[7] Song, B., Qi, G., Xu, L. (2019). A survey of three-dimensional flight path planning for unmanned aerial vehicle. 2019 Chinese Control And Decision Conference (CCDC), Nanchang, China, China. https://doi.org/10.1109/ccdc.2019.8832890

[8] Liu, Y., Bucknall, R. (2018). A survey of formation control and motion planning of multiple unmanned vehicles. Robotica, 36(7): 1019-1047. https://doi.org/10.1017/S0263574718000218

[9] Phuong, P.D., Recchiuto, C.T., Sgorbissa, A. (2018). Real-time path generation and obstacle avoidance for multirotors: A novel approach. Journal of Intelligent and Robotic Systems: Theory and Applications, 89(1-2): 27-49. https://doi.org/10.1007/s10846-017-0478-9

[10] Seo, J., Kim, Y., Kim, S., Tsourdos, A. (2017). Collision avoidance strategies for unmanned aerial vehicles in formation flight. IEEE Transactions on Aerospace and Electronic Systems, 53(6): 2718-2734. https://doi.org/10.1109/TAES.2017.2714898

[11] Yang, J., Yin, D., Shen, L. (2017). Reciprocal geometric conflict resolution on unmanned aerial vehicles by heading control. Journal of Guidance, Control, and Dynamics, 40(10): 1-13. https://doi.org/10.2514/1.G002607

[12] Lin, Y., Saripalli, S. (2017). Sampling-based path planning for UAV collision avoidance. IEEE Transactions on Intelligent Transportation Systems, 18(11): 3179-3192. https://doi.org/10.1109/TITS.2017.2673778

[13] Liang, X., Meng, G., Xu, Y., Luo, H. (2018). A geometrical path planning method for unmanned aerial vehicle in 2D/3D complex environment. Intelligent Service Robotics, 11(3): 301-312. https://doi.org/10.1007/s11370-018-0254-0

[14] Li, J., Deng, G., Luo, C., Lin, Q., Yan, Q., Ming, Z. (2016). A hybrid path planning method in unmanned air/ground vehicle (UAV/UGV) cooperative systems. IEEE Transactions on Vehicular Technology, 65(12): 9585-9596. https://doi.org/10.1109/TVT.2016.2623666

[15] Wang, G.G., Chu, H.E., Mirjalili, S. (2016). Three-dimensional path planning for UCAV using an improved bat algorithm. Aerospace Science and Technology, 49: 231-238. https://doi.org/10.1016/j.ast.2015.11.040

[16] Song, B., Wang, Z., Sheng, L. (2016). A new genetic algorithm approach to smooth path planning for mobile robots. Assembly Automation, 36(2): 138-145. https://doi.org/10.1108/aa-11-2015-094

[17] Shao, Z., Yan, F., Zhou, Z., Zhu, X. (2019). Path planning for multi-UAV formation rendezvous based on distributed cooperative particle swarm optimization. Applied Sciences (Switzerland), 9(13): 2621. https://doi.org/10.3390/app9132621

[18] Yang, J., Yin, D., Niu, Y., Zhu, L. (2016). Cooperative conflict detection and resolution of civil unmanned aerial vehicles in metropolis. Advances in Mechanical Engineering, 8(6): 1-16. https://doi.org/10.1177/1687814016651195

[19] Radmanesh, M., Kumar, M. (2016). Flight formation of UAVs in presence of moving obstacles using fast-dynamic mixed integer linear programming. Aerospace Science and Technology, 50: 149-160. https://doi.org/10.1016/j.ast.2015.12.021

[20] Chang, K., Xia, Y., Huang, K. (2016). UAV formation control design with obstacle avoidance in dynamic three-dimensional environment. Springer Plus, 5: 1124. https://doi.org/10.1186/s40064-016-2476-y

[21] Zhu, L., Cheng, X., Yuan, F.G. (2016). A 3D collision avoidance strategy for UAV with physical constraints. Measurement: Journal of the International Measurement Confederation, 77: 40-49. https://doi.org/10.1016/j.measurement.2015.09.006

[22] Sun, J., Tang, J., Lao, S. (2017). Collision avoidance for cooperative UASs with optimized artificial potential field algorithm. IEEE Access, 5: 18382-18390. https://doi.org/10.1109/ACCESS.2017.2746752

[23] Nie, Z.L., Zhang, X.J., Guan, X.M. (2017). UAV formation flight based on artificial potential force in 3D environment. 2017 29th Chinese Control and Decision Conference (CCDC), Chongqing, China. https://doi.org/10.1109/CCDC.2017.7979468

[24] Sun, J., Tang, J., Lao, S. (2017). Collision avoidance for cooperative UAVs with optimized artificial potential field algorithm. IEEE Access, 5: 18382-18390. https://doi.org/10.1109/ACCESS.2017.2746752

[25] Bayat, F., Najafinia, S., Aliyari, M. (2018). Mobile robots path planning: Electrostatic potential field approach. Expert Systems with Applications, 100: 68-78. https://doi.org/10.1016/j.eswa.2018.01.050

[26] Zhou, Z., Wang, J., Zhu, Z., Yang, D., Wu, J. (2018). Tangent navigated robot path planning strategy using particle swarm optimized artificial potential field. Optik, 158: 639-651. https://doi.org/10.1016/j.ijleo.2017.12.169

[27] Zhang, J., Yan, J., Zhang, P. (2018). Fixed-wing UAV formation control design with collision avoidance based on an improved artificial potential field. IEEE Access, 6: 78342-78351. https://doi.org/10.1109/ACCESS.2018.2885003

[28] Zhu, X., Liang, Y., Yan, M. (2019). A flexible collision avoidance strategy for the formation of multiple unmanned aerial vehicles. IEEE Access, 7: 140743-140754. https://doi.org/10.1109/access.2019.2944160

[29] Lin, Y., Saripalli, S. (2015). Collision avoidance for UAVs using reachable sets. 2015 International Conference on Unmanned Aircraft Systems (ICUAS), Denver, CO, USA. https://doi.org/10.1109/ICUAS.2015.7152295