Autonomous Conflict Detection and Resolution for Unmanned Aerial Vehicles (2017)

In the last decade, the commercial values of Unmanned Aerial Vehicles (UAV), defined as devices that are capable of sustainable flights in the atmosphere that do not require to have a human (pilot) on-board, become widely recognized thanks to the advancement of technology in materials, sensors, computation, and telemetry. As UAVs are becoming cheaper and more user-friendly, many companies are motivated to incorporate them in their everyday business, such as for delivery services, journalisms, or providing Internet services.All of commercial prospective applications for UAVs, however, can only be achieved once the vehicles are fully integrated into the airspace system. This is not the case yet, since UAV operations, in most part of the world, are strictly regulated to fly only within the visual line of sight (VLOS) of the ground pilot, forbidding the otherwise beyond visual line of sight (BVLOS) flight. One main reason for such strict regulations is the apprehension about the safety of UAV operations, which are likely to be heterogeneous due to the possible large variation of UAVs in the airspace, each with their own preference on how to interact with other UAVs and with the current (manned) air traffic. Hence, airspace management, especially in the mitigation of mid-air conflicts and collisions, is expected to become much more complex, compromising the overall safety.Therefore, the problem of safe UAV integration into the airspace is the selected topic for this research, especially in the development of Conflict Detection and Resolution (CD&amp;R) systems. The particular system describes any procedures and devices for vehicles to mitigate potential mid-air conflicts and collisions. For a UAV, this system needs to consider a wide range of obstacles it might encounter, from a static unmoving object to other vehicles with completely different characteristics. Moreover, there can be interactions between two UAVs with different levels of CD&amp;R system awareness. Only when their CD&amp;R systems are fully defined and regulated to handle such diverse scenarios, can UAVs be fully integrated into the airspace.The main goal of this research is to define and evaluate systems for detecting and resolving possible mid-air conflicts of Unmanned Aerial Vehicles, specifically to support safe beyond visual line-of-sight operations in an integrated airspace. This goal is achieved by addressing the four research problems, i.e. the airspace incompatibility, the CD&amp;R diversity, the doubt on UAV safety, and the UAV autonomous CD&amp;R inadequacy. Directly from those problems, four research questions are formulated as follows:&gt;What structure can be defined to manage the CD&amp;R system for UAVs operating in an integrated airspace?&gt;How can the diverse UAV CD&amp;R approaches be classified into a comprehensive taxonomy that is compatible with the current airspace?&gt;How can the safety parameters of the integrated airspace, under influence of a heterogeneous CD&amp;R approaches, can be determined?&gt;How can an autonomous CD&amp;R system for UAVs be defined to handle potential conflicts, seeing the vehicle as part of the integrated traffic in the airspace?To address the first question, this research proposes a taxonomy of CD\\&amp;R approaches for UAV operating in an integrated airspace. Possible approaches for UAVs are surveyed and broken down based on their types of surveillance, coordination, maneuver, and autonomy. The factors are combined back into several `generic approaches’, for example, the Traffic Warningand Collision Avoidance System (TCAS) in manned flight can be seen as CD\\&amp;R that uses combination of \\textit{a distributed dependent surveillance, an explicit coordination, an escape maneuver, and conducted manually}. The approaches that fits the scheme of UAV integration are then selected methodically, resulting in a novel taxonomy of UAV CD\\&amp;R approaches.From the generic approaches in the taxonomy, a multi-layered architecture is developed in this research, managing CD\\&amp;R procedures in the airspace that are compatible with the manned flights, while also embracing those that are unique to UAVs'. The multi-layered feature means that instead of relying on only one CD\\&amp;R approach, UAVs can implement multiple approach in a fail-safe concept, ensuring that even in a case when one approach fails, there are still available layers that can prevent direct collisions. Six CD\\&amp;R approaches from the taxonomy are further selected as the safety layers, which included the layer of (1) Procedural, (2) Manual, (3) Cooperative, (4) Non-cooperative (5) Escape, and (6) Emergency approaches. A brief implementation of the multi-layered CD&amp;R architecture suggesting that it usage depends closely on the type of mission: in a particular mission some layers might become less necessary, while in others they might be important. The proposed architecture, however, is lacking definitions of physical thresholds between layers, such as the distance or time-to-collision, which need to be defined specifically for each type of UAV. This is warranted for the future work for UAVs air traffic management, but might only be truly be defined once the BVLOS flights of UAVs are allowed in the airspace.Answering the second research question, the previously proposed taxonomy is attributed to available CD&amp;R methods in the literature, in order to determine their fitness and whether they are complementary or interchangeable from one to another. A total of 64 CD&amp;R methods are evaluated, ranging from preflight calculations on deterministic maps, such as a Global Path Planning, to reactive avoidances with on-board sensors, such as by using the Velocity Obstacle method. Using the taxonomy, the position of each approaches in the overall safety management scheme, such as by using a multi-layered architecture, can be defined. The taxonomy attribution has shown that many of the available methods fall outside the taxonomy, and suggests the need to concentrate research more to parts where representative methods are lacking. On further evaluation, it also becomes apparent that the diversity of CD&amp;R preferences only existed within the walls of laboratories, due to the current UAV flight limitation to only within VLOS. Nevertheless, the taxonomy potentially can aid both developers and authorities in deciding an adequate CD&amp;R approach(es) to ensure safety of an upcoming BVLOS flight in an integrated airspace.The third question is addressed by setting up a series of Monte Carlo simulation to derive two safety parameters, i.e. the frequencies of near mid-air collisions (NMAC), and of mid-air collisions (MAC). The former represents how often two UAVs fly closer to each other than a certain thresholds, which is set to be 50 meters in most of the discussion in this dissertation, while the later describe the actual body-to-body collision between vehicles. The use of the Monte Carlo simulations is meant to overcome the limitation of available analytical methods in literature, by incorporating the effect of distributed CD\\&amp;R system, as well as the heterogeneous condition setup for the airspace. The method, however, has rarely been preferred in the safety parameter derivation, due to its significantly time-consuming process to obtain any meaningful results. This problem is addressed in this research by simulating in high-density setups, of which results are scaled down latter on, to more realistic densities of an airspace.Two CD&amp;R protocols are modeled in the simulations, first one is the cooperative protocol, where each vehicle conduct avoidance that is implicitly coordinated by common rules-of-the-air, and the second one is the non-cooperative protocol, where each vehicle avoids with preferences that are randomly given. A certain target level of safety (TLS) is defined as well in research, to measured the collective performance of the CD&amp;R systems, in which the frequency of NMACs and MACs should be lower than 10E-2 and 10E-7 per hour, respectively. Those values of TLS are proposed on the basis of the equivalent values in manned-flight history for the last decade.As the results, while maintaining the TLS of the airspace, the distributed cooperative CD&amp;R protocol is able to increase the maximum number of operating UAV in one flight level to almost ten times the number when no CD&amp;R is applied. This would mean that for a city like Chicago that has an area of more than five-thousand kilometer-square, a total of 45 UAVs can operate independently in one altitude. It is also concluded that a much better results are obtained while using the cooperative protocol, which justifies the necessity of order in the airspace, which in this case is the implementation of the Right-of-way rules.The usefulness of Monte Carlo simulations method is demonstrated in this research, testing various CD&amp;R algorithms and protocols in a vast number of possible conditions, including those that are previously unpredicted. The downside of the method still appears, however, in which it cannot derive any meaningful results for the frequency of MACs within the number of samples tested, due to the rareness of MACs even in a high-density setups. Hence, more samples are recommended for the future work, along with further extension to include aircraft dynamic model inside the simulations.The fourth question is addressed in this research by introducing two novel CD&amp;R algorithms which are adequate to fill in specific layers in the CD&amp;R architecture explained before. The first algorithm is the Selective Velocity Obstacle (SVO) method, an extension of the Velocity Obstacle method (VO-method) with additional criteria for implicit coordination. This CD&amp;R method is developed specifically for the Cooperative layer in t