# Airspace Geofencing and Flight Planning for Low-Altitude, Urban, Small Unmanned Aircraft Systems
## 3 Definitions and Algorithms
### 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. ```
1:\(\mathcal{P}_{climb},\mathcal{G}_{climb}]\gets MSG(\mathcal{W}[1:2], \mathcal{V},t_{climb},\mathcal{N}_{geo},\delta_{vehicle})\lhd\)generate climb geofence
2:\([\mathcal{P}_{desc},\mathcal{G}_{desc}]\gets MSG(\mathcal{W}[end-1:end], \mathcal{V},t_{desc},\mathcal{N}_{geo},\delta_{vehicle})\lhd\)desent geofence
3:
4:\(\mathcal{P}_{curise}\leftarrow[\mathcal{P}_{climb}[end-1:end],\mathcal{W}[3:end- 2],\mathcal{P}_{desc}[1:2]]\lhd\)3-D Cruise flight
5:\([\mathcal{G}_{curise}]\gets MSG(2 dOperVol(\mathcal{P}_{curise},\delta_{vehicle}),h_{ cruise})\lhd\)Generate cruise geofence
6:\(\mathcal{P}_{traj}\leftarrow[\mathcal{P}_{climb};\mathcal{P}_{curise};\mathcal{P}_{desc}]\)
7:\(\mathcal{G}\leftarrow[\mathcal{G}_{climb};\mathcal{G}_{curise};\mathcal{G}_{ desc}]\)
8:return\([\mathcal{P}_{traj},\mathcal{G}]\)
```  
**Algorithm 1** 3D Flight Trajectory Operational Volumization (_3 dOperVol_). **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_{criise}\)  
**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}]\gets MSG(\mathcal{W}[1:2], \mathcal{V},t_{climb},\mathcal{N}_{geo},\delta_{vehicle})\lhd\)generate climb geofence
2:\([\mathcal{P}_{desc},\mathcal{G}_{desc}]\gets MSG(\mathcal{W}[end-1:end], \mathcal{V},t_{desc},\mathcal{N}_{geo},\delta_{vehicle})\lhd\)desent geofence
3:
4:\(\mathcal{P}_{curise}\leftarrow[\mathcal{P}_{climb}[end-1:end],\mathcal{W}[3:end- 2],\mathcal{P}_{desc}[1:2]]\lhd\)3-D Cruise flight
5:\([\mathcal{G}_{curise}]\gets MSG(2 dOperVol(\mathcal{P}_{curise},\delta_{vehicle}),h_{ cruise})\lhd\)Generate cruise geofence
6:\(\mathcal{P}_{traj}\leftarrow[\mathcal{P}_{climb};\mathcal{P}_{curise};\mathcal{P}_{desc}]\)
7:\(\mathcal{G}\leftarrow[\mathcal{G}_{climb};\mathcal{G}_{curise};\mathcal{G}_{ desc}]\)
8:return\([\mathcal{P}_{traj},\mathcal{G}]\)
```  
**Algorithm 2** 3D Flight Trajectory Operational Volumization (_3 dOperVol_). **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_{criise}\)  
**Outputs:** 3-D Flight Trajectory \(\mathcal{P}_{traj}\), 3-D Geofence for 3-D Flight Trajectory \(\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.