Date of Award

3-2007

Document Type

Thesis

Degree Name

Master of Science

Department

Department of Electrical and Computer Engineering

First Advisor

Gilbert L. Peterson, PhD

Abstract

For a robot to build a map of its surrounding area, it must have accurate position information within the area, and to obtain accurate position information within the area, the robot needs to have an accurate map of the area. This circular problem is the Simultaneous Localization and Mapping (SLAM) problem. An efficient algorithm to solve it is FastSLAM, which is based on the Rao-Blackwellized particle filter. FastSLAM solves the SLAM problem for single-robot mapping using particles to represent the posterior of the robot pose and the map. Each particle of the filter possesses its own global map which is likely to be a grid map. The memory space required for these maps poses a serious limitation to the algorithm's capability when the problem space is large. The problem will only get worse if the algorithm is adapted to multi-robot mapping. This thesis presents an alternate mapping algorithm that extends the single-robot FastSLAM algorithm to a multi-robot mapping algorithm that uses Absolute Space Representations (ASR) to represent the world. But each particle still maintains a local grid to map its vicinity and periodically this grid map is converted into an ASR. An ASR expresses a world in polygons requiring only a minimal amount of memory space. By using this altered mapping strategy, the problem faced in FastSLAM when mapping a large domain can be alleviated. In this algorithm, each robot maps separately, and when two robots encounter each other they exchange range and odometry readings from their last encounter to this encounter. Each robot then sets up another filter for the other robot's data and incrementally updates its own map, incorporating the passed data and its own data at the same time. The passed data is processed in reverse by the receiving robot as if a virtual robot is back-tracking the path of the other robot. The algorithm is demonstrated using three data sets collected using a single robot equipped with odometry and laser-range finder sensors.

AFIT Designator

AFIT-GCE-ENG-07-06

DTIC Accession Number

ADA471795

Download

Share

COinS