Cooperative conflict detection and resolution of civil unmanned aerial vehicles in metropolis

Abstract

Unmanned air vehicles have recently attracted attention of many researchers because of their potential civil applications. A systematic integration of unmanned air vehicles in non-segregated airspace is required that allows safe operation of unmanned air vehicles along with other manned aircrafts. One of the critical issues is conflict detection and resolution. This article proposes to solve unmanned air vehicles’ conflict detection and resolution problem in metropolis airspace. First, the structure of metropolis airspace in the coming future is studied, and the airspace conflict problem between different unmanned air vehicles is analyzed by velocity obstacle theory. Second, a conflict detection and resolution framework in metropolis is proposed, and factors that have influences on conflict-free solutions are discussed. Third, the multi-unmanned air vehicle conflict resolution problem is formalized as a nonlinear optimization problem with the aim of minimizing overall conflict resolution consumption. The safe separation constraint is further discussed to improve the computation efficiency. When the speeds of conflict-involved unmanned air vehicles are equal, the nonlinear safe separation constraint is transformed into linear constraints. The problem is solved by mixed integer convex programming. When unmanned air vehicles are with unequal speeds, we propose to solve the nonlinear optimization problem by stochastic parallel gradient descent–based method. Our approaches are demonstrated in computational examples.

Introduction

Unmanned air vehicles (UAVs) are promising to be applied in many civil fields, such as traffic monitoring and cargo delivery. Many UAV applications are predicted to be concentrated in metropolises. ¹ However, people are worrying about two main kinds of hazards when UAVs access into metropolis airspaces. First, UAVs are potential to cause serious injury to citizens in case they crash to the ground. Second, the mid-air collision between UAVs and manned airplanes or other objects in the metropolis airspace. Loss of separation between UAVs is one of the main causes of these accidents. ² The primary concern is to ensure the air safety when UAVs access into non-segregated airspace. UAVs should provide, first and foremost, the abilities of conflict detection and resolution (CD&R), especially in metropolis airspace. Considering the online requirement and characteristics of UAVs, the UAVs’ CD&R is truly intractable. ³

The CD&R aims to keep the safe separation of a set of aircrafts in a time interval [0, τ], where τ is the look ahead time window. The manned plane CD&R problem has been studied for many years. Air traffic safety is achieved through a hierarchical mechanism. ¹ However, UAVs are different with manned planes in several aspects. First, their traffic management system, regulations, and communication system are far less mature than manned aviation. Moreover, UAVs are different from manned planes in terms of load capacity, maneuverability, and pilot mode. In addition to that, most civil UAVs would fly in low-altitude airspace over the metropolis, where the environment is complex. As a result, it is inappropriate to directly apply CD&R method of manned aviation onto unmanned planes. ⁴

To improve the benefit of air traffic, the number of UAVs in the metropolis airspace is expected to be as large as possible. Therefore, an efficient CD&R system is a necessity. The emerging technologies, such as 4/5G technology and Automatic Dependent Surveillance-Broadcast (ADS-B), have spurred researches on CD&R of UAVs.^5,6 If civil UAVs are permitted to fly in low-altitude airspace, the advanced communication techniques would be capable to connect them with ground-based air traffic management (ATM) system. The ground-based short-term CD&R method would therefore be possible. Based on this idea, we propose to devise an efficient framework for CD&R problem of UAVs.

The CD&R is departed into two phases: conflict detection and conflict resolution. The conflict detection is to foresee possibly loss separation hazards between UAVs. ⁵ The conflict resolution is to resolve these dangers by maneuvers of related UAVs. The objective of conflict resolution is to guarantee the safe separation between UAVs and other objects and to minimize the additional consumption. ⁷ The safe separation can be guaranteed by long-term trajectory planning method and short-term reactive method. ⁸ In this article, we propose to study on the short-term conflict resolution problem. The velocity obstacle theory is applied to analyze the airspace conflict problem. We propose a hierarchical CD&R framework, in which we consider all the elements that may have influence on safe separation problem of UAVs, for example, UAVs’ states, tall buildings, manned aviation, and weather. The conflict resolution strategy is derived based on the analysis of related information. We propose a novel horizontal heading change–based conflict resolution method. The multi-UAV conflict resolution problem is formalized as a nonlinear optimization problem. The safe separation constraint is reduced into linear constraints when the speeds of conflict-involved UAVs are equal. Therefore, the conflict resolution policies can be obtained by mixed integral convex programming (MICP). We prove that the safe separation constraint function is monotonous in each continuous subspace when the speeds of UAVs are not equal. We propose to find the conflict-free solutions by combining stochastic parallel gradient descent (SPGD) method and the existing nonlinear optimization method.

In this article, former researches on UAVs’ airspace integration problem and UAVs’ CD&R problem are reviewed. The UAVs’ CD&R problem in metropolis airspace is discussed and the CD&R framework is devised. Meanwhile, the mathematical expressions on safe separation constraint and fuel consumption are given to formalize the CD&R problem as a nonlinear optimization problem. The safe separation constraint is further discussed in this article.

Related works

Researches on CD&R

Many conflict resolution algorithms have been proposed in aviation areas. The manned planes’ airspace CDR has already been studied for decades. Many mechanisms and technologies for manned planes’ flight safety can be used for reference when we study the UAVs’ CDR problem. Air traffic safety of manned planes is achieved through a hierarchical mechanism with different methodologies to make sure that planes operate at respective routes. ¹ CDR is solved as a trajectory optimization problem when conflicts are predicted to occur at a long distance.^7,9,10 This kind of algorithms aims to obtain the optimization trajectories to avoid conflict in minutes. When the conflict involved UAVs is in a small number, the rule-based conflict resolution method is applied to find safe separation solutions. When aircrafts are predicted to lose separation in miles, Traffic alert and Collision Avoidance System (TCAS)-II would coordinate with neighboring planes to find maneuvers with least hazard. ¹¹ When it comes to free-flight mode, onboard algorithms are devised to find the conflict-free solutions for multiple planes.^12,13

There are also many researches on UAVs’ CD&R problem. One type of these algorithms is trajectories’ optimization method, such as the genetic algorithm–based method,^14,15 bio-inspired collision-free algorithm, ¹⁶ centralized mixed integer quadratic programming, ¹⁷ and the mixed integer linear programming method. ¹⁸ These methods perform well in offline conflict-free path planning. However, it would cost several seconds to obtain conflict-free solution for a small number of UAVs. The computation time would rise at an exponential rate when the number of conflict-involved UAVs becomes large. Another type of CD&R method is reactive method. Reactive methods are typically required to respond to unexpected events or errors in the environment model.^19,20 The reactive method is efficient in keeping aerial vehicles apart. However, these methods consider more on keeping safe separation between UAVs than minimizing the conflict-free costs. The coordination-based optimization method becomes popular when the optimal reciprocal collision avoidance (ORCA) method was proposed by J Van den Berg et al. ²¹ This kind of method is efficient in reducing the conflict avoidance maneuver consumptions. ²²

The combination of the reactive algorithm and optimization planning method is appropriate to UAVs’ CD&R. J Alonso-Mora et al. ²³ propose cooperative collision avoidance algorithms for quadrotors. Their methods combine the centralized optimization method and ORCA algorithm. The objective is to minimize the sum of deviations of agents’ reference velocities from the preferred velocities. Their algorithms are efficient in computing suboptimal solutions.

As UAVs would be used in a wide variety of applications in future, we discuss on the UAVs’ CD&R problem in metropolis airspace. We formulate the UAVs’ CD&R problem as local centralized optimization problems and adopt cooperative maneuvers to avoid the predicted conflicts. The dynamic constraints of UAVs are considered, such as flight envelops, accelerations, and turn rate constraints. Our work is based on previous works on velocity obstacle theory ²¹ and our previous research. ⁴

ATM in metropolis airspace

