Small Unmanned Aircraft Systems (sUAS) will be an important component of the smart city and intelligent transportation environments of the near future. The demand for sUAS related applications, such as commercial delivery and land surveying, is expected to grow rapidly in next few years. In general, sUAS traffic scheduling and management functions are needed to coordinate the launching of sUAS from different launch sites and plan their trajectories to avoid conflict while considering several other constraints such as expected arrival time, minimum flight energy, and availability of communication resources. However, as the airbone sUAS density grows in a certain area, it is difficult to foresee the potential airspace and communications resource conflicts and make immediate decisions to avoid them. To address this challenge, we present a temporal and spatial routing algorithm for sUAS trajectory management in a high density urban area. It plans sUAS movements in a spatial and temporal maze with the consideration of obstacles that are either static or dynamic in time. The routing allows the sUAS to avoid static no-fly areas (i.e. static obstacles) or other in-flight sUAS and areas that have congested communication resources (i.e. dynamic obstacles). The algorithm is evaluated using an agent-based simulation platform. The simulation results show that the proposed algorithm outperforms reference route management algorithms in many areas, especially in processing speed and memory efficiency. Detailed comparisons are provided for the sUAS flight time, the overall throughput, the conflict rate and communication resource utilization. The results demonstrate that our proposed algorithm can be used as a solution to improve the efficiency of airspace and communication resource utilization for next generation smart city and smart transportation.
more »
« less
Hybrid Multiscale Search for Dynamic Planning of Multi-Agent Drone Traffic
Unmanned aerial vehicles or drones are widely used or proposed to carry out various tasks in low-altitude airspace. To safely integrate drone traffic into congested airspace, the current concept of operations for drone traffic management will reserve a static traffic volume for the whole planned trajectory, which is safe but inefficient. In this paper, we propose a dynamic traffic volume reservation method for the drone traffic management system based on a multiscale A* algorithm. The planning airspace is represented as a multiresolution grid world, where the resolution will be coarse for the area on the far side. Therefore, each drone only needs to reserve a temporary traffic volume along the finest flight path in its local area, which helps release the airspace back to others. Moreover, the multiscale A* can run nearly in real-time due to a much smaller search space, which enables dynamically rolling planning to consider updated information. To handle the infeasible corner cases of the multiscale algorithm, a hybrid strategy is further developed, which can maintain a similar optimal level to the classic A* algorithm while still running nearly in real-time. The presented numerical results support the advantages of the proposed approach.
more »
« less
- NSF-PAR ID:
- 10472745
- Publisher / Repository:
- AIAA
- Date Published:
- Journal Name:
- Journal of Guidance, Control, and Dynamics
- Volume:
- 46
- Issue:
- 10
- ISSN:
- 0731-5090
- Page Range / eLocation ID:
- 1963 to 1974
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Small Unmanned Aircraft Systems (sUAS) will be an important component of the smart city and intelligent transportation environments of the near future. The demand for sUAS related applications, such as commercial delivery and land surveying, is expected to grow rapidly in next few years. In general, sUAS traffic routing and management functions are needed to coordinate the launching of sUAS from different launch sites and determine their trajectories to avoid conflict while considering several other constraints such as expected arrival time, minimum flight energy, and availability of communication resources. However, as the airborne sUAS density grows in a certain area, it is difficult to foresee the potential airspace and communications resource conflicts and make immediate decisions to avoid them. To address this challenge, we present a temporal and spatial routing algorithm and simulation platform for sUAS trajectory management in a high density urban area that plans sUAS movements in a spatial and temporal maze taking into account obstacles that are either static or dynamic in time. The routing allows the sUAS to avoid static no-fly areas (i.e. static obstacles) or other in-flight sUAS and areas that have congested communication resources (i.e. dynamic obstacles). The algorithm is evaluated using an agent-based simulation platform. The simulation results show that the proposed algorithm outperforms other route management algorithms in many areas, especially in processing speed and memory efficiency. Detailed comparisons are provided for the sUAS flight time, the overall throughput, conflict rate and communication resource utilization. The results demonstrate that our proposed algorithm can be used to address the airspace and communication resource utilization needs for a next generation smart city and smart transportation.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
-
Cristina Ceballos (Ed.)The current National Airspace System (NAS) is reaching capacity due to increased air traffic, and is based on outdated pre-tactical planning. This study proposes a more dynamic airspace configuration (DAC) approach that could increase throughput and accommodate fluctuating traffic, ideal for emergencies. The proposed approach constructs the airspace as a constraints-embedded graph, compresses its dimensions, and applies a spectral clustering-enabled adaptive algorithm to generate collaborative airport groups and evenly distribute workloads among them. Under various traffic conditions, our experiments demonstrate a 50% reduction in workload imbalances. This research could ultimately form the basis for a recommendation system for optimized airspace configuration. Code available at https://github.com/KeFenge2022/GraphDAC.gitmore » « less
-
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
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.2514/1.G007343
