Online cooperative airspace conflict resolution of unmanned aerial vehicles by space mapping based iterative search method

Abstract

This paper presents an investigation into the locally centralized conflict resolution problem of unmanned aerial vehicles (UAVs), in which the headings are adjustable variables. Firstly, the geometric characteristics of the conflict resolution problem in two-dimensional space are studied, and the problem is reduced into a nonlinear programing model. Secondly, the nonlinear safe separation constraint is transferred into linear style in the sine value space using the space mapping method. The feasible region of two conflict-related UAVs is transformed into a half-space in the sine value space. The minimum adjustment vector and the maximum adjustable vector are obtained in this space. Thirdly, to search for the local optimal conflict-free solution, a two-layered optimization method is given. In the first layer, feasible conflict-free solutions are obtained by iterative search in virtue of the minimum adjustment vector and the maximum adjustable vector. In the second layer, the local optimal solution is generated using the sequential quadratic programing (SQP) method. The effectiveness of the proposed method is verified by numerical simulations. Compared with the existing geometric guidance theory based methods, the proposed method could effectively generate conflict-free solutions that lead to fewer detours, through which UAVs could coordinate online in highly crowded airspace.

Introduction

UAVs have broad application prospects in some civil fields, for example, traffic monitoring, pipeline detection, cargo transportation, and sometimes transport people in the city. ¹ Many UAV applications are predicted to be concentrated in densely populated metropolises. ² The primary concern is to ensure air safety when UAVs access into urban low-altitude airspace. ³ The Air Traffic Management (ATM) unit should provide the capability of Conflict Detection and Resolution (CDR) for UAVs. The conflict detection is to foresee potential loss separation dangers, and the conflict resolution unit is to determine conflict-free maneuvers. ⁴

The objective of CDR is to optimize the flights of UAVs while keeping the safe separation among relevant UAVs in a time interval $[0,\mathrm{\tau }]$ , where $\mathrm{\tau }$ is the look-ahead time window. ⁵ The CDR methods could be classified into three levels according to $\mathrm{\tau }$ . ⁶ The long-term CDR considers the safe separation among aircraft strategically in several hours, which is often accomplished before departure.^7,8 The medium-term CDR studies on the flight safety problem of aircraft in tens of minutes. ⁹ The short-term CDR deals with the safe separation problem in tens of seconds. ¹⁰ In the dynamic environment, the flights of UAVs would be affected by unpredictable factors. Therefore, the online short-term CDR is a necessity.

Some reliable techniques, such as long-range wide area network (LoRa) ¹¹ and 4/5G technology could provide the reliable communication among UAVs in the low-altitude airsapce.^12,13 When UAVs are permitted to fly close to each other, they could share their states and even short term flight attentions via these devices. Therefore, the local cooperative conflict resolution becomes realizable. ¹⁴

Rich researches have been published by the researchers in the short-term CDR field. The online short-term conflict resolution methods could be categorized into several types based on the resolving methodology. ¹⁵ The trajectories optimization methods tend to find the optimal solutions by once or a series of maneuvers. ⁹ Soler et al. ¹⁶ model the conflict resolution problem as a hybrid optimal control problem (OCP), and propose to solve this problem as a Nonlinear Optimization Program (NLP) problem. Omer ¹⁷ proposes three different mixed integer linear program (MILP) based conflict resolution methods, and the velocity and heading change avenues are separately studied. Furthermore, Liu ¹⁸ studies on the continuous air traffic centralized coordination problem. The objective is to coordinate UAVs that close to each other to reach their destinations and maintain the safe separation among them. This problem is formulated as a nonlinear nonconvex optimization model and is kept on solving by receding-horizon progressive heuristic method. By combing the memetic algorithm and the genetic algorithm, Guan et al. ¹⁹ propose the strategic conflict avoidance framework. The sampling based search methods are to search the solutions that could guarantee the proper safe separation among aerial vehicles. ²⁰ The tree search-based algorithm explores the states space and action space by combing the heuristic function and the dynamic model of the conflict-involved UAVs. ²¹ These methods perform well in the scenarios where there are only a limited number of conflict-involved UAVs in the local airspace. As the number of conflict-involved UAVs increases, the computation time will increase exponentially. There are other types of CD&R methods that could extend to deal with congested airspace conflict scenarios. The potential field methods define attractive potential at the target and a repulsive potential around the invaders, such that the vehicle follows the gradient of potentials to yield the path which is attracted by the target and keep the safe separation with static and dynamic hazards during vehicle navigation. ²² Rahmani et al. ²³ present a deconfliction algorithm for the multi-vehicle system by constructing an appropriate navigation function, which is actually one type of the improved potential field method. Roelofsen et al. ²⁴ propose a navigation function-based CDR method for quadrotors with considering the limited sense field. This method is proved to be able to guarantee the collision free among quadrotors by define proper navigation function. These types of methods are collectively called the reactive methods. The shortcoming is this type of methods considers more on keeping safe separation between UAVs than their assigned tasks.

More and more UAVs would fly close to each other as the applications of UAVs become popular in many fields. ¹⁸ In this circumstance, the conflict resolution method should guarantee UAVs to make minor detours to keep safe separation. ²⁵ This paper focuses on the heading change-based short-term CDR of UAVs by using the locally centralized coordination method.^15,17 The geometric guidance algorithms combine the reactive algorithm and optimization planning method together appropriately, and they are agile and efficient to produce short-term conflict-free maneuvers.^10,26 Alonso-Mora et al. ²⁷ propose cooperative collision avoidance algorithms for quadrotors based on the velocity obstacle theory. Their algorithm is proved to be efficient in generating suboptimal solutions. However, according to the velocity obstacle theory, the conflict-related UAVs could become overly close after the look-ahead time interval $\mathrm{\tau }$ . Therefore, the maneuver policies should be updated continually at each time step even for pairwise conflicts. The researchers have explained that the safety separation constraints that exist among aircraft are non-linear. ⁵ Aiming at the conflict resolution problem of diverse UAVs, two methods to enhance computational efficiency are proposed. According to Alonso-Ayuso et al. ²⁸ the continuous heading maneuver area is divided into a group of discrete steerable angles. Therefore, the nonlinear safe separation constraints are changed to linear constraints. Unfortunately, this method could not guarantee the solution efficiency and solution quality simultaneously. Singh and Pham ²⁹ have studied the velocity change-based conflict coordination problem. The problem is reduced to a convex programing problem, which is similar to the speed change-based method proposed in Yang et al. ⁵ The velocity change method would be inefficient when UAVs meet with head-on conflict. Yang et al. ⁵ have also studied the heading change-based conflict resolution method. The stochastic search algorithms and geometric guidance method are combined by them. Complex conflict issues could be handled by this well-designed method. Nevertheless, the calculating time spent by the proposed stochastic parallel gradient descent (SPGD) method varies over time as the search process is directed by stochastic gradient. Furthermore, Yang et al.^30,31 propose the space mapping based conflict resolution method. These two methods could greatly improve the computation efficiency. However, as they decouple the safe separation constraint by the minimum adjustment vectors and the maximum adjustable vectors, and they are lack of online coordination mechanism, these two methods would lead to redundant detours.

According to the discussion above, this paper studies the geometric guidance-based conflict resolution method. The conflict-free constraint is derived from the collision cone model. ³² The problem is reduced to nonlinear programing (NP) problem. We propose a two-layered optimization method in virtue of the space mapping method and the nonlinear optimization algorithm, which is to search the feasible solution in virtue of the iterative space mapping method in the first layer and to generate the optimal solution in virtue of the optimization solver in the second layer. To satisfy the online planning requirement, the flight rules are referenced in searching the local optimal policies. The advantage of this method is that the required degree modifications of relevant UAVs could be obtained directly. Therefore, the centralized coordinator could determine the search direction unambiguously. The existing method is used to compare with this method so that the performance of this approach is demonstrated. In various situations, this method could obtain well-optimized solutions.

