# Airspace Geofencing and Flight Planning for Low-Altitude, Urban, Small Unmanned Aircraft Systems
###### Abstract
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. Figure 1: UAS airspace geofencing examples. The left figure shows a keep-out geofence (red) around One World Trade Center in New York City. A transiting UAS keeps clear of this geofence with a path wrapped by a trajectory or keep-in geofence (yellow). The right figure shows a wind turbine being inspected by a small UAS. During inspection, the usual wind turbine keep-out geofence (red) is expanded as depicted in green to also enclose the inspection UAS. Any other nearby UAS will keep clear of this expanded keep-out geofence (green) during inspection activities. This geofence design assures separation between the two illustrated UAS. 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 deconfiction 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 deconfiction, while Section 8 concludes the paper. Figure 2: Airspace and environment geofencing functionality and data flow.