As the air traffic becomes more and more congested, airspace management becomes crucial to improve the capacity of airspace, especially in the metropolis area. R Ehrmanntraut and S McMillan ²⁴ presented the airspace design process and tools, which aimed at improving the airspace management efficiency. R Geng and P Cheng studied on the dynamic airspace management problem and presented an integer program model to facilitate the utilization of air routes. They mainly focused on the manned aviation, where the air routes are predefined, which may be different with the application of UAVs. ²⁵ P Kopardekar et al. ²⁶ researched on the dynamic airspace configuration problem. The corridors-in-the-sky method and the dynamic resectorization method were proposed to make future airspace efficient. They divided the airspace into three categories, high-altitude airspace and two low-altitude airspace categories: super density metroplex areas and remaining low-altitude airspace. In the super density metropolis areas, meticulous measures were suggested to guarantee the safe separation. E Sunil et al. ¹ propose that as the personal aerial vehicles (PAVs) and UAVs are becoming more and more popular in the air traffic, the airspace structure of metropolis area is required to make dramatic change to account for the extreme traffic densities. Several concepts were proposed to describe different kinds of air traffic. In each air traffic mode, different conflict resolution maneuvers (heading change, speed change, and altitude change) are allowed.

Metropolis airspace conflict problem description

Discussion on the characteristics of metropolis airspace

To study the CDR problem of UAVs in metropolis airspace, we first discuss on the structure of metropolis airspace and entities that should be considered in the metropolis airspace. The metropolis airspace would be congested with large number of UAVs and PAVs in the coming future. In order to guarantee the airspace safety and improve the efficiency of airspace, the metropolis airspace should be divided into different levels from tens of meters to thousands of meters. ²⁶ We classify these airspaces as high-altitude airspaces, middle-altitude airspaces, and low-altitude airspaces, which are shown in Figure 1 (there are many levels in each type of airspace). Different aircrafts fly in different airspaces due to their characteristics. Commercial aircrafts and strategic UAVs (such as global hawks) fly along predefined air routes in high-altitude airspace. The general aviation planes fly mainly in free-flight mode in the middle-altitude airspace. Most civil UAVs would fly in low-altitude airspaces to process their tasks. There would be variable kinds of UAVs, such as cargo delivery UAVs, surveillance UAVs, and entertainment UAVs. Some UAVs would fly at an even lower altitude. However, when the UAVs are flying at low altitude, the CD&R problem would be even more crucial as there are tall buildings and balloons in the low-altitude airspace and so on. ¹

Figure 1.

Demonstration of a local part of metropolis airspace.

Different UAVs fly in different modes. Some UAVs are required to fly along preplanned paths while some UAVs fly in specific regions. The special airspaces can be air routes or regional airspaces. Air routes are rounded tubes, such as airways W_A and W_B in Figure 1. The regional airspaces are airspace regions with low and up altitude bounds, such as region R_A. To improve the efficiency of air traffic, the airspace should be dynamically sectioned according to the requirements of UAVs.

The low-altitude airspace over the metropolis is often complex, because there are many elements that have influence on the airspace environment. As shown in Figure 1, there are tall buildings and no-fly zone in the metropolis. In addition to that, there often are active objects, such as the advertising balloons and helicopters. The ATM system should take all these elements into consideration.

UAV conflict problem description

To guarantee the airspace safety, each UAV is defined with an exclusive airspace region. This region is defined as safe region D(p_i, r_i)

$$\mathrm{D}({\mathrm{p}}_{\mathrm{i}},{\mathrm{r}}_{\mathrm{i}})=\left\{\mathrm{p}|{\Vert {\mathrm{p}}_{\mathrm{x}}{-\mathrm{x}}_{\mathrm{i}},{\mathrm{p}}_{\mathrm{y}}{-\mathrm{y}}_{\mathrm{i}},{\mathrm{p}}_{\mathrm{z}}{-\mathrm{z}}_{\mathrm{i}}\Vert }_{\mathrm{2}}{<\mathrm{r}}_{\mathrm{i}}\right\}$$

(1)

D(p_i, r_i) denotes a sphere with radius r_i and centered at p_i = (x_i, y_i, z_i). The range of safe region is determined by the state and platform specialties (size, material and mobility) of UAV A_i.

When airspaces are allocated to specific users in given time period, they can use the allocated airspaces according to their reported plans. UAV users should release the permitted airspaces when time is out. In this way, the city airspace would be well-regulated. However, UAVs are probably disturbed by unsuspected events, such as bad weather condition. UAVs may have to deviate from the nominal paths in these circumstances, which results in loss separation dangers.

As the low-altitude airspaces are divided into many layers, vehicles in one level have no effect on UAVs in other levels. ¹ The airspace conflict problem is discussed in two-dimensional (2D) space. ²⁷ In the 2D space, UAVs move according to the following equations

$$\begin{array}{cc}\multicolumn{1}{c}{{\stackrel{·}{\mathrm{x}}}_{\mathrm{i}}}& ={\mathrm{v}}_{\mathrm{i}}\cos {\mathrm{\varphi }}_{\mathrm{i}}\hfill \\ \multicolumn{1}{c}{{\stackrel{·}{\mathrm{y}}}_{\mathrm{i}}}& ={\mathrm{v}}_{\mathrm{i}}\sin {\mathrm{\varphi }}_{\mathrm{i}}\hfill \\ \multicolumn{1}{c}{{\stackrel{·}{\mathrm{v}}}_{\mathrm{i}}}& ={\mathrm{a}}_{\mathrm{i}}\hfill \\ \multicolumn{1}{c}{{\stackrel{·}{\mathrm{\varphi }}}_{\mathrm{i}}}& ={\mathrm{w}}_{\mathrm{i}}\hfill \end{array}$$

(2)

where ${\varphi }_{\mathrm{i}}$ denotes the motion direction of A_i; v_i and w_i represent the linear and angular velocities, respectively; a_i is the linear acceleration of A_i. The state of A_i is characterized by $\mathrm{A}:{\mathrm{S}}_{\mathrm{A}}^{\mathrm{i}}({\mathrm{x}}_{\mathrm{i}},{\mathrm{y}}_{\mathrm{i}},{\mathrm{\varphi }}_{\mathrm{i}},{\mathrm{v}}_{\mathrm{i}})$ . Variables ${\mathrm{v}}_{\mathrm{i}}$ and ${\varphi }_{\mathrm{i}}$ are constrained by ${\mathrm{a}}_{\max }^{\mathrm{i}}$ and ${\mathrm{w}}_{{\max }^{\mathrm{i}}}$ . This article studies on conflict resolution by heading control. ${\mathrm{w}}_{\max }^{\mathrm{i}}$ is the maximum angular velocity. The range of heading change in A_i in time window $\tau$ is $[{\varphi }_i-{\mathrm{w}}_{\max }^{\mathrm{i}}\mathrm{\tau },{\mathrm{\varphi }}_{\mathrm{i}}+{\mathrm{w}}_{\max }^{\mathrm{i}}\mathrm{\tau }]$ .

We discuss on the velocity obstacle of UAVs according to the velocity obstacle theory.^21,28 In an analysis of the relationship between UAVs, their relationships are discussed in local coordinates. Such as shown in Figure 2. The position of A_j is taken as the original point of the local coordinates frame. The position of A_i is

$${\mathbf{P}}_{\mathbf{i}}=({\mathrm{x}}_{\mathrm{i}}-{\mathrm{x}}_{\mathrm{j}},{\mathrm{y}}_{\mathrm{i}}-{\mathrm{y}}_{\mathrm{j}})$$

(3)

Figure 2.

Velocity-obstacle set generate from an instantaneous encounter situation.

The velocity of A_j relative to A_i is

$${\overrightarrow{\mathbf{v}}}_{\mathbf{ji}}={\overrightarrow{\mathbf{v}}}_{\mathbf{j}}-{\overrightarrow{\mathbf{v}}}_{\mathbf{i}}=({\stackrel{·}{\mathrm{x}}}_{\mathrm{j}}-{\stackrel{·}{\mathrm{x}}}_{\mathrm{i}},{\stackrel{·}{\mathrm{y}}}_{\mathrm{j}}-{\stackrel{·}{\mathrm{y}}}_{\mathrm{i}})$$

(4)

The safe region of UAV A_i in 2D space is defined as a disk D(p_i, r_i), which is a circular region with radius $r_i$ centered at p_i. The separation distance between two UAVs A_i and A_j is ${\mathrm{r}}_{\mathrm{s}}^{\mathrm{ij}}$

$${\mathrm{r}}_{\mathrm{s}}^{\mathrm{ij}}=\max ({\mathrm{r}}_{\mathrm{i}},{\mathrm{r}}_{\mathrm{j}})$$

(5)

The velocity obstacle for UAVs ${\mathrm{VO}}_{\mathrm{i}|\mathrm{j}}^{\mathrm{\tau }}$ is the set of all relative velocities of A_i with respect to A_j that will result in a loss separation between A_i and A_j at some moment before time $\tau$ . As we have already defined the safe region D(p_i, r_i), the velocity obstacle can be defined as below

