Airspace Geofencing and Flight Planning for Low-Altitude, Urban, Small Unmanned Aircraft Systems

Abstract

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.

1. Introduction

Small Unmanned Aircraft System (UAS) operations are expected to proliferate [1,2] for applications such as small package delivery, surveillance, and the visual inspection of assets including wind turbines, construction sites, bridges, and agricultural products. Several challenges must be overcome to enable routine small UAS operations. The aviation community has proposed UAS Traffic Management (UTM) [3,4,5] to safely and efficiently manage low-altitude airspace where small UAS are expected to operate. UTM services are expected to be based on web apps and datalinks which facilitate the efficient definition and coordination of UAS flight plans.

Airspace geofencing is one of the key capabilities required for UTM [3]. The envisioned geofencing system will enable safe flight operations by dividing airspace into available fly-zone (keep-in geofence) and no-fly zone (keep-out geofence) volumes with statically and dynamically adjusted virtual barriers or “fences” designed to assure UAS separation from obstacles, sensitive areas, and each other. Geofencing will facilitate safety management (i.e., Situational Awareness (SA) for trajectory monitoring, trajectory deviation alerts/geofence breaches, and contingency plans) and flight management (i.e., route-planning, the selection of take-off/landing sites, and mission priority adjustment) for UTM. Figure 1 illustrates airspace geofence examples for UAS flight operations near the One World Trade Center in Manhattan (left) and for wind turbine inspection (right).

Researchers have previously investigated airspace geofencing systems for UTM. A two-dimensional keep-in/keep-out geofence construction algorithm was developed in [6]. Real-time geofence violation detection capabilities have been developed using Ray Casting [7] and Triangle Weight Characterization with Adjacency (TWCA) [8] methods. Potential intersections of 2-D geofences can be rapidly detected using a convex hull approach [9]. A constrained control scheme was developed using an Explicit Reference Governor (ERG) in [10]; this approach ensures a UAS does not violate geofence boundaries. This previous research primarily focused on geofence definition, boundary violation detection, and UAS avionics augmentation to support geofencing. Our work’s focus on 3D path planning with geofence volumes in a realistically mapped urban environment is complementary.

Cooperative UAS flight tests were also evaluated using “separation by segregation” geofencing features in [11]. To define a local geofence volume for applications such as crop inspection, the maximum flight distance a UAS can travel after flight termination was calculated using vehicle dynamics and position sensors in [12] to define geofence geometry. This research demonstrated that a UAS stays within its prescribed keep-in geofence in both nominal and off-nominal (e.g., flight termination) conditions.

A three-dimensional dynamic geofencing volumization solution was proposed using “operational” and “inverse” volumization functions in [13]. Per [13], airspace operational volumization is the process by which a requested flight plan is “wrapped” with a geofence reserved over an approved flight time window. Inverse volumization is the opposite process in which a flight is planned to always remain within a designated airspace geofence volume. This paper extends our work in [13] in several ways. First, we integrate the individual airspace volumization algorithms into a geofencing pipeline described in Section 3. This geofencing pipeline is shown in Figure 2. We also construct simplified keep-in/keep-out 3-D geofencing boundaries based on buildings and UAS flight plans, as illustrated in Figure 1. This algorithm uses parameters such as vehicle speed, geofence boundary safety buffer size, and polygon simplification parameters to generate a flight plan that does not violate keep-in/keep-out geofences in the surrounding region. We define a trajectory keep-in geofence as the airspace volume surrounding the planned flight path with constant ceiling and floor safety buffers. Pathfinding logic is developed for different start and desired end locations of a vehicle in the flight plan. The algorithms are built on computational geometry, where obstacles, buildings, and flight path keep-in geofences are represented as sets of 3-D polygons. Path planning modules are computed efficiently based on a visibility graph approach and set operations in a 3-D environment.

This work is unique in its joint consideration of low-altitude mapped obstacles and geofence volume requirements in 3D multicopter sUAS flight planning. Urban terrain and building maps necessarily create more complex flight paths and safety constraints [14]. As an example, consider package delivery UAS in an urban canyon environment. Safe operation requires obstacle-free path planning for all sUAS operating in this shared low-altitude airspace. Planned sUAS paths must therefore treat both physical obstacles (e.g., buildings, power lines, and terrain) and keep-out geofences as impenetrable obstacles that must be circumvented in a safe flight plan. Our work bridges the gap in the existing geofencing literature by focusing on path planning solutions that assure the satisfaction of keep-in/keep-out geofenced airspace volume constraints.

The contributions of this work are:

• The specification of formal algorithms to define keep-in/keep-out geofences for obstacles to plan UAS paths with separation assurance;
• The integration of airspace and environmental geofencing processing pipelines with user inputs to construct geofences and geofence-wrapped path plans in a real-world urban environment;
• Map data processing to generate keep-out geofences around buildings and terrain and a process to simplify a detailed map dataset to support a more compact representation and improved path planning efficiency;
• A benchmark comparison of our geofenced path planning solutions with a fixed sUAS airway flight corridor design, and a case study of sUAS route deconfliction in shared airspace.

The remaining structure of this paper is organized as follows. Section 2 summarizes previous work in UAS Traffic Management (UTM), sUAS and robotic path planning, and computational geometry methods used in geofencing algorithms. Section 3 defines an airspace geofence, states assumptions made in this work, and introduces sUAS geofencing pipeline algorithms used in the generation of flight trajectory solutions. Section 4 describes OpenStreetMap (OSM) data processing steps to minimize computational time in generating solutions. Section 5 describes Monte Carlo simulation setups that integrate pipeline algorithms with map data processing. Section 6 presents statistics comparing results from our airspace volumization algorithm with a fixed airway flight corridor solution for a region of Manhattan in New York City. Section 7 describes a case study for sUAS route deconfliction, while Section 8 concludes the paper.

2. Literature Review

This section presents related work in UTM, computational geometry, and path planning, all of which are relevant to our geofencing algorithms.

2.1. Unmanned Traffic Management and Geofencing

