Small Unmanned Aircraft Systems (sUAS) are expected to proliferate in low-altitude airspace over the coming decade requiring flight near buildings and over people.Robust urgent landing capabilities including landing site selection are required.

However, conventional fixed-wing emergency landing sites such as open fields and empty roadways are rare in and around cities. This motivates our work to uniquely consider a city's many unoccupied flat rooftops as possible nearby landing sites. We propose novel methods to identify flat rooftop buildings, isolate their flat surfaces, and find touchdown points that maximize distance to obstacles. We model flat rooftop surfaces as polygons that capture their boundaries and possible obstructions on them.

This thesis offers five specific contributions to support urgent rooftop landing. First, the Polylidar algorithm is developed which enables efficient non-convex polygon extraction with interior holes from 2D point sets. A key insight of this work is a novel boundary following method that contrasts computationally expensive geometric unions of triangles. Results from real-world and synthetic benchmarks show comparable accuracy and more than four times speedup compared to other state-of-the-art methods.

Second, we extend polygon extraction from 2D to 3D data where polygons represent flat surfaces and interior holes representing obstacles. Our Polylidar3D algorithm transforms point clouds into a triangular mesh for which planar segmentation and polygon extraction occur in parallel. Dominant plane normals are identified and used to parallelize and regularize planar segments in the mesh. Immediately after a plane has been segmented a polygon extraction task is dynamically spawned. The result is a versatile and extremely fast algorithm for non-convex polygon extraction of 3D data.

Third, we propose a framework for classifying roof shape (e.g., flat) within a city. We process satellite images, airborne LiDAR point clouds, and map building outlines to generate both a LiDAR image and a cropped satellite image of each building. Convolutional neural networks are independently trained for each modality to extract high level features and sent to a random forest classifier for final roof shape prediction. This research contributes the largest multi-city annotated dataset with over 4,500 rooftops used to train and test models. Our results show flat rooftops are identified with 90% precision and recall.

Fourth, we integrate Polylidar3D and our roof shape prediction model to reliably extract flat rooftop surfaces from archived data sources. We model risk as an innovative combination of landing site and path risk metrics and conduct a multi-objective Pareto front analysis for sUAS urgent landing in cities. We create a multi-goal planner that guarantees a risk-optimal solution is found rapidly by avoiding exploration of high-risk options. The proposed emergency planning framework enables a sUAS to select an emergency landing site and corresponding flight plan with minimum total risk.

Fifth, we verify a chosen rooftop landing site on real-time vertical approach with on-board LiDAR and camera sensors. Our method contributes an innovative fusion of semantic segmentation using neural networks with computational geometry as a hybrid algorithm robust to individual sensor and method failure. We construct a high-fidelity simulated city in the Unreal game engine with a statistically-accurate representation of rooftop obstacles. We show our method leads to greater than 4% improvement in intersection-over-union (IOU) accuracy in landing site identification compared to using LiDAR only. Finally, we evaluate results in real-world indoor flight experiments.