The key concept for safe and efficient traffic management for Unmanned Aircraft Systems (UAS) is the notion of operation volume (OV). An OV is a 4-dimensional block of airspace and time, which can express an aircraft’s intent, and can be used for planning, de-confliction, and traffic management. While there are several high-level simulators for UAS Traffic Management (UTM), we are lacking a frame- work for creating, manipulating, and reasoning about OVs for heterogeneous air vehicles. In this paper, we address this and present SkyTrakx—a software toolkit for simulation and verification of UTM scenarios based on OVs. First, we illustrate a use case of SkyTrakx by presenting a specific air traffic coordination protocol. This protocol communicates OVs between participating aircraft and an airspace manager for traffic routing. We show how existing formal verification tools, Dafny and Dione, can assist in automatically checking key properties of the protocol. Second, we show how the OVs can be computed for heterogeneous air vehicles like quadcopters and fixed-wing aircraft using another verification technique, namely reachability analysis. Finally, we show that SkyTrakx can be used to simulate complex scenarios involving heterogeneous vehicles, for testing and performance evaluation in terms of workload and response delays analysis. Our experiments delineate the trade-off between performance and workload across different strategies for generating OVs.
more »
« less
Strategic Deconfliction of Unmanned Aircraft Based on Hexagonal Tessellation and Integer Programming
Unmanned aircraft systems service suppliers adhere to interoperability standards that require unmanned aircraft operators to submit an operational intent, which describes the planned flight path in four-dimensional space. To ensure fairness, the central database follows a first-come, first-served approach, accepting new operational intents as long as they do not conflict with any active ones. However, creating a viable operational intent is challenging due to moving obstacles. This paper introduces an innovative optimization-based procedure to automate the intent filing process. It utilizes a stacked hexagonal tessellation to model the airspace, offering adjustable granularity. Path finding is accomplished using integer programming on the hex grid. The integer program is solved on a grid canvas that includes only necessary cells, striking a balance between computational efficiency and optimality. Simulation experiments demonstrate the procedure’s effectiveness in generating feasible trajectories, even in scenarios with dense, omnidirectional air traffic. This procedure has the potential to become the foundational software core for low-altitude air traffic management systems, providing strategic deconfliction and constraint management services.
more »
« less
- Award ID(s):
- 1944068
- PAR ID:
- 10513815
- Publisher / Repository:
- American Institute of Aeronautics and Astronautics
- Date Published:
- Journal Name:
- Journal of Guidance, Control, and Dynamics
- Volume:
- 46
- Issue:
- 12
- ISSN:
- 0731-5090
- Page Range / eLocation ID:
- 2362 to 2372
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Urban Air Mobility, the scenario where hundreds of manned and Unmanned Aircraft Systems (UASs) carry out a wide variety of missions (e.g., moving humans and goods within the city), is gaining acceptance as a transportation solution of the future. One of the key requirements for this to happen is safely managing the air traffic in these urban airspaces. Due to the expected density of the airspace, this requires fast autonomous solutions that can be deployed online. We propose Learning-‘N-Flying (LNF), a multi-UAS Collision Avoidance (CA) framework. It is decentralized, works on the fly, and allows autonomous Unmanned Aircraft System (UAS)s managed by different operators to safely carry out complex missions, represented using Signal Temporal Logic, in a shared airspace. We initially formulate the problem of predictive collision avoidance for two UASs as a mixed-integer linear program, and show that it is intractable to solve online. Instead, we first develop Learning-to-Fly (L2F) by combining (1) learning-based decision-making and (2) decentralized convex optimization-based control. LNF extends L2F to cases where there are more than two UASs on a collision path. Through extensive simulations, we show that our method can run online (computation time in the order of milliseconds) and under certain assumptions has failure rates of less than 1% in the worst case, improving to near 0% in more relaxed operations. We show the applicability of our scheme to a wide variety of settings through multiple case studies.more » « less
-
null (Ed.)With increasing urban population, there is global interest in Urban Air Mobility (UAM), where hundreds of autonomous Unmanned Aircraft Systems (UAS) execute missions in the airspace above cities. Unlike traditional human-inthe-loop air traffic management, UAM requires decentralized autonomous approaches that scale for an order of magnitude higher aircraft densities and are applicable to urban settings. We present Learning-to-Fly (L2F), a decentralized on-demand airborne collision avoidance framework for multiple UAS that allows them to independently plan and safely execute missions with spatial, temporal and reactive objectives expressed using Signal Temporal Logic. We formulate the problem of predictively avoiding collisions between two UAS without violating mission objectives as a Mixed Integer Linear Program (MILP). This however is intractable to solve online. Instead, we develop L2F, a two-stage collision avoidance method that consists of: 1) a learning-based decision-making scheme and 2) a distributed, linear programming-based UAS control algorithm. Through extensive simulations, we show the real-time applicability of our method which is ≈6000× faster than the MILP approach and can resolve 100% of collisions when there is ample room to maneuver, and shows graceful degradation in performance otherwise. We also compare L2F to two other methods and demonstrate an implementation on quad-rotor robots.more » « less
-
Command and control (C2) data links over cellular networks is envisioned to be a reliable communications modality for various types of missions for Unmanned Aircraft System (UAS). The planning of UAS traffic and the provision of cellular communication resources are cross-coupled decisions that should be analyzed together to understand the quality of service such a modality can provide that meets business needs. The key to effective planning is the accurate estimation of communication link quality and the resource usage for a given air traffic requirement. In this work, a simulation and modelling framework is developed that integrates two open-source simulation platforms, Repast Simphony and ns-3, to generate UAS missions over different geographical areas and simulates the provision of 4G/5G cellular network connectivity to support their C2 and mission data links. To the best of our knowledge, this is the first simulator that co-simulates air traffic and cellular network communications for UAS while leveraging standardized 3GPP propagation models and incorporating detailed management of communication channels (i.e., resource blocks) at the cellular base station level. Three experiments were executed to demonstrate how the integrated simulation platform can be used to provide guidelines in communication resource allocation, air traffic management, and mission safety management in beyond visual line of sight (BVLOS) operations.more » « less
-
more » « less
Abstract Urban air mobility (UAM) is an emerging air transportation mode to alleviate the ground traffic burden and achieve zero direct aviation emissions. Due to the potential economic scaling effects, the UAM traffic flow is expected to increase dramatically once implemented, and its market can be substantially large. To be prepared for the era of UAM, we study the fair and risk‐averse urban air mobility resource allocation model (FairUAM) under passenger demand and airspace capacity uncertainties for fair, safe, and efficient aircraft operations. FairUAM is a two‐stage model, where the first stage is the aircraft resource allocation, and the second stage is to fairly and efficiently assign the ground and airspace delays to each aircraft provided the realization of random airspace capacities and passenger demand. We show that FairUAM is NP‐hard even when there is no delay assignment decision or no aircraft allocation decision. Thus, we recast FairUAM as a mixed‐integer linear program (MILP) and explore model properties and strengthen the model formulation by developing multiple families of valid inequalities. The stronger formulation allows us to develop a customized exact decomposition algorithm with both benders and L‐shaped cuts, which significantly outperforms the off‐the‐shelf solvers. Finally, we numerically demonstrate the effectiveness of the proposed method and draw managerial insights when applying FairUAM to a real‐world network.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.2514/1.G007459