UTM has been identified as a critical capability for future small UAS operations due to their unique operating profiles at low altitude, near complex infrastructure, and likely in mixed-use airspace [3]. UTM-like concepts have been investigated by industry, government, and academia across the globe. As an example, Single European Sky ATM Research (SESAR) recommended UTM to the European Union (EU) to safely coordinate UAS [15]. Centralized and distributed UTM with airspace volumes distinguished by altitude layer was investigated to deconflict UAS traffic in Sweden [16]. UTM was modeled using a multiplayer network of nodes and airways at low-altitude airspace in Luxembourg [5]. The National Aeronautics and Space Administration (NASA) perhaps first coined the term UTM as a system architecture necessary to accommodate UAS in a low-altitude National Airspace System (NAS) layer not frequently occupied by legacy manned aircraft [3]. Representatives from industry have worked to establish adequate security protocols for managing UTM datalinks [17]. NASA, in cooperation with industry, has pursued a series of flight test events to evaluate cooperative UAS operations in beyond visual line of sight (BVLOS) conditions with a “separation by segregation” geofence design [11]. Airspace capacity estimation was analyzed using keep-in and keep-out geofences in [18]. A roadmap for geofence implementation in urban areas with 5G networks and blockchain was introduced in [19].

Dynamic airspace geofencing algorithms are novel to UTM. Two different but equally important perspectives (i.e., local/global) exist in geofencing designs. One perspective is a classical guidance/navigation/control (GNC) approach, where geofence layering is only generated for the individual UAS that has full knowledge of its control system. This vehicle-centered geofence perspective focuses on controlling UAS to ensure that the vehicle does not violate the geofence boundaries (given expected trajectory tracing errors) [10,20]. In this work, each UAS monitors its real-time state vector relative to geofence boundaries to detect and react to potential breaches given uncertainties due to sensor errors and wind disturbances.

Vehicle-centered geofencing research is important but does not consider properties of the operating area airspace or the ground-based environment. Geofencing has also been researched from an airspace system perspective. With this viewpoint, geofences are managed by UTM to organize airspace structure and improve Situational Awareness (SA). UTM will not model individual UAS capabilities and uncertainties in detail, but it can conservatively monitor UAS travel through an approved geofence to offer impending breach warnings to the UAS and actual boundary violations to all traffic per [21].

SA is a fundamental requirement for all flight operations, autonomous or human-piloted [22,23]; while legacy air Traffic Management (ATM) will remain distinct from UTM in the near term, advanced air mobility (AAM) supporting increasingly to fully autonomous flight will motivate the integration of ATM and UTM over the long term. UTM calls for the automation of airspace management tasks. Airspace organization and protection through geofencing can improve SA and in turn safety. Our algorithms can be integrated into both GNC (onboard) and airspace system (UTM) geofencing realizations.

AAM operations, including but not limited to Urban Air Mobility (UAM), are envisioned to have higher altitudes than 400 AGL, where current UTM is designed to serve. Researchers at NASA and Uber investigated the applicability of UTM to coordinate UAM routes safely and efficiently [24]. In their case studies, “Transit-Based Operational Volumes (TBOVs)” were used to wrap the UAM flight path, a notion analogous to the trajectory keep-in geofence discussed in this paper. Inspired by the static “UAM-authorized airspace” active over a fixed duration [24] as an airspace management alternative to geofencing, in our case studies, we designed fixed flight corridors and simulated sUAS flight missions operating in these flight corridors. This alternative solution offers a benchmark with which our dynamic geofence volumization and path planning solutions are compared (Section 5).

2.2. Computational Geometry

Computational geometry has been used to construct and deconflict airspace geofence volumes and to detect/prevent airspace boundary violations (onboard). A scaling algorithm was developed for two-dimensional keep-in/keep-out concave polygon geofences in [6]. This paper uses vehicle performance constraints and steady wind conditions to generate scaled “warning” and “override” geofence boundaries. Once a UAS crosses one of these boundaries, onboard GNC can trigger a corrective response [25] or flight termination. In [26,27,28], algorithms for polygon set operations (i.e., polygon intersections and unions), polygon clipping, convex hull, and point-in-polygon were developed. We use these algorithms to detect and resolve geofence boundary conflicts and generate new geofence volumes by merging conflicting boundaries. A UAS geofence violation detection method was defined in [7] using Ray Casting [29]. A Triangle Weight Characterization with Adjacency (TWCA) algorithm was developed as a faster real-time geofence violation detection method in [8]. TWCA divides geofence into a finite number of triangles and then finds UAS location in a pre-generated adjacency graph. In [9], a 3-D dynamic geofence (“moving geofence”) was constructed using maximum cruise time, speed, and range of the UAS as a pre-departure flight planning algorithm. This paper also proposes a convex hull approach to find conflicts between current and newly submitted flight plans.

2.3. Path Planning

Determining a collision-free geofence-based flight trajectory is central to the design of our geofencing volumization work. A variety of path planning algorithms were considered. Grid-based path planning methods overlay a fixed-resolution grid on top of the configuration space and find discretized line segment paths connecting start state to destination. This search is fast in low-dimensional space but quickly becomes computationally intractable with high-resolution maps and appreciable travel distance. The most notable grid-based path planning algorithms are ${\mathcal{A}}^{\ast }$ [30] and ${\mathcal{D}}^{\ast }$ [31]. A family of roadmap-based path planning algorithms have been developed to offer a more compact search space optimizing a specific cost metric. For example, a visibility graph [32] minimizes travel distance, while a Voronoi diagram maximizes obstacle clearance distance [33]. The application of cell decomposition [34] offers a compact map for discrete search path planning in an obstacle field. Other path planning methods include potential-field algorithms [35] that efficiently build plans with gradient descents but are subject to local minima issues. Sampling-based path planning algorithms [36] have also been developed and are particularly well suited to planning in uncertain environments. Our work utilizes a visibility graph approach to path planning. This approach allows us to directly translate geofence volumes generated with computational geometry into visibility graph roadmaps. As is discussed below, we scale keep-out geofences to assure safe separation is maintained. Note that a visibility graph does not require a rasterized map, enabling geofences to be represented without distortion or approximation.

3. Definitions and Algorithms

The term airspace geofence was formally defined in [37] to support a common framework for airspace volume reservation in UTM. Our work follows this definition:

Definition 1.

A Geofence $g=\{n,v\left[\right],z_f,z_c,m,h\left[\right]\}$ is a volume defined by a list of n vertices in the horizontal plane $v=[(x_1,y_1),(x_2,y_2),\cdots ,(x_n,y_n)]$, where $n\ge 3$, and an altitude floor $z_f$ and ceiling $z_c$. The volume is defined relative to a set of home locations, $h_i=(x_i,y_i,z_i,t_i)$, where $h\left[\right]$ is a list of length $m\ge 2$. Lateral home positions can be represented as latitude/longitude pairs $({\varphi }_i,{\lambda }_i)$ or locally referenced Cartesian coordinates $(x_i,y_i)$. $z_i$ is the altitude of the home location above Mean Sea Level (MSL). $t_i$ is the activation time for home location i where $1\le i\le m$. $t_m$ is the deactivation time for geofence g. For consistency, Cartesian coordinates and altitudes are defined in meters and activation/deactivation times are in seconds.