The rest of this paper is organized as follows. Section II details the online conflict resolution of UAVs. Section III introduces the conflict resolution method based on space mapping. In Section IV, we use several illustrating numerical simulations to prove that this method is effective. Section V gives the conclusion.

Problem formulation

UAVs kinematics

There would be various types of UAVs flying in the airspace. We assume that a group of UAVs would fly close to each other now and then in the local airspace, and they may involve in airspace conflict because of unexpected incidents or bad weather conditions. We anticipate that there are centralized air traffic control units that coordinate UAVs to fly close to their nominal paths and maintain their safe separation. ¹⁸ The particular problem we study is conflict resolution of UAVs with planar and deterministic motions.

In the horizontal flat two-dimensional space, UAV A_i, $i\in N$ , is identified by position ${\mathbf{P}}_i(t)=(x_i(t),y_i(t))$ , heading angle ${\mathrm{\varphi }}_i(t)$ , and speed $v_i(t)$ . The kinematic model of A_i is as the equation (1):

$$\begin{array}{l}{\stackrel{.}{x}}_i(t)=v_i(t)\cos {\mathrm{\varphi }}_i(t)\\ {\stackrel{.}{y}}_i(t)=v_i(t)\sin {\mathrm{\varphi }}_i(t)\\ {\stackrel{.}{v}}_i(t)=a_i(t)\\ {\stackrel{.}{\mathrm{\varphi }}}_i(t)=w_i(t)\end{array}$$

(1)

where $w_i(t)$ is the turn rate of A_i, $a_i(t)$ is the acceleration of A_i. A_i is subject to control constraints:

$$a_i(t)\in [a_{max}^{i,n},a_{max}^{i,p}],w_i(t)\in [-w_{max}^i,w_{max}^i]$$

(2)

where $a_{max}^{i,p}$ is the maximum acceleration rate, $a_{max}^{i,n}$ is the maximum deceleration rate, and the maximum turn rate is $w_{max}^i$ . We have that $w_{max}^i=1/R_{min,i}$ , where the minimum turn radius of A_i is $R_{min,i}$ .

$$R_{min,i}=\frac{v_i^2{\cos }^2{\mathrm{\gamma }}_{max}}{\mathrm{\eta }g\sin \left|{\mathrm{\psi }}_{max}\right|}$$

(3)

where the max roll angle is ${\mathrm{\psi }}_{max}$ , the max pitch angle is ${\mathrm{\gamma }}_{max}$ , $\mathrm{\eta }$ and g are constants.

A potential collision danger could be resolved by heading change, altitude change, ³³ or speed change. ³⁴ When flying at low-altitude airspace in the urban area, it is more practical for the fixed wing UAV to adopt the horizontal heading maneuver strategies to avoid conflict, because the speed adjustment may destabilize the aircraft, and the altitude adjustment may cause the aircraft to leave the low altitude airspace and enter the medium-altitude airspace that the 4/5G communication could not reach. ³⁵ In this paper, one UAV A_i would be designed with horizontal heading maneuver strategies to keep the safe separation with its neighbors. ⁵ That is ${\mathrm{\varphi }}_i(t)={\mathrm{\varphi }}_i(0)+{\mathrm{\phi }}_i$ , where ${\mathrm{\phi }}_i$ is the heading maneuver policy. We assume that the magnitude of ${\mathrm{v}}_i(\mathrm{t})$ would keep almost constant when A_i takes the heading maneuver. ³⁰ Therefore, we use $v_i$ short for $v_i(t)$ .

In order to ensure the safety of aircraft in flight, we define the safe area of each UAV A_i according to its characteristics and platform features (e.g. mobile performance and size). The safe area is defined as $D_i({\mathbf{P}}_i(t),r_i)$ :

$$D({\mathbf{P}}_i(t),r_i)=\{p::||p_x-x(t),p_y-y(t)|{|}_2<r_i\}$$

(4)

where $r_i$ is the safe radius of A_i. $D_i({\mathbf{P}}_i(t),r_i)$ denotes a circular region with radius $r_i$ , and its center is ${\mathbf{P}}_i(t)=(x_i(t),y_i(t))$ . As UAVs are significantly smaller than manned aircraft, the safety radius set for each UAV is hundreds of meters. ³¹ The loss separation is defined as one UAV entering the safe region of the other one.

We aim to find the heading change policies $\mathrm{\Phi }=\{{\mathrm{\phi }}_1,...,{\mathrm{\phi }}_N\}$ for N UAVs. According to UAVs’ dynamic characteristics, the heading change angle $\mathrm{\Phi }$ could not be achieved instantaneously. Therefore, we should discuss the detailed heading change policy first.

We assume that the tracking systems mounted on UAVs are able to track planned heading maneuver policies within the allowable error range. ³⁶ In the online planning process, we approximate the modified trace by using dubins curves. ⁵ Such as shown in Figure 1, to minimize the error, we assume that UAVs would take the maximum angular rates to reach the planned heading direction. Based on the dubins method, we devise to use the curve-curve (“CC”) maneuver method to track the planned heading maneuvers in the shortest time. The path tracking process is departed into two processes: to turn to the required direction with the maximum rate in the first process and to modify the heading direction with maximum inverse angular rate. We could obtain the maximum reachable turning angular by $\mathrm{\tau }$ and $w_{max}^i$ , which is denoted as ${\mathrm{\phi }}_{max}^i(\mathrm{\tau })$ . The value of ${\mathrm{\phi }}_i$ should be in the range $[-{\mathrm{\phi }}_{max}^i(\mathrm{\tau }),{\mathrm{\phi }}_{max}^i(\mathrm{\tau })]$ .

Figure 1.

UAV tracks the planned path. UAV’s mobility limits its maximum maneuver heading degree.

In the heading modification process, the distance between the initial point and endpoint is less than the production of initial velocity and $\mathrm{\tau }$ . As $\mathrm{\tau }$ is tens of seconds, we assume that the maneuverable range of UAVs in $\mathrm{\tau }$ is less than $\mathrm{\pi }/3$ , the maximum difference rate between the real motion distance and the distance between the initial point and endpoint is:

$$\mathrm{\zeta }=(v\mathrm{\tau }-\Vert \mathrm{EI}\Vert )/v\mathrm{\tau }\le \mathrm{\pi }/3-1=0.047$$

(5)

The error $\mathrm{\zeta }$ is much less than the upper bound compensation of manned aircraft. ¹⁷ We assume that the minor error could be eliminated in the path tracking step.

Safe separation constraint

We firstly discuss the pairwise UAVs safe separation condition. The pairwise safe separation constraint is expressed as equation (6):

$$r_s^{\mathrm{ij}}-\Vert {\mathbf{P}}_i(t)-{\mathbf{P}}_j(t)\Vert \le 0$$

(6)

where $r_s^{\mathrm{ij}}=max(r_i,r_j)$ is the compound safe radius. ‖.‖ is the Euclidean norm. The situation between A_i and A_j is defined as losing separation if the distance between them is less than $r_s^{\mathrm{ij}}$ .

The spatial relationship between UAVs is analyzed by local coordinates. In Figure 3, the position of A_j at t = 0 is set as the original point of the local coordinates frame. The coordinate of A_i in the local coordinates frame at time t = 0 are:

$${\mathbf{P}}_{\mathbf{i}}(0)=(x_i(0)-x_j(0),y_i(0)-y_j(0))$$

(7)

Suppose that A_i and A_j take heading maneuvers ${\mathrm{\phi }}_i$ and ${\mathrm{\phi }}_j$ to avoid each other. The modified velocities of them at $\mathrm{\tau }$ are denoted as equation (8):