$${\mathrm{VO}}_{\mathrm{i}|\mathrm{j}}^{\mathrm{\tau }}=\{\mathrm{v}|\exists \mathrm{t}\in [0,\mathrm{\tau }]::\mathrm{tv}\in \mathrm{D}({\mathrm{p}}_{\mathrm{i}},{\mathrm{r}}_{\mathrm{s}}^{\mathrm{ij}})\}$$

(6)

The definition of the velocity obstacle implies that $\forall {\mathrm{v}}_{\mathrm{j}}\in {\mathrm{VO}}_{\mathrm{i}|\mathrm{j}}^{\mathrm{\tau }}$ would lead to undesired penetration of the ${\mathrm{D}}_{\mathrm{ij}}$ in $\tau$ , which is shown in Figure 2. Conversely, if ${\mathrm{v}}_{\mathrm{j}}\notin {\mathrm{VO}}_{\mathrm{i}|\mathrm{j}}^{\mathrm{\tau }}$ , A_i and A_j are guaranteed to be collision-free for at least $\tau$ time. The time window $\tau$ defines the finite time horizon to predict the loss separation dangers. The time window $\tau$ should consider both the dynamics of UAVs and efficiency, which is to allow UAVs to have enough time to maneuver and avoid unnecessary maneuvers. ¹⁸

CD&R framework design

In the low-altitude metropolis airspace, we anticipate that UAVs would equip with communication devices, such as the ADS-B and 4/5G units. The ground ATM system keeps on inspecting UAVs in virtue of these communication devices. The control time period is ${\mathrm{t}}_{\mathrm{c}}$ . As we stated above, the airspace environment is complex; therefore, the conflict detection system should comprehensively consider these elements, as shown in Figure 3.

Figure 3.

Conflict detection and resolution framework.

In each control period, the CD&R system obtains information from the environment. The information includes the states of UAVs, the states of low-altitude manned planes, the geography and weather information of local region, and information about airspace. The state information of UAVs include not only the motion states of UAVs but also information about their tasks, whether they have fulfilled their tasks and the types of their tasks. After the information is obtained, the system would then validate the lose separation dangers of every UAV in the local airspace. The dangers include loss separation with manned planes or other UAVs, collision with tall buildings, flying into no-fly zones, bad weather regions, and so on.

Conflict detection

Many people have discussed on the problem of detecting the proximity traffics. ⁵ It is inefficient to check the relationship between each pair of UAVs in the air at each time period t_c when there are plenty of UAVs in the metropolis airspace in the future. The states of UAVs are unable to change dramatically. That is to say, two UAVs would not get in proximity to each other in a short time period if they are far apart currently. We devise a conflict detection mechanism considering both the safety requirement and computation efficiency. The main idea of this mechanism is to check the relationships between proximity UAVs with high frequency and to validate the states between UAVs at low frequency if they are far apart. The system stores proximity UAV pairs in a memory unit. We define it as watching unit. The system would check the relationship between these UAV pairs in each control time period. After conflicts are ascertained, the conflict information would be recorded in conflict matrix (CM). Meanwhile, the relationships between all UAV pairs in the local airspace are stored in another memory unit. We name it as global unit. The system would update information in global unit offline. If there are UAV pairs that may potentially meet with conflict in the coming future, these UAV pairs would be added to the watching unit. This method is also available to conflict detection between UAVs and other objects.

The CM records the conflict information in the local airspace UAV pairs; there may be multiple safe separation constraints among one given UAV and other UAVs, which is shown in Figure 4. In order to give an explicit description on the multi-UAV conflict scenario, we use the graph $\mathrm{G}(\mathrm{t})=(\mathrm{V},\mathrm{E}(\mathrm{t}))$ to express the relationships among UAVs, where V = {1,…, N} is the vertex set. ⁴ Each vertex denotes one UAV A_i. $E(t)=\{(j,i)|c{r}_{\mathrm{ij}}=1\}$ is the corresponding edge set, which expresses the conflict relations. $c{r}_{\mathrm{ij}}=1$ means A_i and A_j are potential to loss separation in $\tau$ time. In this article, $\mathrm{G}(\mathrm{t})$ is situation-specific. The conflict clusters are derived based on the graph $\mathrm{G}(\mathrm{t})$ .

Figure 4.

(a) A configuration with six UAVs. Their velocities are indicated by arrows. (b) The graphs generated based on the states.

Conflict cluster

A conflict cluster is a sub-graph formed by the transitive closure of aircraft pairs in conflict. UAVs in the local airspace can be departed into a number of conflict clusters in the local airspace. For example, in Figure 4(b), the conflict graph contains two conflict clusters based on current states. The multi-UAV CM is derived from the adjacency matrix of the constraint cluster.

Conflict analysis and conflict resolution strategy decision

After conflict information is ascertained, the system would consider several problems before searching the safe separation solutions. Three solutions for conflict resolution are proposed as control over altitude, velocity, and heading. ²⁹ However, there are different types of conflict dangers between UAVs, as shown in Figure 5. Different types of conflict can be resolved by different maneuver strategies, for example, the head on conflict and the conflict that two UAVs fly in the same path can be resolved by horizontal heading change and vertical altitude change. The left/right converge can be resolved by heading change, altitude change, or speed change. When UAVs are encountering with static obstacles, they have to make horizontal heading change or vertical altitude changes. The CD&R system should classify the conflict types between UAV pairs and ascertain the conflict resolution strategy.

Figure 5.

Encounter types’ definition: (a) head on, (b) left/right converge, (c) same path, and (d) encounter with static obstacle (bad weather, buildings, no-fly zone).

The local environment should be considered when ascertaining conflict resolution strategy. In the airspace, the conflict resolution policy may have influences not only on conflict-involved UAVs but also on other UAVs around them. Inappropriate maneuvers may lead to new conflict. As shown in Figure 4, if A₆ and A₁ take inappropriate maneuvers, they would probability meet with conflict in the coming several minutes. Therefore, appropriate measures should be taken to resolve the conflict.

In the airspace, each UAV is designated with a distinct task and they are assigned with special airspace. Different UAVs are in different situations in the conflict. For example, some UAVs are processing their tasks while some UAVs have already fulfilled their tasks. The deviations from their nominal paths would have different influences on them. The conflict detection system should find a policy to weigh the influences on conflict-related UAVs. We define coefficient ${\rho }_i$ to depict the unit loss of A_i for deviating from nominal path.

Cooperative conflict resolution

As we stated above, conflicts should be carefully analyzed before devising conflict resolution maneuvers. The airspace conflict can be resolved by various kinds of methods. The speed control method maybe inefficient when the distances between UAVs and other objectives are close; in addition to that, the speed control method cannot resolve many kinds of conflict between UAVs. As the airspace is divided into different levels, the main strategy would be planar heading change rather than altitude control. In this article, we study on conflict resolution method by heading control.

Conflict resolution condition

The objective of CDR is to minimize the influence of de-confliction maneuvers on other aerial vehicles and to minimize the fuel consumption. When the speed of agents is slow, the conflict in $\tau$ time is avoided by choosing v_i and v_j to be out of the gray region in Figure 2. ²¹ However, in the real environment, the dynamics of UAVs would largely restrict the mobility of UAVs as the speed of UAVs is high. The computation load would increase if UAVs make minor turnings in each time step. In addition to that, this strategy would increase the loss separation probability because of uncertainty. We determine that ${\overrightarrow{\mathbf{v}}}_{\mathbf{ji}}$ should be modified to be tangent with D_ij in conflict resolution process. ³⁰ As we assume that V_i and V_j keep constant, the displacement of UAV A_i relative to A_j in $[0,\tau ]$ is

$${\overrightarrow{\mathbf{S}}}_{\mathbf{ji}}=(({\stackrel{·}{\mathrm{x}}}_{\mathrm{j}}-{\stackrel{·}{\mathrm{x}}}_{\mathrm{i}})\tau ,({\stackrel{·}{\mathrm{y}}}_{\mathrm{j}}-{\stackrel{·}{\mathrm{y}}}_{\mathrm{i}})\tau )$$

(7)

The direction change cannot be achieved instantaneously. We assume that the tracking system can track planned traces within acceptable error range, as shown in Figure 6. When we consider the tracking capability of UAVs, the maximum traceable heading degree in time period $[0,\tau ]$ is ${\phi }_{\max }^i(\tau )$ .