This data structure supports geofence types: static, durational, and dynamic. A static geofence has a permanent fixed home location $h\left[\right]$ and typically surrounds physical obstacles such as buildings or sensitive areas (i.e., no-fly zones). A durational geofence is active over a finite time interval with a fixed home location $h\left[\right]$. A dynamic geofence is active over a specific time interval; its home location can move over time.

The following simplifying assumption is made in this paper to facilitate path planning and eliminate the need for traffic deconfliction.

Assumption 1.

One aircraft (e.g., UAS) is allocated to each local geofence volume. No other UAS is permitted to cross into this volume. UTM efficiency therefore relies on minimizing each reserved geofence volume and its duration.

Dynamic airspace volumization for geofencing will enhance safety by wrapping a UAS in an airspace volume that assures separation from other traffic. The below subsections describe our geofencing algorithm pipeline for UTM, where flight plans are designed with keep-in/keep-out geofencing volumes on a low-altitude airspace map. Three-dimensional trajectory keep-in geofence volumes safely wrapping UAS flight paths are described in Section 3.1, keep-out geofence construction for a low-altitude urban map is described in Section 3.2, and geofence-based path planning solutions are illustrated in Section 3.3.

3.1. Airspace Operational Volumization

Operational volumization constructs a trajectory keep-in geofence overlaid on a user-defined 3-D flight trajectory. Climb and descent segments are first generated with vehicle dynamics inputs such as velocity and desired time to climb/descend. Then, three-dimensional cruise operational volumes are created between the climb and descent geofence pair. This assures a geofence volume always encloses the flight trajectory with the prescribed safety buffer ${\delta }_{vehicle}$. This algorithm integrates 2-D flight trajectory operational volumization with the Multiple Staircase Geofence (MSG) algorithm per [13]. Three-dimensional trajectory volumization is shown in Algorithm 1. Figure 3 shows an example of a 3-D trajectory with its corresponding three-dimensional geofence volume. A sequence of geofence volumes is constructed by connecting climb, cruise, and descent geofences with user-specified safety buffers.

Algorithm 1 3D Flight Trajectory Operational Volumization (3dOperVol).

Inputs: 2-D Trajectory waypoints $\mathcal{W}$, Velocity $\mathcal{V}$, Time to Climb $t_{climb}$, Time to Descent $t_{desc}$, Number of Geofence ${\mathcal{N}}_{geo}$, UAS Safety Buffer ${\delta }_{vehicle}$, Cruise Altitude $h_{cruise}$ Outputs: 3-D Flight Trajectory ${\mathcal{P}}_{traj}$, 3-D Geofence for 3-D Flight Trajectory $\mathcal{G}$ Algorithm: 1: $[{\mathcal{P}}_{climb},{\mathcal{G}}_{climb}]\leftarrow MSG(\mathcal{W}[1:2],\mathcal{V},t_{climb},{\mathcal{N}}_{geo},{\delta }_{vehicle})$⊲ generate climb geofence 2: $[{\mathcal{P}}_{desc},{\mathcal{G}}_{desc}]\leftarrow MSG(\mathcal{W}[end-1:end],\mathcal{V},t_{desc},{\mathcal{N}}_{geo},{\delta }_{vehicle})⊲$ descent geofence 3:   4: ${\mathcal{P}}_{cruise}\leftarrow [{\mathcal{P}}_{climb}[end-1:end],\mathcal{W}[3:end-2],{\mathcal{P}}_{desc}[1:2]]$⊲ 3-D Cruise flight 5: $\left[{\mathcal{G}}_{cruise}\right]\leftarrow MSG(2dOperVol({\mathcal{P}}_{cruise},{\delta }_{vehicle}),h_{cruise})$⊲ Generate cruise geofence 6: ${\mathcal{P}}_{traj}\leftarrow [{\mathcal{P}}_{climb};{\mathcal{P}}_{cruise};{\mathcal{P}}_{desc}]$ 7: $\mathcal{G}\leftarrow [{\mathcal{G}}_{climb};{\mathcal{G}}_{cruise};{\mathcal{G}}_{desc}]$ 8: return [${\mathcal{P}}_{traj},\mathcal{G}$]

To minimize airspace volume reservation duration, we utilize the shrinking durational geofence (SDG) and multi-stage durational geofence (MDG) algorithms in [13] for the cruise segment. A shrinking durational geofence (SDG) removes a previously occupied geofence volume at each time update in UTM. A multi-stage durational geofence (MDG) has multiple volumes generated over the flight trajectory with temporal or spatial overlap. For transitions between MDG regions, either temporal or spatial overlap is used to guarantee the UAS is always enclosed by at least one MDG. Overlap offers a buffer in case the UAS flies faster or slower than expected. Note that climb and descent segments utilize multiple staircase geofences so that previously occupied staircase geofences can be removed sequentially.

3.2. Constructing a Geofence Volume from an Urban Map

Keep-out geofences are constructed around obstacles (i.e., buildings) to assure separation between UAS and obstacles or no-fly airspace zones. The construction of keep-out geofence volumes from a building and terrain map must be efficiently carried out to constrain the computation time needed to generate geofence-based path planning solutions. For this work, we utilize a visibility graph approach to path planning, as illustrated in Section 3.3. The time complexity of visibility graph generation is $O\left(n^{2}log\left(n\right)\right)$, where n is the total number of vertices in all polygons. In a real-world environment, the number of keep-out geofences in the urban environment can be significant (i.e., 14,000 building cluster geofence polygons in the southern Manhattan map). We utilize two algorithms to achieve map simplification. First, we downsample geofence vertices in the map as shown in Algorithm 2 per [38] with user-defined parameters $n_{maxVert}$ and $p_{dwnSmple}$. This updated set of keep-out geofences is then used to construct a region of interest (ROI) visibility graph. The ROI in the map is first constructed as a rectangular box surrounding departure and destination points. Then, polygon intersection, point-in-polygon, and convex hull operations are used to define the actual region of interest for which geofence-based path planning solutions are generated. Generation of the flight planning visibility graph ROI is shown in Algorithm 3. Figure 4 shows an example of polygon vertex set downsampling. Figure 5 illustrates an initial rectangular ROI $P_{recROI}$ example.

