The Velocity Assignment Problem for Conflict Resolution with Multiple Aerial Vehicles Sharing Airspace

Depósito de Investigación de la Universidad de Sevilla https://idus.us.es/ . This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/s10846-012-9768-4 1 The velocity assignment problem for conflict resolution with multiple aerial vehicles sharing airspace D. Alejo*, J. M. D´ ıaz-B´ a˜ nez**, J. A. Cobano*, P. P´ erez-Lantero*** and A. Ollero*˜ * *Robotics, Vision and Control Group Engineering School, University of Seville 41092 Seville, Spain **Applied Mathematics II Department Engineering School, University of Seville 41092 Seville, Spain ***Escuela de Ingenier´ ıa Civil en Inform´ atica, Universidad de Valpara´ ıso 2340000 Valpara´ ıso, Chile ˜ *Center for Advanced Aerospace Technologies (CATEC) Aeropolis, Aerospace Technological Park of Andalusia 41309 La Rinconada-Seville, Spain [dalejo,jacobano,aollero]@cartuja.us.es,[email protected],[email protected] Abstract—Efficient conflict resolution methods for multiple aerial vehicles sharing airspace are presented. The problem of assigning a velocity profile to each aerial vehicle in real time, such that the separation between them is greater than a given safety distance, is considered and the total deviation from the initial planned trajectory is minimized. The proposed methods involve the use of appropriate airspace discretization. In the paper it is demonstrated that this aerial vehicle velocity assignment problem is NP-hard. Then, the paper presents three different collision detection and resolution methods based on speed planning. The paper also presents simulations and studies for several scenarios. I. INTRODUCTION Automation technologies will play an important role in the different applications of Unmanned Aerial Vehicles (UAVs) and Air Traffic Management (ATM) systems that should satisfy high air traffic demand. Moreover, the integration of UAVs in nonsegregated aerial spaces is being also considered for the future ATM [1]. Systems with multiple UAVs present significant advantages in different applications by increasing efficiency, performance, reconfigurability, and robustness [2][3]. In these scenarios, the UAVs should maintain as much as possible the planned trajectories but also maintaining minimum separation between them. UAV conflict detection and resolution (CDR) methods have been studied extensively. An overview of papers on deconfliction can be found in [4], where the CDR methods are characterized depending on the following factors: dimensions of the state information, technique for dynamic state propagation, conflict detection threshold, conflict resolution technique, maneuvering dimensions, and management of multiple UAV conflicts. There are methods for optimal coordinated maneuvers but these require significant computational effort [5]. Another CDR method is based on a mixed-integer linear program (MILP) to optimize the total flight time by modifying velocity or heading [6]. However, this method only allows one speed change for each aircraft. There are also several methods in which conflicts are solved by changing only the speed [7]. Some of these methods are devoted only to pairwise conflicts and involve computational studies to forecast future traffic levels [8]. The geometric approach presented in [9] is also for pairwise non- 2 cooperative aircraft collision avoidance. In [10] the uncertainties encountered when solving pairwise conflicts are considered. The method described in [11] is based on MILP to solve pairwise conflicts by changing speeds for a large number of aircrafts. The method proposed in [12] considers the problem in three dimensions using mixed-integer nonlinear programming to solve the conflicts with only velocity changes by minimizing the total flight time. However, this approach requires a high computation time. The method in [13] is based on the use of genetic algorithms to solve conflicts by considering the problem of optimal path planning between given waypoints. The main drawback of genetic algorithms is that the computation time is not predictable and the convergence to a solution is not ensured in a finite time interval. The optimal control method in [14] uses a kinematic model of the aircraft flying in a horizontal plane with constant velocity and solves conflicts for two or three aircraft by changing the heading. Another approach [15] involves the application of a hybrid system model that generates safe maneuvers. On the other hand, the stochastic method described in [16] is based on the Monte Carlo approach and the computation time is again high. In this paper, a 3D conflict resolution problem for multiple UAVs sharing airspace is studied, where a state propagation method is needed to predict trajectories. There are numerous techniques to predict positions in conflict detection [17][18][19][20][21]. In this work it is assumed that the initial trajectories of each UAV are known (given by a sequence of waypoints) and the detection method is based on a grid model. Therefore, each trajectory is defined by the cells through which the corresponding UAV passes. The methods proposed in this paper are based on speed planning to solve conflicts. The velocity profiles for all the UAVs involved in a conflict are computed and the problem is solved by maintaining the planned 3D space trajectory. This approach has the advantage that the probability of creating new conflicts with other UAV in the airspace is low. A dynamic environment is also considered. In this environment the conflicts between two or more UAVs are solved in real time, at low computational cost, once they are detected. Three methods are presented here. In the first one, the problem is reduced to a scheduling problem and then a greedy approach is considered in order to find an optimal solution. In the second method, a discrete velocity allocation (DVA) problem considering pairs of velocities is implemented to solve the conflicts. Finally, the third proposed method is based on the technique presented in [22], in which suboptimal solutions are found. This method presents several advantages with respect to [22]: it solves conflicts with more than two UAVs and ensures minimum separation between UAVs. In this paper different kind of scenarios are simulated to point out the characteristics of the proposed methods. This paper is organized in seven sections. Section II presents the problem formulation. Proof that the Velocity Assignment Problem (VAP) is NP-hard is provided in Section III. The proposed conflict resolution methods are described in Section IV. Finally, section V shows the simulations carried out and Section VI details the conclusions. II. PROBLEM FORMULATION The problem considered in this paper concerns conflict detection and resolution between UAVs in a common airspace. The detection algorithm is based on the discretization of the airspace divided into cubic cells, also called the grid model (see Figure 1). Other possible way to encode the statement of the problem are [23][24]. The discretization is chosen in this paper because the detection algorithm is simpler and faster. Moreover, a trajectory can be parameterized by the number of cells that the UAV passes through with entrance and departure time. The size of the cells is a parameter and the safety distance is given by a number of cells. The resolution algorithm is based on changing the velocity profile of the UAVs involved in the potential collision. Note that velocity refers to speed in this problem because changes of velocity direction are not considered. The time for which each UAV stays in a cell depends on its model. It is assumed that each UAV knows the trajectories of other UAVs, i.e., the list of cells that other UAVs will fly across (see Figure 2). Thus, in Figure 1 the cells through which UAV1 passes are: 7, 4, 5, 2, 3. In the case of UAV2 they are: 9, 6, 5, 4, 1. Both UAVs fly in the same flight level. Method described in [22] presents a disadvantage. Collision is defined when two UAVs lay in the 3 Figure 1. UAV trajectories in a discretized airspace divided into cells. Figure 2. The UAV trajectory is described as a sequence of visited cells. same cell and at the same time. However, with this definition two UAVs that are not in the same cell can be closer than other two ones that are actually in the same cell (see Figure 3). Therefore the algorithm based on the simple space discretization in cells does not ensure minimum separation between UAVs. A natural idea to cope with this disadvantage is simply to change the conflict definition. In this paper we consider that two UAVs maintain the minimum separation if they are separated vertically and horizontally by a safety distance. If there is an UAV in a cell C, there is a conflict when there is another UAV in a neighboring cell to C. The following definitions are considered in this paper: •Neighboring cells to C: is the set of cells whose distance is less than the safety distance considered (see Figure 4). Figure 3. Disadvantage of the grid model: UAV3 and UAV4 are in conflict while UAV1 and UAV2 are not. •Conflict: a cell Ccrossed by an UAV is in conflict if there is another one which crosses a cell in the neighborhood of C. •Conflict Zone (CZ): set of consecutive cells of two or more UAVs that are in conflict (see Figure 5). •Collision: there are two UAVs crossing a CZ at once. One of the first approaches of the collision avoidance problem in robotics was proposed in [25], where once all paths have been planned by each aerial vehicle, a velocity profile that avoids collisions in all paths is found by means of the proposed Velocity Planning Problem (VPP) methods assigning velocities. The VAP addressed in this paper can be defined mathematically as follows: Let U={U1, ..., Un} be a set of UAVs represented by points in a threedimesional space moving with constant initial velocities onto straight lines. Each UAV has a constrained interval of available velocities and when a collision is detected, a velocity is assigned to each of the involved UAV. The initial velocities are modified under the constraints, such that the collision is avoided and the total deviation from the initial velocities is minimized. In this model, each UAV Uihas an initial trajectory identified by its initial velocity vi. These velocities are computed to optimally perform a given mission. The method finds new velocities such that a given criterion is optimized. The objective function or total deviation can be modeled as: 4 Figure 4. Examples of neighboring cell definition with different safety distances. Figure 5. Conflict zone (gray) in a scenario with two UAVs. The safety distance is given by two cells. J= n X i=1 Ci X j=1 tij −t0 ij2(1) where nis the number of UAVs of the system, Ci is the number of cells crossed by the Ui,tij and t0 ij are the stay times of the Uiwhen crossing the cell number jin the solution trajectory and the original trajectory respectively. Basically, the objective is to minimize this total deviation with respect to the initial stay time in each cell. The VAP is NP-hard; that is to say, a polynomial time algorithm is not possible or, unless, P=NP [26]. Although it is generally assumed that this problem is NP-hard, we do not know where the proof is published. This is proved in Section III. Therefore, we propose some strategies based on velocity planning for the collision avoidance problem of UAVs sharing airspace. Three methods are proposed to avoid collisions (see Section IV): 1) the Greedy method (G), 2) the use of a constrained version of the VAP problem in which pairs of velocities are allocated, and 3) a heuristic approach for velocity planning (VP) based on [22] with non trivial modifications made in order to improve the possible applications. It is worth noting that it is possible to find a solution that avoids the initial collision but generates a new collision with other UAVs. Therefore, when solving collisions we distinguish three types of UAVs: the UAVs that are directly involved in the detected potential collision, the UAVs whose trajectories collide with the possible solution trajectories of the directly involved UAVs and whose velocities can be changed, and the non-cooperative UAVs that would maintain their initial velocities. III. NP HARDNESS PROOF The NP-hardness is showed by considering a reduction from one of the so-called one-machine scheduling problems (see [27] for a comprehensive survey). The problem that is reduced in this case is the “Sequencing with Release Times and Deadlines” (SRD), which is strongly NP-complete [27], [26] and defined as follows: Given Njobs - each associated with a release time, a deadline, and a processing time - decide whether there is a nonpreemptive schedule of these Njobs on a single machine such that all jobs meet their deadlines. In other words, the SRD asks for a sequence of execution of the Njobs so that no execution of any job is interrupted to execute any other job, no two jobs are executed at a same time, and every job starts not before its release time and finishes not after its deadline. By exploiting the similarity between jobs which are to be non-preemptively scheduled on a single machine, and UVAs that must pass one after another through a single cell of the discretized space, we prove the following theorem: Theorem 3.1: The VAP is NP-hard. 5 Proof: Let ISRD be an instance of the SRD consisting of njobs j1, j2, . . . , jn. Each job jihas release time tmin(i), processing time D(i), and deadline tmax(i). We reduce ISRD to the following instance V APSRD of the VAP: •All aerial vehicles UAV1, UAV2, . . . , UAVn pass at the same time through a same cell C of the discretized space. •Once a vehicle enters C, it increases its speed to the maximum possible value in order to lie inside Cthe minimum amount of time, giving more chances to other UAVs of entering C. •The speed range of each vehicle allows UAVi enter Cat least at time tmin(i)and at most at time tmax(i)−D(i), where D(i)is the amount of time in which UAViis inside Cmoving at its maximum speed. Let t(i)denote the time in which UAVienters C. If instance V APSRD has any feasible solution, then we can obtain a sequence UAVπ1, UAVπ2, . . . , UAVπn of the UAVs so that they enter Cin this order. Furthermore, for all 1≤i≤n,UAVπisatisfies both tmin(πi)≤t(πi)and t(πi) + D(πi)≤ tmax(πi). Then, jobs j1, j2, . . . , jncan be scheduled as jπ1, jπ2, . . . , jπn, where job jπistarts at time t(πi), giving a solution to instance ISRD. Proving that instance ISRD has a solution implies that instance V APSRD has a feasible solution is similar. Therefore, there exists a solution to ISRD if and only if V APSRD has a feasible solution. Then, deciding if the VAP has a feasible solution is NP-complete and the result follows. In subsequent research, the use of heuristics for scheduling problems can be explored. For example, a related problem is the following one: Given N tasks with release times, durations and deadlines, find a non-preemptive schedule such that all tasks meet their deadlines and the number of machines used to process all tasks is minimum. This is known as the “Scheduling with Release Times and Deadlines on a Minimum Number of Machines” and it is NP-hard [27]. In the same paper some approximation algorithms and heuristics were also proposed. It should be noted that if one is able to modify not only the speed but also the altitude of the UAVs in the cell of the space through which they pass at the same time, the cell could be considered a multiprocessor. Each processor of the cell will correspond to a different altitude, in charge of scheduling the entrance and departure times of the UAVs. IV. PROPOSED METHODS In this section we present three CDR methods for UAVs, all based on speed planning. When the trajectories are computed, our methods check whether there are some UAVs whose trajectories could be in conflict. When such a case is identified, a further computation decides whether there would be a collision. A potential collision is solved by changing the stay times of each UAV in each cell; that is, by assigning a velocity profile to each UAV. The proposed methods are centralized. Scalability is one of the most important advantages of decentralized methods have, while centralized methods could present a disadvantage for being prone to failures in the central system. The aim in this paper is to search for near-optimal solutions. For this reason, the planned trajectories of all UAVs must be known. However, scalability can be achieved in centralized methods by applying it not to the whole system but to a subset composed only by the UAVs involved in a conflict (see section II). A. Greedy method The Greedy method (G) works as an on-line algorithm in which the decision concerning some UAVs in conflict, whose speed must be modified, does not use any information related to future conflicts. The problem can be reduced to an on-line scheduling problem [28]. Let U={U1, U2, ..., Un}be the UAVs and assume that their initial speeds are the possible maximum ones, respectively. It is also assumed that the cells of the space are enumerated. We further consider that each UAV Uiflies from time t= 0 to time t=tfpassing through some cells of the space. Then, for each UAV we partition its flight time-line [0, tf)into intervals, where each interval corresponds to the period of time in which Uipasses through a cell. In other words, each time-line of any UAV is a consecutive sequence of labeled intervals, meaning the sequences of cells UAV Uipasses through (see Figure 6(a)). For the sake of simplicity, the Greedy method is presented for conflict cells. However, it can be generalized to conflict zones. 6 Figure 6. Greedy algorithm. UAV1passes through cells 3, 5, 1, 2 y 7. When t=t1(a) the velocity of UAV2is decreased delaying its stay on cell 5 for avoiding the collision with UAV1in cell 3 (b). Let Ui(t)denote the label of the cell in which UAV Uiis at instant of time t. The Greedy method considers the arrangement of labels Ui(t)and makes a sweep from t= 0 to tfwhile changing the speed of the UAVs accordingly in order to maintain the invariant that, at any time t, no pair of distinct UAVs Uiand Uj, such Ui(t) = Uj(t)exists. In order to achieve this goal the following rule is applied: If at instant tsome UAV Uienters to the cell labeled kand there exists an UAV Ujsuch that Uj(t) = k, then the speed of Uiis decreased to avoid the collision with Ujon that cell. Figure 6 shows an example where the outcome of situation (a) in which UAV2tries to enter in cell 3 in which UAV1is passing through, is situation (b) where UAV2enters cell 3at the same time as UAV1leaves. Suppose that at instant tin the sweep, UAV Ui is in cell k, and UAV Ujand UAV Upenter cell k. It must be decided whether Ujor Upis more retarded. This case is called decision situation and the decision taken might cause new conflicts for future instants of time, or possibly lead to a point in which there is no way of avoid collisions between the UAVs. The Greedy method described above has been implemented as a first or preprocessing step, working as follows. If no decision situation is found then an optimal solution for the VAP problem is obtained. Otherwise, the Greedy method is stopped because it cannot guarantee to obtain an optimal solution. At this point any approximation method (e.g. any of those proposed in following sections) can be applied. B. The discrete allocation problem In this section we consider the discrete velocity allocation problem (DVA), that is, the VAP subject xixj Fij = (xi∧xj)∨(xi∧xj) Figure 7. Fij means that UAViand UAVjdo not collide if they have the same velocity, either v0or v1. to a discrete set of velocities. A solution for this problem gives an approximation to the general continuous VAP. Given a partition of the interval of velocities v1, v2, . . . , vmassign a vito each UAV such that there is no collision between the UAVs when they move constantly with the allocated speed. Firstly, we deal with an easier problem, called the Two Velocity Assignment Problem (2-VAP) in which two fixed velocities v0and v1are only considered. Let UAV1, UAV2, . . . , UAVnbe the n UAVs. Theorem 4.1: The 2-VAP can be solved in O(n2) time in the worst case. Proof: Consider nlogic variables x1, x2, . . . , xn, where xi= 0 if UAViis assigned velocity v0, and xi= 1 otherwise. For each pair UAVi, UAVjof UAVs we can test that assignments of velocities do not collide (i.e. assignment of 0’s and 1’s to xiand xj). Then, we can obtain a logic formula Fi,j, with variables xiand xj, such that all its positive interpretations imply an assignment of velocities to both UAViand UAVj, so that they never collide. Each Fi,j can be rewritten in Conjunctive Normal Form with two variables per clause (i.e. xiand xj) (see Figure 7). Therefore, our problem is reduced to assigning 0’s and 1’s to x1, x2, . . . , xnsuch that F= Vn i=1 Fi,j = 1, where Fis also in Conjunctive Normal Form with two variables per clause. This is an instance of the 2-SAT problem which can be solved in polynomial time as follows [29]: Let GF=hV, Eibe a directed graph, where V= {x1,¯x1, x2,¯x2, . . . , xn,¯xn}and (α, β)∈Eif and only if there exists in Fa clause logically equivalent to ¯α∨β(see Figure 8). It holds that Fis unsatisfiable if and only if for some xithere exist in GFa path from xito ¯xiand a path from ¯xito xi. Thus, polynomial time algorithms on path searching in graphs can be applied. A refined algorithm running in O(n+n0) time is possible [29], where n0is the number of edges of GF. Since n0is O(n2)in the worst case, the result follows. 7 x1 x2 x2 x3 x3 x1 Figure 8. The graph GFcorresponding to F= ( ¯x1∨x2)∧( ¯x2∨ x3)∧(x1∨¯x3)∧(x2∨x3). It is worth noting, using arguments similar to the above ones, that whenever three or more velocities are used instead of two, the problem can be reduced to an instance of the k-SAT problem (k≥3), which is NP-complete [26]. Using the above algorithm to solve the 2-VAP, we can give an approximation algorithm to the discrete version of the VAP. We solve the 2-VAP for each pair of velocities and, if a pair of velocities avoiding collision exists, it can be identified as an approximation to the optimal trajectory. Then, we select the best pair of velocities found, that is, that minimizing the deviation from the initial trajectory. By applying this approach, we assign two velocities to the UAVs, without collisions, from a finite set of velocities. Since O(m2)pairs of velocities are tested, the time complexity of this approximation is O(m2(n2+t)) in the worst case, where tis the time spent in computing the total deviation from the initial trajectories. This algorithm is very efficient in dense airspace although the solution is an approximation to the optimal deviation. Therefore, the use of this algorithm involves considering a trade-off between computation time and flight plan deviation. C. Heuristic velocity planning with optimization phase This method can also be applied in the case where the Greedy method does not solve the avoiding collision problem. The method, that will be called VP, is based on the algorithm presented in [22]. The method has two steps: •Search tree step, which finds a solution if it exists by exploring all possible arrival orders to each conflict zone, and •Optimization step, which minimizes a cost function. In this method each UAV trajectory is decomposed into zones that consist of groups of cells (see Section II). In contrast, the method proposed in [22] considers each cell separately. 1) Search tree step: This step asks if the collision avoidance problem can be solved by performing changes in the velocity profiles of the UAVs. The goal of the search tree algorithm is to obtain arrival orders to each CZ that provide a valid solution. In this step, we assume that all the vehicles travel at their maximum velocity. Then it is only possible to decrease their velocities to avoid a collision. Let us consider a scenario with two UAVs and only one CZ described in Figure 5. The building of a tree is described in Algorithm 1. Each node of a tree represents a visited cell for the UAV. Let us consider two nodes, Niand Ni+1, that are related to neighbor cells, C(i)and C(i+ 1). We assume that Niis the parent of Ni+1. The corresponding edge between them has assigned a weight w. This weight is calculated according to the following formula and considering maximum speed of each UAV (see step 7): w(Ni, Ni+1) = tin(C(i+ 1)) −tin(C(i)) (2) where tin(C(j)) represents the entrance time to the cell C(j). Let us also define the arrival order to a CZ as the order in which the UAVs pass through it. This order is determined by the estimated arrival time to the CZ of each UAV (see step 2) and influences the building of each tree in order to decide if the building stops or continuous by comparing the arrival time to the CZ with the time of the UAVs preceding. Therefore, for nvehicles, a CZ has n!different arrival orders. All the possible arrival orders are explored until a solution is found. In the scenario showed in Figure 5, there are two arrival orders and the first one to be tested is UAV2-UAV1 because UAV2 arrives before. First, the tree is built for UAV1, then for UAV2 and so on when there are more UAVs. Whenever a CZ is reached, the tree only calculates its following weight if all UAVs that precede the UAV which is building its tree, given by arrival order, have already calculated the weights of the edges related to that CZ (steps 8 and 9). Figure 9 represents the 8 Algorithm 1 Search Tree Algorithm 1: repeat 2: Get the arrival order to all conflict zones to be checked. 3: Start the trees of all UAVs. 4: while there are some trees not completed and there are not any unavoidable collision.do 5: for each tree do 6: if the tree is not completed then 7: Calculate the minimum weights of the next edges up to the next conflict node. 8: if the end was not reached and all previous vehicles have calculated the weights of their conflict edges then 9: Calculate the weight of the conflict egde. 10: if a collision has been detected then 11: Go back and create new branches that solve the collision. Backtrack also related trees. 12: if the beginning of the tree is reached then 13: An unavoidable collision has been detected 14: end if 15: end if 16: end if 17: end if 18: end for 19: end while 20: until A solution is found or all arrival orders have been unsuccessfully checked. 21: return The arrival order of the solution, or an error if not found. complete trees in the proposed example. Note that the horizontal length of each edge is proportional to its weight. In this case, when UAV1 comes in CZ1, instant t1, it does not continue building its tree because the UAV before it, UAV2, has not calculated its weights of the edge related to that CZ, so the UAV1 tree is stopped and the UAV2 tree is started and completed. Otherwise, the algorithm will continue with the tree of the UAV1. Whenever a weight related to the CZ is calculated, the algorithm checks if the arrival time to that conflict leads or not to a potential collision with Figure 9. Trees generated in the example scenario. UAV2 tree only has one branch because is the first UAV that passes through CZ1. UAV1 has two branches because a collision has been detected in CZ1 so a backtracking process starts. regard to the UAVs preceding. In this case, when the weight associated with the CZ of UAV1 tree is calculated in the upper branch, a potential collision is detected with UAV2. If a potential collision is detected, then the algorithm creates a new branch in the tree, assigning greater weights (that is, greater differences of the entrance time, so speed decreases) in as fewer edges as necessary in order to avoid that potential collision (step 11). The lower UAV1 branch represented in Figure 9 is generated and the potential collision is avoided because UAV1 comes in CZ later, instant t2, that is, when UAV2 is leaving CZ. If the collision cannot be avoided considering the speed constrains of the UAV, the algorithm fails with the proposed arrival order and another arrival order has to be checked (steps 12 and 13). The complexity of the algorithm grows as the number of CZs increases. Let us assume that there are mCZs with nUAVs, where niof them are involved in the ith conflict. So, a total of n1!n2!, . . . , nm!different orders should be checked. The first arrival order is determined by the estimated arrival time to a CZ of each UAV. Then, each tree is built considering the arrival order to detect potential collision. If no solution is found with the first arrival order, a new order should be checked. The algorithm permutes the arrival order to the CZ from the cost function J. The CZ with highest cost is chosen to define the arrival order. This cost is defined as: Ji=µi−σi(3)