# Airspace Geofencing and Flight Planning for Low-Altitude, Urban, Small Unmanned Aircraft Systems
## 3 Definitions and Algorithms
### 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}. \tag{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 [PERSON]'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  
Figure 4: Example of reducing number of vertices to simplify the associated visibility graph. The left illustration shows three original polygons. The right illustration shows the polygons after applying the vertex downsampling algorithm. \(n_{maxVert}\) and \(p_{dunSingle}\) are 15 and 60%, respectively. The time complexity of visibility graph generation is \(O(n^{2}log(n))\), where \(n\) is the total number of vertices in all polygons. The number of vertices in the lower polygon illustrated here is reduced from 15 to 9. Figure 5: Illustration of rectangular ROI generation. Start point, destination point, and ROI initial buffer size \(\delta_{ROI}\) are used to initialize the rectangular ROI per Algorithm 3.  
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*d_{travel}+\beta*P_{travel}+\gamma*t_{wait}. \tag{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.