* Faculty       * Staff       * Contact       * Institute Directory
* Undergraduate       * Graduate       * Institute Admissions: Undergraduate | Graduate      
* Events       * Institute Events      
* Lab Manual       * Institute Computing      
No Menu Selected

* Research

Ph.D. Theses

Mapping with Limited Sensing

By Kristopher Beevers
Advisor: Wesley Huang
January 15, 2007

For a mobile robot to interact with its environment in complex ways, it must possess a model of the environment, i.e., a map. It is generally infeasible for an accurate map to be constructed by hand and provided to the robot prior to deployment, so the robot must build a map online.

Most mapping algorithms assume the availability of frequent, high fidelity feedback from the environment acquired using sensors such as scanning laser rangefinders. Such sensors provide dense, accurate, and long-range data at great expense: they typically cost thousands of (US) dollars, consume significant power and space resources, and require the use of powerful computers for data processing. These sensors are therefore unsuitable for deployment in many applications, e.g., consumer robots, disposable robots for search and rescue or hazardous material detection, or mobile sensor networks.

This thesis instead examines the mapping problem in the context of limited sensing. Sensors such as infrared rangefinder arrays are inexpensive, low-power, and small, but they give only low-resolution, short-range feedback about the environment and are thus difficult to use for mapping. The main contributions of this thesis are a theoretical characterization of the relative capabilities of mapping sensors, and the development and demonstration of several practical algorithms for building maps with real, inexpensive sensors.

The thesis begins by examining a generalized model of mapping sensors. The model is applied with a simple mapping algorithm to characterize the space of sensors in terms of their suitability for mapping, and theoretical bounds on map error in terms of the capabilities of the sensor are derived. The thesis then turns to practical algorithms for simultaneous localization and mapping (SLAM) with limited sensors. In the context of particle filtering SLAM, an approach is formulated for accumulating low-resolution sensor measurements in "multiscans" that contain sufficient information for feature extraction and data association. To manage uncertainty due to limited feedback, a new technique for incorporating prior knowledge in the mapping process is developed, and new sampling techniques to combat estimation degeneracies in particle filtering SLAM are described. The algorithms presented in the thesis are validated experimentally through simulation, tests on well-known benchmark data sets, and implementation and deployment on real robots, and a working implementation of particle filtering SLAM on an 8-bit microcontroller with a small infrared rangefinder array is described in detail.

* Return to main PhD Theses page