This monograph is a revised version of the D.Phil. thesis of the first author, submitted in October 1990 to the University of Oxford. This work investigates the problem of mobile robot navigation using sonar. We view model-based navigation as a process of tracking naturally occurring environment features, which we refer to as "targets". Targets that have been predicted from the environment map are tracked to provide that are observed, but not predicted, vehicle position estimates. Targets represent unknown environment features or obstacles, and cause new tracks to be initiated, classified, and ultimately integrated into the map. Chapter 1 presents a brief definition of the problem and a discussion of the basic research issues involved. No attempt is made to survey ex­ haustively the mobile robot navigation literature-the reader is strongly encouraged to consult other sources. The recent collection edited by Cox and Wilfong [34] is an excellent starting point, as it contains many of the standard works of the field. Also, we assume familiarity with the Kalman filter. There are many well-known texts on the subject; our notation derives from Bar-Shalom and Fortmann [7]. Chapter 2 provides a detailed sonar sensor model. A good sensor model of our approach to navigation, and is used both for is a crucial component predicting expected observations and classifying unexpected observations.

Preface.- 1 Introduction.- 1.1 The Navigation Problem.- 1.2 Why Use Sonar?.- 1.3 Choosing a Representation.- 1.4 The Kalman Filter.- 1.5 Data Association.- 1.6 Overview.- 2 A Sonar Sensor Model.- 2.1 Introduction.- 2.2 Previous Work.- 2.3 Terminology.- 2.4 The Physics of Sonar.- 2.5 Predicting Sonar Data.- 2.6 Theory vs Practice.- 2.7 Regions of Constant Depth.- 2.8 Sparse vs Densely Sampled Data.- 2.9 Discussion.- 2.10 Summary.- 3 Model-based Localization.- 3.1 Introduction.- 3.2 Problem Statement.- 3.3 The Basic Localization Cycle.- 3.4 Algorithm Summary.- 3.5 Off-line Processing of Densely Sampled Data.- 3.6 Sparse Data Error Model.- 3.7 Tracking Planar Targets.- 3.8 Tracking Planes, Corners, and Cylinders.- 3.9 Hands-off Localization Results.- 3.10 Discussion.- 3.11 Alternative Approaches.- 3.12 Summary.- 4 Map Building.- 4.1 Introduction.- 4.2 Specular Event Interpretation.- 4.3 Rules for RCD-based Sonar Interpretation.- 4.4 Map Building via Track Initiation.- 4.5 Experimental Results.- 4.6 Multiple Hypothesis Track Initiation.- 4.7 Alternative Approaches.- 4.8 Why Build Accurate Maps?.- 5 Simultaneous Map Building and Localization.- 5.1 A Unified Approach to Navigation.- 5.2 Research Issues.- 5.3 Restatement of the problem.- 5.4 A Strategy for Decoupling A(k I k).- 5.5 Initialization With Sonar.- 5.6 Dynamic Map Building and Maintenance.- 5.7 Summary.- 6 Directed Sensing Strategies.- 6.1 The Time Problem.- 6.2 Tracking Sonars.- 6.3 Orienteering.- 6.4 Related Research: Sensor Control.- 6.5 Summary.- 7 Why Use Sonar?.- 7.1 Sonar vs the Infrared Rangefinder.- 7.2 Sonar vs Vision.- 7.3 Sensor Fusion.- 7.4 Future Research.- 7.5 Contributions.- A Hardware and Software.- A.1 Mobile Robots.- A.2 The Polaroid Ultrasonic Ranging System.- A.3 Software.