Date of Award

3-2004

Document Type

Thesis

Degree Name

Master of Science

Department

Department of Electrical and Computer Engineering

First Advisor

Gilbert L. Peterson, PhD

Abstract

Robot mapping remains one of the most challenging problems in robot programming. Most successful methods use some form of occupancy grid for representing a mapped region. An occupancy grid is a two dimensional array in which the array cells represents (x,y) coordinates of a cartesian map. This approach becomes problematic in mapping large environments as the map quickly becomes too large for processing and storage. Rather than storing the map as an occupancy grid, our robot (equipped with ultrasonic sonars) views the world as a series of connected spaces. These spaces are initially mapped as an occupancy grid in a room-by-room fashion using a modified version of the Histogram In Motion Mapping (HIMM) algorithm extended in this thesis. As the robot leaves a space, denoted by passing through a doorway, it converts the grid to a polygonal representation using a novel edge detection technique. Then, it stores the polygonal representation as rooms and hallways in a set of Absolute Space Representations (ASRs) representing the space connections. Using this representation makes navigation and localization easier for the robot to process. The system also performs localization on the simplified cognitive version of the map using an iterative method of estimating the maximum likelihood of the robot's correct position. This is accomplished using the Expectation Maximization algorithm. Treating vector directions from the polygonal map as a Gaussian distribution, the Expectation Maximization algorithm is applied, for the first time, to find the most probable correct pose while using a cognitive mapping approach.

AFIT Designator

AFIT-GCS-ENG-04-10

DTIC Accession Number

ADA424280

Download

Share

COinS