Computer Science Department
School of Computer Science, Carnegie Mellon University


Approximate Continuous Belief Distributions for Exploration

Wennie Tabib

Ph.D. Thesis

May 2019


Keywords: NA

Efficient and robust robotic exploration has the potential to solve significant challenges and save lives when disasters occur underground. Cave rescues to extricate trapped or lost spelunkers are difficult and demanding endeavors performed dozens of times each year in the United States in environments that are often neither mapped nor surveyed and have limited to nonexistent communications due to the convoluted nature of underground voids. Underground nuclear waste storage facilities become inaccessible to humans when radiation leaks occur, so efficient pose estimation and mapping to localize radiation leaks is of the utmost importance. Catastrophic sinkholes appear suddenly in areas of karst terrain throughout the United States, swallowing homes, and trapping residents in debris.

Without reliable communications, robots must operate autonomously to efficiently explore these subterranean environments, but many Simultaneous Localization and Mapping (SLAM) techniques do not generate maps fit for active perception. Occupancy grid map techniques are typically used after solving the SLAM problem to generate feasible trajectories. The advantage of occupancy grid maps is they may be updated quickly, but the gains in speed come at the cost of either memory efficiency or fidelity. In exploration contexts, systems maneuvering in large environments must elect to decrease the resolution of the occupancy grid map in order to mitigate explosive memory demands or suffer increasingly slower speeds when manipulating occupancy grid maps with small cell sizes. For computationally constrained systems, the latter is prohibitive, but employing low-resolution environment representations has significant disadvantages. For example, small passageways and hazards may be obscured and rich details obliterated.

Gaussian Mixture Models (GMMs) are well suited to compactly represent sensor observations and model the structural correlations present in the environment. These generative models are advantageous as compared to voxelized representations that assume independence between cells and lose dependencies between spatially distinct locations. GMM-based perception tasks such as registration have been studied, but solutions are either not real-time viable or have not been evaluated with large, realworld datasets. There are few works that address the viability of leveraging these models for tasks such as SLAM and exploration, because a significant challenge to overcome is the time needed to create these models.

This thesis develops information-theoretic exploration with approximate continuous distributions that unifies high-resolution, low memory footprint environment modeling with occupancy mapping techniques while remaining amenable to local and global pose updates. This is possible through innovations in robust distribution to distribution registration, arbitrary resolution occupancy modeling, real-time information-theoretic exploration, and simultaneous localization and mapping. These developments are evaluated in simulation, with real-world datasets, and onboard an aerial system and tested in complex environments. The results demonstrate that leveraging compact generative models yields substantial gains over state-of-the-art methods in model fidelity, accuracy, and memory efficiency.

147 pages

Thesis Committee:
Nathan Michael (Co-Chair)
Red Whittaker (Co-Chair)
Nancy Pollard
Debadeepta Dey (Microsoft Research)

Srinivasan Seshan, Head, Computer Science Department
Tom M. Mitchell, Interim Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by