In Urban Air Mobility (UAM) networks, takeoff and landing sites, called vertiports, are likely to experience intermittent closures due to, e.g., adverse weather. To ensure safety, all in-flight Urban Air Vehicles (UAVs) in a UAM network must therefore have alternative landing sites with sufficient landing capacity in the event of a vertiport closure. In this paper, we study the problem of safety verification of UAM schedules in the face of vertiport closures. We first provide necessary and sufficient conditions for a given UAM schedule to be safe in the sense that, if a vertiport closure occurs, then all UAVs will be able to safely land at a backup landing site. We then extend these results to the scenario of multiple vertiport closures. Next, we convert these conditions to an efficient algorithm for verifying the safety of a UAM schedule via a linear program by using properties of totally unimodular matrices. Our algorithm allows for uncertain travel time between UAM vertiports and scales quadratically with the number of scheduled UAVs. We demonstrate our algorithm on a UAM network with up to 1,000 UAVs.
more »
« less
Online Probabilistic Collision Detection for Urban Air Mobility under Data-Driven Uncertainty
Urban air mobility (UAM) using unmanned aerial vehicles (UAV) is an emerging way of air transportation within metropolitan areas. For the sake of the successful operations of UAM in dynamic and uncertain airspace environments, it is important to provide safe path planning for UAVs. To achieve the path planning with safety assurance, the first step is to detect collisions. Due to uncertainty, especially data-driven uncertainty, it’s impossible to decide deterministically whether a collision occurs between a pair of UAVs. Instead, we are going to evaluate the probability of collision online in this paper for any general data-driven distribution. A sampling method based on kernel density estimator (KDE) is introduced to approximate the data-driven distribution of the uncertainty, and then the probability of collision can be converted to the Riemann sum of KDE values over the domain of the combined safety range. Comprehensive numerical simulations demonstrate the feasibility and eciency of the online evaluation of probabilistic collision for UAM using the proposed algorithm of collision detection.
more »
« less
- Award ID(s):
- 2138612
- NSF-PAR ID:
- 10472747
- Publisher / Repository:
- American Institute of Aeronautics and Astronautics
- Date Published:
- ISBN:
- 978-1-62410-699-6
- Format(s):
- Medium: X
- Location:
- National Harbor, MD & Online
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Advanced Air Mobility (AAM) using electrical vertical take-off and landing (eVTOL) aircraft is an emerging way of air transportation within metropolitan areas. A key challenge for the success of AAM is how to manage large-scale flight operations with safety guarantees in high-density, dynamic, and uncertain airspace environments in real time. To address these challenges, we introduce the concept of a data-driven probabilistic geofence, which can guarantee that the probability of potential conflicts between eVTOL aircraft is bounded under data-driven uncertainties. To evaluate the probabilistic geofences online, Kernel Density Estimation (KDE) based on Fast Fourier Transform (FFT) is customized to model data-driven uncertainties. Based on the FFT-KDE values from data-driven uncertainties, we introduce an optimization framework of Integer Linear Programming (ILP) to find a parallelogram box to approximate the data-driven probabilistic geofence. To overcome the computational burden of ILP, an efficient heuristic algorithm is further developed. Numerical results demonstrate the feasibility and efficiency of the proposed algorithms.more » « less
-
This paper describes a hierarchical solution consisting of a multi-phase planner and a low-level safe controller to jointly solve the safe navigation problem in crowded, dynamic, and uncertain environments. The planner employs dynamic gap analysis and trajectory optimization to achieve collision avoidance with respect to the predicted trajectories of dynamic agents within the sensing and planning horizon and with robustness to agent uncertainty. To address uncertainty over the planning horizon and real-time safety, a fast reactive safe set algorithm (SSA) is adopted, which monitors and modifies the unsafe control during trajectory tracking. Compared to other existing methods, our approach offers theoretical guarantees of safety and achieves collision-free navigation with higher probability in uncertain environments, as demonstrated in scenarios with 20 and 50 dynamic agents.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
-
null (Ed.)more » « less
Abstract Quadrotors can provide services such as infrastructure inspection and search-and-rescue, which require operating autonomously in cluttered environments. Autonomy is typically achieved with receding-horizon planning, where a short plan is executed while a new one is computed, because sensors receive limited information at any time. To ensure safety and prevent robot loss, plans must be verified as collision free despite uncertainty (e.g, tracking error). Existing spline-based planners dilate obstacles uniformly to compensate for uncertainty, which can be conservative. On the other hand, reachability-based planners can include trajectory-dependent uncertainty as a function of the planned trajectory. This work applies Reachability-based Trajectory Design (RTD) to plan quadrotor trajectories that are safe despite trajectory-dependent tracking error. This is achieved by using zonotopes in a novel way for online planning. Simulations show aggressive flight up to 5 m/s with zero crashes in 500 cluttered, randomized environments.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.2514/6.2023-2539
