|Mapping with limited sensing||
Kristopher R. Beevers
Rensselaer Polytechnic Institute
Algorithmic Robotics Laboratory
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.
The following software was developed in the course of my thesis research. It is posted here in the hopes that others may find it useful in research or application. Most of the source code is C/C++, and all of it was compiled and used on a Linux 2.6.x system. All of the software was implemented by myself unless otherwise noted. Each package contains a README file with package-specific notes.
My ability to support this code is limited, but if you have specific questions, send them and I will help if I can.
WARNING: this code is "research-ware" and most of it is definitely not suitable for production use. It is messy, poorly commented, largely unoptimized, etc. Nevertheless, it implements most of the algorithms described in my thesis and you may find it useful for better understanding them, implementing them yourself, and so on.
gridsim2.tar.gz (42 KB)
slam3.tar.gz (79 KB)
ratbot-slam.tar.gz (34 KB)
fixedpoint.tar.gz (20 KB)
ktracker.tar.gz (13 MB, source + calibration data)
ktracker-src.tar.gz (23 KB, source only)