Algorithm 2 Reduce Map Geofence Vertex Set.

Inputs: Set of Keep-out Geofences ${\mathcal{S}}_{geo}$, Downsample Threshold $n_{maxVert}$, Downsample Tolerance In Percentage $p_{dwnSmple}$ Outputs: Set of Downsampled Keep-out Geofences ${\mathcal{S}}_{ds}$ Algorithm: 1: ${\mathcal{S}}_{ds}\leftarrow \left[\right]⊲$ initialize the output set 2:   3: for$\mathcal{S}\in {\mathcal{S}}_{geo}$do 4:  if $len\left(\mathcal{S}\right)/2>n_{maxVert}$ then 5:   ${\mathcal{S}}_{out}\leftarrow DecimatePoly(\mathcal{S},p_{dwnSmple})⊲$ downsample polygon vertices 6:   $k\leftarrow 1$ 7:   for $j=1:len\left({\mathcal{S}}_{out}\right)$ do 8:    $\mathcal{G}[k:k+1]\leftarrow {\mathcal{S}}_{out}[j,1:2]⊲$ obtain geofence data structure 9:    $k=k+2$ 10:   end for 11:  end if 12:  ${\mathcal{S}}_{ds}\leftarrow {\mathcal{S}}_{ds}.add\left(\mathcal{G}\right)$ 13: end for 14: return${\mathcal{S}}_{ds}$

Algorithm 3 Compute Visibility Graph ROI.

Inputs: Departure Point ${\mathcal{P}}_{start}$, Destination Point ${\mathcal{P}}_{end}$, ROI Inital Buffer ${\delta }_{ROI}$, Keep-out Geofence Set ${\mathcal{S}}_{geo}$ Outputs: Keep-out Geofences in ROI ${\mathcal{S}}_{ROI}$ Algorithm: 1: $P_{recROI}\leftarrow getRecROI({\mathcal{P}}_{start},{\mathcal{P}}_{end},{\delta }_{ROI})⊲$ get Rectangular ROI vertices 2:   3: //get convexhull ROI where geofencing solutions are generated 4: $S_{intersect}\leftarrow \left[\right]⊲$ initialize the intersecting geofence set 5: for$\mathcal{S}\in {\mathcal{S}}_{geo}$do 6:  if $searchIntersect(S,P_{recROI})\ne \varnothing$ then 7:   ${\mathcal{S}}_{intersect}\leftarrow {\mathcal{S}}_{intsct}.add\left(S\right)⊲$ Append intersecting geofence 8:  end if 9: end for 10:   11: //Search keep-out geofences inside the convex hull $P_{ROI}$ 12: $S_{ROI}\leftarrow \left[\right]⊲$ initialize $S_{ROI}$ 13: $P_{ROI}\leftarrow convexHull\left(S_{intersect}\right)⊲$ ROI where geofencing solutions are generated 14: for$\mathcal{S}\in {\mathcal{S}}_{geo}$do 15:  if $searchIntersect(S,P_{ROI})\ne \varnothing$ then 16:   ${\mathcal{S}}_{ROI}\leftarrow {\mathcal{S}}_{intsct}.add\left(S\right)⊲$ Append intersecting geofence 17:  end if 18: end for 19: return$S_{ROI}$

3.3. UAS Flight Planning in a Geofenced UTM Airspace

Flight plans are typically optimized over distance, energy usage, and flight time (delay) cost metrics. A UAS configuration space is first obtained from user-defined safety buffers ${\delta }_{vehicle},{\delta }_{building}$ around the vehicle and obstacles, respectively. The UAS can then be treated as a point mass in configuration space with obstacle boundaries expanded for safety by:

$${\delta }_{sb}={\delta }_{vehicle}+{\delta }_{building}.$$

(1)

This safety buffer ensures the vehicle maintains sufficient clearance from any obstacles. ${\delta }_{vehicle}$ and ${\delta }_{building}$ are user-specified parameters in this work.

Our proposed geofencing pipeline applies three inverse volumization options per [13] based on user-specified departure and destination locations. The first option is a “turn” solution that calculates climb, cruise, and descent flight trajectories that turn away from nearby obstacles, maintaining a minimum-distance path from start to end. For this module, a low-dimensional visibility graph search with Dijkstra’s algorithm [39] plans paths around obstacles (i.e., polygons) defined in a local Cartesian frame. We modeled keep-out geofences on obstacles as open set 3-D polygons extruded from 2-D obstacles with fixed heights. Per Section 2.3, an obstacle-free visibility graph or roadmap space can be constructed from geofence and obstacle polygons without rasterization [32,40].

The second path planning option is a “constant cruise altitude climb” module for which the UAS climbs over no-fly and obstacle volumes until a direct-heading route to the destination is obstacle-free. For this option, a vehicle first climbs to a pre-determined cruise altitude greater than the highest building en route to the destination. Then, the vehicle flies directly to the destination at cruise altitude. As the vehicle approaches the end of its cruise segment, it descends to the destination free of obstacles along the path. The third path planning option is a “vertical terrain follower” module, where a UAS follows the terrain altitude profile en route to the destination, flying as low as possible. This solution minimizes the time a UAS will spend at a high altitude potentially in conflict with other transiting traffic, but it adds complexity to the altitude profile. Figure 6 shows examples of turn, constant cruise altitude, and terrain follower climb solutions per [13].

To determine which of three solutions is best, a weighted cost function over time, distance, and energy is defined:

$$\mathcal{C}=\alpha \ast d_{travel}+\beta \ast P_{travel}+\gamma \ast t_{wait}.$$

(2)

where $d_{travel},P_{travel},and{t}_{wait}$ are distance traveled, power consumption, and time delay until durational geofences disappear, respectively. Weighting factors $\alpha ,\beta ,and\gamma$ are user-defined. The path planning solution with minimum cost is then suggested to an operator and/or automation. The flight planning process with geofencing is shown in Algorithm 4. In this algorithm, the departure point, destination point, cruise altitude, and keep-out geofence boundary coordinates are input along with cruise velocity and climb/descent times. For the turn solution, a Rotational Plane Sweep (RPS) algorithm is used to find all straight-line segments connecting line-of-sight vertices to form a visibility graph map. Then, Dijkstra’s algorithm finds the minimum distance path from departure to destination point. For constant altitude climb and terrain follower solutions, points of intersection between a straight line solution path and obstacles are found using a polygon-line intersection operator. Then, obstacle height at the intersection points are extracted from keep-out geofence data. Three-dimensional flight trajectory “turn”, “constant cruise altitude”, and “terrain follower” solutions are wrapped with geofences using Algorithm 1. The best solution is the minimum cost module based on Equation (2). Note that geofence segment duration is not explicitly considered in this paper. Instead, it is assumed the flight trajectory keep-in geofence generated using Algorithm 4 remains active from UAS launch to landing.