Figure 6.

Demonstration of UAV path tracking process. The planned paths are shown as dot dash lines, whereas the real tracking paths are shown as dotted lines. The maximum maneuver heading degree is restricted by the tracking ability of each UAV.

Cooperative pairwise conflict resolution constraint

As multi-UAV conflict is constructed by many pairwise conflicts, we discuss on the safe separation constraints of pairwise UAVs first. In the local coordinate, the displacement of A_j is ${\overrightarrow{\mathbf{S}}}_{\mathbf{ji}}$ . The headings of A_i and A_j are ${\mathrm{\varphi }}_{\mathrm{i}}+{\mathrm{\phi }}_{\mathrm{i}}$ and ${\mathrm{\varphi }}_{\mathrm{j}}+{\mathrm{\phi }}_{\mathrm{j}}$ when they take heading maneuvers $({\mathrm{\phi }}_{\mathrm{i}},{\mathrm{\phi }}_{\mathrm{j}})$ , as shown in Figure 7.

Figure 7.

Two-UAV cooperative conflict resolution schema.

${\overrightarrow{\mathbf{S}}}_{\mathbf{ji}}$ changes to ${\overrightarrow{\mathbf{S}}\prime }_{\mathrm{ji}}$ . The terminal point of ${\overrightarrow{\mathbf{S}}\prime }_{\mathrm{ji}}$ is defined as E_j

$$\begin{array}{l}{E}_j=\tau \left({\mathrm{v}}_{\mathrm{j}}\cos ({\varphi }_{\mathrm{j}}+{\phi }_{\mathrm{j}})-{\mathrm{v}}_{\mathrm{i}}\cos ({\varphi }_{\mathrm{i}}+{\phi }_{\mathrm{i}})\right),\\ \tau \left({\mathrm{v}}_{\mathrm{j}}\sin ({\varphi }_{\mathrm{j}}+{\phi }_{\mathrm{j}})-{\mathrm{v}}_{\mathrm{i}}\sin ({\varphi }_i+{\phi }_i)\right)\end{array}$$

(8)

$\overrightarrow{\mathrm{S}}{\text{'}}_{\mathrm{ji}}$ should be tangent with ${\mathrm{D}}_{\mathrm{ij}}$ . The slope of $\overrightarrow{\mathrm{S}}{\text{'}}_{\mathrm{ji}}$ is

$$\mathrm{k}({\mathrm{\phi }}_{\mathrm{i}},{\mathrm{\phi }}_{\mathrm{j}})=\frac{{\mathrm{v}}_{\mathrm{j}}\sin ({\mathrm{\varphi }}_{\mathrm{j}}+{\mathrm{\phi }}_{\mathrm{j}})-{\mathrm{v}}_{\mathrm{i}}\sin ({\mathrm{\varphi }}_{\mathrm{i}}+{\mathrm{\phi }}_{\mathrm{i}})}{{\mathrm{v}}_{\mathrm{j}}\cos ({\mathrm{\varphi }}_{\mathrm{j}}+{\mathrm{\phi }}_{\mathrm{j}})-{\mathrm{v}}_{\mathrm{i}}\cos ({\mathrm{\varphi }}_{\mathrm{i}}+{\mathrm{\phi }}_{\mathrm{i}})}$$

(9)