$${\mathbf{v}}_i(\mathrm{\tau })=\left(\begin{array}{c}{v}_i\cos ({\mathrm{\varphi }}_i(0)+{\mathrm{\phi }}_i)\hfill \\ \multicolumn{1}{c}{v_i\sin ({\mathrm{\varphi }}_i(0)+{\mathrm{\phi }}_i)}\end{array}\right),{\mathbf{v}}_j(\mathrm{\tau })=\left(\begin{array}{c}{v}_j\cos ({\mathrm{\varphi }}_j(0)+{\mathrm{\phi }}_j)\hfill \\ \multicolumn{1}{c}{v_j\sin ({\mathrm{\varphi }}_j(0)+{\mathrm{\phi }}_j)}\end{array}\right)$$

(8)

The velocity of A_j relative to A_i is:

$${\mathbf{v}}_{\mathrm{ji}}(\mathrm{\tau })=(v_j^x(\mathrm{\tau })-v_i^x(\mathrm{\tau }),v_j^y(\mathrm{\tau })-v_i^y(\mathrm{\tau }))$$

(9)

To keep the safe separation between A_i and A_j, ${\mathbf{v}}_{\mathrm{ji}}(\mathrm{\tau })$ should be outside the dark delta-shaped region in Figure 2.

Figure 2.

The collision cone based safe separation constraint.

The constraint (6) is transferred as:

$$r_s^{ij}-|-k_{ji}{P}_{ix}+P_{iy}|/\sqrt{1+k_{ji}^2}\le 0$$

(10)

where $k_{\mathrm{ji}}$ is the slope of ${\mathbf{v}}_{\mathrm{ji}}(\mathrm{\tau })$ . It is expressed as:

$$k_{\mathrm{ji}}=(v_j^y(\mathrm{\tau })-v_i^y(\mathrm{\tau }))/(v_j^x(\mathrm{\tau })-v_i^x(\mathrm{\tau }))$$

(11)

According to the geometric safe separation constraint, with consideration on the dynamic constraint of UAVs, we find that there are three types of situations between two nearby UAVs in $[0,\mathrm{\tau }]$ ⁵ : practical conflict, potential conflict and no conflict. As shown in Figure 3, the gray regions are the reachable regions of two UAVs. The cases shown in Figure 3(a) and (b) are defined as a practical conflict and a potential conflict, respectively. The case shown in Figure 3(c) is defined as no conflict. The practical conflict refers to the situation that two UAVs will conflict in $\mathrm{\tau }$ according to the current headings. The potential conflict refers to the situation that if two UAVs move according to the current headings then the safe distance will be ensured, if the UAVs (or one of them) change their headings inappropriately, then conflict may occur. No conflict means that the current relative speed of the two UAV is not in their respective speed obstacles. Due to the limited maneuverability of each UAV, it is impossible for them to conflict, as shown in Figure 3(c). The potential conflict should be considered when there are more than two UAVs involving in the local conflict. The variable ${\mathrm{\kappa }}_{\mathrm{ij}}$ is defined to denote the relation between UAVs.