Algorithm 4 Flight Planning With Geofencing.

Inputs: Departure Point ${\mathcal{R}}_{start}$, Destination Point ${\mathcal{R}}_{end}$, Cruise Altitude $h_{cruise}$, Keep-out Geofence Boundaries ${\mathcal{S}}_{geo}$, Aircraft Velocity $\mathcal{V}$, Time to Climb $t_{climb}$, Time to Descend $t_{desc}$, Number of Geofences ${\mathcal{N}}_{geo}$, UAS Safety Buffer ${\delta }_{vehicle}$ Outputs: Planned Flight Trajectory ${\mathcal{P}}_{traj}$, Trajectory-wrapping 3-D Geofence Volumes $\mathcal{G}$ Algorithm: 1: //turn solution module 2: ${\mathcal{R}}_{VG}\leftarrow [{\mathcal{R}}_{start};{\mathcal{S}}_{geo};{\mathcal{R}}_{end}]$⊲ Vertices of Visibility Graph 3: $[edges,vert\_ID]\leftarrow RPS\left({\mathcal{R}}_{VG}\right)$⊲ get visibility graph edges on the map using RPS 4: $\left[R_{turn}\right]\leftarrow dijkstraPath({\mathcal{R}}_{start},{\mathcal{R}}_{end},edges,vert\_ID)$⊲ get min. distance path 5: $[{\mathcal{P}}_{turn},{\mathcal{G}}_{turn}]\leftarrow 3dOperVol({\mathcal{R}}_{turn},\mathcal{V},[t_{climb},t_{desc}],{\mathcal{N}}_{geo},{\delta }_{vehicle},h_{cruise})$ 6: ${\mathcal{D}}_{turn}\leftarrow getDist\left({\mathcal{P}}_{turn}\right)$⊲ get turn module flight distance 7:   8: //climb solution modules 9: ${\mathcal{R}}_{intersect}\leftarrow searchIntersect\left({\mathcal{R}}_{VG}\right)$⊲ get intersections from [${\mathcal{R}}_{start};{\mathcal{R}}_{end}$] to ${\mathcal{S}}_{geo}$ 10: if${\mathcal{R}}_{intersect}\ne \varnothing$then 11:    $h_{intersect}\leftarrow extractHeight({\mathcal{R}}_{intersect},{\mathcal{S}}_{geo})$⊲ get heights at intersections 12:    $h_{max}\leftarrow max\left(h_{intersect}\right)$ 13:     14:    //constant cruise altitude 15:    $[{\mathcal{P}}_{const},{\mathcal{G}}_{const}]\leftarrow 3dOperVol({\mathcal{R}}_{intersect},\mathcal{V},[t_{climb},t_{desc}],{\mathcal{N}}_{geo},{\delta }_{vehicle},h_{max})$ 16:    ${\mathcal{D}}_{const}\leftarrow getDist\left({\mathcal{P}}_{const}\right)$⊲ get constant altitude cruise flight distance 17:     18:    //terrain follower 19:    $[{\mathcal{P}}_{terr},{\mathcal{G}}_{terr}]\leftarrow 3dOperVol({\mathcal{R}}_{intersect},\mathcal{V},[t_{climb},t_{desc}],{\mathcal{N}}_{geo},{\delta }_{vehicle},h_{intersect})$ 20:    ${\mathcal{D}}_{terrain}\leftarrow getDist\left({\mathcal{P}}_{terr}\right)$⊲ get terrain follower flight distance 21: end if 22:   23: //cost comparison 24: $[{\mathcal{C}}_{min},opt]\leftarrow costCompare({\mathcal{D}}_{turn},{\mathcal{D}}_{const},{\mathcal{D}}_{terrain})$ 25: if opt == 1 then 26:    $[{\mathcal{P}}_{traj},{\mathcal{G}}_{traj}]\leftarrow [p_{turn},{\mathcal{G}}_{turn}]$⊲ best sol: turn module 27: else if opt == 2 then 28:    $[{\mathcal{P}}_{traj},{\mathcal{G}}_{traj}]\leftarrow [p_{const},{\mathcal{G}}_{const}]$⊲ best sol: constant cruise altitude module 29: else 30:    $[{\mathcal{P}}_{traj},{\mathcal{G}}_{traj}]\leftarrow [p_{terr},{\mathcal{G}}_{terr}]$⊲ best sol: terrain follower module 31: end if 32: return$[{\mathcal{P}}_{traj},{\mathcal{G}}_{traj}]$

4. Environment Modeling

Map Data Processing

To evaluate the proposed geofencing capability in a complex low-altitude environment, we processed OpenStreetMap (OSM) data for the Manhattan Borough of New York City (USA). OSM is a collaborative global mapping project that creates geographical data and information [41]. OSM is frequently updated and provides map entities including airways, roads, buildings, and more. To minimize map processing overhead for this work, we used pre-processed georeferenced OSM Manhattan building data as described in Ref. [42]. This raw data contain building coordinates represented as polygon vertices, building heights, and street level in WGS 84/UTM zone 18N [43], where units are in meters with East, North, Up (ENU) axes. We applied a combination of set and convex hull [32] operations to simplify geofence geometry for flight planning. Figure 7 shows the flowchart for map data post-processing. After post-processing, the dataset was partitioned into four categories: buildings with heights greater than 20 m, 60 m, 122 m, and 400 m. Depending on sUAS start and end altitude (i.e., roof of building, ground), flight planning utilizes one of these four datasets to generate plans and associated geofence volumes.

Figure 8 shows a map of southern Manhattan with closely spaced building clusters each enclosed by a single keep-out geofence to simplify the Manhattan urban canyon map. Figure 9 shows an example of post-processed georeferenced data and its 3-D keep-out geofence.

