The speed assignment problem for conflict resolution in aerial robotics

Depósito de Investigación de la Universidad de Sevilla https://idus.us.es/ This is an Accepted Manuscript of an conference paper published by IEEE in: Alejo D., Cobano J.A., Trujillo M.A., Viguria A., Rodriguez A., Ollero A. The speed assignment problem for conflict resolution in aerial robotics (2012) Proceedings - IEEE International Conference on Robotics and Automation, art. no. 6225026, pp. 3619 - 3624, DOI: 10.1109/ICRA.2012.6225026 “© 2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other Works” The speed assignment problem for conflict resolution in aerial robotics D. Alejo, J. A. Cobano, M. A. Trujillo, A. Viguria, A. Rodriguez and A. Ollero Abstract— This paper presents an efficient conflict resolution method for multiple aerial vehicles based on speed planning. The problem is assigning a speed profile to each aerial vehicle in real time such that the separation between them is greater than a minimum safety value and the total deviation from the initial planned trajectories is minimized. Also, the arrival time of each aerial vehicle at the end waypoint of the trajectory is taken into account to solve the conflicts. The proposed method involves the use of appropriate airspace discretization. The method consists of two steps: a search tree step, which finds if it exists a solution; and an optimization step by solving a QP-problem, which minimizes a cost function. The paper also presents simulations for several scenarios and experiments that have been carried out in the multivehicle aerial testbed of the Center for Advanced Aerospace Technologies (CATEC). I. INTRODUCTION It has been shown that Unmanned Aerial Vehicles (UAVs) are very useful in different kind of applications such as data collection and transportation among others [1][2]. It has been also pointed out that systems of multiple UAVs offers advantages when comparing with the use of a single one in different applications by increasing efficiency, performance, reconfigurability, and robustness. Multiple UAVs can now be cooperatively used to carry out tasks where they can exchange sensor information, and perform, for example, detection and monitoring activities among other tasks [3][4]. In these tasks each trajectory has to be conflict-free. A conflict occurs when two or more UAVs experience a loss of minimum separation. Therefore, the problem is to maintain as much as possible the planned trajectories but also maintaining minimum separation between UAVs. An overview of proposed models on conflict detection and resolution (CDR) can be found in [5]. A geometric approach for pair wise non-cooperative aircraft collision avoidance is presented in [6]. Reference [7] concerns a CDR method based on a mixed-integer linear program (MILP) to optimize the total flight time by modifying velocity or heading. However, this method only allows one speed change for each aircraft. In This work was supported by the European Commission FP7 ICT Programme under the ARCAS Project (FP7-ICT-287617) and the CLEAR Project (DPI2011-28937-C02-01) funded by the Ministerio de Ciencia e Innovacion of the Spanish Government and co-funded with European Regional Development Fund. Also the partial funding from Junta de Andaluc´ ıa project P09-TEP-5120 is acknowledged. D. Alejo, J. A. Cobano, A. Rodriguez and A. Ollero are with the Systems Engineering and Automatic Control Department, University of Seville, Camino de los Descubrimientos s/n, 41092, Seville (Spain) [dalejo,jacobano,castano, aollero]@cartuja.us.es M. A. Trujillo, A. Viguria and A. Ollero are also with the Center for Advanced Aerospace Technologies (CATEC), Aeropolis, Aerospace Technological Park of Andalusia, 41309, La Rinconada-Seville (Spain) [matrujillo,aviguria,aollero]@catec.aero [8] it is assumed that aircraft cruise at constant altitude with varying velocities and that conflicts are resolved in the horizontal plane using heading change, velocity change, or a combination thereof. The paper [9] presents decentralized collision avoidance algorithms for systems with second order dynamics and acceleration constraints, using a switching control law. Other methods [10][11] are based on the use of genetic algorithms to solve conflicts by means of optimal path planning between given waypoints. In [12] the uncertainties are also considered. 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 stochastic method described in [13] is based on the Monte Carlo approach and the computation time is again high. There are also several methods in which conflicts are solved by changing only the speed [14][15]. The method described in [16] is based on MILP to solve pair wise conflicts by changing speeds for a large number of aircraft. In [17] the solution is computed in a centralized way to solve the collision avoidance problem with a minimum change of the initial trajectory. In this paper, the conflict resolution problem for multiple UAVs is studied. The speed profiles for all the UAVs involved in a conflict are computed in order to solve the problem. This approach has the advantage that the probability of creating new conflicts with other UAVs in the airspace is low. Also, we extend this kind of resolution methods to a more general case where more objectives are considered, minimizing the total deviation from the initial planned trajectory and ensuring the time of arrival at the end waypoint of the trajectory. Obviously a solution does not always exist in this approach. In the case of head-to-head conflict a change of speed is not sufficient to avoid the conflict. Another conflict resolution method should be implemented in order to solve this kind of conflict (for example, changing the heading or level of flight). Following the categorization in [5], our proposed method is described in the three-dimensional space. We assume that the initial trajectories of each UAV are known and the method to determine when a collision can occur is based on a grid model. Therefore each trajectory is defined by the 3D cells where the UAV passes through. The conflict resolution methodology is to maintain the planned trajectory and solve the conflicts by means of speed changes by minimizing a cost function. Another significant characteristic is the ability to solve conflicts among UAVs in real time. A related paper is [18] in which a CDR method for multiple UAVs is presented. The method proposed in this paper ensures separation between UAVs, which is not the case for the method described in [18]. Other improvements with respect to [21] are: acceleration constrains are included, the new generated QP-problem is simpler, that is, the number of variables and constrains is reduced, and a new cost in the QP-problem is considered. This paper is organized into five sections. The problem formulation is described in Section II. The proposed method is presented in Section III. Section IV describes the simulations and experiments performed. Finally the conclusions are detailed in Section V. II. PROBLEM FORMULATION The problem considered in this paper concerns collision detection and resolution among multiple UAVs in a common airspace. The separation among them should be greater than a minimum value. In order to maintain the previously computed planned trajectories, the heading changes are not allowed and the solution only considers speed changes. Therefore, a possible collision is solved when a collisionfree trajectory for each UAV is computed by changing cooperatively its speed profile. This is other improvement with respect to [14] where only an aircraft performs the maneuver to avoid the conflict. The detection algorithm is based on the discretization of the airspace divided into cubic cells, also called the grid model. This discretization offers the following advantages: parameterize a trajectory by the number of cells that the UAV passes through with entrance and departure time; and, the detection algorithm is simpler and faster. On the other hand, the size of cell is a parameter and is set between five or ten times lower than the minimum separation in order to minimize the discretization effects while not increasing the problem complexity. 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. In [18] a collision of two UAVs is predicted when they lie in the same cell of the discretized space at the same time. From this definition it is possible for two UAVs that are not in the same cell to be closer than another two that are actually in the same cell [17]. Therfore, the following definitions are considered in this paper: •Neighboring cells to C(i): set of cells whose separation from C(i) is less than the minimum separation. •Conflict: C(i) is crossed by an UAV and there is another UAV that crosses a cell in the neighborhood of C(i). •Conflict Zone (CZ): Let C1(n)and C2(n)be the sequence of cells visited by UAV1 and UAV2. Let us assume that C1(C5) and C2(E3) are the first conflictive cells between them (see Figure 1(A)). Eventually C1(G5) and C2(E7) are also in conflict while C1(H5) and C2(E8) are not. Then, cells C1(C5, D5, E5, F5, G5, H5) and C2(E3, E4, E5, E6, E7) compose a CZ (see Figure 1(A)). This definition could be easily extended to CZs crossed by more than two vehicles. •Collision: two UAVs cross a CZ at the same time. On the other hand, 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. Fig. 1. A) Scenario with two UAVs and conflict zone (gray cells). The safety distance is given by two cells; B) Trees generated in (A). III. PROPOSED METHOD The proposed method checks whether there are UAVs whose trajectories could be conflictive. When such a case is identified, a further computation decides if there would be a collision or not. A collision is solved by changing the stay times of each UAV in each cell; that is, by assigning a speed profile to each UAV. The method, that will be called VP (Velocity Planning), has two steps: (1) the search tree step, which finds a solution if it exists by exploring all possible arrival orders to each CZ; and (2), the optimization step, which minimizes the cost function. A. Search tree step The goal of the search tree algorithm is to obtain arrival orders for each CZ that provide a valid solution. Initially, we assume that all the vehicles travel at their maximum speed and to avoid a collision it is only possible to decrease the velocities. 1) One conflict zone problem: Let us consider a scenario with two UAVs and only one CZ described in Figure 1(A). 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). 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 in Algorithm 1): w(Ni, Ni+1) = tin(C(i+ 1)) −tin(C(i)) (1) where Niis the root node and Ni+1 is the child node. tin(C(j)) represents the entrance time to a cell C(j). 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. 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 in Algorithm 1) 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 1(A), there area 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 in Algorithm 1). Figure 1(B) represents the 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 CZ (t1) it does not continuous 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 regard to the UAVs preceding. In this case, when the weight associated to the CZ of UAV1 tree is calculated in the upper branch, a potential collision is detected with UAV2 (t1, t2). If a potential collision is detected, then the algorithm creates a new branch in the tree, assigning greater weights (that is, the time increases and speed decreases) in as fewer edges as necessary in order to avoid that potential collision (step 11 in Algorithm 1). The lower UAV1 branch represented in Figure 1(B) is generated and the potential collision is avoided because UAV1 comes in CZ in 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 in Algorithm 1). 2) More than one conflict zone: 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!...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(2) where µiand σiare the mean and standard deviation of the set of estimated arrival times of each UAV to the CZ. The mean of the arrival times to a CZ is considered because a change in earlier CZs can affect the following CZs. The standard deviation is included in order to take into account the differences between the arrival times of the different UAVs to a CZ. In order to find a solution, it is advisable to change the arrival order to a conflict where all the estimated arrival time of the vehicles involved in it are similar. The backtracking process takes place when a collision is detected and a new tree should be built for one o more UAVs. In this case, the backtracking process can become more complex than the previous case considering one CZ. Note that the backtracking process is only done for the UAVs which arrive to the corresponding CZ later. B. QP-problem When the search tree algorithm finds a solution, we have a valid arrival order for all the CZs in the collision avoidance problem. At this point, an improvement on the objective function can be done by solving a QP-problem. The QPproblem minimizes a quadratic cost function with linear constraints. The considered cost function in order to obtain the most similar trajectory to the initial one is: JQP = n X i=1 mi X k=1 tik −tref ik tref ik !2 (3) where tik is the stay time in the kth zone visited by the ith UAV and tref ik is the stay time in the original trajectory. nrepresents the number of UAVs of the system and mithe number of zones crossed by the UAV ith trajectory. The stay time in each zone can be very different, so the denominator has been included in order to minimize large variations in the stay time in small zones. This would lead to saturations in the velocity control signal. The constraints of the model are: tik −aikvik −bik ≤0(4) cik +dik −tik ≤0(5) The maximum and minimum stay time in each cell depends on the initial velocity at those cells, vik. This dependence is in fact non linear, but we have to linearize it in order to formulate the QP-problem. This is achieved by interpolation with aik,bik,cik and dik as the interpolation coefficients. Moreover, the following constraints regarding vik are considered: vik −vmax ≤0(6) vmin −vik ≤0(7) |vi,k −vi,k−1| ≤ ai,maxdi,k−1 vref (8) where i= 1...n and k= 1...mi. Eq. (6)-(7) are given by the UAV model, and (8) relates the initial velocity in one cell with the other in the previous cell because of the maximum acceleration constraint. In the third equation, ai,max represents the maximum desired acceleration of the ith UAV and di,k represents the distance traveled by the ith UAV in the kth zone. nis the number of UAVs in the system and mithe number of zones that are crossed by the ith UAV. Another constraint is considered in order to keep the Estimated Time of Arrival (ETA) at the end waypoint of each ith UAV within a margin: | mi X j=1 tij −tm| ≤ 0(9) where tflight represents the initial estimated flight time, tmis the maximum margin allowed, tij is the time spent in the jth zone by the ith UAV and miis the number of zones crossed by the ith UAV. Finally, for each CZ and each ith UAV that has to cross that zone immediately before jth UAV, the following constraints should be considered in order to avoid collisions: Q X k=1 tik − P−1 X k=1 tjk ≤0(10) where Pindicates the entry cell in the CZ of the jth UAV and Qindicates the cell that has left ith UAV. The above optimization problem can be solved by means of the QP-solver implemented in the Computational Geometry Algorithms Library (CGAL) [19]. IV. SIMULATIONS AND EXPERIMENTS Many simulations and several experiments have been carried out to validate the proposed method. The algorithms have been run in a PC with a 2GHz Dual Core processor and 2 GB of RAM. The operating system was Kubuntu Linux with kernel 2.6.32. The code has been written in the C++ language and compiled with gcc-4.4.2. In order to compute the trajectories it is necessary to model the behavior of the UAVs. In the proposed method it is possible to use models of arbitrary complexity. The simple model presented in [20] is used in the simulations. Two different scenarios, S1 and S2, are considered to analyze how the computing time depends on the scenario considered (see Figure 2 and 3). Fig. 2. Scenario S1: cell size is 150m and safety distance is 4 cells. Fig. 3. Scenario S2: cell size is 150 m and safety distance is 3 cells. The computing times and the criteria results obtained in S1 and S2 are shown in Figure 4 and 5, respectively. This method can be efficiently applied in real time to a system composed of a maximum of 6 UAVs when the solution has to be computed in few seconds. Note that the computing time required to detect conflicts also increases with the number of UAVs because more CZs are detected. The computing time Fig. 4. Computational time spent in S1 and S2. Fig. 5. Criteria results in S1 and S2. for a QP-problem increases because new CZs appear, thus adding constraints to the system. Similarly, the number of variables considered in the QP-problem also increases when new UAVs are added to the system. Two variables are needed for each zone that is crossed by an UAV. The dependency of computing time with the number of UAVs is very significant. The experiments have been carried out in the indoor multi-UAV testbed of the CATEC with four Hummingbird quadrotors (see Figure 6) with 200gr payload and up to 20 minutes flight autonomy. The testbed has an indoor localization system based on 20 VICON cameras. This system is able to provide, in real time, the position and attitude of each UAV with centimeter accuracy. The size of cell 0.1m and safety distance is 0.7m in the experiments. Fig. 6. Testbed where the experiments were carried out. In the first experiment, a circular scenario is considered (see Figure 7). The parameters are: vik=0.5m/s, vmin=0.05m/s, vmax=2m/s, tflight=16s and tm=1.5s. A conflict is detected in the center, and then the method computes the speed profile for each UAV to avoid it in a cooperative way by minimizing the cost (2). The speed profile (SP) computed for each UAV and the time of speed change (T) are shown in Table I. When a UAV comes into the CZ it increases its speed in order to exit more rapidly. The order of entry in this case is: UAV3, UAV4, UAV1, UAV2. Moreover, each UAV maintains its initial trajectory and fulfills its ETA (5). These values are shown in bold in Table I. On the other hand, Figure 8 shows the separation between UAVs. Fig. 7. Experiment 1(grey lines) and Experiment 2 (black lines). TABLE I SPEED PROFILE AND TIME FOR EACH UAV IN EXPERIMENT I. UAVs SP(m/s) T(s) UAVs SP(m/s) T(s) 1 0.268 7.609 3 0.945 2.699 1 2.000 9.948 3 1.533 5.321 1 0.228 14.870 3 0.137 14.531 2 0.232 9.772 4 0.425 5.571 2 0.880 13.976 4 2.000 7.714 2 0.627 17.481 4 0.164 14.774 Fig. 8. Experiment I: separation between UAVs. The second experiment presents a different scenario (see Figure 7). The considered parameters are: vik=0.2m/s, vmin=0.05m/s, vmax=0.8m/s, tflight=40s and tm=1.5s. The speed profiles are shown in Table II. Also, the separation between UAVs is depicted in Figure 9. TABLE II SPEED PROFILE AND TIME FOR EACH UAV IN EXPERIMENT II. UAVs SP(m/s) T(s) UAVs SP(m/s) T(s) 1 0.208 11.091 3 0.127 18.388 1 0.205 18.396 3 0.227 25.287 1 0.166 21.257 3 0.198 27.718 1 0.203 28.767 3 0.256 33.739 1 0.200 39.947 3 0.283 41.312 2 0.188 12.048 4 0.362 6.616 2 0.231 18.679 4 0.263 12.054 2 0.200 21.079 4 0.186 14.470 2 0.229 27.711 4 0.225 21.247 2 0.198 39.093 4 0.128 38.696 Fig. 9. Experiment II: separation between UAVs. V. CONCLUSIONS The proposed method solves collisions for multiple UAVs by changing the speed profiles of each UAV and is based on that is presented in [18] but with some changes which ensure the separation between UAVs. The paper has led to advances in this problem. The most important advantages with respect to previous works are: the arrival time of each UAV at the end waypoint of the trajectory is taken into account to solve the conflicts; low computational time; multiple aircraft are considered in different scenarios and the detection of conflicts takes into account several UAVs rather than just a pair of aircraft as in [14][15][16]. Furthermore, the proposed method allows the speed profile to be changed in such a way that each UAV can return to its necessary speed after solving the conflict in order to fulfill the ETA, so more than one speed change is allowed. This does not occur in [15]. The method computes a near-optimal solution, with small deviations from the initial trajectories. The implemented method has been validated by simulation and by experimentation with several UAVs in the CATEC multi-vehicle testbed The method can be also applied in real time to Air Traffic Management in which the time of arrival and the 4D (3D and time) trajectories play an important role. Future work will be focused on adding other maneuvers to solve conflicts such as the change of heading [12]. Also, uncertainty should be considered to explore more realistic scenarios [12]. REFERENCES [1] I. Maza, F. Caballero, J. Capitan, J. Martinez-de Dios, and A. Ollero, “A distributed architecture for a robotic platform with aerial sensor transportation and self-deployment capabilities,” Journal of Field Robotics, vol. 28, no. 3, pp. 303–328, 2011. [2] J. A. Cobano, J. R. Mart´ ınez-de Dios, R. Conde, J. M. S´ anchezMatamoros, and A. Ollero, “Data retrieving from heterogeneous wireless sensor network nodes using uavs,” Journal of Intelligent and Robotic Systems, vol. 60, no. 1, pp. 133–151, 2010. [3] J. How, E. King, and Y. Kuwata, “Flight demonstrations of cooperative control for uav teams,” Architecture, vol. 1, no. September, pp. 505– 513, 2004. [4] A. Ollero and I. Maza, Multiple Heterogeneous Unmanned Aerial Vehicles. Springer Publishing Company, Incorporated, 1st ed., 2007. [5] J. K. Kuchar and L. C. Yang, “A review of conflict detection and resolution modeling methods,” IEEE Transactions on Intelligent Transportation Systems, vol. 1, pp. 179–189, 2000. [6] C. Carbone, U. Ciniglio, F. Corraro, and S. Luongo, “A novel 3d geometric algorithm for aircraft autonomous collision avoidance,” in Decision and Control, 2006 45th IEEE Conference on, pp. 1580 – 1585, dec. 2006. [7] L. Pallottino, E. Feron, and A. Bicchi, “Conflict resolution problems for air traffic management systems solved with mixed integer programming,” Intelligent Transportation Systems, IEEE Transactions on, vol. 3, pp. 3 –11, mar 2002. [8] I. Hwang, C. J. Tomlin, I. Hwang, and C. Tomlin, “C.: Protocol-based conflict resolution for air traffic control. air traffic control quarterly 15(1,” 2007. [9] G. M. Hoffmann and C. J. Tomlin, “Decentralized cooperative collision avoidance for acceleration constrained vehicles,” in Proc. 47th IEEE Conf. Decision and Control CDC 2008, pp. 4357–4363, 2008. [10] R. Vivona, D. Karr, and D.Roscoe, “Pattern-based genetic algorithm for airborne conflict resolution,” in AIAA Guidance, Navigation and Control Conference and Exhibit, (Keystone, Colorado), August 2006. [11] R. Conde, D. Alejo, J. Cobano, A. Viguria, and A. Ollero, “Conflict detection and resolution method for cooperating unmanned aerial vehicles,” Journal of Intelligent & Robotic Systems, vol. 65, pp. 495– 505, 2012. 10.1007/s10846-011-9564-6. [12] J. A. Cobano, R. Conde, D. Alejo, and A. Ollero, “Path planning based on genetic algorithms and the monte-carlo method to avoid aerial vehicle collisions under uncertainties,” in Proc. IEEE Int Robotics and Automation (ICRA) Conf, pp. 4429–4434, 2011. [13] A. Lecchini, W. Glover, J. Lygeros, and J. Maciejowski, “Monte carlo optimization for conflict resolution in air traffic control,” Intelligent Transportation Systems, IEEE Transactions on, vol. 7, pp. 470 –482, dec. 2006. [14] R. Ehrmanntraut, “The potential of speed control,” in 23rd Digital Avionics Systems Conference, vol. 1, pp. 3.E.3–1–7, oct. 2004. [15] M. A. Christodoulou and S. G. Kodaxakis, “Automatic commercial aircraft-collision avoidance in free flight: the three-dimensional problem,” IEEE Transactions on Intelligent Transportation Systems, vol. 7, no. 2, pp. 242–249, 2006. [16] A. Vela, S. Solak, W. Singhose, and J.-P. Clarke, “A mixed integer program for flight-level assignment and speed control for conflict resolution,” in Decision and Control, 2009 held jointly with the 2009 28th Chinese Control Conference. CDC/CCC 2009. Proceedings of the 48th IEEE Conference on, pp. 5219 –5226, dec. 2009. [17] D. Alejo, R. Conde, J. Cobano, and A. Ollero, “Multi-uav collision avoidance with separation assurance under uncertainties,” in Mechatronics, 2009. ICM 2009. IEEE International Conference on, pp. 1 –6, april 2009. [18] J. J. Rebollo, A. Ollero, and I. Maza, “Collision avoidance among multiple aerial robots and other non-cooperative aircraft based on velocity planning,” in 7th Conference on Mobile Robots, (Albufeira, Portugal), 2007. [19] T. C. Project, CGAL User and Reference Manual. CGAL Editorial Board, 3.9 ed., 2011. http //www.cgal.org/Manual/3.9/doc html/cgal manual/packages.html. [20] T. W. McLain, R. W. Beard, and A. Beard, “Coordination variables, coordination functions, and cooperative timing missions,” 2003.