Contributions to deconfliction advanced U-space services for multiple unmanned aerial systems including field tests validation

DEPARTAMENTO DE INGENIER´ IA DE SISTEMAS Y AUTOM´ ATICA ESCUELA T´ ECNICA SUPERIOR DE INGENIER´ IA UNIVERSIDAD DE SEVILLA Contributions to deconfliction advanced U-space services for multiple unmanned aerial systems including field tests validation por H´ector P´erez Le´on Ingeniero en Electr´onica Industrial, Rob´otica y Autom´atica PROPUESTA DE TESIS DOCTORAL PARA LA OBTENCI ´ ON DEL T´ ITULO DE DOCTOR POR LA UNIVERSIDAD DE SEVILLA SEVILLA, 2022 Directores Dr.-Ing. Jes´us Iv´an Maza Alca˜n´ız, Profesor Titular Dr.-Ing. An´ıbal Ollero Baturone, Catedr´atico ii UNIVERSIDAD DE SEVILLA Memoria para optar al grado de Doctor por la Universidad de Sevilla Autor: H´ector P´erez Le´on T´ıtulo: Contributions to deconfliction advanced U-space services for multiple unmanned aerial systems including field tests validation Departamento: Departamento de Ingenier´ıa de Sistemas y Autom´atica V◦B◦Director: Jes´us Iv´an Maza Alca˜n´ız V◦B◦Director: An´ıbal Ollero Baturone El autor: H´ector P´erez Le´on iii iv Life before death. Strength before weakness. Journey before destination. v vi Acknowledgements First and foremost, I want to express my gratitude to my supervisors, Professor Iv´an Maza and Professor An´ıbal Ollero, for all of their guidance and support all along this Thesis. In particular, I would like to express my deep gratitude and admiration to Professor Iv´an Maza for the personal teaching and time dedicated to setting my work on the right path to achieve the objectives. Without the amazing team of people at the Robotics, Vision, and Control Laboratory, research activities like the ones carried out for this Thesis would not have been feasible. I would want to express my gratitude to my coworkers for their generosity, support, and encouragement. Many wonderful moments have resulted from the mix of superb professional individuals in a friendly environment. Alejandro Braza, Jos´e Andr´es Mill´an, Alejandro Castillejo, Rafael Salmoral, Pedro S´anchez, Arturo Torres, and Alfonso Alc´antara, thank you for the kindness, and the amusing times. Jos´e Joaqu´ın Acevedo and Fran Real, in particular, deserve special thanks for spending many hours programming, and developing with me, I learned a lot from you. A hearty thanks to my life partner, Alejandra, who was always there for me. Unintentionally you have been a part of this journey, encouraging me during the hardest times and celebrating with me every small victory. Finally, I would want to express my gratitude to my family. Thanks to my sister, for giving me her point of view on tricky situations and for pushing me out of my comfort zone. Thanks to my parents for their constant love and support. They have given me the tools I have needed to face any problem throughout my life. H´ector P´erez Le´on vii viii Abstract Unmanned Aerial Systems (UAS) will become commonplace, the number of UAS flying in European airspace is expected to increase from a few thousand to hundreds of thousands by 2050. To prepare for this approaching, national and international organizations involved in aerial traffic management are now developing new laws and restructuring the airspace to incorporate UAS into civil airspace. The Single European Sky ATM Research considers the development of the U-space, a crucial step to enable the safe, secure, and efficient access of a large set of UAS into airspace. The design, integration, and validation of a set of modules that contribute to our UTM architecture for advanced U-space services are described in this Thesis. With an emphasis on conflict detection and resolution features, the architecture is flexible, modular, and scalable. The UTM is designed to work without the need for human involvement, to achieve U-space required scalability due to the large number of expected operations. However, it recommends actions to the UAS operator since, under current regulations, the operator is accountable for carrying out the recommendations of the UTM. Moreover, our development is based on the Robot Operating System (ROS) and is open source. The main developments of the proposed Thesis are monitoring and tactical deconfliction services, which are in charge of identifying and resolving possible conflicts that arise in the shared airspace of several UAS. By limiting the conflict search to a local search surrounding each waypoint, the proposed conflict detection method aims to improve conflict detection. By splitting the issue down into smaller subproblems with only two waypoints, the conflict resolution method tries to decrease the deviation distance from the initial flight plan. ix xvi Contents A.2.3 Geofence Intrusion . . . . . . . . . . . . . . . . . . . . . . . . 154 References 157 List of Figures 2.1 U-space levels CORUS (2019). Each level increases the level of drone automation and connectivity. Advanced services are planned to be developed in 2025, and full services after 2030. . . . . . . . . . . . . . 11 2.2 Graphical representation of the VLL airspace sections divided by U- space. ................................... 13 2.3 Graphical representation of a geofence and an OV of an UAS operation. The OV is made up of two parts: the flight geometry, which describes the extent of airspace in which the UAS will operate, and the contingency volume, which is an outside surrounding volume that accounts for environmental or performance uncertainty. . . . . . . . . 21 3.1 Overview of the proposed UTM architecture. Green modules implement U-space services, gray are auxiliary modules, and the blue one is an external module of the UTM used to DAA unexpected structures. Moreover, outside the UTM are all active UAS, and the authorities, which may interact with the UTM warning of threats. Arrows show services between modules, on the other hand, dashed arrows represent topics. ................................... 32 xvii xviii List of Figures 3.2 Scheme with the internal components (purple) of the Tracking module. The data association component matches the measurements from the UAS with their previously position calculated to update the corresponding Kalman filters. The future UAS trajectories are predicted using the output of the data association and the flight plans, which are read from the Database module. Finally, the predicted trajectories are stored in the Database after being calculated, as well as the tracks afterbeingupdated. ........................... 36 3.3 Iterative procedure to solve a conflict in the case of a loss of separation from left to right. The flight plans of the two lower UAS are in conflict and need to be separated. Then, the middle UAS enters in conflict with the upper UAS, so these two get separated again to achieve a final solution without loss of separation. . . . . . . . . . . . . . . . . 41 3.4 Left, Gazebo world with a 3D model of a rectangular prism, and a multirotor with a 3D LIDAR attached. Right, RViz visualization of the output of the LIDAR in form of pointcloud, which is transformed in an octomap. Colors represent the height of the obstacle. . . . . . . 44 3.5 The UTM architecture in the ROS graph. The nodes (ellipsoid) are the modules described in Section 3.1 and the rectangles are the topics usedinthesystem............................. 50 4.1 Left, geofence conflict. Right, geofence intrusion . . . . . . . . . . . . 56 4.2 Zones where a pair of waypoints of two different trajectories can be free of conflict. The red area is the only one in which a pair of waypoints have a time difference below the inter-waypoint period τand a distance below the safety distance δ. The dark green area represents a conflicting time between waypoints, but it is a safe area to fly because there is enough distance. On the other hand, the light green area is a safe area to fly due to enough time between waypoints despide the conflictingdistance............................. 57 List of Figures xix 4.3 Estimated trajectories within a given time horizon of several UAS sharing a common airspace. Each estimated trajectory is marked with a differentcolor................................ 58 4.4 Interactions between UAS and UTM modules. The UTM sytem is out of the scope of this chapter, details shown in Figure 3.1. . . . . . . . 60 4.5 The signed angle method is used to evaluate whether a tested waypoint (black dot) is inside or outside a polygonal geofence. Left, an example where the angles of an external waypoint sum up to 0◦. Right, an interior waypoint whose angles sum up to 360◦. ............ 61 4.6 Airspace shared by two trajectories divided into a grid. The altitude is not shown for the sake of clarity. Black circles represent the waypoints and the associated number its arrival time. . . . . . . . . . . . . . . . 62 4.7 Conflict detection process associated to the third waypoint from the blue trajectory in the scenario represented in Figure 4.6. This waypoint is stored into its cell and its neighboring cells (dashed cells in the figure) are checked to look for waypoints from other trajectories (green trajectory, in this case). The analyzed waypoint has to be validated against the third and four waypoints from the green trajectory, as it is shownintheexample. .......................... 63 4.8 On the left two trajectories with a pair of waypoints in conflict. On the right, the alternative trajectories provided by separating the conflicting waypoint to match the safety distance. . . . . . . . . . . . . . . . . . 67 4.9 Left, an UAS flight plan intersecting a geofence. The last waypoint of its flight plan before entering the geofence (WP1) and the first waypoint after leaving it (WP2) are obtained, and this segment of the flight plan is replaced by the alternative route (dashed orange line). Right, an UAS inside a geofence. The escape point (WP2) is that on the geofence’s border closest to the UAS (WP1). From WP3to the first point of the flight plan after leaving the geofence (WP4), an alternative route avoiding the geofence is inserted to modify the original flight plan and respecting at every moment the safety distance. . . . . . . . . . . 69 xx List of Figures 4.10 Summary of the test battery increasing the number of UAS and comparing the proposed solution against the time shift based approach: (a) Processing time by test to detect and resolve all the conflicts. (b) Mean deviation by waypoint between the generated and the original trajectories. ................................ 70 4.11 Summary of the test battery increasing the time horizon and comparing the proposed solution against the time shift based approach: (a) Processing time by test to detect and resolve all the conflicts. (b) Mean deviation by waypoint between the generated and the original trajectories. ................................ 71 4.12 Simulation results. (a) Three dimensional view of the initial waypoints, the reference trajectory generated and the actual trajectory flown. (b) reference velocity and current velocity of the UAS. (c) Normal distance between the UAS and the generated trajectory. (d) Difference between the reference time and the current time. . . . . . . . . . . . . . . . . 73 4.13 (a) 3D Visualization of the traveled trajectories. (b) Distances between UAS. UAS 0 has a conflict with UAS 1 but the solution of the conflict detection and resolution module keeps the distance above the limit. . 74 4.14 (a) 3D Visualization of the traveled trajectories. (b) Distances between UAS. UAS 0 has a conflict with UAS 1 but the solution of the conflict detection and resolution module keeps the distance above the limit. UAS 0 is using the 4D trajectory follower. . . . . . . . . . . . . . . . 75 4.15 (a) 3D Visualization of the traveled trajectories. (b) Distances between UAS. UAS 0 has a conflict with UAS 1 but the solution of the conflict detection and resolution module keeps the distance above the limit. UAS 0 is not using the 4D trajectory follower, and it causes a conflict with UAS 2, lowering their distance below the limit. . . . . . . . . . 76 List of Figures xxi 5.1 The trajectory follower design allows to use it by simply configuring the initial 4D waypoint list. It also provides more configuration options to suit the user needs. The generator is called by the follower and runs once to generate a discrete curve with the reference time on each point ofthecurve................................. 81 5.2 Top view of the three-dimensional path follower based on the carrot chasing algorithm without taking into account the orientation error. . 82 5.3 Graphical example of Algorithm 2. Red segments are infeasible and should be extended to a grey segment. Green segments are modifiable and can be reduced to match the initial times. . . . . . . . . . . . . . 85 5.4 The different layers of the software architecture make the system modular. Different autopilots and simulators can be used. . . . . . . . . . 85 5.5 Simulated experiment. (a) Three dimensional view of the initial waypoints, the trajectory generated and the trajectory described. (b) reference velocity and current velocity of the UAS. (c) Normal distance between the UAS and the generated trajectory. (d) Difference between the reference time and the current time. . . . . . . . . . . . . . . . . 88 5.6 OptiTrackTestbed ............................ 89 5.7 DJI F500 Hexacopter used in the flight tests . . . . . . . . . . . . . . 89 5.8 Real experiment inside the OptiTrack Testbed. (a) Three dimensional view of the initial waypoints, the trajectory generated and the trajectory described. (b) reference velocity and current velocity of the UAS. (c) Normal distance between the UAS and the generated trajectory. (d) Difference between the reference time and the current time. . . . 90 5.9 Mean and standard deviation of error J1and error J2with the same initial 4D waypoint list on different simulations modifying the maximum velocity on each experiment. . . . . . . . . . . . . . . . . . . . . . . . 91 5.10 Random segments using 3 m/s as vmax. (a) reference velocity and current velocity of the UAS. (b) Difference between the reference time andthecurrenttime............................ 92 xxii List of Figures 5.11 Difference of times tdand reached times trof methods 1 and 2 following thesame4Dtrajectory.......................... 93 6.1 Three setups used along the SITL tests, HITL tests, and real experiments. (a) SITL setup. We simulated an airspace and its active aircraft using Gazebo. (b) HITL setup. In this case aircraft were not flying so the onboard modules and autopilots were simulated by EVERIS. (c) Experiments setup. USE had a laptop with the UTM architecture, EVERIS one with the Remote Pilot Station (RPS) and with access to the Ground Control Station (GCS), finally EVERIS and IRI had their softwareonboard.............................. 97 6.2 Graphical user interface developed by SATWAYS running on the RPS ClientApplication. ............................ 98 6.3 DJIMatrice600Pro ........................... 100 6.4 Left, the Atlantic I. Right, the Scrab II. . . . . . . . . . . . . . . . . 100 6.5 Test Flight Center Air Traffic Laboratory for Advanced unmanned System located in Jaen, Spain. . . . . . . . . . . . . . . . . . . . . . . 102 6.6 Three scenarios defined in order to solve potential conflicts. (a) Conflict between M600 and Atlantic due to loss of safety distance. (b) Firefighters warn about a wildfire, M600 appears inside the created geofence. (c) M600 suffers jamming, the created geofence intersects with theAtlantic................................. 105 6.7 El Arenosillo Testing Center (CEDEA) located in Huelva, Spain. . . . 106 6.8 Three scenarios defined in order to solve potential conflicts. (a) Conflict between Scrab and Atlantic due to loss of safety distance. (b) Scrab suffers jamming, the created geofence intersects with the Atlantic. (c) Firefighters warn about a wildfire, Atlantic appears inside the created geofence................................... 109 6.9 First real experiment carried out in ATLAS visualized using RViz. Top view of the loss of separation conflict between the operation 1 done by the M600 (orange) and the operation 2 done by the Atlantic (green). 110 List of Figures xxiii 6.10 First real experiment carried out in ATLAS visualized using RViz. Side view of the alternative flight plan accepted by the M600 operator to avoid the loss separation conflict between the operation 1 done by the M600 (orange) and the operation 2 done by the Atlantic (green). . . . 112 6.11 Second real experiment carried out in ATLAS visualized using RViz. View of the geofence intrusion conflict between the operation 3 done by the M600 (orange) and the geofence (red) created due to the warning of a wildfire by the firefighters. . . . . . . . . . . . . . . . . . . . . . . 114 6.12 Second real experiment carried out in ATLAS visualized using RViz. View of the alternative flight plan accepted by the M600 operator to avoid the geofence intrusion conflict between the operation 3 done by the M600 (orange) and the geofence (red) created due to the warning of a wildfire by the firefighters. . . . . . . . . . . . . . . . . . . . . . . 114 6.13 Third real experiment carried out in ATLAS visualized using RViz. View of the geofence conflict between the operation 4 done by the Atlantic (green) and the geofence (yellow) created due to the warning of a jamming attack, which was received by the operation 5 carried out bytheM600(orange). .......................... 115 6.14 Third real experiment carried out in ATLAS visualized using RViz. Top view of the alternative flight plan accepted by the Atlantic operator to avoid the geofence conflict between the operation 4 carried out by the Atlantic (green) and the geofence (red) created due to the warning of a jamming attack. . . . . . . . . . . . . . . . . . . . . . . 116 6.15 First real experiment carried out in El Arenosillo visualized using RViz. Top view of the loss of separation conflict between the operation 1 done by the Atlantic (green) and the operation 2 done by the Scrab (orange).118 6.16 First real experiment carried out in El Arenosillo visualized using RViz. Side view of the alternative flight plan accepted by the Atlantic operator to avoid the loss of separation conflict between the operation 1 done by the Atlantic (green) and the operation 2 done by the Scrab (orange)................................... 118 xxiv List of Figures 6.17 Second real experiment carried out in El Arenosillo visualized using RViz. Top view of the geofence conflict between the operation 3 done by the Atlantic (green) and the geofence (red) created due to the warning of a jamming attack, which was received by the operation 2 carried out by the Scrab (orange). . . . . . . . . . . . . . . . . . . . . . . . . 119 6.18 Second real experiment carried out in El Arenosillo visualized using RViz. Top view of the alternative flight plan accepted by the Atlantic operator to avoid the geofence conflict between the operation 3 carried out by the Atlantic (green) and the geofence (red) created due to the warning of a jamming attack. . . . . . . . . . . . . . . . . . . . . . . 120 6.19 Third real experiment carried out in El Arenosillo visualized using RViz. View of the geofence intrusion conflict between the operation 4 done by the Atlantic (green) and the geofence (red) created due to the warning of a wildfire by the firefighters. . . . . . . . . . . . . . . . . . 121 6.20 Third real experiment carried out in El Arenosillo visualized using RViz. View of the alternative flight plan accepted by the Atlantic operator to avoid the geofence intrusion conflict between the operation 4 done by the Atlantic (green) and the geofence (red) created due to the warning of a wildfire by the firefighters. . . . . . . . . . . . . . . . 121 6.21 Comparison between brute force based method and discretized method. Required time to detect all potential conflicts. The simulations have been performed assuming a common volume of 50x50x10 meters. (a) Results of a battery of tests increasing the number of trajectories. (b) Results of a battery of tests increasing the number of waypoints per trajectory. ................................ 124 6.22 Required time to initialize the 4D grid, depending on the time horizon. The simulations have been performed assuming a common volume of 50x50x10meters. ............................. 125 6.23 Left, ATLAS control tower. Right, RViz visualization of the octomap representation based on the LIDAR point cloud, and the conflictive flight plan under the ROS framework. . . . . . . . . . . . . . . . . . . 127 List of Figures xxv 6.24 The Unifly U-space Service Provicer interface. Representation of the alternative flight plan carried out by the UAS and the OV reserved in theU-spacesystem............................. 127 6.25 Top view of how lack of information may result in collisions. The flight plan is represented with a blue arrow, the green line is the new route generated by the path planner, and the red one is the segment that will collide into a building. (a) First stage. With insuficient information the path planner generates an alternative route that will collide into the building. (b) Second stage. The UAS followed a portion of the new route, gained information, detects a potential collision, and the path planner recalculated a new safe route. . . . . . . . . . . . . . . . . . . 128 6.26 Side view of the problem caused by the blind spots of the LIDAR. (a) First stage. The LIDAR detects a building wall, area colored in yellow. (b) Second stage. The LIDAR detects the building roof, which concealed the rest of the building. The path planner may give a new route that may cause a further collision. (c) Third stage. The remaining red parts of the building have been concealed by previous detections, therefore presenting a hazardous situation caused by no information gain due to the blind spots of the sensor. . . . . . . . . . . . . . . . . 129 A.1 Perspective view of a 3D example, where tα=tA2and tβ=tB1. Segments are now defined in the same time interval. . . . . . . . . . . . . 144 A.2 Perspective view of a 3D example, where δ1γ1and δ2γ2are the segments within a loss of separation conflict . . . . . . . . . . . . . . . . . . . . 147 A.3 Graphical representation of the possible conflicts that can appear between a 4D trajectory and a geofence. Left, geofence intrusion due to γ=r(mentry) inside the geofence. Right, geofence conflict due to δ=r(mexit) matching the geofence border. . . . . . . . . . . . . . . . 151 2Introduction communications, high-resolution light sensors, on-board computational capacity, and power-efficient hardware. UAS are being used in different spheres of business and are projected to become a commercial delivery method in the near future, while convergent technology has been expanding recently. With an ambitious approach, in December 2016, the first PrimeAir delivery service was launched Amazon (2016). DHL Express and EHang have formed a strategic relationship to jointly create a fully automated and intelligent smart UAS delivery system in China’s urban areas DHL-Ehang (2019). Google Project Wing has been awarded permission to transform its public-access UAS delivery experiments in Australia into a full-fledged business. Just over 100.000 drone deliveries were made in Australia by Wing in 2021, and they reached 30.000 in the first two months of 2022 Alphabet (2022). According to the 2016 European Drones Outlook Study SESAR (2016), the growing UAS business will support potential economic growth. In most economic areas, unmanned aircraft will become a part of daily life. Indeed, by 2050, the number of UAS flying in European airspace is estimated to rise from a few thousand to hundreds of thousands, mostly for government and commercial purposes. By 2035, the yearly economic impact in Europe might surpass EUR 10.000 million, with 100.000 new direct jobs created to support UAS operations. The agriculture industry, for example, is expected to have 150.000 UAS operating by 2035. In the domains of utilities and security, roughly 60.000 unmanned aircraft will be employed to aid in natural disaster management and traffic control, among other activities. To address this nearing scenario, national and international organizations related to aerial traffic management are currently elaborating new regulations and reorganizing the airspace to integrate the UAS in the civil airspace. U-space is the UAS Traffic Management (UTM) solution for Europe, where the Single European Sky ATM Research (SESAR) considers the development of the U-space, a key step to enable the safe, secure and efficient access of a large set of UAS to the civil airspace SESAR (2017), through a set of services related to flight planning, tracking, conflict management, etc. A similar concept is being developed by the National Aeronautics and Space Administration (NASA) in the United States of America Kopardekar (2015). 1.2 Objectives 3 According to Unmanned Airspace’s December 2021 prediction for the worldwide UTM market in 2021-2025 Butterworth-Hayes and Mahon (2021), the new sector value is USD 1.380 million, which includes awards from commercial, strategic national UTM development programs, and tactical UTM service operational charges. SESAR also created the 4D-Trajectory Based Operations (4D-TBO) concept, which was originally aimed for manned commercial aircraft but is now being examined in the U-space context. The addition of time as a fourth dimension in the flight plan specification improves airspace occupancy, which is mostly connected to conflict resolution U-space services CORUS (2019). As a result, establishing accurate and precise 4D trajectory control methods becomes a critical problem for the development of the 4D-TBO in the U-space, which will allow the integration of an increasing number of UAS into civil airspace. 1.2 Objectives The main objectives of this Thesis are: •Build a modular and scalable implementation of several modules based on advanced U-space services. •Develop a method that can detect different types of conflicts between UAS trajectories and geofences. •Develop an algorithm that can solve different types of conflicts between UAS trajectories and geofences proposing alternatives routes to the operator. •Implement an onboard module that can detect large static obstacles and avoid them by using a path planner to generate alternative routes. •Implement a trajectory follower that improves the performance of the position controller of an autopilot when following a list of waypoints. 4Introduction 1.3 Contributions The Thesis meets the objectives previously outlined, producing the following main contributions: 1. An implementation of two advanced U-space services, tactical deconfliction and monitoring, which are part of an architecture framed in the U-space ecosystem. The architecture is flexible and general, and it is focused on advanced services for automated conflict detection and resolution. The system is capable of detecting and resolving different types of conflicts based on 4D UAS trajectories. 2. A conflict detection method for multiple 4D UAS trajectories sharing the same space and a conflict resolution method. The modules that contain these methods are also able to detect and solve conflicts between UAS and geofences. 3. A 4D trajectory follower which improves the performance of the position controller of an autopilot when following a list of waypoints. It can correct an infeasible trajectory given by the user before doing it, which increases the performance of the follower. 4. An autonomous detect and avoid onboard system for UAS. This system uses a LIDAR to get data from the real world, uses octomap to transform the point cloud from the sensor into a 3D map and uses the Lazy Theta∗algorithm to avoid unexpected large static obstacles. Chapter 1 presents the motivation, objectives and framework in which this Thesis has been developed. Moreover, it presents the contributions and scientific output of this Thesis. Chapter 2 describes the existing work related to this Thesis. More precisely, it presents the U-space framework and its set of new services that rely on a high level of digitalization and automation of functions and specific procedures designed to support safe, efficient, and secure access to airspace for a large number of UAS. As such, U- space is an enabling framework designed to facilitate any kind of routine mission, in 1.3 Contributions 5 all classes of airspace and all types of environments, even the most congested, while addressing an appropriate interface with manned aviation and air traffic control. Chapter 3 presents the developed services, Contribution 1 of this Thesis. It details the modules that contribute to the architecture, which services are related to each module, and how they are implemented in software. This chapter contains a detailed explanation of how the modules are connected and how are the messages used, as well as which robot frameworks have been chosen for this Thesis and a comparison with other frameworks. Moreover, it details the onboard autonomous detect and avoid module presented in this Thesis, Contribution 4. Chapter 4 is focused on two modules: Monitoring and Tactical Deconfliction. These modules are in charge of conflict detection and conflict resolution, respectively, Contribution 2 of this Thesis. The monitoring module detecting conflicts between 4D trajectories and geofences should warn of all conflicts in the shortest possible time. The tactical deconfliction module solves threats one by one depending on the threat type. Each threat should be solved with more than one alternative flight plan and each alternative solution must have been made with an independent strategy. The methods used for each module are described in this chapter. Chapter 5 describes the work related to the Contribution 3. A 4D trajectory follower is needed to perform flight plans in the U-space context. This chapter details the follower based on the carrot chasing algorithm and presents the problems that can appear if, in this context, a 4D trajectory follower is not used. Chapter 6 presents the experiments carried out on the field, the results of which are presented in this chapter. Moreover, it presents a comparison between a brute force based method, detailed in appendix A, and the discretized based method chosen for this Thesis, which can be scaled without problems. The brute force based method was developed in the first place to be able to make tests quickly in the field, which is not scalable, however, it is fast and does not need to set up. 6Introduction 1.4 Thesis framework This Thesis has been developed within the context of a number of R&D projects funded by the European Commission in H2020. In all of them, Very Low Level (VLL) airspace scenarios were an important part, as well as U-space operations. The PhD candidate designed and implemented the developments presented in this Thesis within the Robotics, Vision and Control group at the University of Seville. SAFEDRONE (H2020-783211). The scope of the SAFEDRONE project was to acquire practical experience in VLL operations where general aviation, state aviation, and optionally piloted aircraft and UAS will share the airspace. It is important to highlight that this project had a clear practical focus, which primary activities were innovation, integration, and especially, demonstrating activities with flight tests. GAUSS (H2020-ICT-776293). The main objective of the GAUSS project was the achievement of an acceptable level in terms of performance, safety, and security for both current UAS and future U-space operations. The research was focused on the consecution of precise and secure positioning to enable U-space operations, supporting the management and coordination of all UAS in the VLL airspace. 1.5 Scientific output The following peer-reviewed publications have been published based on the work presented in this Thesis: •Perez-Leon, H., Acevedo, J. J., Maza, I., and Ollero, A. (2021a). Integration of a 4D-trajectory Follower to Improve Multi-UAV Conflict Management Within the U-Space Context. Journal of Intelligent and Robotic Systems, 102(3):62 •Perez-Leon, H., Acevedo, J. J., Maza, I., and Ollero, A. (2020a). A 4D trajectory follower based on the ’Carrot chasing’ algorithm for UAS within the U-space context. In 2020 International Conference on Unmanned Aircraft Systems (ICUAS), page 1860–1867. IEEE 1.5 Scientific output 7 •Perez-Leon, H., Acevedo, J. J., Millan-Romera, J. A., Castillejo-Calle, A., Maza, I., and Ollero, A. (2020b). An Aerial Robot Path Follower Based on the ‘Carrot Chasing’ Algorithm. In Silva, M. F., Lu´ıs Lima, J., Reis, L. P., Sanfeliu, A., and Tardioli, D., editors, Robot 2019: Fourth Iberian Robotics Conference, volume 1093, page 37–47. Springer International Publishing •Capitan, C., Perez-Leon, H., Capitan, J., Casta˜no, A., and Ollero, A. (2021). Unmanned Aerial Traffic Management System Architecture for U-Space In- Flight Services. Applied Sciences, 11(9):3995 •Faria, M., Ferreira, A. S., Perez-Leon, H., Maza, I., and Viguria, A. (2019). Autonomous 3D Exploration of Large Structures Using an UAV Equipped with a 2D LIDAR. Sensors, 19(22):4849 •Millan-Romera, J. A., Perez-Leon, H., Castillejo-Calle, A., Maza, I., and Ollero, A. (2019b). ROS-MAGNA, a ROS-based framework for the definition and management of multi-UAS cooperative missions. In 2019 International Conference on Unmanned Aircraft Systems (ICUAS), page 1477–1486. IEEE •Millan-Romera, J. A., Acevedo, J. J., Castano, A. R., Perez-Leon, H., Capitan, C., and Ollero, A. (2019a). A UTM simulator based on ROS and Gazebo. In 2019 Workshop on Research, Education and Development of Unmanned Aerial Systems (RED UAS), page 132–141. IEEE •Castillejo-Calle, A., Millan-Romera, J. A., Perez-Leon, H., Andrade-Pineda, J. L., Maza, I., and Ollero, A. (2019). A multi-UAS system for the inspection of photovoltaic plants based on the ROS-MAGNA framework. In 2019 Workshop on Research, Education and Development of Unmanned Aerial Systems (RED UAS), pages 266–270. IEEE The following open source software based on the work presented in this Thesis have been released and field tested: 8Introduction •Perez-Leon, H. (2020). UPAT Follower: UAV Path and Trajectory Follower. https://github.com/hecperleo/upat_follower (accesed on 17 February 2022) •Perez-Leon, H., Braza, A., Jose Joaquin, A., Capitan, C., and Real, F. (2021b). GAUSS UTM system architecture. https://github.com/grvcTeam/gauss (accesed on 17 February 2022) Chapter 2 Related work One of the most important concepts and technologies currently being developed in the field of drones is the future system of Air Traffic Management (ATM) in the very low level altitude, which will be controlled by an unmanned aerial system traffic management. It will allow effective and organized management of the large volume of civilian unmanned aircraft that will be able to use the airspace in the medium-long term. Despite ATM has traditionally depended on voice communication through an Air Traffic Control (ATC) entity, the restricted workload and communication capacity of this centralized resource makes it a bottleneck for system expansion. As a result, the growth of UAS operations needs a new airspace management paradigm, in which digital communication plays a key role and responsibilities are shared among several stakeholders rather than a single central actor. 2.1 U-space This section mainly gathers the information contained in the following official documents SESAR (2017); CORUS (2019, 2020). To foster the expansion of the UAS sector and the usage of these aircraft in Europe, the European Union has devised a concept termed U-space: the progressive implementation of procedures and a set of services meant to make it easier for large groups of drones to access the airspace in a safe, efficient, and secure manner. These services and operations, whether they are 9 10 Related work on board the drone or part of the ground-based environment, rely on a high level of digitisation and automation of tasks. NASA has also developed its own UTM model in the United States of America Kopardekar (2015), but this Thesis is focused on the U-space concept. U-space provides a simple and effective interface to manned aircraft, ATM service providers, and authorities, as well as an enabling architecture to facilitate normal drone operations. As a result, U-space should not be regarded as a specified volume of airspace reserved only for the operation of drones. U-space can ensure that drones operate smoothly in all sorts of operating settings and airspace, including but not limited to VLL airspace. It addresses the requirements for supporting a variety of tasks and may affect all drone users and types of drones. U-space, according to CORUS1, is an environment that allows for commercial activities including drone use while maintaining an acceptable level of safety and public acceptance. CORUS came up with this Concept of Operations (ConOps) by thinking about the most common U-space use cases first. The following are the key principles that govern U-space delivery: to protect the safety of all airspace users in the U-space framework, as well as ground personnel; to provide a scalable, flexible and adaptable system that can respond to changes in demand, volume, technology, business models and applications, while managing the interface with manned aviation; to allow for high-density operations with several autonomous drones under the guidance of fleet operators; to ensure that all users have equal and fair access to the airspace; to assist business models of drone operators by enabling competitive and cost-effective service offering at all times; to reduce deployment and operational costs as much as possible by using current aviation services and infrastructure, such as Global Navigation Satellite System (GNSS), as well as services from other industries, such as mobile communication services; to accelerate implementation by incorporating technology and standards from other industries when they fulfill U-space requirements; while establishing adequate standards for safety, security, and resilience, to use a risk-based and performance-driven approach, while minimizing environmental effect and preserving privacy of the people. 1https://www.sesarju.eu/projects/corus 2.1 U-space 11 2.1.1 Implementation The U-space services will be gradually introduced over four phases, from U1 to U4, based on the increasing availability of blocks of services and enabling technologies, the increasing level of drone automation, and advanced forms of environmental interaction, primarily enabled through data exchange and digital information, see Figure 2.1. All services offered in a particular phase may use other services provided in that phase, as well as those provided in earlier stages. Figure 2.1: U-space levels CORUS (2019). Each level increases the level of drone automation and connectivity. Advanced services are planned to be developed in 2025, and full services after 2030. The U-space foundation, U1, offers e-registration, e-identification, and geofencing services. Moreover, the initial U-space services corresponding to the U2 stage, assist drone operations management and may include flight planning, flight permission, tracking, airspace dynamic information, and procedural interfaces with ATC. Advanced U-space services, U3, support more complicated activities in congested locations, such as capacity management and conflict detection aid. Indeed, the availability of automatic Detect And Avoid (DAA) functions, as well as more reliable communication methods, will result in a considerable rise in operations in all situations. Finally, U-space full services, U4, especially those with integrated interfaces with human aircraft, provide U-space full operating potential and rely on a high degree of automation, connection, and digitalization for both the drone and the U-space. 2.1.2 Very low level airspace The VLL airspace is below the usual airspace utilized by aircraft operating under visual flight rules. Although this airspace is normally unoccupied, it is utilized for 18 Related work •Geospatial information service. Collects and provides the relevant terrain map, buildings, and obstacles with different levels of precision for the drone operation. •Population density map. Collects and presents a population density map for the drone operator to assess ground risk. This could be proxy data, e.g., mobile telephone density. •Electromagnetic interference information. Collects and presents relevant electromagnetic interference information for the drone operation. •Navigation Coverage information. Provides information about navigation coverage for missions that will rely on it. This information can be specialised depending on the navigation infrastructure available (e.g., ground or satellite based). •Communication Coverage information. Provides information about communication coverage for missions that will rely on it. This information can be specialised depending on the communication infrastructure available (e.g., ground or satellite based). •Procedural Interface with ATC. A mechanism invoked by the operation plan processing service for coordinating the entry of a flight into controlled airspace before flight. Through this, ATC can either accept or refuse the flight and can describe the requirements and process to be followed by the flight. Finally, the advanced services, U3: •Dynamic Capacity Management. Responsible for balancing traffic demand and capacity constraints during operational plan processing. •Tactical Conflict Resolution. Checks for possible conflicts in real time and issues instructions to the aircraft to change their speed, level or heading as needed. •Collaborative Interface with ATC. Offers verbal or textual communication between the remote pilot and ATC when a drone is in a controlled area. This 2.1 U-space 19 service replaces previous ad hoc solutions and enables flights to receive instructions and clearances in a standard and efficient manner. 2.1.4 Separation and conflict resolution Separation is a concept that keeps planes at a safe distance from one another to decrease the danger of a collision. ATC is responsible for maintaining a minimum separation between manned aircraft in controlled airspace, based on the flight rules, followed by the aircraft and the airspace class. The remain-well-clear rule ensures self-separation in uncontrolled airspace and for airplanes in controlled airspace for whom separation is not provided by ATC. Minimum separation is maintained in both circumstances thanks to procedural restrictions or a situational observation approach. The capabilities of the service providing it or the capabilities of the aircraft involved are typically the basis for each separation requirement. With the advent of compact, high-accuracy positional positioning and tracking devices, the minimum separation distance for safe aircraft separation may now be determined by the total navigation and capability of the surveillance system. Separation is a performancebased navigation function that is described in terms of accuracy, integrity, continuity, availability, and functionality. Weather conditions can have an impact on tiny drones in a variety of ways, thus they must be considered when determining the needed gap between two aircraft. Conflict management is divided into three levels, which also apply to U-space. The strategic deconfliction is focused on the preflight stage of the operation, however, the tactical separation provision is focused on the in-flight stage of the operation. •Strategic deconfliction. Prior to departure, the ability to organize a flight that does not conflict with other users. This includes operators discussing operation plans with appropriate parties and minimizing any potential loss of separation through agreed-upon procedural separation or route planning that avoids other planes. •Tactical separation provision. The capacity to retain situational awareness through visual or instrumental means. Radar is used by ATC to anticipate 20 Related work aircraft trajectories and to give clearance to avoid potential conflicts. Similarly, visual flight rules denote the tactical steps required to deal with the possibility of a loss of separation between two aircraft in uncontrolled airspace. •Collision avoidance. If all preceding separation plans and precautions fail, the capacity to avoid a collision as a last resort. Collision avoidance is accomplished in U-space using detect and avoid methods. These three conflict management levels are still applicable in U-space. These services can benefit from collision avoidance systems that anticipate a possible loss of separation. When in controlled airspace, the Collaborative interface to ATC service or the Tactical conflict resolution service can be used to propagate clearances. U- space will also assist in the development of DAA technologies to ensure that missions are carried out safely. DAA on-board drones aim to provide UAS with capabilities similar to those already available to manned aircraft via see and avoid. Geofences are a new tool for risk mitigation. They are used to putting up geographical barriers to prohibit unwanted drones from entering and exiting a certain area. Geofences consist of a three-dimensional volume and a temporal component representing the time it will be active within the U-space. The following are the characteristics of geofences: it is mandatory to obey them, but exceptions, which will have a standard technical implementation, may be granted. While most geofences exclude aircraft from restricted or controlled areas, a drone may be restricted to staying inside a geofence. They may be temporary, have time of operation, and may be created with immediate effect. In the U-space, the Operational Volume (OV) of an UAS operation is a critical operational component for airspace control. OVs are like geofences, see Figure 2.3, they are 3D segments with a temporal component that represents the time it will be active within the U-space. The UAS should remain inside the OV at all times. Moreover, geographic overlapping between operations is permitted due to the temporal component of an OV as long as they are separated in time. The concept of OV is key to the development of this thesis, since it is one of the main parameters taken into account for the detection of conflicts, as well as for their 2.1 U-space 21 Geofence Operational volume Figure 2.3: Graphical representation of a geofence and an OV of an UAS operation. The OV is made up of two parts: the flight geometry, which describes the extent of airspace in which the UAS will operate, and the contingency volume, which is an outside surrounding volume that accounts for environmental or performance uncertainty. resolution. These methods of conflict detection and resolution are detailed in Section 4. It must be taken into account that not all UAVs have the same dynamics, it is not the same a multirotor than a fixed wing, therefore, their OVs have to be different, being those of the multirotor much smaller as they have a high maneuverability. In addition, it is not possible to assume a high precision in the localization of the UAVs, which influences the size of these OVs. 2.1.5 European UAS Direct Remote ID The basis of regulating low-altitude UAS traffic is identification, which successfully permits responsible ownership and allows for the safe integration of UAVs into airspace. The aircraft information, owner or possessor information, and operator information make up the basic content of identification. The ASD-STAN5association introduced a technical standard to the European UAS digital remote ID ASD-STAN (2021). Some drone activities require the drone operator to be readily identifiable by the entity controlling the flight during the flight, U-space operating drones are in this situation. In this instance, the U-space Service Provider (USSP) must guarantee that the remote identification of the drone is processed continuously throughout the flight and that the remote identification of the drone is sent to authorized users. Drones 5https://asd-stan.org/ 22 Related work operating in the U-space must have a Network Remote ID (NRI) function to ensure that they can connect to the U-space through the Internet. Such oversight does not apply to operations carried out outside the U-space. To make it possible to read the registration number, the drone should allow easy digital access to it. To that purpose, the Commission Delegated Regulation (EU) 2019/945 requires that drones designed for open category or declaration activities have a Direct Remote ID (DRI) function in their design. During the whole flight, this feature broadcasts the registration number of the operator as well as position of the drone in a form that may be received by existing mobile devices. Drones of class C0, for which the operator is not required to be registered, and drones of class C4, which are aeromodels, are the sole exceptions. The legislation also specifies an add-on that allows drones without DRI to meet extra national criteria if necessary. Practical implementation of DRI on the UAS may be predicted in two ways. Most drones that have already been sold to customers or are now on the market will require a firmware upgrade from suppliers to meet the DRI standards. UAS that do not receive this level of support from suppliers, or that lack the necessary Wi-Fi or Bluetooth technology onboard, can nevertheless retrofit with add-on devices from third parties. The first option has the benefit of being simple to install, consumers do not have to do anything but update the firmware. The benefit of the add-on, on the other hand, is that it adds new functionality to the drone, maybe including NRI. The downside of the add-on is that it necessitates the purchase and installation of extra equipment. 2.2 UTM related work Traditional ATM systems rely heavily on the human aspect, which is incompatible with drone operations’ inherent automation. Aside from that, ATM systems would be unable to grow to accommodate the enormous volume of UAS operations expected in the future. As a result, it is clear that new control systems are required to allow the efficient concurrent operation of UAS while also ensuring the safety of other aircraft and residents. Even though it has lately been a rising topic, the development 2.2 UTM related work 23 of UTMs, such as the NASA’ model in the United States Kopardekar (2015) and Europe’s U-space SESAR (2017), is still at an early stage. There are a number of services embedded in each framework that will include separation and collision avoidance, route planning services, and airspace design. Other UAS traffic management frameworks that are comparable to UTM models include China’s Civil UAS Operation Management System EU-China-APP (2018) and Japan’s UTM Consortium (2017). The NASA Technology Capability Level, UTM Pilot Program FAA (2019), and UAS Integration Pilot Program FAA (2017) demonstrations in the United States, and the European Network of U-space Stakeholders in Europe Commission (2021), overseen by Eurocontrol and SESAR, support these UTM frameworks with real-world demonstrations and testing. There are also a number of commercial UTM applications on the market. They provide the majority of strategic services but only a few tactical services. AirMap (2018), for example, focuses on unmanned aircraft system registration, geographic information systems, flight communication, traffic monitoring, and user interfaces. The Unifly platform connects authorities and pilots to ensure that UAS are securely integrated into the airspace Unifly (2020). This platform has been used in the experiments detailed in Section 6.2. On the one hand, authorities can see and authorize UAS flights in real time, as well as regulate no flight zones. Pilots may manage their UAS, plan and acquire flight authorisations that are compliant with international and local laws. The Thales ECOsystem UTM Thales (2017), which combines UAS and pilot registration, is another framework. Airspace regulation and situational awareness are used as guidelines in ECOsystem’s flight planning features. It also comes with tools for working with map overlays and 3D landscape views. Moreover, Indra is working on two solutions for managing unmanned aerial traffic, UTM Hub and UTM Connect Indra (2019). The UTM Hub is a critical tool for law enforcement to track and manage drone operations, on the other hand, the UTM Connect is a multiplatform unmanned service provider solution that enables the connection between a drone and the UTM. Furthermore, Airbus is developing digital ATM technologies to help new aerial vehicles, such as air taxis and delivery drones, enter and use the airspace securely Airbus (2018). The Galicia Institude of Technology is working on Automatic 24 Related work Intelligent SeRvices for U-space, AIRUS ITG (2018), which will focus on the development of key services such as validation of flight plans according to technical and regulatory requirements, establishment of prohibited areas, air traffic decongestion, strategic and tactical resolution of collision conflicts and real-time flight tracking. The UTM from OneSky is an enterprise-ready system with a variety of deployment choices OneSky (2019). It is intended to help national authorities manage UAS traffic in a unified airspace while maintaining regulatory compliance and flight safety. UAS and pilot registration, flight plan management, airspace analytics, flight monitoring, collision avoidance, and more are all supported by the framework. Strategic UTM services and some tactical capabilities, such as UAS monitoring, are available through the preceding UTM solutions. They do not handle operations independently throughout the flight phase, despite the fact that they are capable of providing real-time information on the UAS. It is also worth noting that all of those applications are commercial products that may not be available to the public as open source software. The scientific community has also been working on functional UTM frameworks. Several works Rumba and Nikitenko (2020); Xu et al. (2020) published reviews of related topics. In Taiwan, a prototype UTM for aviation surveillance was suggested Lin et al. (2019). The Automatic Dependent Surveillance Broadcast (ADS-B) technology utilized for surveillance is one of its fundamental qualities, allowing it to monitor cars. There is a preflight protocol for scheduling and approving flights, and the UTM can then provide surveillance warnings throughout the operation, however, the pilot must make all conflict resolution choices. In Sweden, a new UTM has been introduced Lundberg et al. (2018). It includes a comprehensive toolbox for managing traffic, geofences, flight altitude separation, and advanced visualization, as seen in general aviation. By modelling future urban airspace, this research has also uncovered concerns that intense traffic in the VLL airspace would bring to city users. In general, the preceding systems’ functions have only been shown through basic simulations, with a number of works devoted to field flying campaigns for early tests Aweiss et al. (2019); Alarcon et al. (2020). Carrami˜nana et al. (2021) presented 2.3 Project results overview 25 an agent-based simulation platform with a microservice architecture that can replicate UTM information sources including flight plans and telemetry messages. It also takes into account the manual definition of events to replicate unanticipated contingencies such communication interruptions or pilot actions. Shoufan and Alkadi (2021) presented a system that incorporates counter-drone technology into the UTM for information transmission and coordination, based on a set of clarifying protocols, to provide a responsible reaction to the detected drones. Furthermore, there are several techniques for conflict resolution and emergency management regarding the deployment of certain tactical services. Although automated decision-making has not been fully resolved in UTM systems, some studies Tan et al. (2019); Ho et al. (2019); Sacharny et al. (2020) have focused on flight planning and scheduling at a strategic level in the preflight phase. In general, because of the large search space required to identify the optimal conflict resolution in VLL airspace scenarios, approximation solutions based on heuristic solvers Tan et al. (2019) or lane maneuvers Sacharny et al. (2020) dominate the optimal deconfliction alternatives. In Rubio-Hervas et al. (2018), a probabilistic framework for expressing the risk associated with UAS operations is provided, that approach might be incorporated for automatic, real-time data processing. 2.3 Project results overview The European Commission mandated the SESAR JU in 2017 to coordinate all U- space and drone integration research and development efforts. This section summarizes the work done, focusing on the conclusions of demonstration projects that covered all elements of drone operations, as well as the supporting technologies and services necessary SESAR (2019). The outcomes of these initiatives demonstrate the progress made on the building blocks of U-space. Simultaneously, the programmes indicated significant gaps in the performance of specific technologies or areas where more study is required, particularly in the field of urban air mobility operations and the interface with manned aircraft. 26 Related work 2.3.1 Demonstrations DIODE: D-flight Internet Of Drones Environment The DIODE project aimed to show that it was possible to successfully operate many drones flying in extremely low-level airspace at the same time while carrying out different operations and missions. The proposal assumed that all aircraft, both manned and unmanned, would report their locations. In other words, the entire flow is cooperative, which reduces the complexity. The demos took a risk-based strategy to provide initial and advanced U-space services that met drone operators’ expectations. D-Flight, a specialised platform that enables e-registration, e-identification, and static geofencing in conformity with European rules set to take effect in 2020, was used to keep track of the drones. Onboard drones, DIODE exhibited developed and mature capabilities that facilitate the implementation of a risk-based and operation-centric U-space concept. DOMUS: Demonstration Of Multiple U-space Suppliers Three service providers interacted with one ecosystem manager, while many drone operators used drones from various manufacturers in the DOMUS demos. In this method, the ecosystem manager serves as the primary USSP, ensuring data integrity and serving as a single point of truth for the system: ensuring safety, security, and privacy, as well as facilitating the entry of additional service providers. It also served as a single point of contact for ATC. DOMUS exhibited e-registration, e-identification, geofencing, tracking, flight planning, dynamic flight management, and interfaces with ATC, which are all described in the U1 and U2 specifications of U-space. Some U3 services were also put to the test, including tactical deconfliction between two drones and dynamic geofencing in coordination with ATM. EuroDRONE: A European UTM Testbed for U-space EuroDRONE experimented with several concepts, technologies, and architectures to enhance stakeholder collaboration in a U-space environment. The research tested 2.3 Project results overview 27 on U-space features ranges from basic services to more complex services such as automatically identify and avoid utilizing cloud software and hardware. EuroDRONE conducted highly automated unmanned flights using drones that were completely capable of flying mission planning, employing a cloud-based UTM coupled with a small, intelligent transponder processing board. The experiments featured a unique vehicle-to-infrastructure link that was connected to a self-learning UTM platform and could communicate real-time flight data. The flights showcased end-to-end UTM solutions for both VLOS and BVLOS logistics and emergency services. The insights were utilized to develop a viable, automated cloud-based UTM architecture, which was then validated through simulation and live demonstrations. GEOSAFE: Geofencing for safe and autonomous flight in Europe The goal of the GEOSAFE study was to identify state-of-the-art geofencing U-space systems and make suggestions for future geofencing system definitions. The project was built on a one-year flight test campaign that evaluated basic and sophisticated geofencing services in pretactical flight, tactical operations, and dynamic circumstances. The project found that the majority of drones fit the criteria for pretactical geofencing and that the existing technology is ready for early U-space services. Despite the absence of standardization, solutions exist to provide tactical geofencing, which is required to deliver enhanced U-space services. However, the technology capable of supporting dynamic geofencing is not yet mature enough to meet full U-space service levels, although this is expected to change quickly in the near future, not least because dynamic geofencing is a critical function for unmanned vehicles operating beyond the line of sight. GOF-USPACE: Safe drone integration in Gulf of Finland The GOF-USPACE partners created a preoperational authority FIMS by developing an interoperability architecture for combining existing solutions from three USSPs to 34 Developed services is in charge of transforming this position data from geographic to local coordinates, thus our UTM works in local coordinates internally. External stakeholders can use the USM module to transmit warning information to the UTM, for example, a wildfire declared by the fire-fighters. Each UAS can also transmit warning information, like the detection of a jamming2or spoofing3attack. The USM module is in charge of commanding to the UAS operators the actions recommended by the UTM to avoid imminent or future threats. These recommended actions to variate the flight plan of the UAS must be confirmed or rejected by the involved UAS operator due to actual regulatory restrictions. In case of acceptance, the USM would notify the Database module to update the state of the corresponding operation. 3.1.2 Database The Database module is in charge of storing and handling the necessary information for the UTM related to the actual situation of the airspace. This situation means the information of the operation of each UAS flying or that have an operation scheduled, and the information related to the geofences that are active. Other modules of the UTM can read the Database or write to it to perform their functions, so the Database works as a server for the whole system. For example, the Monitoring module needs to check the estimated trajectory of every active UAS, so it reads from the Database information at every step to carry out its task. On the other hand, the Tracking module calculates the estimated trajectory of all active UAS and updates this information writing it in the Database. Table 3.1 and Table 3.2 details the data structures that compose the Database, which are geofences and operations. A geofence is a 4D volume of the airspace, a 3D geometrical space with an activation period of time, which is restricted to fly inside for regular UAS. An operation is composed of the reserved 4D trajectory, the estimated trajectory that the UAS will do, safety-related volumes around the flight 2A jamming attack consists of an attempt to endanger the GNSS signal of an UAS. 3In a spoofing attack, fraudulent GNSS signals that are stronger than the real unencrypted signals are sent into the UAS to cause it to deviate from its intended course. 3.1 UAS traffic management architecture 35 Table 3.1: Attributes of a geofence object. Attribute Description Identifier Unique number for geofence identification Type Cylindrical or polygonal Min/max altitude Altitude range where the geofence is active Start/end time Time period in which the geofence is active Table 3.2: Attributes of an UAS operation object. Some ConOps examples are: power line inspection, long forest surveillance, wind turbine inspection and event monitoring. Attribute Description Identifier Unique identification of the aircraft Priority Priority of the operation in the airspace Flight plan Reserved 4D trajectory for the operation Next waypoint Waypoint index that the UAS is currently targeting Estimated trajectory Prediction of the future UAS trajectory ConOps Description of the concept of the operation Flight geometry Radius of the cylindrical volume where the UAS is intended to remain during its operation Operational Volume Radius of the outer cylindrical volume to account for environmental or performance uncertainties plan, and the information needed to have a unique identification of the operation, like the International Civil Aviation Organization4(ICAO) address. 3.1.3 Tracking This module is in charge of tracking all active UAS in the airspace. Within a certain time horizon, the Tracking module updates in real time the current position and predicts trajectory of each UAS. The module computes the tracks by fusing information from different sources, UAS telemetry, and ADS-B transceivers if they are available, that it receives through the USM. The estimated trajectory of each active UAS is predicted given its current position and velocity, as well as its flight plan. The Tracking module updates the 4The ICAO addresses are 24-bit numbers to identify aircraft uniquely worldwide. 36 Developed services tracks of the active UAS in the Database module, to make this information available for the rest of the modules. Figure 3.2: Scheme with the internal components (purple) of the Tracking module. The data association component matches the measurements from the UAS with their previously position calculated to update the corresponding Kalman filters. The future UAS trajectories are predicted using the output of the data association and the flight plans, which are read from the Database module. Finally, the predicted trajectories are stored in the Database after being calculated, as well as the tracks after being updated. The Tracking module estimates through a Kalman Filter that integrates the measurements coming from the onboard ADS-B transceiver and the UAS telemetry. Figure 3.2 details how Tracking implements a stochastic filter that maintains a list of objects to estimate the state of all UAS in the airspace. Each state consists of a 3D position and velocity. Irregular sensor rates, noisy and delayed measurements can be handled by the filter and make the data more usable by the UTM. At a constant rate, the list of active UAS is read from the Database module to identify if there is a new operation. The Tracking module gets constantly just the information needed of the active UAS operations from the Database to perform its tasks, but if there is a new UAS active, it gets the information of the operation. This avoids updating unnecessary information of the operation every step. The state of all those UAS is predicted and then updated with the received observations that can be easily associated with its corresponding flight plan, since they all come with a unique UAS identifier. If an operation has an unknown UAS identifier, it 3.1 UAS traffic management architecture 37 will be considered as a noncooperative aircraft and the filter will ignore it, an attempt has been made to replicate the behavior of the NRI shown in Section 2.1.5. Furthermore, the current waypoint for each UAS is computed by searching for the waypoint in its flight plan that is closest to its current position. The estimated trajectory is also predicted for each trajectory, but it is limited by a given time horizon to reduce the computational load. If the current position of the UAS is close enough to its current waypoint, the prediction of the estimated trajectory sticks to the flight plan. Otherwise, the Kalman Filter is used to predict a trajectory given the current UAS position and velocity. Finally, the Tracking module updates the information about the trajectories in the Database module after each step. The difference between our implementation and what is established in the U-space ecosystem definition is that our present implementation only handles cooperative UAS instead of being designed to take both cooperative and non-cooperative UAS into account. This is because our work has been dedicated to enabling automated decisionmaking for UAS that are actively operating, which is useless for non-cooperative aircraft. These non-cooperative aircraft need to be handled as uncontrollable hazards that are invading the controlled airspace. Moreover, our Tracking module does have the capacity to update and store data in real-time from many sources. If necessary, other services may also access these data via the Database module. 3.1.4 Monitoring The functionality of the Monitoring module is to detect potential conflicts of the observed airspace that needs to be managed by the UTM. This module deals with conflicts related to UAS trajectories, it detects the case of an UAS getting out of its reserved flight volume, if it conflicts with a geofence or whether two UAS lose a minimum required separation. To perform this detection, the module reads periodically information from the Database module about the UAS estimated trajectories and geofences, and it uses that data to report detected conflicts in the monitored airspace. 38 Developed services When Monitoring notifies a conflict, it should indicate the type of the detected conflict, an estimation of the time instant when the conflict will occur, and a snapshot of the parts of the airspace involved in the conflict. This means the estimated trajectories of the involved UAS and, if necessary, the information related to the conflicting geofence. This snapshot is key so that the modules resolving the conflicts use the same information to evaluate the situation and to avoid time glitches and incoherent solutions. Monitoring detects possible conflicts in sequence. It first checks if an UAS is out of its OV, which is a 4D volume around the flight plan with a temporal component that means at what time the spatial volume will be active. This is the first check of the Monitoring module because if an UAS is out of its OV, the UTM treats it as a noncooperative UAS and as an out of control UAS. This UAS is doing something that was not expected, so the UTM notifies the operator that the UAS involved should return as soon as possible to its flight plan. Further checks are not necessary if the OV conflict is detected, it is an early return of the module to avoid extra computational time. If the observed UAS is inside its OV, the Monitoring module starts checking for possible conflict with active geofences. As an early return, Monitoring checks if the UAS is right now inside a geofence, if it is the case, the UAS should leave it as soon as possible. For example, this case can appear if an UAS is monitoring a field for agriculture and the firefighters warn of a wildfire in the same zone that the UAS is having its operation. This conflict is called geofence intrusion and if it is matched, further checks are not necessary to avoid extra computational time. Another possible conflict related to geofences is geofence conflict. To detect this conflict, Monitoring checks if the estimated trajectory of the observed UAS intersects with an active geofence. Every waypoint belonging to the estimated trajectory of each UAS is compared against the active geofences, to determine whether the UAS is already intruding a geofence or it is estimated to enter one in a short future time. The last check that makes the Monitoring module is called loss of separation, this appears when two UAS loss a safety distance. It is computed last because it needs more computational load to determine if there is a conflict, so the Monitoring 3.1 UAS traffic management architecture 39 module gets here as previous early returns were not matched. This check is done with a geometrical approach whose details can be seen in Acevedo et al. (2019). The Monitoring module discretizes the airspace to model it as a 4D grid, where each cell represents a 4D volume in space and time (dX,dY ,dZ,dT) and stores a list of all UAS whose trajectory is estimated to be inside. Hence, each waypoint of an UAS trajectory only needs to be compared with other waypoints of other UAS within the neighboring 4D cells. For each waypoint in the 4D grid, the distances to the waypoints in the list of its neighboring cells are calculated. A loss of separation conflict will be reported, if any of these distances is shorter than a safety distance. As mentioned above in the Tracking method, our present implementation does not take non-cooperative UAS into account, as established in the U-space ecosystem definition. Our Monitoring method does not provide a particular communication link to give traffic information to the UAS operators, however, this could be done simply through the USM module. On the other hand, our Monitoring implementation achieves all the other expected features of the U-space ecosystem definition; for example, it detects and warns in real time about conflicts involving geofences, flight non-conformances, and inter-UAS separation. 3.1.5 Emergency Management The Emergency Management module is the component of the UTM that decides which alternative route will be given to the UAS operator. It interacts with the Monitoring, USM, Database and the Tactical Deconfliction modules. The Emergency Management receives reports about external warnings coming from UAS operators or auxiliary stakeholders in the U-space through the USM module. For example, a jamming attack, the declaration of a wildfire, or any other threatening event notified by the authorities. If the Emergency Management module receives a detected threat from the authorities through the USM module, it creates a geofence to isolate that threat. This can result in several conflicts that should be detected by the Monitoring module, like having an UAS inside that geofence or an UAS flight plan intersecting it, see Section 3.1.4. 40 Developed services This module also receives conflicts detected by the Monitoring module and asks the Tactical Deconfliction module for support to have a list of alternative flight plans, see Section 4.2.2. The Emergency Management should choose among all possibilities and send the result to the USM to notify the corresponding UAS operator of the proposed alternative flight plan. The selection of the alternative flight plan is done minimizing the cost and the risk level of the route, more details can be seen in Capitan et al. (2021). The architecture proposes safe alternative flight plans to maintain a secure airspace. In the U-space ecosystem definition, the Emergency Management service notifies UAS operators of alerts and any other emergency assistance. Moreover, our EM implementation can make automatic decisions to manage hazardous situations in real time by proposing safe and effective deconfliction maneuvers to the UAS operator. 3.1.6 Tactical Deconfliction The module Tactical Deconfliction is in charge of resolving conflicting situations, calculating a list of different alternative flight plans for UAVs involved. The request to solve a conflict is sent by the Emergency Management module, and it contains all information related to the event to solve, like the data of the involved operations and the active geofences. The response is sent by the Tactical Deconfliction with the alternative flight plan list, every alternative has an associated cost and risk that will be used by the Emergency Management to choose the proposed alternative flight plan. The Tactical Deconfliction module has two strategies to solve conflicts, if the conflict involves one single UAS or if the conflict involves multiple UAS. The first strategy is used to solve conflicts with a single UAS involved, for example, an UAS that is out of its OV or has a conflict with a geofence. If it is out of its OV, the Tactical Deconfliction calculates two alternative flight plans: the first one from the current UAS position to the closest point of its flight plan, and the second one from the UAS position to its next waypoint in the flight plan, no matter how long the UAS remains out of its OV. There are two possible cases if an UAS has a conflict with a geofence: geofence conflict and geofence intrusion. The first case appears when an 3.1 UAS traffic management architecture 41 UAS flight plan goes through a geofence, so one of the computed alternative flight plans should go around the geofence to avoid it. On the other hand, if the UAS is already within a geofence, it gets out of the geofence as soon as possible, and then it goes around the geofence to resume its flight plan afterwards. The second strategy is used to solve conflicts with multiple UAS involved, which mainly result in a loss of separation between two UAS. The number of alternative flight plans returned in this case is directly related to the priorities of the operations. If the UAS involved has the same priority, the module returns the possibilities, but if the priorities are different, the Tactical Deconfliction module returns just the alternatives that involve the UAS with less priority. This is key to reduce the computational time and to avoid alternative routes for aircraft with less maniobrability than the others. In the case of multiple UAS involved, the Tactical Deconfliction module uses a geometric approach based on repulsive forces to modify the current flight plan. The details of the implemented algorithm can be seen in Acevedo et al. (2020), it generates several alternative flight plans applying vertical and horizontal separation to the involved UAS trajectories. Even if a conflict is solved, the chosen alternative flight plan could still produce additional conflicts with geofences or even with other flight plans. In this case, the Monitoring module would report those new pending conflicts in subsequent iterations, see Figure 3.3, until there is no conflict. Figure 3.3: Iterative procedure to solve a conflict in the case of a loss of separation from left to right. The flight plans of the two lower UAS are in conflict and need to be separated. Then, the middle UAS enters in conflict with the upper UAS, so these two get separated again to achieve a final solution without loss of separation. If all alternative flight plans are too risky to continue with the operation, the Emergency Management module could select between the two options given by the 42 Developed services Tactical Deconfliction module, which are an alternative flight plan to return to home and another one to go to its closest landing spot. These landing spots are selected by the operator and stored in the Database module. In the U-space ecosystem definition the Tactical Deconfliction service is designed to provide UAS operators deconfliction information via the USM. However, in the presented architecture, the EM module is an additional step that fills this duty. The EM requests assistance from the TD module in generating possible alternative plans and incorporates the automated decision-making capacity. Thus, the decision on the appropriate course of action for real time deconfliction is left to the EM. 3.1.7 Onboard autonomous detect and avoid module Based on the notion of future intelligent drones equipped with onboard sensors with high computing capabilities, we examined the integration of advanced functionality in U-space. The integration of onboard DAA capabilities, as well as the consequences for U-space services, were examined. In the framework of the European SAFEDRONE project5we developed an onboard autonomous DAA module, which is external and independent of the UTM architecture, and we tested it in a specific scenario. It was considered a scenario with an UAS flying a previously approved flight plan at a very low altitude and encountering an unanticipated static ground obstacle. The UAS then had to compute an alternative flight plan autonomously to avoid the obstacle. Our objective was to figure out which processes should be followed and how they should change in the near future to help DAA capabilities. A multirotor platform was chosen for this situation because of its higher manoeuvrability compared to fixedwing systems, as well as its ability to hover while it awaits approval of the new flight plan. Geographic Information System (GIS) support will be key in the future to enable safe and secure trajectories in VLL and urban environment, it provides information about several layers related to a city: buildings, population, traffic, vegetation, etc. This information will allow future developments to optimize trajectories in those 5https://cordis.europa.eu/project/id/783211 3.1 UAS traffic management architecture 43 complex scenarios, however, temporary static large obstacles like cranes, scaffolding, etc., may not be included in GIS maps. Therefore, the development of an onboard DAA module is needed to ensure that UAS can accomplish their trajectories even when encountering unforeseen obstacles. To detect those unexpected obstacles, the multirotor had a 3D LIDAR mounted, which gave a stream of point cloud measurements that were to be integrated continuously into a virtual representation of the world. The selected environment representation is the octree implementation of the octomap Hornung et al. (2013) library6, which implements a 3D occupancy grid mapping approach, providing data structure and mapping algorithms. Once the representation was done, the module was able to calculate whether the accepted flight plan crossed an obstacle. In such cases, the path planner computed an alternative route to avoid the unexpected obstacle. The path planner chosen was the Lazy Theta∗Nash et al. (2010), which is based on the well known A∗algorithm. A considerable disadvantage of the A∗algorithm is that it creates paths using only the edges of the grid. On the other hand, Theta∗algorithms do not have the constraint of using only the edges of the grid, as it uses any angle. Each extended vertex does a line-of-sight check for each extended visible neighbor, allowing the vertex’s parent to be any other graph vertex, resulting in realistic and short-looking routes. In comparison to Theta∗, Lazy Theta∗decreases the number of line-of-sight inspections, allowing it to locate routes quicker while maintaining the same length. The DAA module integrates the presented algorithms of this section using a single onboard computer that allows the UAS to generate a virtual representation of the world, detect unexpected obstacles, generate an alternative route to avoid it, communicate with the operator in charge of the operation, autonomously and online. Figure 3.4 shows a simulation of the module, the rectangle prism is being detected by the simulated 3D LIDAR. Pink dots represent the point cloud, which is the input of the octomap library that transforms this information into 3D voxels. The representation allows the module to differentiate between three types of space: obstacle, free, and unknown. If the beam of the sensor goes from the sensor to the maximum range, 6https://octomap.github.io/ 50 Developed services Figure 3.5: The UTM architecture in the ROS graph. The nodes (ellipsoid) are the modules described in Section 3.1 and the rectangles are the topics used in the system. as a client, the services provided by the Database module. When it detects a conflict, it sends a threat to the Emergency Management module using the service threats, which contains a snapshot of the current state of the airspace, this way time glitches can be avoided not being necessary for Tactical Deconfliction to consult the Database. It is in charge of returning alternative flight plans for a received conflict, thus it acts as a server of the service deconfliction. The response is received by the Emergency Management module, which selects the alternative route that will be proposed to the operator, this module uses the service notifications as a client being the USM module the server. In the case of the services update flight plans and change flight status, the USM module is a client of the Tracking module, as this one is in charge of writing to the Database, it should store the flight plans accepted by the operator and store the status of the flight plan, whether its flight plan has started or finished. In ROS, when submitting a request to a service, a synchronous client will block the calling thread until the response has been received, nothing else can happen on that thread during the call. The call might take any duration to finish, and the answer is sent immediately to the client once it is finished. On the other hand, there are cases in the UTM architecture when the communication between nodes does not need to be synchronous, thus these modules communicate using topics for certain tasks, see Figure 3.5. For example, whenever an operator accepts an alternative flight plan or whenever an authority warns to the UTM about a threat. Moreover, the telemetry received from the UAS is also asynchronous, even though it is sent periodically. The module USM is the one with more communications using topics, this is due to the need of listening to certain sources on standby until a certain event triggers a process. For example, if a stakeholder warns the UTM of a wildfire, it uses this 3.4 Conclusions 51 module, and it is in charge of sending to the Emergency Management module the warning as soon as possible. On the other hand, the USM is constantly listening to the topic rpa state info where is the information related to all active UAS in the observed airspace. There is one topic for all active UAS, so the module just needs to check one, translate the coordinates from geographic to local, and send the information using the topic position report, with the Tracking module being the receiver. Moreover, when the UTM detects a conflict in the observed airspace, solves it, and proposes to the operator an alternative route, it proposes the new flight plan by using the topic alternative flight plan and the response of the operator is sent back using the topic flight acceptance. To summarize, it can be said that the internal communications of the UTM architecture are done using mainly services using a request and response interaction and, on the other hand, the communications between the UTM and the external actors are done using mainly topics using a publisher and subscriber interation. 3.4 Conclusions This chapter presents the architecture developed for our UAS traffic management, which has a modular and reusable design, does not impose requirements on the execution capabilities of the aircraft, runs at a very high level and is built upon ROS. The UTM architecture can work without a human intervening in the process, aiming to match the final objective of the U-space framework. However, it suggests actions to the UAS operator, due to the current regulation, where the operator is the one who has the responsability to go ahead with the proposed actions of the UTM. The functionalities implemented by the UTM architecture are compared with the ones implemented by the definition of the U-space ecosystem. In the first place, the proposed UTM architecture does not take into account noncooperative UAS. It is mainly focused on enabling automated decision-making for operation UAS, hence all UAS involved in the system must be cooperative. Despite this, the Tracking module can record and update data in real time reported from different sources, like UAS onboard telemetry, and ADS-B. This information is constantly updated and available 52 Developed services for other modules if needed in the Database. In terms of Monitoring, this module does not provide traffic information to UAS operators, however, it accomplishes other expected functionalities, for example, it detects and alerts in real time about conflicts related to multiple UAS loss of separation, flight nonconformances and geofences. Moreover, the Tactical Deconfliction module transmits deconfliction information in real time, it does from the USM to the UAS operator, however, in our scheme an additional step is added. It computes different alternatives and sends them to the Emergency Management module instead of to the USM directly, because the Emergency Management decides automatically which alternative will be proposed to the UAS operator. Finally, an onboard autonomous DAA module, which is external and independent of the UTM architecture, has been presented. It is in charge of detecting and avoiding temporary static large obstacles like cranes, scaffolding, etc., using an onboard 3D LIDAR to detect the obstacle, and the Lazy Theta∗algorithm to avoid it. The DAA module is not intended to detect other non-cooperative aircraft, which is a very complex task that is not solved at the time of writing of the presented Thesis. This is due to the scarcity on the market of on-board sensors for UAS that allow long-range detection of other small aircraft. Chapter 4 Conflict detection and resolution This chapter presents a method for multi-UAS conflict management at the tactical level, based on the estimation of 4D UAS trajectories. The proposed solution represents the scenario by means of a 4D grid and uses a geometric approach to resolve conflicts in an iterative manner, minimizing the deviation with respect to the initial estimated trajectory. This method is divided in two main modules of the UTM architecture of the presented Thesis, the Monitoring module, which is in charge of detecting conflicts in the observed airspace, and the Tactical Deconfliction module, which calculates alternative flight plans to avoid the detected conflicts. These modules are previously explained in Section 3.1. Moreover, this chapter details the need to have a 4D trajectory follower onboard UAS to maximize the available VLL airspace. 4.1 Introduction and related work In terms of U-space, the concept of multi-UAS conflict management becomes a key challenge that is considered at two levels: strategic, which relates to preflight approaches, and in-flight approaches that are called tactical. This Thesis is focused on the tactical phase in which the UAS are flying, i.e., tactical conflict management is addressed as a conjunction of conflict detection and tactical conflict resolution. At a strategic level, most works focus on studying the probability of conflicts between pairs of UAS, as in Liu and Hwang (2011). A quite relevant work related 53 54 Conflict detection and resolution to strategic multitrajectory conflict detection is Kuenz and Peinecke (2009). They propose the sequential division of the airspace to get subspaces containing an unique trajectory. However, its performance may decrease significantly for too dense scenarios. In Mercado Velasco et al. (2015), the authors incorporate intent information from predefined trajectories to complement a Velocity Obstacle approach, but focusing on the 2D problem. On the other hand, at the tactical level, conflict detection is also a well-studied problem in the literature. The conditions to define a potential conflict between two UAS, based on their tracked trajectories, are stated in Alonso-Ayuso et al. (2013). Authors in Yang et al. (2015) pose a hierarchical approach, which reduces the computation time to detect potential imminent conflicts by checking the relative distance between pairs of UAS in an asynchronous way. In Tang et al. (2010), they show how the intended flight plan may enhance the conflict detection in a tactical phase. Another reactive approach, rather spread, is using the concept of velocity obstacles Lalish and Morgansen (2012). These methods search a velocity space to assign the vehicle velocities leading to collision-free trajectories in the future. Another geometric approach based on space-time prisms is proposed in Siqi et al. (2018). In Besada et al. (2020) the authors present a flight planning tool for safe urban operations, which combines both the strategic and tactical levels. It predicts trajectories and provides the flight plan designer with visual data so he can build flights that are compliant with the status of the airspace at the time. Another related area is multivehicle path finding, where a set of vehicles need to find collision-free paths Wolfgang et al. (2019). Different optimization methods have been applied to solve the problem in continuous Mellinger et al. (2012) or discrete space Yu and Lavalle (2016). Centralized constrained optimization solvers have been proposed. For instance, Turpin et al. (2014) proposed to model the problem as a task allocation and then compute the optimal trajectories in terms of traveled distance. In Karamouzas and Guy (2015), linear programming in a velocity space is used. Moreover, sequential convex programming has been proposed to obtain solutions in non-convex scenarios Alonso-mora et al. (2016). The main issue with these methods for multivehicle path finding is that they do not scale well with the size of the team and hence, they do not allow aerial vehicles to replan online in case of contingency 4.2 Problem statement 55 or failures. However, Besada-Portas et al. (2010) proposed a method for multiple UAVs based on evolutionary algorithms for realistic scenarios that presented a good scalability. The fitness of the solutions is evaluated using a method that enables for easy addition of additional optimization indices and modification of the objectives and priorities, which gives this planner its flexibility. Finally, the concept of 4D-TBO is another relevant issue in the U-space context. It consists in the integration of the temporal dimension into the traditional flight plan, which includes only the intended three dimensions spatial trajectory. Therefore, any delay in the time schedule should be assumed as a separation from the intended trajectory, just as a vertical or horizontal deviation. This concept is especially relevant for U-space tactical services, such as monitoring and tactical deconfliction, where 4D- TBO increases the aerial traffic predictability, maximizing the airspace capacity and improving the overall safety in UAS traffic management. Robust, efficient, and precise autonomous following of predefined trajectories is a requirement of the UAS for all these applications. The trajectory tracking problem for UAS is well studied in the literature, and there are different geometric or control methods. The rest of the chapter is structured as follows. First, Section 4.2 states the conflict detection, tactical deconfliction, and 4D trajectory tracking problems. In Section 4.3, a conflict detection and resolution system and a 4D trajectory follower are presented. Section 4.4, summarizes the set of simulation results used to validate the proposed approach. Finally, Section 4.5 closes the chapter with the conclusions and future work. 4.2 Problem statement We address conflict detection and resolution for multi-UAS systems from a tactical point of view and based on 4D trajectories. There are several challenges and complementary issues to take into account to approach this problem. From a tactical point of view, the conflicts can not be detected at the current time t, but predicted with enough time to decide and execute the most proper actions to avoid the potential conflict, for example, following an alternative flight plan. Therefore, to handle the 56 Conflict detection and resolution conflict detection problem, it is required to have an estimation of the 4D trajectory of the UAS for a given time horizon. 4.2.1 Conflict detection problem The UTM architecture proposed in this Thesis is able to detect conflicts in an observed airspace using the Monitoring module, presented in Section 3.1.4. In this section, we will focus on three conflicts that should be detected, loss of separation, geofence conflict, and geofence intrusion. The first one is the only case that involves two UAS, the others are related just to the UAS 4D trajectory and a geofence. •Ageofence intrusion event is a conflict between an UAS and a geofence, and it appears when an UAS is suddenly inside a geofence, see Figure 4.1. This can happen if an UAS is doing its operation, and an external stakeholder warns the UTM of a threat, for example, firefighters warn of a wildfire in the zone where the UAS is flying. Geofences can be polygons or cylinders, thus the system should be able to detect if an UAS is inside a geofence no matter the shape of the geofence. Figure 4.1: Left, geofence conflict. Right, geofence intrusion •Ageofence conflict event appears when the estimated 4D trajectory of an UAS is intersecting with a geofence in space and in time, see Figure 4.1. As in the previous conflict, the UTM should be able to detect the conflict no matter the shape of the geofence. •Aloss of separation event is a conflict between two UAS, and it is defined as a situation where they approach below their safety distance. Depending on the 4.2 Problem statement 57 type of vehicle, different separation parameters for the lateral, longitudinal, and vertical dimensions may be considered and different shapes around the vehicle may be considered as their safety zones: an elliptical cylinder, an ellipsoid or a sphere. For the presented methods the cylinder has been chosen in order to be able to use the operational volume concept described in Section 2.1.4. Therefore, the safety distance will have to be at least equal to or greater than the sum of both OVs. A conflict between two UAS will happen at time tif and only if |pi(t)−pj(t)| ≤ δ, being pi(t) and pj(t) the positions at time tof UAS Aiand Aj, respectively, and δthe safety distance parameter. Let assume a 4D trajectory as an ordered list of waypoints, being it defined by an expected threedimensional position and its estimated arrival time. Let us also consider that every pair of consecutive waypoints are equally time-spaced by the same interwaypoint period τfor any trajectory. Therefore, a potential conflict between a pair of trajectories will happen if there exist a pair of waypoints of both trajectories with a time difference below the inter-waypoint period and distance below the safety distance δ, see Figure 4.2. Δtime τ δ distance conflict Figure 4.2: Zones where a pair of waypoints of two different trajectories can be free of conflict. The red area is the only one in which a pair of waypoints have a time difference below the inter-waypoint period τand a distance below the safety distance δ. The dark green area represents a conflicting time between waypoints, but it is a safe area to fly because there is enough distance. On the other hand, the light green area is a safe area to fly due to enough time between waypoints despide the conflicting distance. 58 Conflict detection and resolution 4.2.2 Tactical deconfliction problem Let us consider a set of 4D trajectories for UAS sharing a common airspace defined within a given time horizon, see Figure 4.3. The conflict detection and resolution problem implies not only to detect potential conflicts according to the definitions of the trajectories presented in Section 4.2.1, but also to propose an alternative set of 4D trajectories which ensure no potential conflicts among them. Figure 4.3: Estimated trajectories within a given time horizon of several UAS sharing a common airspace. Each estimated trajectory is marked with a different color. There are infinite possible solutions to the posed problem. To assess the relevant solutions, it will be assumed that the initial trajectories are the reference ones from an operational point of view, since they come from the flight plans provided by the UAS operators. Therefore, the mean distance deviation from the initial trajectories to the alternative ones will be chosen as the minimization criteria. This distance deviation may be calculated as the three-dimensional distance between a pair of waypoints with the same estimated arrival time from the alternative and initial trajectories. It is interesting to take into account the priorities associated with the different UAS to solve the problem. A potential conflict between two UAS with different priorities should be solved modifying only the trajectory of the UAS with lower priority. Therefore, the optimization criteria should consider weighting the trajectory deviations according to these priorities. 4.2 Problem statement 59 On the other hand, since this problem should be solved in-flight and the alternative trajectories have to be submitted, accepted, and executed by the UAS, the required processing time to obtain a suitable solution has to be minimized. 4.2.3 4D trajectory tracking problem The problem described in Section 4.2.2 is based on the accurate tracking of 4D trajectories by the involved UAS: each UAS has to follow its assigned waypoints matching each associated arrival time. Delays or advances with respect to the estimated arrival time may cause unexpected conflicts and require to update the estimation of the trajectories, to detect new conflicts and to generate alternative trajectories continuously. However, commercial autonomous navigation systems for UAS do not usually manage 4D trajectories and set a cruise flight speed to follow a given three-dimensional path. The 4D trajectory could hardly be tracked using these systems, even when the arrival times associated with each waypoint had been properly chosen according to the UAS cruise speed. Moreover, matching the specified arrival times manually is not an easy task that can do every single UAS pilot. Let us assume that an UAS can be directly controlled through three-dimensional velocity commands. Known the intended 4D trajectory of the UAS, the objective is to implement a system which tracks accurately the positions and the associated arrival times based on velocity commands. The maximum flight speed should be also considered for the UAS. Formally, the criteria to minimize are two: the mean minimum distance between the actual travelled trajectory and the estimated one; and the mean difference between the actual and the estimated arrival times of every waypoint. The 4D trajectory follower is detailed in Chapter 5. 66 Conflict detection and resolution 4.3.2 Tactical deconfliction module The Tactical Deconfliction module is in charge of calculating different alternative routes for a given conflict. The generated alternative flight plans are sent with two relevant parameters: the cost, which is determined by the total distance travelled by the UAS, and the riskiness, which is determined by the minimum distance between the alternative route and any geofence, or, in case that the solution goes through any geofence partially, by the length of the route portions that remain within a geofence. These parameters are needed by the Emergency Management module to determine which alternative flight plan should be proposed to the operator of the UAS involved in the conflict. It should be noticed that the proposed approach requires that UAS can adapt their flight velocities to properly follow the generated trajectories. Although the initial flight plans could have been chosen to fly at a single nominal speed, alternative trajectories do not respect this principle. For example, an UAS has a flight plan of four waypoints P1, P2, P3, P4with its corresponding times t1, t2, t3, t4and a conflict is detected in the third waypoint (P3, t3). The Tactical Deconfliction module modifies the position of P3to avoid the conflict, but t3remains the same, therefore the distances P3P2and P4P3are larger than initially and the UAS should cover more distance in the same time. Loss of separation In terms of multi-UAS conflict, the algorithm proposed is based on a geometric approach to solve sequentially each conflict between pairs of waypoints. The idea is separating each pair of conflicting waypoints independently and taking advantage of the periodic checks performed by the monitoring service to solve iteratively more complex situations, for example, with more than two UAS involved. For each conflict received, it computes a new pair of waypoints separated enough to match the safety distance, as it is shown in Figure 4.8. These new waypoints are calculated modifying the three-dimensional position, but not the arrival time, generating an estimated variation of the nominal speed of the UAS with respect to 4.3 Solution adopted 67 the original one. Then, they are fused with the associated trajectories and reported to the corresponding UAS. 00.511.52012 0 1 2 3 Conflict XY Z (a) 00.511.52012 0 1 2 3 Safety distance XY Z (b) Figure 4.8: On the left two trajectories with a pair of waypoints in conflict. On the right, the alternative trajectories provided by separating the conflicting waypoint to match the safety distance. To calculate the new waypoints, different issues have to be considered. First, UAS operations may be assigned with different priorities. We keep without variation the trajectories associated with UAS with higher priority, proposing alternative trajectories for the UAS with lower priority. In addition, waypoint separation may be performed following different directions: the direction which joins both waypoints, vertically or horizontally. The first option seems to be more efficient from an airspace capacity point of view and according to the conditions specified in Section 4.2.2. However, the latter options are safer since they are more predictable for the rest of manned and unmanned aircraft. Despite each conflict being solved independently, not considering the rest of the trajectories, the monitoring service runs periodically and generates an iterative process which was illustrated in Figure 3.3. Finally, it has to be checked if the UAS can follow the alternative trajectory, matching the arrival time requirements according to its speed capabilities. In summary, this one may be assured always the required cruise speed of the UAS to perform the initial plan is lower than the half of its maximum speed. In case this condition 68 Conflict detection and resolution is not met, different strategies may be adopted: modifying the previous or next waypoint to the conflicting one; or assigning a different separation weight to each conflicting waypoint depending on the difference between the original cruise speed and the maximum speed. Geofence intrusion and geofence conflict There are two possible cases if an UAS has a conflict with a geofence. The first case appears when an UAS flight plan goes through a geofence, here the Tactical Deconfliction computes an alternative flight plan around the geofence to avoid it, see left Figure 4.9. On the other hand, if the UAS is already within a geofence, it gets out of the geofence through the closest point and then it goes around the geofence to resume its flight plan afterwards, see right Figure 4.9. When this module needs to compute an alternative flight plan to go around a geofence, it uses a heuristic path planner based on the well-known A∗algorithm. This path planner has been developed by our research group, is public1and has been used in several applications like in autonomous planning for multiple aerial cinematographers Caraballo et al. (2020). 4.3.3 4D trajectory follower based on the carrot chasing algorithm The 4D trajectory tracking problem is solved with a method based on the carrot chasing algorithm. It is composed by two algorithms: the generator and the follower. This 4D trajectory follower has been developed in this Thesis, and it is detailed in Chapter 5. The generator algorithm creates a much more dense list of waypoints based on the ordered list of waypoints received and it can be approximated to a continuous curve. To follow a 4D trajectory, it should interpolate the initial list of times matching the number of waypoints of the more dense list. 1github.com/Angel-M-Montes/path_planner 4.4 Validation results 69 WP2 WP1 Geofence WP2 WP1 WP3 WP4 Geofence Figure 4.9: Left, an UAS flight plan intersecting a geofence. The last waypoint of its flight plan before entering the geofence (WP1) and the first waypoint after leaving it (WP2) are obtained, and this segment of the flight plan is replaced by the alternative route (dashed orange line). Right, an UAS inside a geofence. The escape point (WP2) is that on the geofence’s border closest to the UAS (WP1). From WP3to the first point of the flight plan after leaving the geofence (WP4), an alternative route avoiding the geofence is inserted to modify the original flight plan and respecting at every moment the safety distance. 4.4 Validation results This section details the different simulation tests carried out in order to validate the approaches proposed in this chapter. Large scale simulations based on MATLAB are provided to analyze the scalability of the conflict detection and resolution approach, and ROS-Gazebo based tests are performed to validate the entire system integration in operation. 4.4.1 Scalability analysis Time-based algorithms are a traditional solution for ATM conflicts. Thus, the proposed solution is compared with a conflict resolution approach based on the recursive time shift algorithm Peinecke and Kuenz (2017). It proposes to shift the trajectories in time, starting at conflicting waypoints, to find the successful trajectories. Regarding the conflict detection approach, a detailed comparison with respect to the traditional exhaustive search approach was presented in Acevedo et al. (2019). 70 Conflict detection and resolution MATLAB simulations for large-scale scenarios have been carried out on an Intel [email protected], to analyze the scalability of the developed conflict detection and resolution system. The first element which can influence the optimization criteria described in Section 4.2.2 is the number of involved UAS. Therefore, a test battery increasing the number of UAVs and setting the time horizon to 100 seconds and the 4D cell dimensions to 100×100×100 meters was carried out. Figure 4.10 shows the processing time and the mean deviation with respect to the original trajectories using the proposed and alternative approaches. 10 20 30 40 50 60 70 80 90 100 0 5 10 15 20 25 30 Number of UAS Processing time (s) Proposed solution Recursive time shift (a) 10 20 30 40 50 60 70 80 90 100 0 0.5 1 1.5 2 2.5 3 3.5 4 Number of UAS Mean deviation (m) Proposed solution Recursive time shift (b) Figure 4.10: Summary of the test battery increasing the number of UAS and comparing the proposed solution against the time shift based approach: (a) Processing time by test to detect and resolve all the conflicts. (b) Mean deviation by waypoint between the generated and the original trajectories. The time horizon is another interesting element whose impact on the system efficiency should be analyzed. A large time horizon may be necessary to match the U-space requirements, allowing the UAS operators to receive, analyze, and execute proper commands to avoid potential conflicts. Therefore, a second test battery increasing the time horizon and setting the number of involved UAS to 30 and the 4D cell dimensions to 100 ×100 ×100 meters has been performed. Processing time and mean deviation with respect to the original trajectories are shown in Figure 4.11. The results show that the proposed solution requires much less processing time and gets much less deviation with respect to the original trajectories than the more traditional recursive time shift algorithm. These improvements are highly related to 4.4 Validation results 71 20 40 60 80 100 120 140 160 180 200 0 5 10 15 20 25 30 Time horizon (s) Processing time (s) Proposed solution Recursive time shift (a) 20 40 60 80 100 120 140 160 180 200 0 1 2 3 4 5 Time horizon (s) Mean deviation (m) Proposed solution Recursive time shift (b) Figure 4.11: Summary of the test battery increasing the time horizon and comparing the proposed solution against the time shift based approach: (a) Processing time by test to detect and resolve all the conflicts. (b) Mean deviation by waypoint between the generated and the original trajectories. the number of involved trajectories and the considered time horizon. The proposed solution exploits the assumption of following accurately the trajectory both in time and space to modify only the conflicting waypoints. However, shifting a trajectory in time implies to modify every waypoint in the trajectory, generating new conflicts which have to be detected and solved again. 4.4.2 Multi-UAS tests for loss of separation The proposed solution was tested on ROS Quigley et al. (2009) Kinetic under the Ubuntu 16.04 operating system using GAZEBO Koenig and Howard (2004), the PX4 v1.7.3 SITL Meier et al. (2015) functionality to simulate the autopilot and the UAS Abstraction Layer (UAL) v3.0 Real et al. (2020) to interact with the simulated UAS. The simulation environment allows running the same software used in a real UAS, with the advantage of not needing pilots or permissions. In addition, it supports testing the same real scenario quickly and as many times as the developer wants. The previous section presented a scalability analysis running tests involving 100 UAS, this section is focused on the behaviour of UAS on the simulation framework, thus the tests use 3 UAS to clarify the results. 72 Conflict detection and resolution The following tests use multiple UAS with flight plans that have the same characteristics, such as the longitude (100 meters), the arrival time of the last waypoint (37.5 seconds), and cruising speed (2.7 m/s), however they differ in the origin and arrival poses. The conflict detection and resolution system has a safety distance δof 10 meters and an inter-waypoint distance τof 5 seconds. For each multi-UAS test, two plots are provided: 3D visualization of the UAS travelling along their flight plans and the distance between the UAS involved in the test. Figure 4.12 shows an example of these flight plans in detail, with a trajectory that can be followed by the simulated UAS which has a maximum velocity of 4 m/s. Figure 4.12a has different scales on the axes to better visualize the error between trajectories. Moreover, how the trajectory follower caps the commanded velocity to the maximum velocity in the first seconds is shown in Figure 4.12b. Figure 4.12d shows the difference between the UAS actual time and the reference time: if it is negative, the UAS is behind of the schedule, otherwise the UAS is ahead of schedule. The 4D trajectory follower always tries to make the time difference equal to zero. It also tries to minimize the normal distance between the UAS and the trajectory. The space and time errors that the 4D trajectory follower tries to minimize are shown in Table 4.1. Table 4.1: Simulated test errors Error Min Mean Max Std Var Space (m) 0.002 0.036 0.129 0.030 0.001 Time (s) 0.000 0.196 1.047 0.311 0.097 The first test presents a conflict after 15 seconds between two UAS that start their flight plans at the same time. UAS 0 and 1 have priorities 0 and 1, respectively. The conflict detection and resolution module decides to leave one flight plan as it is and modifies the other flight plan due to the UAS priorities to solve the conflict. Despite the increment of the flight plan longitude, the UAS manages to fly through the trajectory in time because it uses the 4D trajectory follower, which minimizes its time and space errors. UAS 0 finishes its flight in 37.46 seconds even modifying its flight plan, and UAS 1 finishes in 37.51 seconds. Figure 4.13b shows the distance 4.4 Validation results 73 (a) (b) (c) (d) Figure 4.12: Simulation results. (a) Three dimensional view of the initial waypoints, the reference trajectory generated and the actual trajectory flown. (b) reference velocity and current velocity of the UAS. (c) Normal distance between the UAS and the generated trajectory. (d) Difference between the reference time and the current time. between UAS which never goes below the limit which is 10 meters. A 3D visualization of the trajectories can be seen in Figure 4.13a. The second test presents three UAS flying with flight plans similar to the ones used in the previous simulations except for UAS 2, which has a flight plan that lasts 7.5 seconds more. The conflict between UAS 1 and UAS 2 is found in the same position and time that happened in the previous test. As the priorities do not change, the conflict detection and resolution module calculates the same solution. The solution of the conflict between UAS 0 and UAS 1 does not create another conflict between UAS 0 and 2, and they fly through the same waypoint at different times, so the 74 Conflict detection and resolution X axis 020 40 60 80 100 Y axis −60 −40 −20 020 40 Z axis 0 2 4 6 8 10 12 14 UAV 0 flight plan UAV 0 trajectory UAV 1 trajectory (a) 0 10 20 30 40 Time (s) 10 20 30 40 50 60 70 80 Distance (m) Limit = 10m Distance UAV0 - UAV1 (b) Figure 4.13: (a) 3D Visualization of the traveled trajectories. (b) Distances between UAS. UAS 0 has a conflict with UAS 1 but the solution of the conflict detection and resolution module keeps the distance above the limit. minimum distance between UAS is not violated, UAS 0 goes through the waypoint at 30 seconds, and UAS 2 at 37.5 seconds. Figure 4.14b shows distances between the UAS which never goes below the limit. UAS 0 finishes its flight in 38.14 seconds even modifying its flight plan, UAS 1 finishes in 37.44 seconds, and UAS 2 in 44.94 seconds. A 3D visualization of the trajectories can be seen in Figure 4.14a and a video of the simulation is publicly available2. The third test presents the relevance of using a 4D trajectory follower. The conflict detection and resolution module gives its solution to the UAS 0 which follows the new trajectory with a cruising speed of 2.7 m/s to match the mean of the velocity of the last test. The new trajectory is longer than the initial flight plan, so while going along the modified trajectory to avoid UAS 1, UAS 0 is delayed. This causes a conflict between UAS 0 and 2 where their flight plans cross at 37.5 seconds, which did not appear in the previous test and the distance between UAS 0 and 2 goes below the limit, see Figure 4.15b. The new trajectory causes a new conflict, it will be reported again from the monitoring to the deconfliction node, generating an iterative process 2https://youtu.be/0U42krj1MTM 4.5 Conclusions 75 X axis 020 40 60 80 100 Y axis −100 −80 −60 −40 −20 020 40 Z axis 0 2 4 6 8 10 12 14 UAV 0 flight plan UAV 0 trajectory UAV 1 trajectory UAV 2 trajectory (a) 0 10 20 30 40 Time (s) 20 40 60 80 100 120 140 Distance (m) Limit = 10m Distance UAV0 - UAV1 Distance UAV0 - UAV2 Distance UAV1 - UAV2 (b) Figure 4.14: (a) 3D Visualization of the traveled trajectories. (b) Distances between UAS. UAS 0 has a conflict with UAS 1 but the solution of the conflict detection and resolution module keeps the distance above the limit. UAS 0 is using the 4D trajectory follower. to solve the conflict, but in this test, the conflict will not be solved to emphasize that the distance between UAS goes below the limit. A 3D visualization of the trajectories can be seen in Figure 4.15a and a video of the simulation is publicly available3. 4.5 Conclusions The use of UAS will be increased in the next decades, being the ATM much more complex. In this context, the concept of 4D trajectory becomes a key element to increase the flight safety and to maximize the shared airspace usage. This chapter faces this challenge, presenting two modules for conflict detection and conflict resolution. The presented conflict detection method tries to optimize the search of conflicts, limiting it to a local search around each waypoint. Regarding the conflict resolution method, it tries to minimize the deviation distance with respect to the initial trajectory, splitting the whole problem into several simpler subproblems with just two 3https://youtu.be/8oKwk7tL-dI 82 4D Trajectory Based Operation Follower to apply the trajectory following method efficiently. Hence, it uses the trajectory generator to get a discrete curve γ(λ) from the ordered list of waypoints W. Then, continuously, it receives the UAS pose p(t) and the actual time tto generate the velocity commands v(t), based on the method described below. UAV Normal distance Look ahead distance Virtual target Velocity command Figure 5.2: Top view of the three-dimensional path follower based on the carrot chasing algorithm without taking into account the orientation error. The proposed trajectory following method is based on the carrot chasing algorithm, see Figure 5.2. The method runs as follows, first the λpargument is obtained using expression 5.1, which minimizes the distance from the UAS position to the trajectory. The fixed look-ahead distance dis added and the virtual target pose in the trajectory is achieved as pt(t) = γ(λp(t) + d).(5.4) To fix the time error, the cruising speed is calculated for the time tas vc=d τ(λp(t) + d)−t.(5.5) The last step is to calculate the velocity command based on the cruising speed, as v(t) = vc pt(t)−p(t) |pt(t)−p(t)|(5.6) to reach the target virtual pose. 5.4 UAS Path And Trajectory Follower 83 5.4.3 Policy adopted to deal with infeasible 4D trajectories It is possible that the user can set up an infeasible list of 4D waypoints according to the UAS capabilities, where some waypoints wiare feasible and others are not. In that case, the proposed module should fix the initial list and replace it with feasible times to let the UAS perform a normal navigation through the trajectory. The difference of time between going through a segment at maximum velocity and going at the reference velocity vreference should be checked, being vreference the reference velocity to match the times, see Equation 5.7. ∆T=wi+1 −wi vreference −wi+1 −wi vmax (5.7) Each segment siis classified in three different ways: infeasible if ∆Tis negative, modifiable if it is positive and non-modifiable if ∆Tis equal to zero. Non-modifiable segments are the ones where the UAS goes through them at the maximum speed. Negative segments should be extended in time because the UAS has not enough time to go from its beginning to the end of the segment even at the maximum speed. Modifiable segments Sare the ones where the UAS can increase its velocity, so they can be reduced in time if needed, see Figure 5.3. To fix the infeasible time list, the trajectory generator starts extending the segments that are infeasible until they are non-modifiable and stores how long it is extended. At that point, the list is formed by modifiable and non-modifiable segments. The last part is to share equally, if possible, the amount of time stored between the modifiable segments. Every modifiable segment can receive just an amount of time that converts it into a non-modifiable segment, if the time that it should receive is longer than that the other modifiable segments should receive the rest of the time if possible, see Algorithm 2. 5.4.4 Software implementation details The work described in this chapter has been integrated with the UAL, which tries to abstract the user programmer from the platform’s autopilot, defining a common 84 4D Trajectory Based Operation Follower Algorithm 2: Algorithm to correct the times of the initial waypoint list. It takes the extra time accumulated by infeasible segments and tries to share it equally between the modifiable segments. te: total time extra, dte: time extra division, ts: subtract time, foreach wi∈Wdo calculate ∆T; if ∆T > 0then S.push back(si); else if ∆T < 0then te=te+ ∆T; add ∆Tto the following waypoints in W; end end while te= 0 AND S.size() >0do dte=te S.size() ; foreach si∈Sdo calculate ∆T; if ∆T≥dtethen ts=dte; else ts= ∆T; end te=te−ts; subtract tsto the following waypoints in W; end clear S; foreach wi∈Wdo calculate ∆T; if ∆T > 0then S.push back(si); end end end 5.4 UAS Path And Trajectory Follower 85 Step 1 2 31 1 2 3 4 5 4 5 1 2 3 4 5 time Step 2 Step 3 Figure 5.3: Graphical example of Algorithm 2. Red segments are infeasible and should be extended to a grey segment. Green segments are modifiable and can be reduced to match the initial times. interface with a collection of the most used information and functionalities of an UAS. In particular, the developments presented in this chapter are based on the release 3.0 of UAL and the Kinetic version of ROS. The proposed system receives a list of 4D waypoints, generates a 4D trajectory, and calculates which velocity vector should use UAL as the reference at every instance through the trajectory. UAV Abstraction Layer UAV Path And Trajectory Follower PX4 DJI Simulator // Autopilot ArdupilotCrazyflie Airsim Figure 5.4: The different layers of the software architecture make the system modular. Different autopilots and simulators can be used. The software architecture is split into four main layers, as depicted in Figure 5.4. In the upper half is the developed UAS path and trajectory follower, which has been packaged as a ROS node to facilitate experimentation and integration, and is built on top of UAL. The lower half of the software architecture is composed by 86 4D Trajectory Based Operation Follower the autopilot, simulators, and communication drivers. The UAL provides a back-end that works with MAVROS2which is in charge of providing a communication driver to ROS for various autopilots that uses MAVLink MAVLink (2013) as communication protocol. MAVROS is the ROS adaptation of MAVLink protocol. The simulator used in these developments is based on the PX4 SITL development which is the official SITL environment for the Pixhawk autopilot Meier et al. (2011). UAL has implemented others back-end which provides communications with Crazyflie, Airsim, Ardupilot or DJI protocols. The developed trajectory follower includes two modes: following the trajectory without changing the yaw or aiming at the virtual point. The proposed module is under continuously development and publicly available in a stable version along with examples and a guide of how to use it. It can be found in the GitHub repository called UPAT Follower3under the MIT License. 5.5 Validation results This section presents different results using the proposed system and a hexacopter as an aerial platform. We ran in simulation large missions and we tested short real experiments inside our indoor testbed to see the scalability of the proposed module. The difference between a large and a short mission is the distance between waypoints. 5.5.1 Simulation results Our module was tested using GAZEBO, the PX4 SITL functionality to simulate the autopilot, and UAL to interact with simulated UAS. This simulation environment allows running and trying different tests without flying a real UAS using the same software. We tested a large mission with different velocities between segments, to achieve that the mission should have different times to travel every segment. Table 5.1 shows the initial waypoint list and the reference time tdof each waypoint. It also shows at which time trthe simulated UAS reached every waypoint. The mission is feasible for 2https://wiki.ros.org/mavros 3https://github.com/hecperleo/upat_follower 5.5 Validation results 87 the simulated UAS which has in this case a maximum velocity of 4 m/s. Figure 5.5a has different scales of axes to appreciate the error between trajectories. Moreover, how the trajectory follower caps the commanded velocity to the maximum velocity in the first seconds is shown in Figure 5.5b. On the other hand, Figure 5.5d details how the difference between the UAS actual time and the reference time is, if it is negative, the UAS is behind of the schedule, otherwise the UAS is ahead of schedule. The proposed system always tries to make the time difference equal to zero. It also tries to minimize the normal distance between the UAS and the trajectory. Figure 5.5c presents how the UAS after reaching a waypoint moves away by inertia, but recovers while following the next segment of the trajectory. Those errors that the system tries to minimize are shown in Table 5.2, and it is worth to mention that the farthest behind the schedule was 0.830 seconds and the farthest ahead schedule was 0.625 seconds. Table 5.1: Simulated large mission w1w2w3w4w5w6w7w8 x(m) 40.0 -40.0 -40.0 40.0 40.0 -40.0 -40.0 40.0 y(m) 30.0 30.0 -30.0 -30.0 30.0 30.0 -30.0 -30.0 z(m) 2.0 2.0 2.0 2.0 10.0 10.0 10.0 10.0 td(s) 0.0 28.3 66.4 95.0 133.1 161.7 204.6 247.4 tr(s) 0.0 28.4 66.2 95.1 132.9 161.9 204.4 247.3 Table 5.2: Simulated large mission errors Error Min Mean Max Std Var∗ Space J1(m) 0.007 0.188 1.02 0.195 0.038 Time J2(s) 0.000 0.086 0.830 0.100 0.010 ∗Variance units are squared. 5.5.2 Real experiments The real experiment is scaled with respect to the simulated due to the limited volume available inside our OptiTrack testbed, which is located the Aerial Robotics Laboratory of the University of Seville, see Figure 5.6. It is equipped with an overhead 88 4D Trajectory Based Operation Follower (a) (b) (c) (d) Figure 5.5: Simulated experiment. (a) Three dimensional view of the initial waypoints, the trajectory generated and the trajectory described. (b) reference velocity and current velocity of the UAS. (c) Normal distance between the UAS and the generated trajectory. (d) Difference between the reference time and the current time. motion capture system which tracks the 6 degrees of freedom pose of one or more objects. Each object tracked needs to be defined as a rigid body, which is a cluster of reflective markers arranged in a unique configuration for each object. A computer processes the motion capture data, matches it to one predefined rigid body of the UAS, and transmits the pose to the aerial platform at a reference frequency, in this case at 30 Hz to replicate the frequency at which a global position system used outdoors would send information. The aerial platform used for the real experiment is a DJI F550 hexacopter, see Figure 5.7. It has an on-board computer Intel NUC5i7RYH with 16 GB RAM and 5.5 Validation results 89 Figure 5.6: OptiTrack Testbed a 256 GB Samsung 950 PRO M.2 SSD hard disk. The on-board computer can be connected to the Pixhawk autopilot through a serial or USB port. It uses two independent 4S 5500 mAh batteries, one for the motors and autopilot, and the other for the on-board computer. This configuration allows the developer to keep the computer turned on between experiments, to modify the code, or to check or download data, even if the battery for the motors and autopilot is low and needs to be replaced. Figure 5.7: DJI F500 Hexacopter used in the flight tests 90 4D Trajectory Based Operation Follower The real experiment is scaled with respect to the simulated one and the UAS should go at different speeds through the segments. Table 5.3 shows the initial waypoint list and the reference times and the reached times. Figure 5.8 shows the results of the real experiment, where the real UAS has a similar behaviour comparing it with the simulated one. A video of the experiment is publicly available4. The proposed module tries to minimize online the normal distance error and the time error through the trajectory, see Table 5.4. It is worth to mention that the farthest behind schedule was 0.487 seconds and the farthest ahead schedule was 0.346 seconds. (a) (b) (c) (d) Figure 5.8: Real experiment inside the OptiTrack Testbed. (a) Three dimensional view of the initial waypoints, the trajectory generated and the trajectory described. (b) reference velocity and current velocity of the UAS. (c) Normal distance between the UAS and the generated trajectory. (d) Difference between the reference time and the current time. 4https://youtu.be/Yv-gHy4_PVs 5.5 Validation results 91 Table 5.3: Real scaled mission results w1w2w3w4w5w6w7w8 x(m) 4.0 -4.0 -4.0 4.0 4.0 -4.0 -4.0 4.0 y(m) 3.0 3.0 -3.0 -3.0 3.0 3.0 -3.0 -3.0 z(m) 1.0 1.0 1.0 1.0 2.0 2.0 2.0 2.0 td(s) 0.0 14.0 30.0 42.0 58.0 70.0 88.0 106.0 tr(s) 0.0 14.0 29.8 42.0 57.8 69.9 87.8 105.6 Table 5.4: Real scaled mission errors Error Min Mean Max Std Var∗ Space J1(m) 0.001 0.039 0.141 0.026 0.001 Time J2(s) 0.000 0.071 0.487 0.054 0.003 ∗Variance units are squared. 5.5.3 Comparison between methods This subsection analyzes a version of the proposed system without using Algorithm 2, method 1, and another version that uses this algorithm, method 2. We tested in simulation a feasible mission using 4 m/s as vmax, and we simulated it three more times lowering its maximum velocity but without modifying the initial 4D waypoint list W, see Table 5.1. By doing that, there is a point where a feasible segment becomes infeasible because of the maximum velocity reduction. Figure 5.9 shows the result of equations 5.2 and 5.3 on the simulations. It also shows the values using the absolute value of the errors, but in these cases, where the reference velocity matches the maximum velocity, the UAS is mostly behind schedule. Figure 5.9: Mean and standard deviation of error J1and error J2with the same initial 4D waypoint list on different simulations modifying the maximum velocity on each experiment. 98 Experiments partner involved was IRI7, and they were in charge of checking the health of the GNSS signal, converting the telemetry to the Message Queuing Telemetry Transport (MQTT) protocol and sending it through 4G communication. Finally, SATWAYS developed the RPS client application and the server for the communication of the components via Internet, see Figure 6.2. Figure 6.2: Graphical user interface developed by SATWAYS running on the RPS Client Application. Our UTM was connected via Internet with EVERIS to carry out the experiments, they sent us in real time the telemetry of each active UAS processed by IRI, and, if any conflict or threat appeared, we communicated back with EVERIS proposing to the operators an alternative route to follow and to avoid the potential conflict. This communication was done exchanging JavaScript Object Notation messages between our UTM and each UAS RPS, and it was done using the MQTT protocol. We tried to replicate a real U-space environment using Internet as our communication medium, not being necessary to have the UTM computer in the same network of the RPS computers. 7https://www.iri.upc.edu/ 6.1 UTM experiments 99 Aircraft used During the experiments, we used three UAS: Matrice 600 Pro, Atlantic I and Scrab II. These aircraft are quite different from each other, first we had one quadrotor and two fixed wings, therefore they have different maneuveravility and different autopilots. Moreover, there is a large gap between the maximum velocity between each UAS and the cruising velocity. These characteristics have to be taken into account to define useful scenarios to test U-space services. For example, if the Scrab II is flying at 200 km/h, the UTM detects a conflict with this aircraft and the UTM creates a geofence in the position of the Scrab II, every second delayed will result in a 28-meter error. This is an unfavourable case, but it shows how accurate the whole system must be to avoid errors. The characteristics of the UAS involved in the experiments done in the project GAUSS are summarized in Table 6.1. Table 6.1: Summary of the characteristics of each aircraft used. Characteristic M600 Atlantic I Scrab II MTOM (kg) 15 50 90 Payload (kg) 5 5 10 Autonomy (min) 15 60 300 Range (km) 3 100 100 Maximum speed (m/s) 18 48 120 Cruising speed (m/s) - 30 60 Wingspan (m) - 3.8 2.5 Length (m) 1.2 2.8 2.9 The DJI Matrice 600 Pro (M600), is intended for professional aerial photography and industrial applications, see Figure 6.3. It inherits everything from the previous version of the M600, but with increased flight performance and loading capacity. The system’s modular architecture makes it simple to mount additional modules, while preinstalled arms and antennae save setup time. The A3 Pro flying controller, Lightbridge 2 HD communication system, Intelligent Batteries, and Battery Management system are among the newest DJI technologies used in the airframe. The M600 is excellent for professional aerial photography and industrial applications since it is 100 Experiments natively compatible with several Zenmuse cameras and gimbals and has complete integration with third-party software and hardware. Figure 6.3: DJI Matrice 600 Pro The Atlantic is an UAS composed completely of composite materials that is intended for quick operational response, see Figure 6.4. Only two people are required to operate it on a mission, whether it is taking off from a runway or launching from a catapult, due to its simplicity and reliability. The Atlantic follows the flight plan autonomously and automatically, and features a parachute recovery mechanism in case of an emergency. Platform, ground station, and weather resistant laptop with command and control software make up the entire system. The Atlantic is a particularly adaptable unit since it can carry a wide range of payloads, such as EO/IR sensors, radio and radar equipment. Figure 6.4: Left, the Atlantic I. Right, the Scrab II. 6.1 UTM experiments 101 Figure 6.4 shows the Scrab II, a target UAS propelled by twin turbines. It has been developed and engineered to deliver great performance while keeping the operating and maintenance operations as simple as possible. Its propulsion consists of two turbines that are controlled by the onboard electronics of the target aircraft. The great flying capabilities of the Scrab II are owed to the power of the configuration, which allows it to attain speeds of up to 120 m/s. Its easy functioning, on the other hand, makes it a multifunctional target that may be utilized in a variety of settings. Moreover, the internal components of the aircraft are shielded, this includes for offshore exercises. Finally, the communications of the target UAS, which can reach radio connection lengths of up to 100 kilometers, are extremely reliable. 6.1.2 Scenario definition This section details the order of the operations carried out in the field experiments as well as which conflicts have been forced to be resolved later. We conducted experiments in two different test flight centers, the first one was in ATLAS, and the aim was to test the land scenarios of the project. The second one was in El Arenosillo and the main purpose was testing the whole system in a marine scenario with fast aircraft. ATLAS The first one was in the Test Flight Center ATLAS8(Air Traffic Laboratory for Advanced unmanned System) located in Jaen, Spain. It offers an aerodrome equipped with scientific facilities and airspace ideally suited to the development of experimental flights with UAS, see Figure 6.5. In addition to the facilities, ATLAS has a segregated airspace9that has an extension of 1000 km2, which is an incredible advantage to do experimental flight saving time in terms of bureaucracy that should be done when not having a segregated airspace. In these experiments, the aircraft used are the M600 8http://atlascenter.aero/en/atlas_aa23.html 9http://atlascenter.aero/en/espacio-aereo_aa7.html 102 Experiments and the Atlantic I, detailed in Section 6.1.1. Due to safety reasons, the Atlantic was allowed to fly at a minimum of 400 meters above the ground. This limited us to create two operations that get in conflict by losing its safety distance, thus we were forced to increase the parameters involved in the detection of the loss of separation conflict. The rest of the conflicts were not customized to get a proper demonstration of the UTM developed. Figure 6.5: Test Flight Center Air Traffic Laboratory for Advanced unmanned System located in Jaen, Spain. The three scenarios done in ATLAS are depicted in Figure 6.6, and the following paragraphs detail which conflicts appeared and how the UTM solves them. Table 6.2 summarizes the characteristics of the operations done in ATLAS. The first scenario carried out in ATLAS was composed by operations 1 and 2, see Figure 6.6a. Operation 1 was an agriculture inspection done by the M600, while operation 2 was a forest inspection done by the Atlantic. Due to the minimum flight altitude of the Atlantic, we could have flown the M600 at a higher altitude, however we decided to keep it at a comfortable altitude for the safety pilot. It also allowed us to see the M600 without binoculars following the alternative flight plan given by the UTM to avoid the loss of separation conflict. In this case, the difference of altitude between UAS were 350 meters, and operation 1 started 16 seconds after operation 2 to be able to make the two UAS coincide in the same latitude and longitude. The alternative flight plan given to the M600 was equal to the one that was previously accepted, but decreasing its height at the last segment of the flight plan, this way the loss of separation conflict were avoided modifying the altitude of the M600. It was the M600 one that modified its flight plan due to the priority of the UAS. Quadrotors are 6.1 UTM experiments 103 often given lower priority than fixed wings because they have more maneuverability. An exception can be an emergency operation carried out by a quadrotor, for example, delivering rescue and medical supplies to an injured person in the forest. Table 6.2: Summary of all operations done in ATLAS. UAS Name Description Potential threat Speed (m/s) Altitude (m) M600 Op 1 Agriculture inspection Loss of separation 3.3 70 Op 3 Windturbine inspection Geofence intrusion 1.0 30 - 90 Op 5 Event monitoring Jamming 3.3 70 Atlantic Op 2 Forest inspection Loss of separation 15 600 Op 4 Powerline inspection Geofence conflict 15 420 Figure 6.6b shows the second scenario tested in ATLAS, and it was formed by operation 3, which was a windturbine inspection done by the M600. In this case, the difference of altitude imposed by the minimum height of the Atlantic and the difference of the start time of the operations did not matter as much as in the first scenario. This scenario was created to test how the firefighters can interact with the UTM, how it creates geofences in the commanded place, and how the system gives the operator an alternative flight plan to leave as soon as possible the conflictive geofence. To carry out these tests, both UAS started their operations and, suddenly, we simulated the interaction of the firefighters telling the UTM that a wildfire has appeared, and thus the utm created a geofence in the commanded place with the given radius. After the geofence generation, the M600 was inside that geofence, in such a way that the UTM detected a geofence intrusion and sent a notification to the operator in charge of operation 3 telling him to leave the geofence as soon as possible. The third scenario tested in ATLAS can be seen in Figure 6.6c, and it was formed by operations 4 and 5. In this case, operation 4 was a powerline inspection done by the Atlantic and operation 5 was an event monitoring done by the M600. This 104 Experiments scenario was created to test two different threats: the first one was to test the jamming attack on an UAS and see how the UTM acted, the second one was to test a geofence conflict. In this scenario, both UAS started its respective operations and followed its flight plans, suddenly, we simulated a jamming attack on the M600, the UTM sent a notification to the operator in charge of the M600 telling him to land it as soon as possible because of the jamming attack. Therefore, a geofence was created by the UTM to prevent other UAS flying near the jamming zone, and this geofence intersected with the flight plan of operation 4, thus the UTM detects a geofence conflict. To solve this potential threat, the UTM sent a notification to the operator in charge of operation 5, telling him that the flight plan of the Atlantic is intersecting with a geofence and proposing an alternative flight plan to avoid it. El Arenosillo The second field experiments were carried out in the testing center of El Arenosillo10 (CEDEA) located in Huelva, Spain. It was a sounding rocket base, but nowadays, it is active in other National Institute of Aerospace Technology11 (INTA) and Ministry of Defense programmes, mainly atmospheric studies and tests of unmanned aircraft. This test center has been used by the military to make shooting tests with UAS like the Scrab described in Section 6.1.1. Figure 6.8 shows three marine scenarios tested in El Arenosillo, and the following paragraphs detail which conflicts appeared and how the UTM solves them. Table 6.3 summarizes the characteristics of the operations done in El Arenosillo. The first marine scenario carried out in El Arenosillo was composed by operations 1 and 2, see Figure 6.8a. Both operations were marine inspections, operation 1 was done by the Atlantic, while operation 2 was done by the Scrab. In this marine scenario, the minimum altitude limitation was the same presented in ATLAS, thus the Atlantic had to fly above 400 meters. In addition to that, the Scrab had also the requisite to fly above that height, therefore we decided to fly the Scrab at 700 meters and the Atlantic at 500 meters of altitude, letting a safety distance between UAS of 10https://www.inta.es/INTA/en/quienes-somos/historia/el-arenosillo/ 11https://www.inta.es/INTA/en/quienes-somos/ 6.1 UTM experiments 105 (a) (b) (c) Figure 6.6: Three scenarios defined in order to solve potential conflicts. (a) Conflict between M600 and Atlantic due to loss of safety distance. (b) Firefighters warn about a wildfire, M600 appears inside the created geofence. (c) M600 suffers jamming, the created geofence intersects with the Atlantic. 106 Experiments Figure 6.7: El Arenosillo Testing Center (CEDEA) located in Huelva, Spain. Table 6.3: Summary of all operations done in El Arenosillo. UAS Name Description Potential threat Speed (m/s) Altitude (m) Atlantic Op 1 Marine inspection Loss of separation 22 500 Op 3 Transition to next operation Geogence conflict 22 500 Op 4 Beach monitoring Geofence intrusion 22 500 Scrab Op 2 Marine inspection Loss of separation and Jamming 55 700 6.1 UTM experiments 107 200 meters. To match both aircraft in the same longitude and latitude, operation 2 started 750 seconds after operation 1, since this allowed us to force a loss of separation conflict. The alternative flight plan given to the Atlantic was not equal to the one that was previously accepted, and decreasing its altitude in El Arenosillo, the UAS could not cross in the airspace, and thus the alternative flight plan given to the Atlantic was a safe spot in the airspace. It was the M600 one that modified its flight plan due to the priority of the UAS. In this case, the Scrab had more maneuverability, however we had only 30 minutes of effective fly due to its autonomy, thus the alternative flight plans were given to the Atlantic. We had to manage these 30 minutes of effective fly per day of the Scarb, therefore we decided to schedule the operations of the Atlantic to generate potential conflicts with the one and only operation of the Scrab. This is one of the reasons of having a safe spot as an alternative flight plan to avoid the loss of separation conflict, and it allowed us to confirm the detection of the conflict and continue right away with the next operation wasting as little time as possible. Figure 6.8b shows the second scenario tested in El Arenosillo, and it was formed by operations 2 and 3, which was a marine inspection done by the Scrab and a transition to another operation done by the Atlantic respectively. In this case, the difference of height imposed on the aircraft for safety reasons did not matter as much as in the first scenario. In terms of timing, the Scrab started its operation in the previous scenario and did not finish, but the Atlantic started operation 3 when the Scrab was in its antepenultimate segment of the flight plan. This scenario was created to test two things: the first one was to test the jamming attack on the Scrab and see how the UTM acted, the second one was to test a geofence conflict. In this scenario, both UAS followed their respective flight plans and, suddenly, we simulated a jamming attack on the Scrab, the UTM sent a notification to the operator in charge of the Scrab telling him to land it as soon as possible because of the jamming attack. Therefore, a geofence was created by the UTM to prevent other UAS flying near the jamming zone, and this geofence intersected with the flight plan of operation 3, thus the UTM detects a geofence conflict. To solve this potential threat, the UTM sent a notification to the operator in charge of operation 3, telling him that the flight plan of the Atlantic is intersecting with a geofence and proposing an alternative flight plan to avoid it. All 114 Experiments Figure 6.11: Second real experiment carried out in ATLAS visualized using RViz. View of the geofence intrusion conflict between the operation 3 done by the M600 (orange) and the geofence (red) created due to the warning of a wildfire by the firefighters. Figure 6.12: Second real experiment carried out in ATLAS visualized using RViz. View of the alternative flight plan accepted by the M600 operator to avoid the geofence intrusion conflict between the operation 3 done by the M600 (orange) and the geofence (red) created due to the warning of a wildfire by the firefighters. 6.1 UTM experiments 115 The last scenario tested in ATLAS involved operation 4 done by the M600 at 3.3 m/s and operation 5 done by the Atlantic at 15 m/s. Here we tested a jamming attack on an UAS, and a geofence conflict produced by the geofence created to protect other UAS from the jamming attack. In this case, while both aircraft were doing their operations, we simulated a jamming attack on the M600, therefore a geofence was created in the Database in 3.5 milliseconds by the UTM. This geofence intersected with the flight plan of the Atlantic, see Figure 6.13, and it took Monitoring 0.18 seconds to detect the geofence conflict. The procedure after this is the same presented in the previous scenarios, thus Table 6.6 summarizes the timing of the events of this scenario. The UTM was able to detect, compute multiple solutions, and propose to the operator an alternative flight plan in 3.9 seconds. The solution accepted by the operator can be seen in Figure 6.14. There is a difference of the geofence color between the two figures presented in this scenario, because the system has the ability to distinguish between active (red) and nonactive (yellow) geofences. The geofences are 3D shapes plus the temporal dimension, thus the airspace can be optimized. Figure 6.13: Third real experiment carried out in ATLAS visualized using RViz. View of the geofence conflict between the operation 4 done by the Atlantic (green) and the geofence (yellow) created due to the warning of a jamming attack, which was received by the operation 5 carried out by the M600 (orange). 116 Experiments Figure 6.14: Third real experiment carried out in ATLAS visualized using RViz. Top view of the alternative flight plan accepted by the Atlantic operator to avoid the geofence conflict between the operation 4 carried out by the Atlantic (green) and the geofence (red) created due to the warning of a jamming attack. Table 6.6: Timeline of geofence conflict in ATLAS, third experiment. 0.0s ···• Atlantic starts operation 4. 31.34s ···• M600 starts operation 5. 95.15s ···• M600 receives a jamming attack. 95.16s ···• Emergency Management creates a geofence. 96.85s ···• Monitoring detects the geofence conflict. 96.99s ···• Tactical Deconfliction calculates the alternative flight plans. 97.82s ···• Emergency Management chooses an alternative flight plan. 98.85s ···• U-space Service Manager suggests landing the M600. 98.85s ···• U-space Service Manager suggests the alternative flight plan. 110.1s ···• M600 operator accepts and decides to land the M600. 123.8s ···• Atlantic operator accepts and loads the new flight plan. 482.2s ···• Atlantic finishes its operation. 6.1 UTM experiments 117 El Arenosillo Due to the limitations presented in the Flight Test Center El Arenosillo, where the autonomy of the Scrab was the largest one, we decided to schedule the operations in such a way that the Scrab did one operation while the Atlantic did multiple ones to force different potential conflicts. For this reason, Table 6.3 has just one operation done by the Scrab and three done by the Atlantic. Figure 6.8 has a visual representation of the scenarios and the potential conflicts forced. In the marine scenarios, the Atlantic kept the minimum altitude limitation presented in the experiments carried out in ATLAS, thus the operations done by the Atlantic had an altitude of 500 meters, while the Scrab flew at 700 meters, letting a safety distance between them of 200 meters at the closest point. The flight plans were influenced by another requirement presented in El Arenosillo, which was that UAS could not cross each other in the airspace, no matter at what altitude were the aircraft flying. This influenced the way alternative flight plans were proposed, the procedure of aborting operations if needed, and it limited the airspace given to carry out the experiments. The first marine scenario carried out in El Arenosillo was composed by operation 1 done by the Atlantic at 22 m/s and operation 2 done by the Scrab at 55 m/s. To match both aircraft in the same longitude and latitude, operation 2 started 750 seconds after operation 1, since this allowed us to force a loss of separation conflict, see Figure 6.15. The requirement of not crossing UAS in the airspace was not violated because they never did. The Monitoring module, using the estimated trajectory, detected the conflict before the aircraft crossed with each other, and it took 0.17 milliseconds to detect the conflict. Due to the requirement of not crossing, the alternative flight plan given to the Atlantic was completely different to the accepted flight plan, see Figure 6.16. The solution proposed was a safe spot in the airspace to avoid having the aircraft crossing each other, and taking into account the rest of the experiments since the Scrab has only 30 minutes of autonomy assigned to run operations. The second scenario tested in El Arenosillo involved operation 2 done by the Scrab at 55 m/s and operation 3 done by the Atlantic at 22 m/s. Here we tested a jamming attack on an UAS, and a geofence conflict produced by the geofence created to protect other UAS from the jamming attack. In this case, while both aircraft were doing their 118 Experiments Figure 6.15: First real experiment carried out in El Arenosillo visualized using RViz. Top view of the loss of separation conflict between the operation 1 done by the Atlantic (green) and the operation 2 done by the Scrab (orange). Figure 6.16: First real experiment carried out in El Arenosillo visualized using RViz. Side view of the alternative flight plan accepted by the Atlantic operator to avoid the loss of separation conflict between the operation 1 done by the Atlantic (green) and the operation 2 done by the Scrab (orange). 6.1 UTM experiments 119 operations, we simulated a jamming attack on the Atlantic, therefore a geofence was created in the UTM. This geofence intersected with the flight plan of the Scrab, see Figure 6.17, and the Monitoring module spent 0.18 milliseconds to detect the geofence conflict. The procedure after this is the same as the one presented in the previous scenarios. The UTM was able to detect, compute multiple solutions, and propose to the operator an alternative flight plan in 3.8 seconds. The solution accepted by the operator can be seen in Figure 6.18. After avoiding the potential conflict, the Atlantic finished its operation 3 and went to start the last operation of the experiments. On the other hand, the Scrab finished operation 2 and went to its landing spot to start the landing maneuver using a parachute. Figure 6.17: Second real experiment carried out in El Arenosillo visualized using RViz. Top view of the geofence conflict between the operation 3 done by the Atlantic (green) and the geofence (red) created due to the warning of a jamming attack, which was received by the operation 2 carried out by the Scrab (orange). The geofence intrusion was the last conflict tested in El Arenosillo, which appears if an UAS is inside an active geofence. The operation 4 carried out by the Atlantic at 22 m/s was a rectangle, thus the operation simulated a beach monitoring. In this scenario, we simulated the interaction between the UTM and the firefighters, which were the ones that warned the UTM of a wildfire in a certain area. It took 39.1 milliseconds between the firefighters warned the UTM and a geofence was created in the Database. Figure 6.19 shows part of the operation inside the geofence: the 120 Experiments Figure 6.18: Second real experiment carried out in El Arenosillo visualized using RViz. Top view of the alternative flight plan accepted by the Atlantic operator to avoid the geofence conflict between the operation 3 carried out by the Atlantic (green) and the geofence (red) created due to the warning of a jamming attack. Atlantic was at this moment at this part, thus the geofence intrusion was detected by the Monitoring module in 0.19 milliseconds. The procedure is the same as the last scenario presented: Monitoring warned the Emergency Management module, and this one asked for support to the Tactical Deconfliction module, which calculated a list of alternative flight plans. Tactical Deconfliction spent 0.4 milliseconds computing the list and Emergency Management spent 0.31 seconds deciding which one was proposed to the operator. In this case, the alternative flight plan proposed was a straight line to a landing spot. Therefore, the suggestion went from the Emergency Management through the USM module to the operator in 3.9 milliseconds. The operator spent 13 seconds deciding to accept or decline the alternative flight plan suggested, and when accepted, the new flight plan was stored in the Database in 0.5 seconds. Figure 6.20 shows the alternative flight plan accepted by the operator and the one that the Atlantic followed to finish its operation. Finally, a timeline is presented in Table 6.7 detailing the events of the experiments carried out in El Arenosillo. Unlike in the case of the experiments carried out in ATLAS, the marine scenarios were designed to be done using one take off of both aircraft, due to the autonomy limitation of the Scrab. This resulted in experiments 6.1 UTM experiments 121 Figure 6.19: Third real experiment carried out in El Arenosillo visualized using RViz. View of the geofence intrusion conflict between the operation 4 done by the Atlantic (green) and the geofence (red) created due to the warning of a wildfire by the firefighters. Figure 6.20: Third real experiment carried out in El Arenosillo visualized using RViz. View of the alternative flight plan accepted by the Atlantic operator to avoid the geofence intrusion conflict between the operation 4 done by the Atlantic (green) and the geofence (red) created due to the warning of a wildfire by the firefighters. 122 Experiments with chained operations, i.e. the last point of the first operation of the Atlantic is the start point of its second operation, and the last point of the second operation is the first point of the third operation. Chaining operations allowed us to lose the minimum time possible between operations and we were able to repeat a segment if an operation was aborted due to any unexpected problem. The timeline summarizes the order of the events presented during all experiments carried out in El Arenosillo, where three conflicts were forced to be later detected and resolved, which are differentiated in the timeline by a time jump. The time of each event is referred to the start of operation 2 carried out by the Scrab. 6.1.4 Comparison between methods This section presents a comparison between two approaches that solve the same problem: how to detect and solve conflicts between 4D UAS trajectories. The method chosen for this Thesis is detailed in Chapter 4 and is the one that can be scaled without problems, and therefore it is the final solution. Before that, a brute force method was developed in the first place to be able to make tests quickly in the field, a method that does not need to set up parameters to work properly, see Appendix A for more details. A brute force method was not a problem knowing that no more than five UAS were going to be tested simultaneously in the field experiments. A significant number of simulations were run to assess the effectiveness of the algorithm implemented in the Monitoring module in relation to the number of UAS and the size of the planned trajectories, with the latter being proportional to the number of waypoints for each trajectory. Each simulation creates a scenario consisting of a certain number of straight trajectories between two random waypoints in a rectangular prism with predetermined spatial dimensions XY Z and a predetermined time horizon T. Then, using the discretized based method detailed in Chapter 4 and the appropriate time and iterations, each scenario is analyzed. Additionally, each situation is assessed using the brute force approach presented in Appendix A to compare the time and iterations required and check whether they provide the same results. 6.1 UTM experiments 123 Table 6.7: Timeline of all experiments carried out in El Arenosillo 0.0s ···• Atlantic starts operation 1. 693s ···• Scrab starts operation 2. 693s ···• Monitoring detects the loss of separation. 693s ···• Tactical Deconfliction calculates the alternative flight plans. 694s ···• Emergency Management chooses an alternative flight plan. 694s ···• U-space Service Manager suggests the alternative flight plan. 711s ···• Atlantic operator accepts and loads the new flight plan. 712s ···• Atlantic starts its new flight plan. 1076 ···• Atlantic finishes its operation. . . . 1256s ···• Atlantic starts operation 3. 1368s ···• Scrab receives a jamming attack, so UTM creates a geofence. 1368s ···• Monitoring detects the geofence intrusion. 1368s ···• Tactical Deconfliction calculates the alternative flight plans. 1369s ···• Emergency Management chooses an alternative flight plan. 1370s ···• USM suggests landing the Scrab and new plan to Atlantic. 1391s ···• Scrab operator accepts and decides to land the Scrab. 1394s ···• Atlantic operator accepts and loads the new flight plan. 1395s ···• Atlantic starts its new flight plan. 1616s ···• Atlantic finishes its operation. . . . 1796s ···• Atlantic starts operation 4. 1976s ···• Firefighters warn about a wildfire in the area. 1977s ···• Emergency Management creates a geofence. 1977s ···• Monitoring detects the geofence intrusion. 1978s ···• Tactical Deconfliction calculates the alternative flight plans. 1978s ···• Emergency Management chooses an alternative flight plan. 1978s ···• U-space Service Manager suggests the alternative flight plan. 1994s ···• Atlantic operator accepts and loads the new flight plan. 1996s ···• Atlantic starts its new flight plan. 2141s ···• Atlantic finishes its operation.