A southern Manhattan, New York City map was defined by 14,000 building cluster geofence polygons using the above procedure. To further simplify the map, we downsampled geofence vertices and construct an updated set of keep-out geofences from the ROI visibility graph per Algorithms 2 and 3 in Section 3.2. Figure 10 shows an example of the rectangular ROI, ROI obstacle polygon, and visibility graph generation pipeline. The “turn” flight planning visibility graph was constructed from keep-out geofences inside the ROI along with departure and destination locations.

5. Simulation Setup

Monte Carlo simulations were used to evaluate proposed airspace volumization strategies on the Manhattan map. Figure 11 shows the flowchart of pathfinding logic in our simulation setup. Pathfinding logic comprises four solution modules for the airspace geofencing algorithm. Once the start and end locations were defined, the keep-out geofence ROI polygons (Figure 10) were extracted from post-processed map data. Constant cruise altitude and terrain follower modules were generated by searching the intersection points between the buildings’ keep-out geofences and the line that connects UAS start and end waypoints. A pure turn solution was generated if both start and end locations were on the ground. If either start or end location was on the roof of the building (i.e., inside of the keep-out geofence), a constant cruise altitude algorithm was first used to find the flight path from the start/end point to the outside of the keep-out geofence, and the turn module solution was used to calculate the remaining flight path, creating a combined solution.

Control parameters are shown in

Table 1. Control parameters for geofenced flight planning case studies.

${\mathcal{V}}_{\mathit{vehicle}}$	${\mathit{\delta }}_{\mathit{vehicle}}$	${\mathit{\delta }}_{\mathit{building}}$	${\mathit{N}}_{\mathit{geofence}}$	${\mathit{z}}_{\mathit{cruise}}$
5 (m/s)	2 (m)	5 (m)	5	50 (m)

. To offer an experimentally grounded dataset, a prototype quadplane’s power consumption model [44] was used per

Table 2. Flight power consumption data from [44].

Climb	Descent	Forward Flight
312 (J/s)	300 (J/s)	328 (J/s)

to compute $P_{travel}$ in climb, cruise, and descent segments. A quadplane is a hybrid quadrotor/fixed-wing UAS designed to vertically takeoff and land in an urban environment. For our simulations, the quadrotor motors were active in all phases of flight; cruise power would otherwise be lower. Cost function weighting factors $\alpha =0.6,\beta =0.2,\gamma =0.0$ were chosen to prioritize minimum-distance solutions. Note that $\gamma$ was set to zero because building obstacles have static or permanent geofences.

6. Simulation Results

A total of 1010 Monte Carlo simulations were run with our Manhattan maps. For each case, start and destination points were randomly defined. Selected start/end altitudes ranged from 20 m above ground level to the highest building roof. The 20 m value represents an above-ground vertical climb to hover waypoint to ensure the multicopter is well clear of people on the ground when it begins executing its lateral flight plan. If both start and end points had altitudes less than 50 m, the cruise altitude for the turn solution was set at 50 m. Otherwise, cruise altitude was adjusted based on the following condition:

$$z_{cruise}=max\{h_{start},h_{end}\}if{h}_{start}>50\mathrm{m}\left|\right|h_{end}>50\mathrm{m}.$$

(3)

Our airspace volumization algorithm used this condition to choose one of the fixed-altitude datasets described in Section 4. As $z_{cruise}$ becomes larger, fewer obstacles were present, so fewer calculations were needed to generate and plan a flight through the visibility graph. For each case, cost values of the four planning options (“turn”, “constant cruise alt.”, “terrain follower”, “combined (constant cruise altitude + turn)” ) were calculated using Equation (2), and the minimum cost solution was selected as the best solution. Note in the Manhattan data the “wait” solution was never used because buildings are permanent, resulting in static geofence obstacles only.

Monte Carlo results offer an opportunity to compare our airspace volumization solutions against a manual fixed airway or “flight corridor” airspace design. A conventional fixed-altitude airway is permanently designated on a map to enable traffic “queues” to organize in a way that can be managed by human air traffic controllers. It is unclear whether UTM will benefit from this legacy design practice, motivating our comparison of path costs for our airspace volumization and fixed airway solutions. Unlike our airspace volumization, fixed airway/flight corridor maps only require a local search for the closest airway to join. The UAS then follows fixed airway routes until exiting over a short final segment to the end state. We generated a pair of low-altitude horizontal and vertical airways through our Lower Manhattan map to illustrate the airways concept and support our evaluation.

The designed vertical airway in Lower Manhattan follows Broadway, the north–south main thoroughfare, from its origin at Bowling Green to Houston Street. The horizontal airway follows Chambers Street from River Terrance in the west to Municipal Plaza in the east, and then follows the Brooklyn Bridge until it reaches the East River. We provided two sets of the same cross airways at 150 m and 500 m to offer each UAS an altitude choice since more obstacles are present at 150 m but the climb will be more substantial to 500 m. Figure 12 shows our manually defined airway corridors. To offer a practical comparison, only randomly generated start and end points that do not lie in the same quadrants (i.e., 712 out of 1010 simulation examples) were considered. If randomly-generated start and end points were located in the same quadrant, the airways were unused, thus offering no benefit to efficiency or airspace organization.

Figure 13 shows a top-down route view comparing our airspace volumization and flight corridor solutions. Cost weights $\alpha =0.6,\beta =0.2,\gamma =0.0$ were again used, so $d_{travel}$ was prioritized in minimizing overall cost. For the illustrated case, the “turn” solution is best. Flight corridor solution cost was in fact typically higher than any of our airspace volumization solutions. For the same example, altitude vs. time plots for each solution are shown in Figure 14. Examples of geofencing solutions are shown in Figure 15, Figure 16 and Figure 17, where three alternative trajectory solutions are generated, ensuring the avoidance of no-fly zones. Building keep-out geofences are shown in green.

For each Monte Carlo simulation, the minimum-cost $\mathcal{C}$ solution was compared to flight corridor solution costs at 150 m and 500 m per

Table 3. Number of cases where airspace volumization $vol$ has minimum cost (left) and number of cases where the flight corridor at 150 m has lower cost than the corridor at 500 m.