$${\mathrm{\kappa }}_{\mathrm{ij}}=\{\begin{array}{cc}\begin{array}{c}1\hfill \\ \multicolumn{1}{c}{0}\end{array}\hfill & \begin{array}{c}{A}_i\mathrm{practical}/\mathrm{potential}\mathrm{conflict}\mathrm{with}{\mathrm{A}}_j\hfill \\ \multicolumn{1}{c}{\mathrm{other}\mathrm{wise}}\end{array}\hfill \end{array}$$

(12)

Figure 3.

Geometric construction for conflict avoidance constraint: (a) practical conflict, (b) potential conflict, and (c) no conflict.

Multi-UAV conflict resolution problem

In the short-term conflict resolution problem, the value of $\mathrm{\tau }$ is determined with considering both the dynamics of UAVs and airspace efficiency, that is to guarantee UAVs to have enough time to maneuver and to reduce unnecessary detours. ³⁰ In the multi-UAV conflict resolution scenario, there are multiple coupled pairwise conflicts. The graph $\mathrm{G}(\mathrm{t})=(\mathrm{V},\mathrm{E}(\mathrm{t}))$ is used to determine the relevant multi-UAV conflict, where V = is the vertex set and $\mathrm{E}(\mathrm{t})=\{(\mathrm{j},\mathrm{i})|{\mathrm{c}}_{\mathrm{ij}}=1\}$ is the corresponding edge set. ³⁷ The multi-UAV conflict matrix (CM) is derived by the adjacency matrix of G(t). CM = {cm(i,j)=1 if ${\mathrm{e}}_{\mathrm{ij}}(\mathrm{t})\in \mathrm{E}(\mathrm{t})$ , else cm(i,j) = 0| $i,j\in n$ }. The UAVs that are involved in one relevant multi-UAV conflict would form a connected graph.

Different types of UAVs have different tasks and priorities. In addition to that, the air traffic situation is varying. In the congested environment, the conflict resolution strategy should be carefully designed. Two variables are defined, namely $d_{\mathrm{dev}}^i$ , and ${\mathrm{\rho }}_d^i$ . $d_{\mathrm{dev}}^i$ describes the deviation distance of UAV A_i from the predefined plan. The deviation would have influences on the tasks of each UAV. ${\mathrm{\rho }}_d^i$ denotes the influence of deviation of A_i. The values of ${\mathrm{\rho }}_d^i$ is described as:

$${\mathrm{\rho }}_d^i=f_{\mathrm{dev}}^i({\mathrm{\rho }}_d^{i,o},d_{\mathrm{dev}}^i)$$

(13)

where ${\mathrm{\rho }}_{d,o}^i$ is a pre-defined constant and it denotes the spatial importance of the mission assigned to A_i. The structures of $f_{\mathrm{dev}}^i$ are task-specific.

Objective function

A successful conflict resolution policy of UAVs should ensure the safe separation among them, with respect to their performance limitations, and accommodate to other desirable behaviors or objectives simultaneously. We regard the safe separation requirements and performance limitations as hard constraints, and the other desirable behaviors are expressed in the objective function.

The primary concern of the objective function is to evaluate the cost of heading maneuvers. The cost includes fuel consumption and the influences on the tasks of UAVs. According to the conflict resolution criterion, UAVs would return to their nominal flight paths after conflicts are resolved. The additional fuel consumption is closely related to the departure distance between current positions and the nominal paths.

On the other hand, we find that the main correlative factor of the tasks performances of UAVs is the deviation distances and durations from the preference traces. Therefore, the main discussion on this problem is to eliminate the deviation distance and to ensure UAVs to return to their nominal flight paths of UAVs.

$$f_i({\mathrm{\phi }}_i)={\mathrm{\rho }}_d^i{v}_i{t}_d^i\sin (|{\mathrm{\phi }}_d^i+{\mathrm{\phi }}_i|)$$

(14)

where $t_d^i$ is the time period between the departure time and the time that A_i begins to return from the maximum deviation position. As $t_d^i$ is determined by $\mathrm{\tau }$ , and we treat it as a known constant. UAVs may have already departed from their nominal flight paths because of previous conflict avoidance maneuvers or dynamic environments. ${\mathrm{\phi }}_d^i$ is used to describe the heading deviation of A_i at time t = 0. Therefore, the main variable is ${\mathrm{\phi }}_i$ .

Local centralized conflict resolution problem

As UAVs are grouped into sub clusters based on the conflict relationships between each pair of UAVs, the conflict relationships of UAVs in one sub cluster should be comprehensively considered in case the conflict resolution maneuvers lead to serious secondary conflicts. ³⁸ Supposing that $n_l$ UAVs involving in the local airspace conflict, the multi-UAV conflict resolution problem is formulated as below:

$$minF=\sum _{i=1}^{n_l}{f}_i({\mathrm{\phi }}_i)$$

(15)

$$\begin{array}{c}\mathrm{s}.\mathrm{t}.\hfill \\ {\mathrm{\varphi }}_i={\mathrm{\varphi }}_i(0),v_i=v_i(0),x_i=x_i(0),y_i=y_i(0)\hfill \\ r_s^{\mathrm{ij}}\mathrm{-}|\mathrm{-}{k}_{\mathrm{ji}}{P}_{\mathrm{ix}}+P_{\mathrm{iy}}|/\sqrt{1+k_{\mathrm{ji}}^2}\le 0,\mathrm{if}\mathrm{c}{\mathrm{r}}_{\mathrm{ij}}=1,r_s^{\mathrm{ij}}=max(r_i,r_j)\hfill \\ {\mathrm{\phi }}_i\in [-{\mathrm{\phi }}_{max}^i(\mathrm{\tau }),{\mathrm{\phi }}_{max}^i(\mathrm{\tau })]i,j\in n_l\hfill \end{array}$$

(16)

Therefore, we model the multi-UAV conflict resolution problem as a nonlinear programing (NP) model.

The space mapping based conflict resolution algorithms

We find that the objective function and the safe separation constraints of the nonlinear programing model defined by equations (15) and (16) are non-convex. ⁵ Furthermore, according to the dynamics of UAVs, the feasible range of each pairwise conflict-related UAVs consist of several sub regions. ⁵ We should search over these disconnect sub regions to obtain the optimal solutions. It is inefficient and impractical in the online conflict resolution scenario. In practice, it is even challenging to find the local optimal solutions efficiently when many UAVs are congested in the local airspace. To improve the computation efficiency, this paper proposes to search the solution in virtue of the space mapping method.

The heading change based maneuver constraint

According to the discussion in Section II, we define the equation (17):

$$k_{\mathrm{ji}}^2({P_{\mathrm{ix}}}^2-r_s^2)-2k_{\mathrm{ji}}{P}_{\mathrm{ix}}{P}_{\mathrm{iy}}+{P_{\mathrm{iy}}}^2-r_s^2=0$$

(17)

The roots of (52) are:

$$\begin{array}{c}{k}_{\mathrm{ji}}^1=(2P_{\mathrm{ix}}{P}_{\mathrm{iy}}-\sqrt{\mathrm{\Delta }})/2({P_{\mathrm{ix}}}^2-r_s^{\mathrm{ij}2})\hfill \\ k_{\mathrm{ji}}^2=(2P_{\mathrm{ix}}{P}_{\mathrm{iy}}+\sqrt{\mathrm{\Delta }})/2({P_{\mathrm{ix}}}^2-r_s^{\mathrm{ij}2})\hfill \end{array}$$

(18)

where $\sqrt{\mathrm{\Delta }}=2r_s^{\mathrm{ij}}\sqrt{{P_{\mathrm{ix}}}^2+{P_{\mathrm{iy}}}^2-{r_s^{\mathrm{ij}}}^2}$ , and $\mathrm{\Delta }>0$ as we assume that two UAVs keep safe separation from each other at $t=0$ . As the heading change problem is invariant to the rotations, this paper discusses the safe separation constraint in the local coordinate frame as shown in Figure 4.

Figure 4.

The feasible region of heading direction of relative displacement. There are two different sub regions because the sign of the denominator of k is contrary in region 1 and region 2.

According to the algebraic calculus, the feasible region is determined as.

$$k_{\mathrm{ji}}^{\mathrm{feasible}}\in (k_{\mathrm{ji}}^2,k_{\mathrm{ji}}^1)$$

(19)

We then find the constraint on the control variable based on the constraint on $k_{\mathrm{ji}}$ . The feasible region that is determined above is restricted in one period of tangent function. In reality, the feasible solutions of $k_{\mathrm{ji}}$ scatters both in the left half and right half of the Cartesian coordinate system, as shown in Figure 4. Although the feasible solution regions are discontinuous in the algebraic calculus, we could recognize that the feasible region is a continuous whole in geometry. However, $k_{\mathrm{ji}}$ is singular when the heading degree of ${\mathbf{V}}_{\mathbf{ji}}$ is $\mathrm{\pi }/2+\mathrm{k}\mathrm{\pi },\mathrm{k}\in Z$ , as $v_j^x-v_i^x=0$ . Therefore, the sign of $v_j^x-v_i^x$ parts the feasible solution region into two sub regions. The signs of $v_j^x-v_i^x$ are inverse in region 1 and region 2. The safe separation constraint can be concluded into two mutually exclusive cases.

The slope of $k_{\mathrm{ji}}$ could be expanded as:

$$k({\mathrm{\phi }}_i,{\mathrm{\phi }}_j)=\frac{v_j\sin ({\mathrm{\varphi }}_j+{\mathrm{\phi }}_j)-v_i\sin ({\mathrm{\varphi }}_i+{\mathrm{\phi }}_i)}{v_j\cos ({\mathrm{\varphi }}_j+{\mathrm{\phi }}_j)-v_i\cos ({\mathrm{\varphi }}_i+{\mathrm{\phi }}_i)}$$

(20)

In metropolis airspace, some homogeneous UAVs may fly at almost the same airspeed. The nonlinear constraint can be transformed into linear constraint. ²⁶ However, in most cases, the conflict involved UAVs are homogeneous and with different airspeeds. Therefore, the safe separation constraint could not be transformed into linear constraint directly in the original position-degree space.

The equation (20) could be transferred as below:

$$v_j\sin ({\mathrm{\varphi }}_j+{\mathrm{\phi }}_j-\delta (k))=v_i\sin ({\mathrm{\varphi }}_i+{\mathrm{\phi }}_i-\delta (k))$$

(21)

where $\delta (k)=\arcsin (k/\sqrt{1+k^2})$ , which is a constant when k is determined.

We define the function:

$$f_{\mathrm{\phi }}^d({\mathrm{\phi }}_i,{\mathrm{\phi }}_j)=v_j\cos ({\mathrm{\varphi }}_j+{\mathrm{\phi }}_j)-v_i\cos ({\mathrm{\varphi }}_i+{\mathrm{\phi }}_i)$$

(22)

The sign of $f_{\mathrm{\phi }}^d({\mathrm{\phi }}_i,{\mathrm{\phi }}_j)$ is different in region 1 and region 2, as shown in Figure 4, which could determine the form of the safe separation constraint. The feasible solution constraint in ${\mathrm{\phi }}_i$ and ${\mathrm{\phi }}_j$ is described below.

• Case (1) the sign of $f_{\mathrm{\phi }}^d({\mathrm{\phi }}_i,{\mathrm{\phi }}_j)$ is negative in region 1, the feasible solution space is expressed as:

$$\{\begin{array}{c}{v}_j\sin ({\mathrm{\varphi }}_j+{\mathrm{\phi }}_j-\delta (k_{\mathrm{ji}}^1))-v_i\sin ({\mathrm{\varphi }}_i+{\mathrm{\phi }}_i-\delta (k_{\mathrm{ji}}^1))\le 0\hfill \\ \multicolumn{1}{c}{f_{\mathrm{\phi }}^d({\mathrm{\phi }}_i,{\mathrm{\phi }}_j)>0}\end{array}$$

(23)

or

$$\{\begin{array}{c}{v}_j\sin ({\mathrm{\varphi }}_j+{\mathrm{\phi }}_j-\delta (k_{\mathrm{ji}}^2))-v_i\sin ({\mathrm{\varphi }}_i+{\mathrm{\phi }}_i-\delta (k_{\mathrm{ji}}^2))\le 0\hfill \\ \multicolumn{1}{c}{f_{\mathrm{\phi }}^d({\mathrm{\phi }}_i,{\mathrm{\phi }}_j)<0}\end{array}$$

(24)

• Case (2) the sign of $f_{\mathrm{\phi }}^d({\mathrm{\phi }}_i,{\mathrm{\phi }}_j)$ is negative in region 2, the feasible solution space is expressed as:

$$\{\begin{array}{c}{v}_i\sin ({\mathrm{\varphi }}_i+{\mathrm{\phi }}_i-\delta (k_{\mathrm{ji}}^1))-v_j\sin ({\mathrm{\varphi }}_j+{\mathrm{\phi }}_j-\delta (k_{\mathrm{ji}}^1))\le 0\hfill \\ \multicolumn{1}{c}{f_{\mathrm{\phi }}^d({\mathrm{\phi }}_i,{\mathrm{\phi }}_j)<0}\end{array}$$

(25)

or

$$\{\begin{array}{c}{v}_i\sin ({\mathrm{\varphi }}_i+{\mathrm{\phi }}_i-\delta (k_{\mathrm{ji}}^2))-v_j\sin ({\mathrm{\varphi }}_j+{\mathrm{\phi }}_j-\delta (k_{\mathrm{ji}}^2))\le 0\hfill \\ \multicolumn{1}{c}{f_{\mathrm{\phi }}^d({\mathrm{\phi }}_i,{\mathrm{\phi }}_j)>0}\end{array}$$

(26)

Space mapping from degree space to sine value space

In equations (23)–(26) define the conflict-free regions of A_i and A_j. However, as these constraints contain sin function, each feasible region is not convex. To simplify the searching process, we propose to change the nonlinear relationship into a linear relationship.

The space mapping relations are defined as the equation (27):

$$\begin{array}{c}{x}_s^{i,b}=\sin ({\mathrm{\varphi }}_i(0)+{\mathrm{\phi }}_i-\delta (k_{\mathrm{ji}}^b))\hfill \\ y_s^{j,b}=\sin ({\mathrm{\varphi }}_j(0)+{\mathrm{\phi }}_j-\delta (k_{\mathrm{ji}}^b))\hfill \end{array}$$

(27)

The values of $x_s^{i,b}$ and $y_s^{j,b}$ are both in the range $[-1,1]$ , $b\in 1,2$ . Equation (27) map angles to sine values. The feasible regions are therefore described by linear constraints in sine value space ³¹ :

• (1). If $d{s}_{\mathrm{ij}}=1$ , the feasible regions are expressed as:

$$\{\begin{array}{c}{v}_j{y}_s^{j,1}\mathrm{-}{v}_i{x}_s^{i,1}\le 0\hfill \\ \multicolumn{1}{c}{f_{\mathrm{\phi }}^d({\mathrm{\phi }}_i,{\mathrm{\phi }}_j)>0}\end{array}\mathrm{and}\{\begin{array}{c}{v}_j{y}_s^{j,2}\mathrm{-}{v}_i{x}_s^{i,2}\le 0\hfill \\ \multicolumn{1}{c}{f_{\mathrm{\phi }}^d({\mathrm{\phi }}_i,{\mathrm{\phi }}_j)<0}\end{array}$$

(28)

• (2). If $d{s}_{\mathrm{ij}}=0$ , the feasible regions are expressed as:

$$\{\begin{array}{c}{v}_i{x}_s^{i,1}\mathrm{-}{v}_j{y}_s^{j,1}\le 0\hfill \\ \multicolumn{1}{c}{f_{\mathrm{\phi }}^d({\mathrm{\phi }}_i,{\mathrm{\phi }}_j)<0}\end{array}\mathrm{and}\{\begin{array}{c}{v}_i{x}_s^{i,2}\mathrm{-}{v}_j{y}_s^{j,2}\le 0\hfill \\ \multicolumn{1}{c}{f_{\mathrm{\phi }}^d({\mathrm{\phi }}_i,{\mathrm{\phi }}_j)>0}\end{array}$$

(29)

The sine value space is defined in a 2-D rectangular coordinate system. The X axis describes the value of $\sin ({\mathrm{\varphi }}_i(0)+{\mathrm{\phi }}_i-\delta (k_{\mathrm{ji}}^b))$ , and Y axis describes the value of $\sin ({\mathrm{\varphi }}_j(0)+{\mathrm{\phi }}_j-\delta (k_{\mathrm{ji}}^b))$ . According to the character of sine function, the value range of X axis is [−1,1], and the value range of Y is [−1,1]. The safe separation constraint of pairwise conflict-related UAVs is changed to be affine in the sine value space. The required modification could be easily obtained in the sine value space.

We make further discussion on how to obtain feasible solutions in sine value space in virtue of these linear constraints. As shown in Figure 5, the gray region is defined as: ${\mathrm{FR}}_{\mathrm{hh},b}^{\mathrm{ij}}$ . $\forall (x_s^{i,b},y_s^{j,b})\in {\mathrm{FR}}_{\mathrm{hh},b}^{\mathrm{ij}}$ corresponds to the maneuver pair $({\mathrm{\phi }}_i,{\mathrm{\phi }}_j)$ that guarantees A_i and A_j to be conflict-free. The boundary dashed slash line $l_{\mathrm{hh}}^{m,b}$ is $v_j{y}_s^{j,b}=v_i{x}_s^{i,b}$ . ${\theta }_{\mathrm{hh}}^{k_b}$ is the interaction angle between $l_{\mathrm{hh}}^{m,b}$ and $X_s^{i,b}$ , and ${\theta }_{\mathrm{hh}}^{k_b}=\arctan (v_i/v_j)$ . $P_o^{\mathrm{ij},b}=(x_{s,o}^{i,b},y_{s,o}^{j,b})$ is the mapping of $({\mathrm{\varphi }}_i(0),{\mathrm{\varphi }}_j(0))$ in the coordinate system $X_s^{i,b}{\mathrm{OY}}_s^{j,b}$ .

Figure 5.

Mapping coordinates for heading change based conflict resolution: (a) mapping coordinates for practical conflict and (b) mapping coordinates for potential conflict.

Suppose the feasible region is constrained by $v_i{x}_s^{i,b}-v_j{y}_s^{j,b}\le 0$ . $P_o^{\mathrm{ij},b}\notin {\mathrm{FR}}_{\mathrm{hh},b}^{\mathrm{ij}}$ if A_i and A_j involve in practical conflict. In this circumstance, A_i and A_j should make heading changes to keep the safe separation. The mapping of $({\mathrm{\varphi }}_i(0)+{\mathrm{\phi }}_i,{\mathrm{\varphi }}_j(0)+{\mathrm{\phi }}_j)$ in coordinates $X_s^{i,b}{\mathrm{OY}}_s^{j,b}$ is denoted as $P_n^{\mathrm{ij},b}=(x_{s,n}^{i,b},y_{s,n}^{j,b})$ . According to the constraint boundary shown in Figure 5(a), the minimum adjustment vector ${\mathbf{u}}_{\mathrm{hh}}^{b,\mathrm{ij}}$ is defined as ${\mathbf{u}}_{\mathrm{hh}}^{b,\mathrm{ij}}=(\underset{P_{\mathrm{hh}}\in l_{\mathrm{hh}}^{m,b}}{\arg min}\Vert P_{\mathrm{hh}}-P_o^{\mathrm{ij},b}\Vert )-P_o^{\mathrm{ij},b}$ .

As shown in Figure 5(a). $\Vert {\mathbf{u}}_{hh}^{b,ij}||$ is the minimum distance from $P_o^{\mathrm{ij},b}$ to ${\mathrm{FR}}_{\mathrm{hh},b}^{\mathrm{ij}}$ . The vector ${\mathbf{m}}_{\mathrm{on}}^{\mathrm{ij},b}$ is defined as $(m_{\mathrm{on}}^{i,b},m_{\mathrm{on}}^{j,b})$ , where $m_{\mathrm{on}}^{i,b}=x_{s,n}^{i,b}-x_{s,o}^{i,b}$ and $m_{\mathrm{on}}^{j,b}=y_{s,n}^{j,b}-y_{s,o}^{j,b}$ . To keep the safe separation of A_i and A_j, it should be ${\mathbf{m}}_{on}^{ij,b}.{\mathbf{u}}_{hh}^{b,ij}/\Vert {\mathbf{u}}_{hh}^{b,ij}\Vert \ge \Vert {\mathbf{u}}_{hh}^{b,ij}\left|\right|$ .

Two potential conflict-involved UAVs should also satisfy constraints (28) or (29). As shown in Figure 3(b), the potential conflict incurs two kinds of constraints. On one hand, to keep the safe separation, $({\mathrm{\phi }}_i,{\mathrm{\phi }}_j)$ should not violate the constraint derived by $k_{\mathrm{ji}}^1$ . This constraint describes the maneuverable range around $({\mathrm{\varphi }}_i(0),{\mathrm{\varphi }}_j(0))$ . On the other hand, the initial motion states of A_i and A_j dissatisfy the constraints derived by $k_{\mathrm{ji}}^2$ . This constraint defines required modifications from $({\mathrm{\varphi }}_i(0),{\mathrm{\varphi }}_j(0))$ .

The type of constraints that is deduced by $k_{\mathrm{ji}}^1$ is defined as potential conflict constraint. As shown in Figure 5(b), $P_o^{\mathrm{ij},b}\in {\mathrm{FR}}_{\mathrm{hh},b}^{\mathrm{ij}}$ . The maximum adjustable vector ${\mathbf{u}}_{\mathrm{hh}}^{p,b,\mathrm{ij}}$ is defined as ${\mathbf{u}}_{\mathrm{hh}}^{p,b,\mathrm{ij}}=(\underset{P_{\mathrm{hh}}\in l_{\mathrm{hh}}^{m,b}}{\arg min}\Vert P_{\mathrm{hh}}-P_o^{\mathrm{ij},b}\Vert )-P_o^{\mathrm{ij},b}$ . To keep the safe separation between UAVs, ${\mathbf{m}}_{\mathrm{on}}^{\mathrm{ij},b}.{\mathbf{u}}_{\mathrm{hh}}^{p,b,\mathrm{ij}}/\Vert {\mathbf{u}}_{\mathrm{hh}}^{p,b,\mathrm{ij}}\Vert \le \Vert {\mathbf{u}}_{\mathrm{hh}}^{p,b,\mathrm{ij}}\Vert$ should be satisfied.

If the modification vector ${\mathbf{m}}_{\mathrm{on}}^{\mathrm{ij},b}$ is determined, the heading modification policy $({\mathrm{\phi }}_i,{\mathrm{\phi }}_j)$ could be determined. The space mapping computation could be solved efficiently with considering the periodicity nature of the sine function. ³⁰

The space mapping based conflict-free local optimal solutions search algorithm

According to the discussion above, we realize that the multi-UAV conflict resolution model defined in (15) and (16) is a MINP model. As the safe separation constraints are non-convex, there is no efficient solver that meets the online computation requirement. According to the discussion in section III B, we propose to search the local optimal solution based on the features of the problem.

There are lots of efficient non-linear solvers. These solvers need to start from feasible initial solutions. Therefore, the main challenge for the problem defined in (15) and (16) is to generate feasible initial solutions efficiently. We propose to find the initial feasible solution in virtue of the space mapping-based iterative searching algorithm.

When the middle-air conflict is a pairwise conflict, the feasible solution could be easily generated as A_i and A_j only need to modify their headings so that the mapping value in the sine value space satisfies that $x_{s,n}^{i,b}-x_{s,o}^{i,b}\le u_h^{i,b}$ and $y_{s,n}^{j,b}-y_{s,o}^{j,b}\le u_h^{j,b}$ respectively, as shown in Figure 5(a).

When the number of conflict-involved UAVs is more than two, the safe separation constraints among UAVs become highly coupled, the feasible maneuver policies could not be generated directly from minimum adjustment vectors. The information of ${\mathbf{u}}_{\mathrm{hh}}^{b,\mathrm{ij}}$ and ${\mathbf{u}}_{\mathrm{hh}}^{p,b,\mathrm{ij}}$ could also be used to generate feasible solutions for highly coupled UAVs.

The value of $k_{\mathrm{ji}}^b,b\in 1,2$ is different for different pairwise conflict-involved UAVs. Supposing that there are three conflict-related UAVs, A_i, A_j, and A_k, the coordinate system $X_s^{i,b_{\mathrm{ij}}}{\mathrm{OY}}_s^{j,b_{\mathrm{ij}}}$ and $X_s^{i,b_{\mathrm{ik}}}{\mathrm{OY}}_s^{k,b_{\mathrm{ik}}}$ are different for UAV pairs A_i–A_j and A_i–A_k, and there is no linearized transfer function between these two spaces. The conflict resolution policies of one UAVs clusters could not be searched in one common sine value space. We propose the space mapping based iterative feasible solution searching algorithm. This algorithm would search feasible solutions by iteratively computations between the unified position-degree coordinate frame and multiple local sine value coordinate frames.

We propose to find out the feasible solutions by iterative searching, as shown in Figure 6. The vectors ${\mathbf{u}}_{\mathrm{hh}}^{p,b,\mathrm{ij}}$ and ${\mathbf{u}}_{\mathrm{hh}}^{b,\mathrm{ij}}$ are used to indicate the search direction, as shown in Figure 7. The algorithm is detailed as below:

Figure 6.

The iterated feasible solution search algorithm.

Figure 7.

The feasible solution searching process in the $X_s^{i,b_{\mathrm{ij}}}{\mathrm{OY}}_s^{j,b_{\mathrm{ij}}}$ coordinate frame.

In the mth iteration, the local centralized coordinator computes the set of the minimum adjustment vectors $U=\{{\mathbf{u}}_{\mathrm{hh}}^{b,\mathrm{ij}},{\mathbf{u}}_{\mathrm{hh}}^{p,b,\mathrm{ij}}\},\forall {\mathrm{\kappa }}_{\mathrm{ij}}=1$ based on the current situation. And then, it generates the required heading maneuvers ${\mathrm{\Phi }}_{i,m}^a=\{{\mathrm{\phi }}_{i,m}^1,{\mathrm{\phi }}_{i,m}^2,...,{\mathrm{\phi }}_{i,m}^{n_i^c}\}$ for each UAV A_i with regarding the involved conflicts of A_i. After that, the coordinator could acquire the heading maneuver constraints of conflict-involved UAVs ${\mathrm{\Phi }}_m^a=\{{\mathrm{\Phi }}_{1,m}^a,...,{\mathrm{\Phi }}_{n_l,m}^a\}$ . There are two mutually exclusive search policies.

If there is no less than one UAV A_i, of which the units of ${\mathrm{\Phi }}_{i,m}^a$ are all positive or negative, then the modification of A_i is ascertained by the equation (30):

$${\mathrm{\phi }}_{i,m}=\mathrm{sign}({\mathrm{\phi }}_{i,m}^1)max\{\left|{\mathrm{\phi }}_{i,m}^1\right|,\left|{\mathrm{\phi }}_{i,m}^2\right|,...,|{\mathrm{\phi }}_{i,m}^{n_i^c}|\}$$

(30)

where $\mathrm{sign}(.)$ is the signum function. If the units of ${\mathrm{\Phi }}_{i,m}$ are not all positive or negative, then ${\mathrm{\phi }}_{i,m}$ is zero.

If there is not one UAV, of which the required modifications are all positive or negative, the coordinator would generate the modifications for each UAV:

$${\mathrm{\phi }}_{i,m}=\delta {\mathrm{\Phi }}_{i,m}^a\mathbf{\xi },i\in n_{\mathrm{l}}$$

(31)

where $\delta$ is a coefficient, and $\mathbf{\xi }$ is a random unit vector.

If the maximum absolute value of ${\mathrm{\Phi }}_m^a$ is less than a lower limited $\sigma$ , the algorithm would stop.

Supposing that the overall iteration number is $n_s$ . The feasible initial solutions of the multi-UAV conflict could be generated by the equation (32):

$${\mathrm{\phi }}_i=\sum _{m=1}^{n_s}{\mathrm{\phi }}_{i,m},i\in n_l$$

(32)

By using the iteration algorithm, the coordinator could generate feasible solutions under a group of constraints if there are feasible solutions. ³¹ The algorithm is shown in Figure 6, and the searching process is depicted in Figure 7.

After feasible solutions are generated, the local optimal solutions could be obtained by using existing efficient solvers.

As we discussed above, the feasible regions for each pairwise conflict are departed as two regions. In the multi-UAV conflict resolution problem, the algorithm would search $2^{n_l^c}$ subspaces to find the global optimal solutions in each conflict cluster, where $n_l^c$ is the number of pairwise conflicts in the conflict cluster. The computation time would increase at an exponential rate as the number of coupled pairwise conflicts increases. So, 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.

The rotations of all UAVs to one side often show good results in both centralized and decentralized methods. Referring to manned flight regulations, the solver prefers to search the local optimal solution so that all UAVs make right/left turns when the amount of conflict-involved UAVs is large.^27,39

Computational experiments

The proposed approach is tested in numerical simulations. Our approach is implemented in MATLAB on a 2.5 GHz Intel i5 quad core processor with 12 GB memory running the Windows 10 operating system. As we discussed above, we focus on the conflict resolution problem in the 2-D space. Therefore, the simulation limits both the conflicts and motions of UAVs on the 2-D planar plane. The speeds of UAVs are in the range (40, 60 m/s). The speeds of UAVs keep constant while they take heading maneuvers. The alert distance is set to be 2.5 km with consideration given to the speeds of UAVs. The safe separation radius of $A_i,i\in N$ is set at 8*v_i, and $w_{max}^i$ is set at 5°/s. In the CDR cycle, the coordinator UAV or the ground based ATM unit first receives the flight information from neighboring UAVs and detects the conflict among UAVs in each time step, and secondly computes the optimal conflict-free policies. It then broadcasts conflict-free policies to neighboring UAVs.

In the first scenario, we demonstrate our algorithm in the roundabout scenario. In this scenario, all the UAVs would reach the center position simultaneously, which makes the conflict unique and intense. Each UAV would have to consider its neighbors equally at the same time, and this scenario could be used to demonstrate the performances of algorithms in minimizing the influence on the air traffic. ²⁸

To demonstrate our method, our method, and the MILP model in Yang et al. ³¹ are used to cope with the UAVs’ roundabout conflict scenarios with the same condition. The initial states of UAVs are recorded in Table 1. The value of $\mathrm{\tau }$ is set at 35 s. The value of ${\mathrm{\rho }}_d^{i,o},\forall i\in n_l$ is set to be one. ${\mathrm{\rho }}_d^i$ is defined as (33):

$${\mathrm{\rho }}_d^i={\mathrm{\rho }}_d^{i,o}+d_{\mathrm{dev}}^i/v_i$$

(33)

Table 1.

The initial states of UAVs in roundabout scenario.

UAV ID	Initial state (km, km, rad, m/s, rad/s)
A1	(13.87, 14.85, 0.70, 50, 0)
A2	(18.77, 13.06, 1.39, 44, 0)
A3	(24.24, 12.65, 2.09, 53, 0)
A4	(28.41, 16.94, 2.79, 56, 0)
A5	(27.52, 22.73, 3.49, 50, 0)
A6	(23.76, 26.51, 4.18, 47, 0)
A7	(18.44, 28.82, −1.39, 56, 0)
A8	(13.87, 25.14, −0.69, 50, 0)
A9	(10.56, 20, 0, 59, 0)

Figure 8 shows the summation of the distances between real positions of UAVs after conflict resolution and their planned positions. It shows explicitly that the iterative optimization method would lead to fewer additional flight distances than the MILP based method.

Figure 8.

Distance between real positions and the planned positions of UAVs.

Figure 9 shows the online planned flight paths of the conflict-related UAVs. As shown in Figure 9, all these UAVs would take right turns cooperatively to avoid each other. We could recognize that UAVs are assigned with small heading modifications during the flight, and UAVs return to the nominal paths after they go through the conflict region. Both these two algorithms could generate smooth flight paths. From a finer viewpoint, we find that the MILP method generates much larger detours for UAVs, such as UAV A₁ and A₂. The reason is that there is not an online coordination mechanism to modify the maneuver responsibilities between UAVs based on their situations. We find that by using our method, UAVs would take different heading maneuver ranges, which is different from the MILP model.

Figure 9.

The conflict-free flight paths of UAVs: (a) MILP method and (b) iterative optimization method.

According to the simulation, the iterative method would take about 0.1 s to generate a local optimal solution for 9 UAVs roundabout scenario, and the MILP method would take about 0.07 s to generate a near-optimal solution. The result shows that our method would take much more time to generate conflict-free solutions. However, as we set the alert distance as 2.5 km and the speeds of UAVs are in the range (40, 60 m/s), the local coordinator would foresee the conflict dangers before 40–50 s. Therefore, the computation efficiency meets the online planning requirements. We would analyze the reason that the MILP leads to more additional distance. The MILP built in Athanasiadou et al. ³⁵ is based on the linearization method. According to the linearization method, the conflict avoidance requirement of each pairwise conflict is decoupled into fixed responsibilities of two UAVs. As shown in Figure 10, the original feasible regions are the blue triangles. However, using the linearization method, the feasible regions of A_i and A_j are the green rectangles.

Figure 10.

The comparison between MILP and our method: (a) mapping coordinates for practical conflict and (b) mapping coordinates for potential conflict.

On the contrary, in our approach, the space mapping method is used to determine the directions that could alleviate the conflict dangers in each iterative searching process. Therefore, the feasible regions of pairwise conflict-involved UAVs are the whole blue rectangles as shown in Figure 10.

According to the MILP method, the feasible region of each pairwise conflict is obviously reduced. As a consequence, when the number of conflict-involved UAVs increases, the original feasible regions of each UAV would be smaller because of multiple conflict resolution constraints. In this situation, according to the linearization method, there may be no feasible region for some UAVs. Therefore, the MILP method will have the difficulty to generate feasible solutions when the number of conflict-involved UAVs is large even though there exist feasible solutions. On the contrary, our approach would find feasible solutions by using the iteratively updated ${\mathbf{u}}_{\mathrm{hh}}^{b,\mathrm{ij}}$ and ${\mathbf{u}}_{\mathrm{hh}}^{p,b,\mathrm{ij}}$ as precise searching direction indicators.

Table 2 records the initial states of 20 UAVs which will converge to the position (20, 20 km). Take the conflict resolution problem of these 20 UAVs as an example. Since the velocities and initial positions of conflict involved UAVs are different, the maneuverable ranges of these UAVs would be different. In addition, as there are many UAVs in the local environment, the maneuverable ranges of some UAVs are limited. Therefore, this complex conflict scenario could not be resolved using the MILP algorithm. In contrast, our method could generate conflict free solutions by iteratively searching the feasible solutions in the whole feasible regions. The conflict free flight paths that are generated using our method are shown as Figure 11. It can be demonstrated that our method is more agile and efficient in generating the conflict free solutions for increased number of UAVs.

Table 2.

The initial states of UAVs in roundabout scenario.

UAV ID	Initial state (km, km, rad, m/s, rad/s)
A1	(11.44, 17.218, 0.314, 50, 0)
A2	(11.84, 14.07, 0.628, 56, 0)
A3	(13.757, 11.40, 0.942, 59, 0)
A4	(17.38, 11.95, 1.256, 47, 0)
A5	(20, 9.38, 1.571, 59, 0)
A6	(22.948, 10.92, 1.885, 53, 0)
A7	(24.65, 13.59, 2.20, 44, 0)
A8	(26.84, 15.02, 2.51, 47, 0)
A9	(29.07, 17.05, 2.83, 53, 0)
A10	(30.61, 20, 3.14, 59, 0)
A11	(30.1, 23.28, 3.456, 59, 0)
A12	(26.84, 24.97, 3.77, 47, 0)
A13	(26.24, 28.59, 4.084, 59, 0)
A14	(23.28, 30.10, 4.398, 59, 0)
A15	(20, 29, −1.57, 50, 0)
A16	(16.88, 29.58, −1.266, 56, 0)
A17	(15.02, 26.84, −0.94, 47, 0)
A18	(12.71, 25.29, −0.628, 50, 0)
A19	(9.89, 23.28, −0.314, 59, 0)
A20	(9.92, 20, 0, 56, 0)

Figure 11.

The conflict free flight paths of 20 UAVs that are generated by using our algorithm.

In the second scenario, we demonstrate our algorithm in a general situation. The second example demonstrates that our algorithm can handle the typical CDR problem in air traffic management. Suppose there are eight UAVs in the local environment and their initial states are recorded in Table 3. As the initial positions of UAVs are close, our method faces the challenge to coordinate related UAVs more elaborately to find feasible solutions. To guarantee to find the feasible solutions in the congested environment, the value of $\mathrm{\tau }$ is set to be 25 s. Figure 12 shows the conflict-free paths generated by our method.

Table 3.

Initial states of multiple UAVs.

UAV ID	Initial state (km, km, radian, m/s)
UAV 1	(21, 21, 0.52, 50)
UAV 2	(23, 21, 1.34, 45)
UAV 3	(24.5, 21.3, 2.33, 42.5)
UAV 4	(25.5, 22.5, 3.22, 47.5)
UAV 5	(25.2, 23.3, 3.84, 52)
UAV 6	(23, 24, −0.63, 35)
UAV 7	(21, 24, −0.78, 47.5)
UAV 8	(22, 22.5, 0, 40)

Figure 12.

The conflict resolution results of multi-UAVs congested environment.

Figure 9 shows our method could generate conflict-free solutions that assure UAVs take minor detours. According to our method, UAVs would go through the central area without abrupt maneuvers.

Figure 13 shows the minimum distances of each UAV with its neighbors in the time period (1, 150 s). The safe radii of UAVs are different as they are defined correlated with their velocities. In Figure 13, the safe radius of each UAV is depicted by the same type of lines as the corresponding minimum distance curve but finer. According to the figure, we find that the initial distances between UAVs are rather small considering the defined safe radii. UAVs are rather close to each other in this time period. However, our method could coordinate the flight paths of related UAVs to keep safe separation.

Figure 13.

The minimum distance of each UAV with other UAVs during the flight. The conflict resolution method is the local centralized optimization method.

Furthermore, we demonstrate the proposed algorithm by using the Monte Carlo method. In this scenario, the initial positions of UAVs are randomly generated. We set these UAVs would randomly go through the central region. Therefore, they would meet with airspace conflicts during their flights. Figure 14 shows the randomly generated scenario that 20 UAVs flying in the local airspace, and the proposed algorithm is used to deal with the conflict situation in the scenario.

Figure 14.

The 20 UAVs randomly go through the central region scenario.

We generate many random instances for each specific number of UAVs in the range (8, 20). As there are tracking errors in the Dubins curve-based flight trace tracking method, we define that two UAVs keep the safe separations when the distances between them are larger than 0.95 $r_s^{\mathrm{ij}}$ . We collect the data on the time period that each pair of UAVs loses safe separation during the flight by using the proposed algorithm and without using any algorithm. The success rate is defined as (34).

$$\mathrm{SR}=1-\frac{T_c^r}{T_c^{\mathrm{ur}}}$$

(34)

where $T_c^r$ is the summation of time periods that each pair of UAVs involves in lose-separation danger when applying the proposed method. $T_c^{\mathrm{ur}}$ is the summation of time periods that each pair of UAVs involves in lose-separation danger according to the original flight plan.

Furthermore, we have studied the capability of the proposed approach for alleviating serious loss separation dangers (the serious loss separation danger is defined as the distance between two UAVs is below 0.5 $r_s^{\mathrm{ij}}$ ). The performance of our algorithm is evaluated by the parameter $\mathrm{SLOS}$ as defined in (35).

$$\mathrm{SLOS}=\frac{T_{\mathrm{slos}}^r}{T_{\mathrm{slos}}^{\mathrm{ur}}}$$

(35)

where $T_{\mathrm{slos}}^r$ is the summation of time periods that each pair of UAVs meet serious lose-separation dangers when applying the proposed method. $T_{\mathrm{slos}}^{\mathrm{ur}}$ is the summation of time periods that each pair of UAVs involves in serious lose-separation danger if they do not take conflict avoidance maneuvers all along. The conflict resolution results are shown in Table 4.

Table 4.

The conflict resolution rates of the proposed algorithm.

UAV number	8	9	10	11	12	13	14
$\mathrm{SR}$	1	1	0.996	0.985	1	0.994	0.985
$\mathrm{SLOS}$	0	0	0	0.009	0	0	0
UAV number	15	16	17	18	19	20
$\mathrm{SR}$	0.988	0.982	0.983	0.974	0.976	0.976
$\mathrm{SLOS}$	0	0	0	0	0	0

As the number of UAVs in the local airspace increase, the airspace conflicts among UAVs would become more intense. Meanwhile, the conflict avoidance maneuvers of UAVs would lead to more subsequent conflicts. As a consequence, there would be some unresolvable situations in the dense environment. As shown in Table 4, the value of $\mathrm{SR}$ would decrease gradually as the number of UAVs increases. On the other hand, we find that the proposed algorithm is able to alleviate the conflict situation effectively such that two UAVs would rarely involve in serious conflict, as shown in Table 4.

Conclusion

When UAVs are permitted to fly in the non-segregated airspace, there would be occasions that many UAVs are congested in the local airspace. The geometric guidance-based conflict resolution approach have great potential in dealing with serious conflict resolution problems. The existing related researches are either computational inefficiency or may lead to redundant flight paths. This paper presents a two-layered geometric-based optimization model. The space mapping method is applied to find the minimum adjustment vectors and the maximum adjustable vectors from nonlinear safe separation constraints in the sine value space. These vectors could be used to indicate the search directions that could alleviate the conflict hazards. The iterative algorithm is proposed to search conflict-free initial solutions. It is time-consuming to search the global optimal solution for many UAVs with related conflicts because the feasible region of each pair of conflicts is divided into many sub regions. Since the online cooperation between UAVs must be satisfied, we use the commercial aviation flight regulation to get the local optimal solution, in which the UAVs will take a right turn to avoid each other. The simulation experiment proves that the computational efficiency and the quality of the obtained solution can meet the requirements to a great extent.