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
Automated Playbook for UAV Traffic Management Based on Spatiotemporal Scenario Data
This paper develops a decision framework to automate the playbook for UAS traffic management (UTM) under uncertain environmental conditions based on spatiotemporal scenario data. Motivated by the traditional air traffic management (ATM) which uses the playbook to guide traffic using pre-validated routes under convective weather, the proposed UTM playbook leverages a database to store optimal UAS routes tagged with spatiotemporal wind scenarios to automate the UAS trajectory management. Our perspective is that the UASs, and many other modern systems, operate in spatiotemporally evolving environments, and similar spatiotemporal scenarios are tied with similar management decisions. Motivated by this feature, our automated playbook solution integrates the offline operations, online operations and a database to enable real-time UAS trajectory management decisions. The solution features the use of similarity between spatiotemporal scenarios to retrieve offline decisions as the initial solution for online fine tuning, which significantly shortens the online decision time. A fast query algorithm that exploits the correlation of spatiotemporal scenarios is utilized in the decision framework to quickly retrieve the best offline decisions. The online fine tuning adapts to trajectory deviations and subject to collision avoidance among UASs. The solution is demonstrated using simulation studies, and can be utilized in other applications, where quick decisions are desired and spatiotemporal environments play a crucial role in the decision process.
more »
« less
- NSF-PAR ID:
- 10304161
- Date Published:
- Journal Name:
- Unmanned Systems
- ISSN:
- 2301-3850
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Airspace geofencing is a key capability for low-altitude Unmanned Aircraft System (UAS) Traffic Management (UTM). Geofenced airspace volumes can be allocated to safely contain compatible UAS flight operations within a fly-zone (keep-in geofence) and ensure the avoidance of no-fly zones (keep-out geofences). This paper presents the application of three-dimensional flight volumization algorithms to support airspace geofence management for UTM. Layered polygon geofence volumes enclose user-input waypoint-based 3-D flight trajectories, and a family of flight trajectory solutions designed to avoid keep-out geofence volumes is proposed using computational geometry. Geofencing and path planning solutions are analyzed in an accurately mapped urban environment. Urban map data processing algorithms are presented. Monte Carlo simulations statistically validate our algorithms, and runtime statistics are tabulated. Benchmark evaluation results in a Manhattan, New York City low-altitude environment compare our geofenced dynamic path planning solutions against a fixed airway corridor design. A case study with UAS route deconfliction is presented, illustrating how the proposed geofencing pipeline supports multi-vehicle deconfliction. This paper contributes to the nascent theory and the practice of dynamic airspace geofencing in support of UTM.more » « less
-
Many transit agencies operating paratransit and microtransit ser-vices have to respond to trip requests that arrive in real-time, which entails solving hard combinatorial and sequential decision-making problems under uncertainty. To avoid decisions that lead to signifi-cant inefficiency in the long term, vehicles should be allocated to requests by optimizing a non-myopic utility function or by batching requests together and optimizing a myopic utility function. While the former approach is typically offline, the latter can be performed online. We point out two major issues with such approaches when applied to paratransit services in practice. First, it is difficult to batch paratransit requests together as they are temporally sparse. Second, the environment in which transit agencies operate changes dynamically (e.g., traffic conditions can change over time), causing the estimates that are learned offline to become stale. To address these challenges, we propose a fully online approach to solve the dynamic vehicle routing problem (DVRP) with time windows and stochastic trip requests that is robust to changing environmental dynamics by construction. We focus on scenarios where requests are relatively sparse-our problem is motivated by applications to paratransit services. We formulate DVRP as a Markov decision process and use Monte Carlo tree search to evaluate actions for any given state. Accounting for stochastic requests while optimizing a non-myopic utility function is computationally challenging; indeed, the action space for such a problem is intractably large in practice. To tackle the large action space, we leverage the structure of the problem to design heuristics that can sample promising actions for the tree search. Our experiments using real-world data from our partner agency show that the proposed approach outperforms existing state-of-the-art approaches both in terms of performance and robustness.more » « less
-
Existing rate adaptation protocols have advocated training to establish the relationship between channel conditions and the optimum modulation and coding scheme. However, innate with in-field operation is encountering scenarios that the rate adaptation mechanism has not yet encountered. Frequently, protocols are optimally tuned for indoor environments but, when taken outdoors, perform poorly. Namely, the decision structure formed by offline training, lacks the ability to adapt to a new situation on the fly. The changing wireless environment calls for a rate adaption scheme that can quickly infer the channel type and adjust accordingly. Typical SNR-based rate adaptation scheme do not capture the nuance of the performance variable in different channel types. In this paper, we propose a novel scheme that allow SNR-based rate selection algorithms to be trained online in the environment in which they are operating. Inspired by the idea that, to do well, an athlete must train for the type of athletic event and environment in which they are competing, we propose FIT, an on-the-fly, in-situ training mechanism for SNRbased protocols. To do so, we first propose the FIT framework which addresses the challenges of making rate decisions with unpredictable fluctuation and lack of repeatability of real wireless channels. To distinguish between channel types in the training, we then characterize wireless channels according to the link-layer performance and introduce a novel, computationally-efficient, channel performance manifold matching technique to infer the channel type given a sequence of throughput measurements for various link-level parameters. To evaluate our methods, we implement rate selection which uses FIT for training alongside channel performance manifold matching. We then perform extensive experiments on emulated and in-field wireless channels to evaluate the online learning process, showing that the rate decision structure can be updated as channel conditions change using existing traffic flows. The experiments are performed over multiple frequency bands. The proposed FIT framework can achieve large throughput gains compared to traditional SNRbased protocols (8X) and offline-training-based methods (1.3X), particularly in a dynamic wireless propagation environments that lack appropriate training.more » « less
-
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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1142/S2301385022500145