$\mathbf{\#}\mathbf{\{}{\mathcal{C}}_{\mathit{vol}\mathbf{.}\mathit{method}}\mathbf{<}{\mathcal{C}}_{\mathbf{150}\mathit{m}}$}	$\mathbf{\#}\mathbf{\{}{\mathcal{C}}_{\mathbf{150}\mathit{m}}\mathbf{<}{\mathcal{C}}_{\mathbf{500}\mathit{m}}$}
698 out of 712 cases	702 out of 712 cases

. Since the flight corridor at 150 m was almost always better than the flight corridor at 500 m, benchmark data compare the best solution obtained using dynamic airspace volumization with the flight corridor at 150 m. The results indicate our airspace geofencing volumization solutions generally have lower cost than flight corridors at 150 m or 500 m do.

The average distance and power consumption of the two-dimensional straight-line path between each start and destination location are shown in

Table 4. Average distance (d), power consumption (P), and minimum and maximum distances of 2D straight-line paths between start and destination states for the Monte Carlo simulations.

${\mathit{\mu }}_{{\mathit{d}}_{\mathbf{2}\mathit{D}\mathit{path}}}$	${\mathit{\mu }}_{{\mathit{P}}_{\mathbf{2}\mathit{D}\mathit{path}}}$	$\mathit{min}\mathbf{\left\{}{\mathit{d}}_{\mathbf{2}\mathit{D}\mathit{path}}\mathbf{\right\}}$	$\mathit{max}\mathbf{\left\{}{\mathit{d}}_{\mathbf{2}\mathit{D}\mathit{path}}\mathbf{\right\}}$
1391 (m)	91259 (J)	189 (m)	3003 (m)

.

The mean and standard deviation for $d_{travel}$, $p_{travel}$ for the minimum cost airspace volumization solution are summarized in

Table 5. Mean $\mu$ and standard deviation $\sigma$ of the minimum-cost airspace volumization solution.

${\mathit{\mu }}_{{\mathit{d}}_{\mathit{travel}}}$	${\mathit{\sigma }}_{{\mathit{d}}_{\mathit{travel}}}$	${\mathit{\mu }}_{{\mathit{P}}_{\mathit{travel}}}$	${\mathit{\sigma }}_{{\mathit{P}}_{\mathit{travel}}}$	$\mathit{min}\mathbf{\left\{}{\mathit{d}}_{\mathit{travel}}\mathbf{\right\}}$	$\mathit{max}\mathbf{\left\{}{\mathit{d}}_{\mathit{travel}}\mathbf{\right\}}$
1595 (m)	606 (m)	94,338 (J)	39,609 (J)	254 (m)	3349 (m)

. The percent frequency distributions of the four solution options are shown in Figure 18.

A similar analysis was performed to compute travel distance and power consumption statistics for the flight corridor solutions at 150 m and 500 m, as shown in

Table 6. Mean $\mu$ and standard deviation $\sigma$ of 150 m flight corridor solutions.

${\mathit{\mu }}_{{\mathit{d}}_{\mathbf{150}\mathit{m}}}$	${\mathit{\sigma }}_{{\mathit{d}}_{\mathbf{150}\mathit{m}}}$	${\mathit{\mu }}_{{\mathit{P}}_{\mathbf{150}\mathit{m}}}$	${\mathit{\sigma }}_{{\mathit{P}}_{\mathbf{150}\mathit{m}}}$	$\mathit{min}\mathbf{\left\{}{\mathit{d}}_{\mathbf{150}\mathit{m}}\mathbf{\right\}}$	$\mathit{max}\mathbf{\left\{}{\mathit{d}}_{\mathbf{150}\mathit{m}}\mathbf{\right\}}$
2303 (m)	820 (m)	149,084 (J)	53,449 (J)	479 (m)	4464 (m)

and

Table 7. Mean $\mu$ and standard deviation $\sigma$ of 500 m flight corridor solutions.

${\mathit{\mu }}_{{\mathit{d}}_{\mathbf{500}\mathit{m}}}$	${\mathit{\sigma }}_{{\mathit{d}}_{\mathbf{500}\mathit{m}}}$	${\mathit{\mu }}_{{\mathit{P}}_{\mathbf{500}\mathit{m}}}$	${\mathit{\sigma }}_{{\mathit{P}}_{\mathbf{500}\mathit{m}}}$	$\mathit{min}\mathbf{\left\{}{\mathit{d}}_{\mathbf{500}\mathit{m}}\mathbf{\right\}}$	$\mathit{max}\mathbf{\left\{}{\mathit{d}}_{\mathbf{500}\mathit{m}}\mathbf{\right\}}$
2796 (m)	788 (m)	179,363 (J)	51,502 (J)	1142 (m)	4836 (m)

.

Dynamic airspace volumization and flight corridor solutions at 150 m are normalized by the two-dimensional straight-line path parameters, indicating the percent increase in average travel distance and power consumption. A normalized benchmark comparison is shown in

Table 8. Normalized travel distance comparison between airspace geofencing and 150 m flight corridor solutions.

${\mathit{\mu }}_{{\mathit{d}}_{\mathit{travel}}}\mathbf{/}{\mathit{\mu }}_{{\mathit{d}}_{\mathbf{2}\mathit{D}\mathit{path}}}$	${\mathit{\mu }}_{{\mathit{P}}_{\mathit{travel}}}\mathbf{/}{\mathit{\mu }}_{{\mathit{P}}_{\mathbf{2}\mathit{D}\mathit{path}}}$	${\mathit{\mu }}_{{\mathit{d}}_{\mathbf{150}\mathit{m}}}\mathbf{/}{\mathit{\mu }}_{{\mathit{d}}_{\mathbf{2}\mathit{D}\mathit{path}}}$	${\mathit{\mu }}_{{\mathit{P}}_{\mathbf{150}\mathit{m}}}\mathbf{/}{\mathit{\mu }}_{{\mathit{P}}_{\mathbf{2}\mathit{D}\mathit{path}}}$
115 (%)	103 (%)	166 (%)	163 (%)

. On average, our 3-D airspace geofencing solution increased travel distance by 15% and power consumption by 3% compared to 2-D straight-line paths from start states to destination states. On the other hand, the travel distance increased by 66 % and power increases by 63% when comparing minimum-cost 3-D geofencing solutions with 150 m flight corridor solutions. This analysis indicates our airspace geofencing algorithm generates routes that offer nontrivial distance (time) and power (energy) reductions relative to flight corridor paths, at least for Manhattan.

All simulations were executed on a standard laptop PC using uncompiled MATLAB code. The mean runtime and standard deviation over all 1010 Monte Carlo simulations were computed. The average runtime was 10.98 s with $\sigma =12.68$. The minimum runtime was 0.13 s, and the maximum runtime was 90.66 s. As the number of obstacles inside the fly-zone increase, runtime also increased, as might be expected. A more computationally efficient visibility graph algorithm could be implemented in future work [45], particularly with a large obstacle set. Migration from uncompiled MATLAB to a compiled code (e.g., in C++) will also improve performance.

A Monte Carlo simulation generated a suite of random launch (start) and landing (end) points for a single sUAS flying in Lower Manhattan. Start and end points were either located on the ground or a flat building roof to simulate the diverse sUAS flight cases that might be encountered in a densely populated urban environment. Keep-out geofences were generated at each building or around blocks of clustered buildings, representing no-fly zones for the sUAS. Our airspace geofencing pipeline successfully generated flight plans and enclosing geofence volumes for four flight trajectory solution options for all 1010 Monte Carlo simulations. The minimum distance and energy cost was chosen as the best solution. Our geofence-based path planning solutions outperformed a more traditional fixed flight corridor routing option.

Our Monte Carlo simulations did not limit the maximum altitude for UAS flight, so the trajectories for some solutions had cruising altitudes greater than 400 ft AGL, beyond the UTM and sUAS ceiling. Our Monte Carlo results showed the “combined” solution option (i.e., constant cruise and turn) was preferred most often. A maximum altitude constraint would eliminate all solutions that climbed above UTM-managed airspace, likely resulting in the more frequent use of visibility graph “turning” solutions. The results in Table 8 showed that our algorithm generates solutions that are 51% and 60% more efficient than flight corridor solutions at 150 m altitude in terms of normalized average flight distance and power consumption, respectively. It is likely that for AAM airspace corridors accessible to sUAS, above 400 ft AGL will be designated. For longer-distance flights, a flight plan might use an efficient dynamically geofenced route to/from a high-altitude transit tube, potentially requiring a hybrid combination of dynamic flight planning and geofencing at UTM-managed altitudes and fixed corridor transit at altitudes managed by legacy ATM.

7. Case Study with sUAS Route Deconfliction

The above results describe single geofenced sUAS routes through a complex urban landscape. In general, UTM will manage multiple sUAS in shared airspace. This section presents a case study illustrating how the proposed geofencing pipeline supports multiple-sUAS deconfliction. For this study, we assume airspace is allocated first-come-first-served. Suppose $sUA{S}_1$ and $sUA{S}_2$ request flight plans each defined by departure and destination coordinates (WGS 84/UTM zone 18N), cruise speed, and targeted cruise altitude as defined in

Table 9. Flight plan parameters for $sUA{S}_1$ and $sUA{S}_2$.

	${\mathit{P}}_{\mathit{Departure}}\mathbf{\left(}\mathbf{m}\mathbf{\right)}$	${\mathit{P}}_{\mathit{Destination}}\mathbf{\left(}\mathbf{m}\mathbf{\right)}$	${\mathit{V}}_{\mathit{UAS}}\mathbf{\left(}\mathbf{m}\mathbf{/}\mathbf{s}\mathbf{\right)}$	${\mathit{h}}_{\mathit{targetCruise}}\mathbf{\left(}\mathbf{m}\mathbf{\right)}$
$sUA{S}_1$	[584,085; 4,508,093; 0]	[584,248; 4,506,598; 0]	30	50
$sUA{S}_2$	[583,600; 4,507,000; 0]	[584,460; 4,507,660; 0]	20	50

. Further, suppose $sUA{S}_1$ receives approval for its flight plan and associated geofence volume before $sUA{S}_2$ contacts UTM. $sUA{S}_2$ will then need to plan a flight that avoids the Manhattan terrain and building geofences as well as the flight trajectory geofence wrapping the $sUA{S}_1$ route. Figure 19 shows the resulting flight plans for $sUA{S}_2$ as a top-down route view comparing our airspace volumization and flight corridor solutions. For this example, altitude vs. time plots for the $sUA{S}_2$ solutions are shown in Figure 20.

Since $sUA{S}_1$ and $sUA{S}_2$ have the same target cruise altitude, a maneuver was required for $sUA{S}_2$ to deconflict its “turn” route from the $sUA{S}_1$ flight trajectory, making this the longest distance solution option. On the other hand, the “constant cruise altitude” and “terrain follower” solutions were not influenced by the $sUA{S}_1$ trajectory because the minimum building height along the straight line path from departure to destination for $sUA{S}_2$ was greater than $sUA{S}_1$’s target cruise altitude. If building height placed $sUA{S}_2$ at $sUA{S}_1$’s cruise altitude, $sUA{S}_2$ would also need to climb over the $sUA{S}_1$ geofence. Note that if $sUA{S}_1$’s airspace volume reservation duration was minimized using SDG or MDG, $sUA{S}_2$’s path had a lower probability of being impacted. Example 3-D $sUA{S}_2$ in “turn”, “constant cruise altitude”, “terrain follower” solutions are shown in Figure 21, Figure 22 and Figure 23.

8. Conclusions and Future Work

This paper applied airspace geofencing volumization and path planning to support UTM management of low-altitude airspace. Layered durational geofences wrapping flight trajectories ensure the UAS will fly without conflict in designated or reserved airspace volumes. Our airspace volumization algorithms generated four conflict-free paths for any keep-in/keep-out geofence volume set based on turn, constant cruise, terrain follower and combination turn/cruise options. The algorithm ranked these paths using a weighted distance, energy, and time cost function, then selected the minimum-cost solution. A city map data of Lower Manhattan was used to construct keep-out geofences around buildings. Monte Carlo simulation studies validate our geofence algorithms and support the statistical characterization of performance including run time. A benchmark comparison of our dynamically geofenced flight plans and conventional flight corridor solutions is provided, showing that our solutions reduce flight distance and power compared to fixed corridor solutions. A case study of two sUAS flight planning demonstrated how the proposed geofencing pipeline supports multiple sUAS deconfliction. Algorithms and definitions from this paper can contribute to future UTM dynamic airspace geofencing operational standards.

This work simplifies flight planning to geometric paths. Future work will incorporate aircraft dynamics into flight plans and geofence layer sizing, extend airspace volumization to enclose cooperative groups of sUAS. Additionally, the altitude constraint and other factors such as day/night local population density, GPS dependency, air traffic volume, and vehicle-specific parameters should be incorporated in the geofenced path planning algorithm to generate solutions that are more realistic for UTM-specific applications. We hope to apply machine learning to large-scale flight track data and urban maps to generalize and optimize geofencing volume designs based on area topology, day/night occupancy, infrastructure, and existing air traffic patterns. We will also explore auto-code generation and Python/C++ implementations to improve path planning computational performance.