Indoor robot navigation using a symbolic landmark map

Abstract

This dissertation addresses the problem of a mobile robot autonomously estimating its location within an a priori map using sensed information. A 2D indoor robot world is sparsely represented as a collection of vertical landmarks encoded as an attributed edge graph. This map is matched to data obtained from a single image with depth to feature information estimated by ultrasonic sensors. The goal of this work is the rapid recovery of an estimated position within a previously mapped domain from an initial state of complete uncertainty. The structure provided by indoor environments permit geometric assumptions that enable rapid vertical landmark detection and classification. Pairs of vertical edges are extracted from monocular images and candidate landmarks identified. Methods of fuzing ultrasonic estimated range data with extracted vertical edge features from a single image are developed. Experiments have demonstrated that the proposed methods classified vertical landmarks with 84 percent accuracy over a large library of domain data. Further experiments lead to the definition of a footprint for accurate ultrasonic sensing. Detailed composite error models for the ultrasonic and imaging systems are developed and used to examine the performance of the proposed sensing geometries. Analysis and experiments lead to the definition of a general navigation envelope that enhances sensing accuracy while only mildly restricting travel and locomotion. An independent suite of test data combined with the developed composite error models are used to conduct a large simulation study on the performance of this methodology in real and synthetic domains. Several heuristic methods are proposed for recovering from sensing errors. Simulation results show that a deterministic error recovery approach outperforms the heuristic methods in measures of speed and accuracy. In one large domain, position recovery is obtained in less than 12 seconds in the absence of error and in less than 15 seconds with realistic modeled error; results show 98 percent correct pose decisions. Similar time and accuracy performances are observed in other domains. The time performance is limited not by the solution approach, but by the mechanical limitations of the robot base. Travel speeds up to 30 feet per second could be supported.