A 4D grid based approach for efficient conflict detection in large-scale multi-UAV scenarios

Depósito de Investigación de la Universidad de Sevilla https://idus.us.es/ This is an Accepted Manuscript of a Conference Paper published by IEEE in 2019 Workshop on Research, Education and Development of Unmanned Aerial Systems (RED UAS), on November 2019, available at: https://doi.org/10.1109/REDUAS47371.2019.8999724 © 2019 IEEE. A 4D grid based approach for efficient conflict detection in large-scale multi-UAV scenarios Jos´ e Joaqu´ ın Acevedo1,´ Angel R. Casta˜ no1, Jos´ e Luis Andrade-Pineda1and An´ ıbal Ollero1 Abstract— This paper proposes an algorithm to detect conflicts among UAVs from a strategic point of view. The method is based on the representation of the airspace as a 4D grid of cells. Given a set of UAVs with their scheduled 4D trajectories (their flight plans), the whole scenario is discretized as a 4D grid and the problem is solved by filling the appropriate cell for each way-point from the trajectories and checking the neighboring cells. The proposed method is tested and compared against a traditional algorithm getting a significantly better performance. The proposed method also scales very well with increasing number of UAVs and way-points per trajectory. I. INTRODUCTION In the last years, Unmanned Aerial Vehicles (UAVs) have been widely used for many civil applications like media production [1], delivering services [2], infrastructure [3] and industrial facilities [4] inspections and many more. Due to this growing usage a new regulation is needed to integrate them in the civil airspace. For this integration the National Aeronautics and Space Administration (NASA) of the United States of America has developed the concept of UAS Traffic Management (UTM) [5]; whereas Europe has adopted the name of U-space for this UTM concept [6]. U-space is currently defined as a set of services [7] and procedures to support safe, efficient, and secure access to airspace for UAVs. U-space services and their functional architecture are still being developed by some projects funded by SESAR Joint Undertaking 1. These services are divided into four phases with increasing complexity and integration level: U1, U2, U3 and U4. U1 services and some of U2 services have already been tested [8], [9], [10], but U2 services are still under development, like the Strategic deconfliction service. This service is defined [7] as: The service to check for possible conflicts in strategic phase for a specific flight/mission plan/intent. It as well provides resolution advisories.. So conflict detection is a key aspect of the Strategic deconfliction service. The conflict detection problem for multi-UAV systems is a well studied topic in the literature. Most of works are focused on studying the probability of conflict between pairs of aerial vehicles, as in [11]. In [12], the predicted probability of conflict between two aircraft is defined, based on their intended trajectories and a probability distance function. The conflict detection between pairs of UAVs is studied from a 1Jose Joaquin Acevedo, Angel R. Casta˜ no, Jose L. Andrade-Pineda and Anbal Ollero are with the Robotics, Vision and Control Group, University of Seville, Spain [jacevedo,castano,jandrade,aollero]@us.es. 1https://www.sesarju.eu/ probabilistic point of view and efficiently solved based on a particle filter approach in [13]. Other works consider the conflict detection problem inflight. Authors of [14] pose a hierarchical approach to predict potential conflicts in-flight. This method tries to reduce the computation time to detect potential imminent conflicts by checking the relative distance between pairs of UAVs in an asynchronous way. The updating rate to check the distance between each pair of UAVs depends on its current separation. In [15], the problem is studied from a tactical approach, showing as the intent flight plan may enhance the conflict detection. Some other works consider a geometric approach based on velocity obstacles [16] or spaceTime prisms [17]. In [18], the authors incorporate the intent information from predefined trajectories to complement the velocity obstacle (VO) representation for conflict detection applications among several autonomous aircrafts, but focusing on the 2D problem. However, the conflict detection problem based on the predefined plans from an strateguc point of view has been traditionally solved using brute forces methods. The presented paper is focused on the multi-UAV conflict detection for Strategic Deconfliction. Therefore, the proposed solution is based just on the planned trajectories, it means based on waypoints. The conditions to define a potential conflict between two aerial vehicles, based on their scheduled trajectories, are stated in [19]. A very relevant work, related to the strategic multi-trajectory conflict detection, is [20]. They propose a strategic conflict detection algorithm based on the sequential division of the airspace to get sub-spaces containing an unique trajectory. However, its performance may decrease significantly for too dense scenarios. Other approaches consider parallel procession to check the distance between every pair of vehicles reducing the computation time [21]. In short, this paper presents: (i) a method to detect conflicts among trajectories of UAVs, based on a 4D representation of the airspace; and (ii) the validation and analysis of the performance of this method through simulations. The remainder of this paper is organized as follows: Section II discusses and describes the conflict detection problem for multiple UAVs; Section III describes our approach to solve this problem based on a 4D grid representation; Section IV shows the simulation results to validate the algorithm; and Section V states the conclusions and proposes the future work. Preprint submitted to RED UAS 2019 DOI 10.1109/reduas47371.2019.8999724 II. THE MULTI-TRAJECTORY CONFLICT DETECTION PROBLEM This paper poses the problem of detecting the potential conflicts for a large set of UAVs, based on their predefined plans. A conflict between two UAVs, Aiand Aj, at time tmay be defined as a situation in which the distance between them is less than the safety distance δ. ||pi(t)−pj(t)|| ≤ δ, (1) where ||∗|| is the euclidean norm, i6=jand piand pjare the positions of Aiand Aj, respectively. Figure 1 illustrates a situation of conflict between a pair of UAVs. This paper focuses on detecting potential conflicts based on predefined plans from a strategic point of view. So, heading information is not taken into account. Fig. 1. Conflict event between a pair of UAVs. Blue sphere delimits the required free volume for UAV Ai. Red sphere illustrates how UAV Aj encroaches the free volume of Ai. Consider a set of nUAVs, sharing a common volume delimited by a rectangular prism of dimensions (X, Y, Z) meters and a time horizon of Tseconds. Each UAV Aihas assigned a 4D trajectory, defined by a ordered list of m(i) way-points: Ai← {Wi 1, Wi 2, ..., Wi m(i)},(2) being each way-point determined by a point in the 4D- space: Wi k:= (xi k, yi k, zi k, ti k).(3) It is assumed that the way-points are equally time-spaced for all the UAVs, such that, for any UAV, the time step (τ seconds) between each pair of consecutive way-points is not enough to move it more than the safety distance: ti k+1 −ti k=τ, (4) τvi≤δ, (5) ∀i= 1, ..., n and ∀k= 1, ..., m(i), being vithe maximum speed for Ai. The objective is to find all the potential conflicts derived from the predefined trajectories in an efficient way. A. Potential conflict conditions Expression 1 defines the condition to state a conflict between two UAVs. However, since this paper considers the problem based on predefined trajectories defined as a discrete list of 4D way-points, this expression may not be evaluated in a direct way. Modeling the trajectory between each pair of consecutive way-points as an straight line and assuming a conservative approach, a potential conflict Cis defined as a pair of waypoint, Wi kand Wj l, from two different trajectories such as the following conditions are accomplished: •their separation Sis less than the safety distance: S(Wi k, Wj l) := ||[xi k, yi k, zi k]−[xj l, yj l, zj l]|| ≤ δ, (6) •the difference of times DT is less than the time step DT(Wi k, Wj l) := |ti k−tj l| ≤ τ(7) Figure 2 illustrates, for a 1D scenario (x), how these conditions assure that all conflicts are detected. III. GRID BASED SOLUTION This problem has been traditionally solved using a brute force method. It implies to evaluate the expressions 6 and 7 for each pair of way-points from each pair of different trajectories. The computational cost would be increased quadratically with the number of trajectories and quadratically with the number of way-points, turning to a too inefficient solution for large scale scenarios. A grid-based solution is proposed to solve the problem in a more efficient way. The whole scenario is discretized and modelled as a 4D grid of cells G, which dimensions are (dX/δe,dY/δe,dZ/δe,dT/τe). Then, each cell G(a, b, c, d) determines a 4D space of dimensions (δ, δ, δ, τ)around the 4D point (aδ, bδ, cδ, dτ), being a, b, c = 0,1,2, ..., dX/δe and d= 1,2,3, ..., dT/τe. Each cell is defined by a structure which includes two fields, related to the way-points located inside: a list of UAV identifiers G(a, b, c, d).ids and a list of way-point identifier G(a, b, c, d).wps. From this scenario definition, it follows that a pair of waypoints may match expressions 6 and 7 if they are located in the same or neighboring cells. As Figure 3 shows, each cell is related to 34= 81 neighboring cells. Fig. 2. Potential conflict between two way-points from two different trajectories. Dashed red lines indicate conflicts between both trajectories, according to expression 1. Using the way-points information and evaluating expressions 6 and 7 an only potential conflict is detected between way-point 2 from left trajectory and way-point 1 from right trajectory, which are the two nearest to the defined conflicts. Note that expression 6 match between way-point 2 from left trajectory and way-point 4 from right trajectory, but expression 7 does not match. So no false conflicts are detected. A. Conflict detection method based on 4D matrix filling This method is based on sequentially filling the appropriate cell from the 4D grid for each way-point, looking for potential conflicts just in the neighboring cells Gn, and including them in the potential conflicts list C. It follows that the computational cost decreases considerably with respect to the brute force method. Algorithm 1 describes the proposed method. Note the relevance of using a matrix of structures type cells and not a simple matrix of numbers. Having a simple variable for cell to store the UAV and way-point identifiers could led to miss some conflicts by overwriting previous way-points. Figure 4 shows a typical situation in which a conflict would not be detected in a simplified 2D (x, y)scenario. The situation is as follows. First, way-point of UAV 1is located on its appropriate cell. Then way-point of UAV 2is located on the same cell and its separation with respect to the way-pont of UAV 1is evaluated, since it is in a neighboring cell. As the separation is above the safety distance δ, no conflict is detected. However, assuming a single variable for each cell, way-point of UAV 1is overwritten by way-point of UAV 2. Finally, a way-point of UAV 3is located on a neighboring cell. So, the separation with respect to the waypoint of UAV 2is evaluated, but it is above δand no conflict Fig. 3. World definition based on a 4D grid. Grey cells are the neighboring cells of black cell. Data: C,G,Wi k,∀i= 1, .., n, ∀k= 1, ..., m(i) Result: C foreach Wi kdo a←round(xi k/δ); b←round(yi k/δ); c←round(zi k/δ); d←round(ti k/τ); Gn←G(a−1 : a+ 1, b −1 : b+ 1, c −1 : c+ 1, d −1 : d+ 1) ; foreach g∈Gndo foreach j=g.ids 6=ido k←g.wps ; if S(Wi k, Wj l)≤δAND DT(Wi k, Wj l)≤τ then C←C∪ {[i, k, j, l]}; end end end G(a, b, c, d).ids ←G(a, b, c, d).ids ∪ {i}; G(a, b, c, d).wps ←G(a, b, c, d).wps ∪ {k}; end Algorithm 1: Conflict detection method based on 4D matrix filling is detected. The separation between way-points from UAVs 3and 1is below δ, but the conflict is not detected because the way-point of UAV 1has been removed. This problem is fixed by using lists instead of simple variables to store the UAV identifiers. IV. VALIDATION RESULTS A large set of simulations has been performed based on MATLAB to evaluate the algorithm performance depending on the number of UAVs and the size of the planned trajectories, being this size related to the number of way-points for each trajectory. Each simulation generates a scenario defined by a determined number of straight trajectories between two random points into a rectangular prism of a determined spatial dimensions (X, Y, Z)and a time horizon T. Then, each scenario is evaluated using the Algorithm 1 and the required time and iterations (assuming an iteration as each evaluation of the expressions 6 and 7). Also, each scenario is evaluated using an optimized brute force algorithm to compare the required time and iterations and check if both get the same results (potential conflict list). Figure 5 shows the average time required to detect all the conflicts depending on the number of trajectories, for both: the method based on filling the 4D grid and the brute force algorithm. Both methods detected the same conflicts for all the simulations. However, while the required time using the brute force algorithm depends quadratically on the number of trajectories, it is increasing linearly with the number of trajectories for the proposed algorithm. Moreover, the average required time to detect all the potential conflicts, depending on the number of way-points per trajectory, is shown in Figure 6 comparing both: the Fig. 4. Situation where a conflict is not detected using simple matrices of variables. 0 50 100 150 200 250 300 350 400 450 500 number of trajectories 0 20 40 60 80 100 time (s) grid based method brute force based method Fig. 5. Required time to detect all the potential conflicts depending on the number of UAVs. The simulations have been performed assuming a common volume of 50x50x10 meters and a time horizon of 30 seconds, being δ= 1mand τ= 1s. The number of way-points per trajectory is chosen randomly, bounded up by the time horizon. method described in Algorithm 1 and the traditional brute force algorithm. Both methods detected the same conflicts for all the simulations. The required time to detect all the conflicts depends linearly on the number pf way-points using the proposed algorithm, but quadratically using the bruteforce based method. 0 20 40 60 80 100 120 140 160 180 200 number of way-points per trajectory 0 5 10 15 20 time (s) grid based method brute force based method Fig. 6. Required time to detect all the potential conflicts, depending on the number of way-points per trajectory. The simulations have been performed assuming a common volume of 50x50x10 meters and 30 trajectories, being δ= 1mand τ= 1s. The time horizon is increasing according to the number of way-points per trajectory. On the other hand, the main drawbacks of the proposed method are related to the required storage capacity and the required time to initialize the grid. Both are related to the volume, time horizon, safety distance δand time step τconsidered. For instance, given the scenario defined in Figure 6, the grid increases its size by 50x50x10 = 25000 for each second in the time horizon. Figure 7 illustrates how the required time to create the grid is increasing with the time horizon. 0 20 40 60 80 100 120 140 160 180 200 time horizon 0 5 10 15 20 25 30 time (s) Fig. 7. Required time to initialize the 4D grid, depending on the time horizon. The simulations have been performed assuming a common volume of 50x50x10 meters, being δ= 1mand τ= 1s. Just to illustrate the results, a scenario with 10 trajectories in a shared volume is represented in Figure 8. The scenario is evaluated with the proposed method, detecting 6pairs of way-points in situation of potential conflict. Therefore, results shows that the proposed methods detects all the potential conflicts, such as they are defined in subsection II-A, in a more efficient manner than the traditional method. Also, the algorithm performance is improving correlated to the number of UAVs and the number of way-points per trajectory. However, results also show increasing storage capacity requirement and initialization time, depending on the size of the scenario and the time horizon. V. CONCLUSIONS The conflict detection problem for multiple planned UAV trajectories is studied in this paper. From the basic definition of a real-time conflict between a pair of UAVs, the conditions to detect the potential conflicts in a multi-UAV scenario are stated, based on the 4D intended trajectories. In a straightforward way, this problem could be solved by comparing exhaustively each pair of way-point from different UAVs. However, this method becomes quite inefficient for large-scale scenarios. Therefore, a method based on filling a 4D grid of cell objects is proposed to solve the problem in a more efficient manner, even for large-scale scenarios. Choosing properly the cell dimensions, it is guaranteed that only way-points located in neighboring cells are sensible to be in conflict. Therefore, the problem is limited to search in the neighboring cells of each way-point . Validation results show that the proposed algorithm is able to detect the same potential conflicts list that the brute force algorithm, but requiring less computational cost. While the required time to detect the whole list depends linearly on the number of trajectories and the number of way-points per trajectories using the proposed method, it depends quadratically using a traditional mehtod. Moreover, the proposed algorithm relative performance behaves even better with increasing number of UAVs and with larger sizes of the trajectories. The main drawbacks of the proposed method are related to the required storage capacity and initialization time. Future developments will be directed to design and integrate a deconfliction algorithm which may exploit the advantages of the presented conflict detection algorithm. ACKNOWLEDGMENT This work has received funding from the European Union’s Horizon 2020 Research and Innovation Programme under grant agreement No 776293 (GAUSS). REFERENCES [1] A. Torres-Gonz´ alez, J. Capit´ an, R. Cunha, A. Ollero, and I. Mademlis, “A Multidrone Approach for Autonomous Cinematography Planning,” in Robot 2017: Third Iberian Robotics Conference, ser. Advances in Intelligent Systems and Computing, A. Ollero, A. Sanfeliu, L. Montano, N. Lau, and C. Cardeira, Eds., vol. 693. Springer International Publishing, 2017, pp. 337–349. [Online]. Available: http://link.springer.com/10.1007/978-3-319-70833-1 28 [2] K. Dorling, J. Heinrichs, G. G. Messier, and S. Magierowski, “Vehicle routing problems for drone delivery,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 47, no. 1, pp. 70–85, Jan 2017. [3] A. Ollero, G. Heredia, A. Franchi, G. Antonelli, K. Kondak, A. Sanfeliu, A. Viguria, J. R. Martinez-de Dios, F. Pierri, J. Cortes, A. Santamaria-Navarro, M. A. Trujillo Soto, R. Balachandran, J. Andrade-Cetto, and A. Rodriguez, “The aeroarms project: Aerial robots with advanced manipulation capabilities for inspection and maintenance,” IEEE Robotics Automation Magazine, vol. 25, no. 4, pp. 12–23, Dec 2018. [4] J. Nikolic, M. Burri, J. Rehder, S. Leutenegger, C. Huerzeler, and R. Siegwart, “A UAV system for inspection of industrial facilities,” in 2013 IEEE Aerospace Conference, March 2013, pp. 1–8. 0 25 1 20 25 2 20 15 Z(m) 3 Y(m) 15 X (m) 10 4 10 5 55 00 Fig. 8. Scenario with 10 trajectories in a shared volume of 25x25x5m, considering a time horizon of 10 s, a safety distance δ= 1mand a time step τ= 1s. Each trajectory is represented by a different color, using an empty circle to indicate each way-point. Way-points in a situation of potential conflict are highlighted using a larger and filled circle. [5] P. Kopardekar, “Unmanned Aerial System (UAS) Traffic Management (UTM): Enabling Civilian Low-Altitude Airspace and Unmanned Aerial System Operations,” no. April 2014, 2015. [6] SESAR, “U-space Blueprint,” pp. 2015–2019, 2017. [7] CORUS, “Concept of Operations for U - Space Enhanced Overview.” [8] “Drones: Swiss U-space Live demonstration - Geneva - September 2017,” 2017. [Online]. Available: https://www.youtube.com/watch?v=Sz08N8 3an8 [9] “Swiss-wide U-space,” 2018. [Online]. Available: https://www.youtube.com/watch?v=-dRj428sJfw [10] “SESAR PODIUM: demonstrating U space services in four European locations,” 2018. [Online]. Available: https://www.youtube.com/watch?v=4 x0iN8EFcQ [11] W. Liu and I. Hwang, “Probabilistic trajectory prediction and conflict detection for air traffic control,” Journal of Guidance, Control, and Dynamics, vol. 34, no. 6, pp. 1779–1789, 2011. [Online]. Available: https://doi.org/10.2514/1.53645 [12] V. P. Jilkov, X. R. Li, and J. H. Ledet, “An efficient algorithm for aircraft conflict detection and resolution using list viterbi algorithm,” in 2015 18th International Conference on Information Fusion (Fusion), July 2015, pp. 1709–1716. [13] L. Ma, Y. Gao, T. Yin, and W. Zhai, “Improved flight conflict detection algorithm based on gauss-hermite particle filter,” Wuhan University Journal of Natural Sciences, vol. 22, no. 3, pp. 269–276, Jun 2017. [Online]. Available: https://doi.org/10.1007/s11859-017-1246-1 [14] J. Yang, D. Yin, Y. Niu, and L. Zhu, “Unmanned aerial vehicles conflict detection and resolution in city airspace,” in 2015 IEEE International Conference on Robotics and Biomimetics (ROBIO), Dec 2015, pp. 2436–2441. [15] H. Tang, J. Robinson, and D. Denery, Tactical Conflict Detection in Terminal Airspace. [Online]. Available: https://arc.aiaa.org/doi/abs/10.2514/6.2010-9294 [16] J. van den Berg, S. J. Guy, M. Lin, and D. Manocha, “Reciprocal nbody collision avoidance,” in Robotics Research, C. Pradalier, R. Siegwart, and G. Hirzinger, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 3–19. [17] H. Siqi, S. Cheng, and Y. Zhang, “A multi-aircraft conflict detection and resolution method for 4-dimensional trajectory-based operation,” Chinese Journal of Aeronautics, vol. 31, no. 7, pp. 1579–1593, 2018. [18] G. A. Mercado Velasco, C. Borst, J. Ellerbroek, M. M. van Paassen, and M. Mulder, “The use of intent information in conflict detection and resolution models based on dynamic velocity obstacles,” IEEE Transactions on Intelligent Transportation Systems, vol. 16, no. 4, pp. 2297–2302, Aug 2015. [19] A. Alonso-Ayuso, L. F. Escudero, P. Olaso, and C. Pizarro, “Conflict avoidance: 0-1 linear models for conflict detection & resolution,” TOP, vol. 21, no. 3, pp. 485–504, Oct 2013. [Online]. Available: https://doi.org/10.1007/s11750-011-0224-6 [20] A. Kuenz and N. Peinecke, “Tiling the world efficient 4d conflict detection for large scale scenarios,” in 2009 IEEE/AIAA 28th Digital Avionics Systems Conference, Oct 2009, pp. 3.B.5–1–3.B.5–10. [21] E. Thompson, N. Clem, D. A. Peter, J. Bryan, B. I. Peterson, and D. Holbrook, “Parallel cuda implementation of conflict detection for application to airspace deconfliction,” The Journal of Supercomputing, vol. 71, no. 10, pp. 3787–3810, Oct 2015. [Online]. Available: https://doi.org/10.1007/s11227-015-1467-z