In this dissertation we present advances in developing an autonomous air vehicle capable of navigating through unknown, indoor environments. The problem imposes stringent limits on the computational power available onboard the vehicle, but the environment necessitates using 3D sensors such as stereo or RGB-D cameras whose data requires significant processing. We address the problem by proposing and developing key elements of a relative navigation scheme that moves as many processing tasks as possible out of the time-critical functions needed to maintain flight. We present in Chapter 2 analysis and results for an improved multirotor helicopter state estimator. The filter generates more accurate estimates by using an improved dynamic model for the vehicle and by properly accounting for the correlations that exist in the uncertainty during state propagation. As a result, the filter can rely more heavily on frequent and easy to process measurements from gyroscopes and accelerometers, making it more robust to error in the processing intensive information received from the exteroceptive sensors. In Chapter 3 we present BERT, a novel approach to map optimization. The goal of map optimization is to produce an accurate global map of the environment by refining the relative pose transformation estimates generated by the real-time navigation system. We develop BERT to jointly optimize the global poses and relative transformations. BERT exploits properties of independence and conditional independence to allow new information to efficiently flow through the network of transformations. We show that BERT achieves the same final solution as a leading iterative optimization algorithm. However, BERT delivers noticeably better intermediate results for the relative transformation estimates. The improved intermediate results, along with more readily available covariance estimates, make BERT especially applicable to our problem where computational resources are limited. We conclude in Chapter 4 with analysis and results that extend BERT beyond the simple example of Chapter 3. We identify important structure in the network of transformations and address challenges arising in more general map optimization problems. We demonstrate results from several variations of the algorithm and conclude the dissertation with a roadmap for future work.

Heavy reliance on GPS is preventing unmanned air systems (UAS) from being fully inte- grated for many of their numerous applications. In the absence of GPS, GPS-reliant UAS have difficulty estimating vehicle states resulting in vehicle failures. Additionally, naively using erro- neous measurements when GPS is available can result in significant state inaccuracies. We present a simultaneous localization and mapping (SLAM) solution to GPS-degraded navigation that al- lows vehicle state estimation and control independent of global information. Optionally, a global map can be constructed from odometry measurements and can be updated with GPS measurements while maintaining robustness against outliers.We detail a relative navigation SLAM framework that distinguishes a relative front end and global back end. It decouples the front-end flight critical processes, such as state estimation and control, from back-end global map construction and optimization. Components of the front end function relative to a locally-established coordinate frame, completely independent from global state information. The approach maintains state estimation continuity in the absence of GPS mea- surements or when there are jumps in the global state, such as after map optimization. A global graph-based SLAM back end complements the relative front end by constructing and refining a global map using odometry measurements provided by the front end.Unlike typical approaches that use GPS in the front end to estimate global states, our unique back end uses a virtual zero and virtual constraint to allow intermittent GPS measurements to be applied directly to the map. Methods are presented to reduce the scale of GPS induced costs and refine the map’s initial orientation prior to optimization, both of which facilitate convergence to a globally consistent map. The approach uses a state-of-the-art robust least-squares optimization algorithm called dynamic covariance scaling (DCS) to identify and reject outlying GPS measure- ments and loop closures. We demonstrate our system’s ability to generate globally consistent and aligned maps in GPS-degraded environments through simulation, hand-carried, and flight test re- sults.