The minimum distance between ${\mathrm{A}}_{\mathrm{i}}$ and $\overrightarrow{\mathrm{S}}{\text{'}}_{\mathrm{ji}}$ is

$$\mathrm{d}({\mathrm{\phi }}_{\mathrm{i}},{\mathrm{\phi }}_{\mathrm{j}})=\frac{|-{\mathrm{k}}_{\mathrm{ij}}{\mathrm{A}}_{\mathrm{x}}^{\mathrm{i}}+{\mathrm{A}}_{\mathrm{y}}^{\mathrm{i}}|}{\sqrt{1+{\mathrm{k}}_{\mathrm{ij}}^2}}$$

(10)

To keep the safe separation, the maneuver degree of conflict relevant UAVs $({\mathrm{\phi }}_{\mathrm{i}},{\mathrm{\phi }}_{\mathrm{j}})$ should satisfy

$$\mathrm{d}({\mathrm{\phi }}_{\mathrm{i}},{\mathrm{\phi }}_{\mathrm{j}})\ge {\mathrm{r}}_{\mathrm{s}}^{\mathrm{ij}}$$

(11)

Obstacle avoidance

There are many no-fly zones in metropolis area, such as military facilities and impacted area. There are also many tall buildings in metropolis. UAVs should avoid fly too close to these builds and no-fly zones. We discuss on how to avoid these objects in this section. We regard tall builds and no-fly zones as statics obstacles in this paper. We can incorporate the obstacle avoidance problem in velocity obstacle–based conflict resolution algorithms. We basically follow the same approach as above, with a key difference being that obstacles do not move, so UAVs should take full responsibility of avoiding obstacles. We assume that these obstacles are convex in geometric shape. The statics obstacle avoidance is solved by avoiding fly into the margins of obstacles. In the 2D environment, there are two edges from the point of view of one given UAV. The range between these two edge points is regarded as unsafe, which is shown in Figure 8.

Figure 8.

(a) A configuration of A_i and a static obstacle O and (b) geometric construction of the velocity obstacle.

Then, the velocity obstacle ${\mathrm{VO}}_{A_i/O}^{\tau }$ induced by the obstacle O is defined as ²¹

$${\mathrm{VO}}_{A_i/O}^{\tau }=\{v|\exists t\in [0,\tau ]::\mathrm{tv}\in O\oplus -D(p_{A_i},r_{A_i})\}$$

(12)

A_i will collide with obstacle O within $\tau$ time if $v_i$ is inside ${\mathrm{VO}}_{A_i/O}^{\tau }$ and it will be collision-free for at least $\tau$ time if $v_i$ is outside ${\mathrm{VO}}_{A_i/O}^{\tau }$ . Hence, we define the region of permitted velocities for A with respect to obstacle O as the complement of ${\mathrm{VO}}_{A_i/O}^{\tau }$ . To guarantee the safety, the velocity of A_i should tangent with ${\mathrm{VO}}_{A_i/O}^{\tau }$ . Therefore, the flyable range is departed as two parts

$${\mathrm{\phi }}_{\mathrm{i}}>{\mathrm{\delta }}_{\mathrm{l}}\mathrm{U}{\mathrm{\phi }}_{\mathrm{i}}<{\mathrm{\delta }}_{\mathrm{r}}$$

(13)

where ${\mathrm{\delta }}_{\mathrm{l}}$ and ${\mathrm{\delta }}_{\mathrm{r}}$ are the minimum heading change degrees of A_i.

Cost function for conflict resolution

The conflict-free maneuvers would lead to additional flight distances of UAVs, which would lead to additional fuel consumptions and time delay. The additional fuel consumption is expressed as

$${\mathrm{f}}_{\mathrm{add}\_\mathrm{fuel}}({\phi }_{\mathrm{i}},\mathrm{t})={\mathrm{f}}_{\mathrm{conflict}\mathrm{free}\_\mathrm{fuel}}({\phi }_{\mathrm{i}},\mathrm{t})-{\mathrm{f}}_{\mathrm{org}\_\mathrm{fuel}}({\phi }_{\mathrm{i}},\mathrm{t})$$

(14)

To find conflict-free solutions with the minimum additional consumptions, the preference directions of conflict-related UAVs are defined pointing to their next waypoints, as shown in Figure 9, which guarantee UAVs to return to their nominal paths as soon as possible.

Figure 9.

Example of the conflict resolution maneuver.

As UAVs’ speeds keep constant, the additional fuel consumptions are approximated by additional flight paths. Obviously, larger deviation angle would result in greater deviation when $t$ is constant. We assume that the distances of additional fly paths are in proportion to the distances of deviations from nominal paths. We define constant coefficients $l_{B_1{R}_1}/d_{B_1{F}_1}=l_{B_2{R}_2}/d_{B_2{F}_2}=\alpha$ and $d_{F_1{R}_1}/d_{B_1{F}_1}=d_{F_2{R}_2}/d_{B_2{F}_2}=\gamma$ . $l_{\mathrm{BR}}$ is the length of the return path and $d_{\mathrm{FR}}$ is the length of the projection of $l_{\mathrm{BR}}$ onto the nominal path. Function (14) is deduced as

$${\mathrm{f}}_{add\_fuel}({\phi }_{\mathrm{i}},\mathrm{t})=\beta vt\left(1+\sqrt{1+{(\alpha -\gamma )}^2}\sin (\left|{\phi }_{\mathrm{i}}+{\phi }_{\mathrm{d}}\right|-\eta )\right)$$

(15)

where $\beta$ is a constant coefficient. $\eta =\arcsin (1/\sqrt{1+{(\alpha -\gamma )}^2})$ . We define that ${\phi }_{\mathrm{i}}<0$ if A_i makes right turn, ${\phi }_{\mathrm{i}}>0$ if A_i makes left turn. ${\phi }_{\mathrm{d}}>0$ if the preference direction is at the right side of current heading direction; ${\phi }_{\mathrm{d}}<0$ if the preference direction is at the left side of current heading direction.

When there are statics obstacles in the local airspace, the distances of conflict resolution detours should take these obstacles into consideration. As the shapes of static obstacles are not symmetrical from the point of view of one given aircraft, the heading change direction would have effect on the conflict-free detour time period. Such that the edge $E_{\mathrm{near}}$ is closer than $E_{\mathrm{far}}$ in Figure 8. A_i would take a longer time to steer clear of $E_{\mathrm{far}}$ than $E_{\mathrm{near}}$ . The differences on maneuver time would lead to different additional fly distances.

As $\eta$ and ${\phi }_{\mathrm{d}}$ are defined constants, the value of equation (15) depends on ${\mathrm{\phi }}_{\mathrm{i}}$ . We define that ${\phi }_{\mathrm{i}}\in [-\pi /2,\pi /2],\forall \mathrm{i}\in \mathrm{n}$ in time window $[0,\tau ]$ . If $\left|{\phi }_d\right|<{\phi }_{\max }^i(\tau )$ . Function (15) is convex in $[-{\phi }_{\max }^i(\tau ),{\phi }_{\mathrm{d}}]$ and $[{\phi }_{\mathrm{d}},{\phi }_{\max }^i(\tau )]$ , respectively. If $\left|{\phi }_{\mathrm{d}}\right|>{\phi }_{\max }^i(\tau )$ , function (15) is convex in the range $[-{\phi }_{\max }^i(\tau ),{\phi }_{\max }^i(\tau )]$ .

Multi-UAV cooperative conflict resolution algorithm

The multi-UAV cooperative conflict resolution problem is casted to a nonlinear optimization problem with nonlinear constraints

$$\min F=\sum _{i=1}^n{\mathrm{f}}_{\mathrm{add}\_\mathrm{fuel}}({\phi }_{\mathrm{i}},t)\times {\rho }_i$$

(16)

S.t.

$$\begin{array}{c}{\mathrm{d}}_{\mathrm{ij}}({\phi }_{\mathrm{i}},{\phi }_{\mathrm{j}})>{\mathrm{r}}_{\mathrm{s}}^{\mathrm{ij}}{\mathrm{d}}_{\mathrm{ij}}\in \mathbf{CM}\cap \mathrm{g}\ne 0,\mathrm{i},\mathrm{j}\in [1,2,\dots ,\mathrm{n}]\hfill \\ {\phi }_i\in [-{\phi }_{\max }^i(\tau ),{\phi }_{\max }^i(\tau )]\hfill \\ {\phi }_{\mathrm{i}}>{\delta }_{\mathrm{l}}^{{\mathrm{q}}_{\mathrm{i}}}\cap {\phi }_{\mathrm{i}}<{\delta }_{\mathrm{r}}^{{\mathrm{q}}_{\mathrm{i}}},\mathrm{i}\in [1,\dots ,\mathrm{n}],{\mathrm{q}}_{\mathrm{i}}\in [1,\dots ,{\mathrm{m}}_{\mathrm{i}}]\hfill \end{array}$$

(17)

where ${\mathrm{m}}_{\mathrm{i}}$ is the number of static obstacles that A_i may collide into in $\tau$ time. The nonlinear optimization problem could be solved by commercial nonlinear optimization solvers, such as the sparse nonlinear optimizer (SNOPT). ³¹ However, these solvers are not agile in solving specific problems and may lead to too much time consumption. In order to solve this nonlinear optimization efficiently, we make further discussion on the safe separation constraint.

We obtain the equation $\mathrm{d}({\mathrm{\phi }}_{\mathrm{i}},{\mathrm{\phi }}_{\mathrm{j}})={\mathrm{r}}_{\mathrm{s}}^{\mathrm{ij}}$ from inequality (11). The equation is expanded as

$$({{\mathrm{A}}_{\mathrm{x}}}^2-{\mathrm{r}}_{\mathrm{s}}){\mathrm{k}}^2-2{\mathrm{A}}_{\mathrm{x}}^{\mathrm{i}}{\mathrm{A}}_{\mathrm{y}}^{\mathrm{i}}\mathrm{k}+{\mathrm{A}}_{\mathrm{y}}^{\mathrm{i}2}-{\mathrm{r}}_{\mathrm{s}}^{\mathrm{ij}2}=0$$

(18)

The discriminant of quadratic equation (18) is $\mathrm{\Delta }=2{\mathrm{r}}_{\mathrm{s}}^{\mathrm{ij}}\sqrt{{\mathrm{A}}_{\mathrm{x}}^{\mathrm{i}2}+{\mathrm{A}}_{\mathrm{y}}^{\mathrm{i}2}-{\mathrm{r}}_{\mathrm{s}}^{\mathrm{ij}2}}$ . As the initial distance between UAVs should be larger than ${\mathrm{r}}_{\mathrm{s}}^{\mathrm{ij}}$ , it means that there is solution for (18), therefore, $\Delta >0$ . The roots of equation (18) are

$${\mathrm{k}}_{\mathrm{ij}}^1=\frac{2{\mathrm{A}}_{\mathrm{y}}^{\mathrm{i}}{\mathrm{A}}_{\mathrm{x}}^{\mathrm{i}}-\mathrm{\Delta }}{2({\mathrm{A}}_{\mathrm{x}}^{\mathrm{i}2}-{\mathrm{r}}_{\mathrm{s}}^{\mathrm{ij}2})},{\mathrm{k}}_{\mathrm{ij}}^2=\frac{2{\mathrm{A}}_{\mathrm{y}}^{\mathrm{i}}{\mathrm{A}}_{\mathrm{x}}^{\mathrm{i}}+\mathrm{\Delta }}{2({\mathrm{A}}_{\mathrm{x}}^{\mathrm{i}2}-{\mathrm{r}}_{\mathrm{s}}^{\mathrm{ij}2})}$$

(19)

To guarantee the safe separation, the feasible solution ranges are determined by k₁ and k₂.

• 1. When ${\mathrm{A}}^2<{\mathrm{r}}_{\mathrm{s}}^{\mathrm{i}{\mathrm{j}}^2}$ , the feasible solution ${\mathrm{k}}_{\mathrm{ij}}^{\mathrm{feasible}}$ should satisfy

$${\mathrm{k}}_{\mathrm{ij}}^{\mathrm{feasible}}\in ({\mathrm{k}}_{\mathrm{ij}}^2{,\mathrm{k}}_{\mathrm{ij}}^1)$$

(20)

• 2. When ${\mathrm{A}}^2>{\mathrm{r}}_{\mathrm{s}}^{\mathrm{i}{\mathrm{j}}^2}$ , the feasible solutions should satisfy

$${\mathrm{k}}_{\mathrm{ij}}^{\mathrm{feasible}}\in \{{\mathrm{k}}_{\mathrm{ij}}|{\mathrm{k}}_{\mathrm{ij}}\in (-00{,\mathrm{k}}_{\mathrm{ij}}^1)\mathrm{U}({\mathrm{k}}_{\mathrm{ij}}^2,+00)\}$$

(21)

As the tangent function satisfies the following equation

$$\underset{\phi \to {\frac{\pi }{2}}^{+}}{lim}\tan (\phi )=+\infty ,\underset{\phi \to {\frac{\pi }{2}}^{-}}{lim}\tan (\phi )=-\infty$$

(22)

In the second case, the feasible heading of $\overrightarrow{\mathrm{S}}{\text{'}}_{\mathrm{ji}}$ could be $\mathrm{\pi }/2+\mathrm{k}\mathrm{\pi },\mathrm{k}\in \mathrm{Z}$ , which make k to be discontinuous at $\pi /2+k\pi$ . However, constraint (21) describes similar feasible solution space of $({\phi }_{\mathrm{i}},{\phi }_{\mathrm{j}})$ as in equation (20), which is shown in Figure 10. Therefore, the solution space for Case 2 is continuous.

Figure 10.

Feasible space of heading direction of relative displacement: (a) ${\mathrm{A}}_{\mathrm{x}}^{\mathrm{i}}<{\mathrm{r}}_{\mathrm{s}}^{\mathrm{ij}}$ and (b) ${\mathrm{A}}_{\mathrm{x}}^{\mathrm{i}}>{\mathrm{r}}_{\mathrm{s}}^{\mathrm{ij}}$ .

As shown in Figure 10, the feasible directions of $\overrightarrow{\mathbf{S}}{\prime }_{\mathrm{ji}}$ are departed into two parts, A and B. The solver needs to search the optimal solutions in these two sections:

1. Conflict resolution for UAVs with equal speeds. In metropolis airspace, some homogeneous UAVs may fly at almost the same airspeed. In this specific circumstance, we study on solving solutions of multi-UAV conflict resolution when UAVs are with the same airspeeds.

The slope function (9) can be simplified by the rules of sum to product formula in trigonometric function when the speeds of UAVs are equal

$${\mathrm{k}}_{\mathrm{ij}}=-\cot \left(\frac{{\mathrm{\varphi }}_{\mathrm{j}}+{\mathrm{\phi }}_{\mathrm{j}}+{\mathrm{\varphi }}_{\mathrm{i}}+{\mathrm{\phi }}_{\mathrm{i}}}{2}\right)$$

(23)

k_ij is the function of ${\mathrm{\phi }}_{\mathrm{i}}$ and ${\mathrm{\phi }}_{\mathrm{j}}$ . The feasible solution space of $({\mathrm{\phi }}_{\mathrm{i}},{\mathrm{\phi }}_{\mathrm{j}})$ would be determined when the feasible space of k_ij is determined.

In constraint (20), ${\mathrm{\phi }}_{\mathrm{i}}$ and ${\phi }_{\mathrm{j}}$ should satisfy the inequalities

$$\{\begin{array}{c}-\cot \left(\frac{{\mathrm{\varphi }}_{\mathrm{j}}+{\mathrm{\phi }}_{\mathrm{j}}+{\mathrm{\varphi }}_{\mathrm{i}}+{\mathrm{\phi }}_{\mathrm{i}}}{2}\right){<\mathrm{k}}_{\mathrm{ij}}^1\hfill \\ \multicolumn{1}{c}{-\cot \left(\frac{{\varphi }_{\mathrm{j}}+{\phi }_{\mathrm{j}}+{\varphi }_{\mathrm{i}}+{\phi }_{\mathrm{i}}}{2}\right){>\mathrm{k}}_{\mathrm{ij}}^2}\end{array}$$

(24)

The feasible solutions are

$${\mathrm{\phi }}_{\mathrm{j}}+{\mathrm{\phi }}_{\mathrm{i}}>2{\mathrm{h}}_{\mathrm{ij}}^1-({\mathrm{\varphi }}_{\mathrm{j}}+{\mathrm{\varphi }}_{\mathrm{i}})\cap {\mathrm{\phi }}_{\mathrm{j}}+{\mathrm{\phi }}_{\mathrm{i}}<2{\mathrm{h}}_{\mathrm{ij}}^2-({\mathrm{\varphi }}_{\mathrm{j}}+{\mathrm{\varphi }}_{\mathrm{i}})$$

(25)

where ${\mathrm{h}}_{\mathrm{ij}}^1=\mathrm{ac}\cot (-{\mathrm{k}}_{\mathrm{ij}}^1)$ and ${\mathrm{h}}_{\mathrm{ij}}^2=\mathrm{arc}\cot (-{\mathrm{k}}_{\mathrm{ij}}^2)$ . We anticipate that both two UAVs can take right of left turn; therefore, the maneuver range is ${\mathrm{\phi }}_{\mathrm{j}},{\mathrm{\phi }}_{\mathrm{i}}\in [-\mathrm{\pi },\mathrm{\pi }]$ and the maneuver range of ${\mathrm{\phi }}_{\mathrm{j}}+{\mathrm{\phi }}_{\mathrm{i}}$ is $[-2\pi ,2\pi ]$ . The feasible range is illustrated in Figure 11. The feasible solution spaces are shown by colored lines.

Figure 11.

Feasible solutions.

Half the feasible space is

$${\mathrm{\phi }}_{\mathrm{j}}+{\mathrm{\phi }}_{\mathrm{i}}\in [2{\mathrm{h}}_{\mathrm{ij}}^1-({\mathrm{\varphi }}_{\mathrm{j}}+{\mathrm{\varphi }}_{\mathrm{i}}),2(\mathrm{\pi }+{\mathrm{h}}_{\mathrm{ij}}^2)-({\mathrm{\varphi }}_{\mathrm{j}}+{\mathrm{\varphi }}_{\mathrm{i}})]$$

(26)

The other half of continuous feasible space is

$${\mathrm{\phi }}_{\mathrm{j}}+{\mathrm{\phi }}_{\mathrm{i}}\in [-2\mathrm{\pi }+2{\mathrm{h}}_{\mathrm{ij}}^1-({\mathrm{\varphi }}_{\mathrm{j}}+{\mathrm{\varphi }}_{\mathrm{i}}),2{\mathrm{h}}_{\mathrm{ij}}^2-({\mathrm{\varphi }}_{\mathrm{j}}+{\mathrm{\varphi }}_{\mathrm{i}})]$$

(27)

Therefore, the feasible solution for ${\mathrm{\phi }}_{\mathrm{j}}$ and ${\mathrm{\phi }}_{\mathrm{i}}$ should satisfy

$$\begin{array}{l}{\phi }_{\mathrm{j}}+{\phi }_{\mathrm{i}}\in \left[\mathrm{2}(-\pi {\mathrm{+h}}_{\mathrm{ij}}^1)-({\varphi }_{\mathrm{j}}+{\varphi }_{\mathrm{i}}),{\mathrm{2h}}_{\mathrm{ij}}^{\mathrm{2}}-({\varphi }_{\mathrm{j}}+{\varphi }_{\mathrm{i}})\right]\\ \mathrm{U}\left[{\mathrm{2h}}_{\mathrm{ij}}^1-({\varphi }_{\mathrm{j}}+{\varphi }_{\mathrm{i}}),\mathrm{2}(\pi {\mathrm{+h}}_{\mathrm{ij}}^{\mathrm{2}})-({\varphi }_{\mathrm{j}}+{\varphi }_{\mathrm{i}})\right]\end{array}$$

(28)

In constraint (21), the feasible solutions ${\phi }_{\mathrm{j}}$ and ${\phi }_{\mathrm{i}}$ are in the following range

$$\begin{array}{l}{\phi }_{\mathrm{j}}+{\phi }_{\mathrm{i}}\in \left[2(-\pi +{\mathrm{h}}_{\mathrm{ij}}^2)-({\varphi }_{\mathrm{j}}+{\varphi }_{\mathrm{i}}),2(-\pi +{\mathrm{h}}_{\mathrm{ij}}^1)-({\varphi }_{\mathrm{j}}+{\varphi }_{\mathrm{i}})\right]\\ \mathrm{U}\left[{\mathrm{2h}}_{\mathrm{ij}}^{\mathrm{2}}-({\varphi }_{\mathrm{j}}+{\varphi }_{\mathrm{i}}),{\mathrm{2h}}_{\mathrm{ij}}^1-({\varphi }_{\mathrm{j}}+{\varphi }_{\mathrm{i}})\right]\end{array}$$

(29)

The safe separation constraint (11) is replaced by linear inequality constraints (28) and (29). The feasible solution space is departed into two convex regions for each pairwise conflict. The nonlinear optimization problem is casted into an MICP problem

$$\min F=\sum _{i=1}^n{\mathrm{f}}_{\mathrm{add}\_\mathrm{fuel}}({\phi }_i,t)\times {\rho }_i$$

(30)

S.t.

$$\begin{array}{c}2(-\pi +h_{\mathrm{ij}}^2)-({\varphi }_j+{\varphi }_i)-({\phi }_j+{\phi }_i)\le (1-s_{\mathrm{ij}}^1)M_1^{\mathrm{ij}}\hfill \\ ({\phi }_j+{\phi }_i)-(2(-\pi +h_{\mathrm{ij}}^1)-({\varphi }_j+{\varphi }_i))\le (1-s_{\mathrm{ij}}^1)M_1^{\mathrm{ij}}\hfill \\ 2h_{\mathrm{ij}}^2-({\varphi }_j+\mathrm{rr}{\varphi }_i)-({\phi }_j+{\phi }_i)\le (1-s_{\mathrm{ij}}^2)M_{\mathrm{ij}}^2\hfill \\ ({\phi }_j+{\phi }_i)-(2h_{\mathrm{ij}}^1-({\varphi }_j+{\varphi }_i))\le (1-s_{\mathrm{ij}}^2)M_2^{\mathrm{ij}}\hfill \\ \sum _{k=1}^2{s}_{\mathrm{ij}}^k=1,i,j\in [1,\dots ,n]\hfill \end{array}$$

$$\begin{array}{c}\multicolumn{1}{c}{{\phi }_i\in [-{\phi }_{\max }^i(\tau ),{\phi }_d]U[{\phi }_d,{\phi }_{\max }^i(\tau )]\mathrm{if}\left|{\phi }_d\right|<{\phi }_{\max }^i(\tau )}\\ \multicolumn{1}{c}{{\phi }_i\in [-{\phi }_{\max }^i(\tau ),{\phi }_{\max }^i(\tau )]\mathrm{if}\left|{\phi }_d\right|\ge {\phi }_{\max }^i(\tau ),i\in [1,\dots ,n]}\end{array}$$

$${\mathrm{\phi }}_{\mathrm{i}}>{\mathrm{\delta }}_{\mathrm{l}}^{\mathrm{q}}\cap {\mathrm{\phi }}_{\mathrm{i}}<{\mathrm{\delta }}_{\mathrm{r}}^{\mathrm{q}},\mathrm{i}\in [1,\dots ,\mathrm{n}],\mathrm{q}\in [1,\dots ,\mathrm{m}]$$

(31)

MICP problem can be solved by the existing commercial solver efficiently when the number of conflict-involved UAVs is limited. As the global optimal solution requires the solver to search all feasible subspaces, the computation time would increase as the number of UAVs increases. Therefore, when conflict-involved UAVs are in a large number, the objective of CD&R is reduced to find a suboptimal solution by searching some subspaces rather than all the subspaces. We propose that all UAVs would turn to right when they meet with the conflict.

• 2. Conflict resolution for UAVs with unequal speeds. In most cases, the conflict-related UAVs are heterogeneous and with unequal speeds. In this situation, we should solve the nonlinear optimization problem. However, most of the efficient nonlinear solvers are required to start from feasible solutions. The feasible solution should satisfy constraints (20) and (21). In order to devise the algorithm that can find the initial feasible solution efficiently, we make further discussion on function (9). We prove $k({\phi }_{\mathrm{i}},{\phi }_{\mathrm{j}})$ is monotonous in every continuous space.

Proof

We first make partial differential on $k({\phi }_{\mathrm{i}},{\phi }_{\mathrm{j}})$ , $((\partial k/\partial {\phi }_j),(\partial k/\partial {\phi }_i))$ . k would probably reach the local extreme at $({\phi }_i^t,{\phi }_j^t)$ if $((\partial k/\partial {\phi }_j^t)=(\partial k/\partial {\phi }_i^t))=0$ ; therefore, we have

$$\{\begin{array}{c}{v}_j^2{\tau }^2-\cos ({\varphi }_j+{\phi }_j^t-{\varphi }_i-{\phi }_i^t)v_j{v}_i{\tau }^2=0\hfill \\ \multicolumn{1}{c}{v_i^2{\tau }^2-\cos ({\varphi }_j+{\phi }_j^t-{\varphi }_i-{\phi }_i^t)v_j{v}_i{\tau }^2=0}\end{array}$$

(32)

Equation (32) can be deduced into equation (33)

$$\begin{array}{c}\cos ({\varphi }_j+{\phi }_j^t-{\varphi }_i-{\phi }_i^t)=\frac{v_j}{v_i}\hfill \\ \cos ({\varphi }_j+{\phi }_j^t-{\varphi }_i-{\phi }_i^t)=\frac{v_i}{v_j}\hfill \end{array}$$

(33)

There is no solution for equation (33) when $v_j\ne v_i$ , which means that k is monotonous in each continuous space that $\cos ({\varphi }_j+{\phi }_j){\mathrm{v}}_{\mathrm{j}}-\cos ({\varphi }_i+{\phi }_i){\mathrm{v}}_{\mathrm{i}}\ne 0$ . The sample value of $\mathrm{k}({\mathrm{\phi }}_{\mathrm{i}},{\mathrm{\phi }}_{\mathrm{j}})$ is shown in Figure 12.

Figure 12.

Value of $k({\phi }_i,{\phi }_j)$ when ${\phi }_i\in (-\pi ,\pi )$ and ${\phi }_j\in (-\pi ,\pi )$ ; the initial motion directions of two UAVs are ${\varphi }_j=\mathrm{pi}/2$ and ${\varphi }_j=-\mathrm{pi}/2$ ; the position of A_j relative to A_i is (1, 1). V_i = 1 and V_j = 0.5.

Since $\mathrm{k}({\mathrm{\phi }}_{\mathrm{i}},{\mathrm{\phi }}_{\mathrm{j}})$ is monotonous in each continuous space and it is a periodic function, we propose to solve the nonlinear optimization problem in two steps: first to find the feasible initial solutions by SPGD algorithm and then to solve the nonlinear optimization problem by the existing nonlinear solver.

Initial solution

In the SPGD algorithm, first, a global PEF J(U) is defined that should only achieve the global extreme when all the safe separation constraints are satisfied ³²

$$J=\frac{1}{n}\sum _{q=1}^n{c}_k^q$$

(34)

where n is the number of pairwise conflicts, and $c_k({\phi }_i,{\phi }_j)$ is the standardization function for the pairwise relationship

$$c_k({\phi }_i,{\phi }_j)={\lambda }_0(k_{\mathrm{ij}})+(1-{\lambda }_0(k_{\mathrm{ij}}))p(k_{\mathrm{ij}})$$

(35)

where ${\lambda }_0(x)$ is an indicator function. In constraint (20), ${\lambda }_0(x)$ is defined as

$${\lambda }_0(x)=\{\begin{array}{c}1x\in ({\mathrm{k}}_{\mathrm{ij}}^1,{\mathrm{k}}_{\mathrm{ij}}^2)\hfill \\ \multicolumn{1}{c}{0x\notin ({\mathrm{k}}_{\mathrm{ij}}^1,{\mathrm{k}}_{\mathrm{ij}}^2)}\end{array}$$

(36)

Function $p(x)$ is defined as

$$p(x)=\{\begin{array}{c}{e}^{x-{\mathrm{k}}_{\mathrm{ij}}^2}x<{\mathrm{k}}_{\mathrm{ij}}^2\hfill \\ \multicolumn{1}{c}{e^{{\mathrm{k}}_{\mathrm{ij}}^1-x}x>{\mathrm{k}}_{\mathrm{ij}}^1}\end{array}$$

(37)

In constraint (21), ${\lambda }_0(x)$ is defined as

$${\lambda }_0(x)=\{\begin{array}{c}0x\in ({\mathrm{k}}_{\mathrm{ij}}^2,{\mathrm{k}}_{\mathrm{ij}}^1)\hfill \\ \multicolumn{1}{c}{1x\notin ({\mathrm{k}}_{\mathrm{ij}}^2,{\mathrm{k}}_{\mathrm{ij}}^1)}\end{array}$$

(38)

Function $p(x)$ is defined as

$$p(x)=\{\begin{array}{c}{e}^{x-{\mathrm{k}}_{\mathrm{ij}}^2}x<{\mathrm{k}}_{\mathrm{ij}}^2\mathrm{and}x>k_{\mathrm{ij}}^m\hfill \\ \multicolumn{1}{c}{e^{{\mathrm{k}}_{\mathrm{ij}}^1-x}x>{\mathrm{k}}_{\mathrm{ij}}^1\mathrm{and}x<k_{\mathrm{ij}}^m}\end{array}$$

(39)

where $k_{\mathrm{ij}}^m=\tan ({\mathrm{y}}_{\mathrm{i}}/{\mathrm{x}}_{\mathrm{i}})$ , which is depicted as red dotted line in Figure 10. The SPGD algorithm guarantees that J converges to its global extremum where its corresponding parameters meet the global optimum and the initial solutions can be obtained with high accuracy in the statistical sense. Thus, with proper parameter design, it can overcome the limitations in converging to local optimal parameters and yield precise results at fast speeds, even for serious correlation. The SPGD-based initial solution searching algorithm is described in Figure 13.

Figure 13.

SPGD-based initial solution search algorithm.

Optimization algorithm

After the initial feasible solution is obtained, the interior point method is applied to find the local optimal solution. The system needs to search $2^{\mathrm{Nc}}~2^{2\mathrm{Nc}}$ sub-domains to find optimization solutions, where $N_c$ is the number of pairwise conflict number. However, as the value of $N_c$ increases, the time consumption for global optimal solution would increase at an exponential rate. In order to meet the online requirement, finding a suboptimal solution becomes more practical than the global optimal solution. According to the traditional regulation and convention, the solver would find the optimal solution that all UAVs make right or left turn. ²³ The rotations of all vehicles to one side often show good result in both centralized and decentralized methods.

Computational experiments

In this section, we describe our implementation of the approach presented above and report the simulated results from several scenarios. We implemented our approach in MATLAB on a 2.8-GHz Intel i5 dual-core processor with 4 GB of memory running Windows 7 operating system. The first experiment demonstrates the computation efficiency of our algorithms. From the perspective of the influence on UAVs’ preplanned paths and performances in complex conflict scenario, the efficiency of the proposed methods is demonstrated in the second and third experiments. In these experiments, the maximum angular velocities of UAVs are 5°/s, the alert distances are 2 km, and the safe radii are 0.4 km, $\tau =10\mathrm{s}$ , and $t_c=1\mathrm{s}$ .

Computation efficiency analysis

In the first experiment, we design a randomly generated crowd scenario. The performance of the proposed methods are tested with randomly generated test problem in a fixed area. There are 64 UAVs in a square area of 400 km². UAVs are uniformly placed in the airspace with random initial motion directions. The system deals with the conflict between UAVs and collects conflict resolution samples in the simulation process. 200 samples are collected for every different numbers of conflict-involved UAVs. The average time consumptions for conflicts resolution are shown in Table 1. It is shown that the computational complexity of the random models is assessed according to the number of planes involved and the density of the aircraft. The computation time would increase rapidly for no matter the global optimal MICP algorithm and the SPGD algorithm. On the contrary, the local optimal can be obtained by the MICP algorithm and the SPGD-based algorithm efficiently. The results show that the regulation-based local optimal solvers are efficient in dealing with large number of UAV-involved conflicts.

Table 1.

Performance of the proposed approach on the random test cases.

UAV number	MICP optimal (s)	MICP local optimal (s)	SPGD-based optimal (s)	SPGD-based suboptimal (s)
2	0.02	0.01	0.05	0.03
4	0.08	0.02	0.3	0.08
6	0.3	0.04	1.3	0.10
8	1.3	0.08	3.5	0.16
10	2.5	0.11	6	0.2
16	8.4	0.18	20	0.25
20	–	0.2	–	0.31

UAV: unmanned air vehicle; MICP: mixed integral convex programming; SPGD: stochastic parallel gradient descent.

Overall, the computational results from the randomly generated models show that the developed algorithms are effective and efficient in solving the conflict resolution problem in near real-time, even for situations with a relatively large number of aircraft in the airspace.

Comparison of algorithms

In this section, we compare our approach with the existing algorithms. As we stated above, there are two different kinds of conflict resolution algorithms, namely, reactive algorithm and trajectory planning algorithm. In this article, we compare our algorithm with the rule-based coordination method, which is a type of reactive algorithm, ²² and the trajectory optimization algorithm. ⁷ There are four UAVs in the environment with equal speeds of 50 m/s. The conflict situations of UAV₁, UAV₂, and UAV₃ are not the same as UAV₄; if they take at least half responsibility in each pairwise conflict, all UAVs have to take large detours to resolve the conflict. The rule-based method achieves low-level coordination between UAVs, which leads to redundant maneuvers. In the multi-UAV cooperative method, the conflict is cleared by assigning different maneuvers to different UAVs.

The CDR results are shown in Figure 14. UAVs fly additional 2, 0.4, and 0.6 km by rule-based method, trajectory planning, and cooperative CDR method, respectively. The trajectory planning algorithm would cost more than 2 min to generate the trajectory while our approach needs 10 s to solve all conflicts on their way. The results show that the cooperative method guarantees both fewer deviations from preplanned traces and less computation time.

Figure 14.

Conflict resolution results’ comparison.

Conflict resolution with static obstacles

In this section, we design a scenario that may occur in the future metropolis airspace. As we discussed section “Cooperative conflict resolution”, there would be various kinds of objects that would disturb low-altitude UAVs. We can regard these objects as dynamic or static obstacles. When these objects are dynamic, we treat these objects as “noncooperative UAVs.” Their priorities are set high values, so that the real UAVs would take all safe separation responsibilities. When these objects are static, we can regard them as round or rectangular static obstacles. The conflict between UAVs and these static obstacles can therefore be resolved by our approaches. We demonstrate our approaches in the following computational experiments.

There are eight UAVs in the local airspace. They are planned to fly across the center of the local airspace, as shown in Figure 15. However, they are disturbed by unexpected events, which make them to deviate from predefined traces. They would lose separation if they keep fly in current headings. There is a static obstacle in the center of the local airspace.

Figure 15.

Conflict resolution without consider static obstacle. UAVs are with equal velocities: (a) UAVs traces time = 85 s, (b) UAVs traces time = 115 s, (c) UAVs traces time = 145 s, and (d) UAVs traces time = 180 s.

Conflict resolution between UAVs when UAVs are with equal velocities and without regard to static obstacle

In the first scenario, the static obstacle in Figure 15 is not concerned. UAVs are with equal velocities, 50 m/s. In this experiment, the conflict is resolved by MICP method. The conflict-free paths are shown in Figure 15. UAVs would return to the nominal paths after conflict dangers are resolved. The result shows that UAV 8 would come into collision with the static obstacle, which is shown as the red ellipse.

The distances between UAVs during the flight time are shown in Figure 16. The red dotted line is the safe distance between UAV pairs. The real lines depict the distances between UAV pairs during the flight time after conflict resolution. The green broken line depicts the minimum distance between all UAV pairs in the flight process. It shows that UAVs can keep the safe separation between each other after de-confliction.

Figure 16.

Distances between UAV pairs.

Conflict resolution between UAVs when UAVs are with unequal velocities and with regard to static obstacle

In this scenario, we set the speeds of UAVs to be not equal. The velocities of UAVs are 40, 30, 35, 25, 60, 50, 55, and 50 m/s, respectively. In this scenario, A₁, A₂, A₃, and A₄ are ahead of A₅, A₆, A₇, and A₈ in the beginning. As the speeds of A₅, A₆, A₇, and A₈ are faster than UAVs A₁, A₂, A₃, A₄, which are in front of them respectively. They would take over them during the flight process. Meanwhile, in order to avoid collide with the static obstacles, UAVs have to take larger detours than do not consider the obstacle. The conflict resolution result is shown in Figure 17.

Figure 17.

Conflict resolution with consider static obstacle. UAVs are with unequal velocities: (a) UAV position time = 115 s, (b) UAV position time = 145 s, (c) UAV position time = 175 s, and (d) UAV position time = 210 s.

The results show that the proposed conflict resolution method can guarantee the safe separation between UAVs. Furthermore, UAVs would not make excessive detours to avoid other UAVs. The experiments demonstrate that our algorithms are efficient in obtaining conflict free solutions.

Conclusion

Our article studies on the issue associate with cooperative CD&R of UAVs in metropolis airspace. We first discuss on the structure of metropolis airspace and analyze the conflict problem between UAVs. Second, we propose a CD&R framework. We cast the cooperative conflict resolution problem into nonlinear optimization problem. When the speeds of pairwise conflict-involved UAVs are equal, the nonlinear safe separation constraint is transformed into linear constraints and the conflict resolution problem is solved by MICP method. When the speeds of UAVs are different, we discuss on the character of the safe separation constraint and propose to solve the nonlinear optimization problem by SPGD-based method. Our methods show their high performances on conflict resolution in the experiments.