Search

The problem of robotic mapping and localization is that of constructing a spatial model (the map) of an environment and estimating positions of robots inside the map. The solution to the problem is a fundamental requirement to enable mobile robots to operate autonomously in their environments. It is relatively straightforward to solve the problem under certain conditions with perfect sensors and unlimited computational power. The challenge arises when a mobile robot needs mapping and localization available outside the restricted operational envelope that is determined by scale, robustness and the amount of prior data needed. In this thesis, we describe several methods that expand this operational envelope, increasing the availability of position estimates to a robot. The idea of "high availability" is common in other system design domains, and we extend that idea here to robot navigation systems that must provide usable data in as a broad range of conditions as possible. At the heart of mapping and localization is optimization. The computational complexity of the optimization limits the scale of maps that can be built in most robot systems, which limits the availability of those methods to relatively small environments. In this thesis, we present a Simultaneous Localization and Mapping (SLAM) algorithm, AprilSAM, that can rapidly estimate the maximum likelihood state for factor graph-based large scale mapping. The algorithm selects between a batch solver and an incremental solver intelligently to balance the speed and the accuracy of the state estimation. As AprilSAM takes less running time than state-of-the-art approaches to achieve the same online mapping performance, it achieves high availability. Performing global localization in a new environment often requires lots of preparations. This limits the availability of algorithms only to familiar environments. Global Positioning System (GPS) sometime could supply the positioning information immediately for outdoor environments. For indoor environments, we propose a factor graph-based localization system, FLAG, that provides global positioning based on floor plans. FLAG significantly reduces the amount of prior information required to perform indoor localization as it doesn't require sending robots into the environment for mapping. Pose estimation in a prior map is a common online localization method for robot navigation. The robustness of a localization system directly depends on the quality of the prior map. A high-resolution map provides a detailed representation of the world, but it is susceptible to feature aliasing since a sensor’s view is noisy and often ambiguous. Such aliasing leads to poor localization performance which limits the availability of algorithms in complex environments. In this thesis, we present a machine learning-based map optimization algorithm, MOSS, that learns to adjust maps to support more robust localization. MOSS achieves high availability by producing maps that support better localization than the original full map.

Time Delay of Arrival (TDOA) based algorithms and Steered Response Power (SRP) based algorithms are two most commonly used methods for sound source detection and localization. SRP is more robust under high reverberation and multi-target conditions, while TDOA is less computationally intensive. This thesis introduces a modified TDOA algorithm, TDOA delay table search (TDOA-DTS), that has more stable performance than the original TDOA, and requires only 4% of the SRP computation load for a 3-dimensional space of a typical room. A 2-step adaptive thresholding procedure based on a Weibull noise peak distributions for the cross-correlations and a binomial distribution for combing potential peaks over all microphone pairs for the final detection. The first threshold limits the potential target peaks in the microphone pair cross-correlations with a user-defined false-alarm (FA) rates. The initial false-positive peak rate can be set to a higher level than desired for the final FA target rate so that high accuracy is not required of the probability distribution model (where model errors do not impact FA rates as they work for threshold set deep into the tail of the curve). The final FA rate can be lowered to the actual desired value using an M out of N (MON) rule on significant correlation peaks from different microphone pairs associated is a point in the space of interest. The algorithm is tested with simulated and real recorded data to verify resulting FA rates are consistent with the user-defined rates down to 10-6.