Navigating Mobile Robots: Sensors and Techniques

by

J. Borenstein, H. R. Everett, and L. Feng

Publisher: A. K. Peters, Ltd., Wellesley, MA
Ph.: +1-617-235-2210
Fax.: +1-617-235-2404
Email: akpeters@tiac.net

 


This book surveys the state of the art in sensors, systems, methods and technologies utilized by a mobile robot to determine its position in the environment. The many potential "solutions" are roughly categorized into two groups: relative and absolute position measurements. The first includes odometry and inertial navigation; the second comprises active beacons, artificial and natural landmark recognition, and model matching. The authors compare and analyze these different methods based on technical publications and on commercial product and patent information. Comparison is centered around the following criteria: accuracy of position and orientation measurements, equipment needed, cost, sampling rate, effective range, computational power required, processing needs, and other special features. No robotics hobbyist or professional should be without this extraordinarily comprehensive look at robot positioning.

The book is available for $39.95 (price subject to change without further notice) from publisher A. K. Peters, Ltd., Wellesley, MA

NOTE: As of 1999 this book is out of print and no longer available anywhere. However, you can download the book in its entirety  under the title "Where am I" Report. This report is identical to the book.

Translation into Romanian is available at: http://www.azoft.com/people/seremina/edu/navi_mob_robots-rom.html
 


(1) Dr. Johann Borenstein
The University of Michigan
2260 Hayward Street
Ann Arbor, MI 48109
Ph.: (763) 763-1560
Fax: (206) 203-1445
Email: johannb@umich.edu

 

(2) Commander H. R. Everett
Naval Command, Control, and Ocean Surveillance Center
RDT&E Division 5303
271 Catalina Boulevard
San Diego CA 92152-5001
Ph.:(619) 553-3672
Fax:(619) 553-6188
Email: Everett@NOSC.MIL

 

(3) Dr. Liqiang Feng

 


Acknowledgments

This research was sponsored by the Office of Technology Development, U.S. Department of Energy, under contract DE-FG02-86NE37969 with the University of Michigan.

The authors wish to thank the Department of Energy (DOE), and especially Dr. Linton W. Yarbrough, DOE Program Manager, Dr. William R. Hamel, D&D, Technical Coordinator, and Dr. Clyde Ward, Landfill Operations Technical Coordinator for their technical and financial support of the research, which forms the basis of this work.

Parts of the text were adapted from Sensors for Mobile Robots: Theory and Application, by H. R. Everett, A K Peters, Ltd., Wellesley, MA, Publishers.

The authors further wish to thank Professors David K. Wehe and Yoram Koren at the University of Michigan for their support, and Mr. Harry Alter (DOE) who has befriended many of the graduate students and sired several of our robots. Thanks are also due to Todd Ashley Everett for making most of the line-art drawings.

 


Introduction

Leonard and Durrant-Whyte [1991] summarized the general problem of mobile robot navigation by three questions: "Where am I?," "Where am I going?," and "How should I get there?." This book surveys the state-of-the-art in sensors, systems, methods, and technologies that aim at answering the first question, that is: robot positioning in its environment.

Perhaps the most important result from surveying the vast body of literature on mobile robot positioning is that to date there is no truly elegant solution for the problem. The many partial solutions can roughly be categorized into two groups: relative and absolute position measurements. Because of the lack of a single, generally good method, developers of automated guided vehicles (AGVs) and mobile robots usually combine two methods, one from each category. The two categories can be further divided into the following subgroups.

Relative Position Measurements

a. Odometry This method uses encoders to measure wheel rotation and/or steering orientation. Odometry has the advantage that it is totally self-contained, and it is always capable of providing the vehicle with an estimate of its position. The disadvantage of odometry is that the position error grows without bound unless an independent reference is used periodically to reduce the error [Cox, 1991].

b. Inertial Navigation This method uses gyroscopes and sometimes accelerometers to measure rate of rotation and acceleration. Measurements are integrated once (or twice) to yield position. Inertial navigation systems also have the advantage that they are self-contained. On the downside, inertial sensor data drifts with time because of the need to integrate rate data to yield position; any small constant error increases without bound after integration. Inertial sensors are thus unsuitable for accurate positioning over an extended period of time. Another problem with inertial navigation is the high equipment cost. For example, highly accurate gyros, used in airplanes, are inhibitively expensive. Very recently fiber-optic gyros (also called laser gyros), which are said to be very accurate, have fallen dramatically in price and have become a very attractive solution for mobile robot navigation.

Absolute Position Measurements

c. Active Beacons This method computes the absolute position of the robot from measuring the direction of incidence of three or more actively transmitted beacons. The transmitters, usually using light or radio frequencies, must be located at known sites in the environment.

d. Artificial Landmark Recognition In this method distinctive artificial landmarks are placed at known locations in the environment. The advantage of artificial landmarks is that they can be designed for optimal detectability even under adverse environmental conditions. As with active beacons, three or more landmarks must be "in view" to allow position estimation. Landmark positioning has the advantage that the position errors are bounded, but detection of external landmarks and real-time position fixing may not always be possible. Unlike the usually point-shaped beacons, artificial landmarks may be defined as a set of features, e.g., a shape or an area. Additional information, for example distance, can be derived from measuring the geometric properties of the landmark, but this approach is computationally intensive and not very accurate.

e. Natural Landmark Recognition Here the landmarks are distinctive features in the environment. There is no need for preparation of the environment, but the environment must be known in advance. The reliability of this method is not as high as with artificial landmarks.

f. Model Matching In this method information acquired from the robot's onboard sensors is compared to a map or world model of the environment. If features from the sensor-based map and the world model map match, then the vehicle's absolute location can be estimated. Map-based positioning often includes improving global maps based on the new sensory observations in a dynamic environment and integrating local maps into the global map to cover previously unexplored areas. The maps used in navigation include two major types: geometric maps and topological maps. Geometric maps represent the world in a global coordinate system, while topological maps represent the world as a network of nodes and arcs.

This book presents and discusses the state-of-the-art in each of the above six categories. The material is organized in two parts: Part I deals with the sensors used in mobile robot positioning, and Part II discusses the methods and techniques that make use of these sensors.

Mobile robot navigation is a very diverse area, and a useful comparison of different approaches is difficult because of the lack of commonly accepted test standards and procedures. The research platforms used differ greatly and so do the key assumptions used in different approaches. Further difficulty arises from the fact that different systems are at different stages in their development. For example, one system may be commercially available, while another system, perhaps with better performance, has been tested only under a limited set of laboratory conditions. For these reasons we generally refrain from comparing or even judging the performance of different systems or techniques. Furthermore, we have not tested most of the systems and techniques, so the results and specifications given in this book are merely quoted from the respective research papers or product spec-sheets.

Because of the above challenges we have defined the purpose of this book to be a survey of the expanding field of mobile robot positioning. It took well over 1.5 man-years to gather and compile the material for this book; we hope this work will help the reader to gain greater understanding in much less time.


Table of Contents

INTRODUCTION xi
Part I Sensors for Mobile Robot Positioning
Chapter 1 Sensors for Dead Reckoning 3
1.1 Optical Encoders 3
1.1.1 Incremental Optical Encoders 4
1.1.2 Absolute Optical Encoders 6
1.2 Doppler Sensors 7
1.2.1 Micro-Trak Trak-Star Ultrasonic Speed Sensor 8
1.2.2 Other Doppler-Effect Systems 9
1.3 Typical Mobility Configurations 9
1.3.1 Differential Drive 9
1.3.2 Tricycle Drive 11
1.3.3 Ackerman Steering 11
1.3.4 Synchro Drive 13
1.3.5 Omnidirectional Drive 15
1.3.6 Multi-Degree-of-Freedom Vehicles 16
1.3.7 MDOF Vehicle with Compliant Linkage 17
1.3.8 Tracked Vehicles 18
Chapter 2 Heading Sensors 21
2.1 Mechanical Gyroscopes 21
2.1.1 Space-Stable Gyroscopes 22
2.1.2 Gyrocompasses 23
2.1.3 Commercially Available Mechanical Gyroscopes 23
2.1.3.1 Futaba Model Helicopter Gyro 23
2.1.3.2 Gyration, Inc. 24
2.2 Optical Gyroscopes 24
2.2.1 Active Ring-Laser Gyros 26
2.2.2 Passive Ring Resonator Gyros 28
2.2.3 Open-Loop Interferometric Fiber Optic Gyros 29
2.2.4 Closed-Loop Interferometric Fiber Optic Gyros 32
2.2.5 Resonant Fiber-Optic Gyros 32
2.2.6 Commercially Available Optical Gyroscopes 33
2.2.6.1 The Andrew AUTOGYRO 33
2.2.6.2 Hitachi Cable Ltd. OFG-3 34
2.3 Geomagnetic Sensors 34
2.3.1 Mechanical Magnetic Compasses 35
2.3.2 Fluxgate Compasses 36
2.3.2.1 Zemco Fluxgate Compasses 42
2.3.2.2 Watson Gyrocompass 44
2.3.2.3 KVH Fluxgate Compasses 45
2.3.3 Hall-Effect Compasses 46
2.3.4 Magnetoresistive Compasses 48
2.3.4.1 Philips AMR Compass 48
2.3.5 Magnetoelastic Compasses 49
Chapter 3 Active Beacons 53
3.1 Navstar Global Positioning System (GPS) 53
3.2 Ground-Based RF Systems 59
3.2.1 Loran 59
3.2.2 Kaman Sciences Radio Frequency Navigation Grid 60
3.2.3 Precision Location Tracking and Telemetry System 61
3.2.4 Motorola Mini-Ranger Falcon 61
3.2.5 Harris Infogeometric System 62
Chapter 4 Sensors for Map-Based Positioning 65
4.1 Time-of-Flight Range Sensors 65
4.1.1 Ultrasonic TOF Systems 67
4.1.1.1 Massa Products Ultrasonic Ranging Module Subsystems 67
4.1.1.2 Polaroid Ultrasonic Ranging Modules 69
4.1.2 Laser-Based TOF Systems 71
4.1.2.1 Schwartz Electro-Optics Laser Rangefinders 71
4.1.2.2 RIEGL Laser Measurement Systems 77
4.1.2.3 RVSI Long Optical Ranging and Detection System 79
4.2 Phase-Shift Measurement 82
4.2.1 Odetics Scanning Laser Imaging System 85
4.2.2 ESP Optical Ranging System 86
4.2.3 Acuity Research AccuRange 3000 87
4.2.4 TRC Light Direction and Ranging System 89
4.2.5 Swiss Federal Institute of Technology's 3-D Imaging Scanner 90
4.2.6 Improving Lidar Performance 91
4.3 Frequency Modulation 93
4.3.1 Eaton VORAD Vehicle Detection and Driver Alert System 95
4.3.2 Safety First Systems Vehicular Obstacle Detection and Warning System 96
Part II Systems and Methods for Mobile Robot Positioning
Chapter 5 Odometry and Other Dead-Reckoning Methods 101
5.1 Systematic and Non-Systematic Odometry Errors 101
5.2 Measurement of Odometry Errors 103
5.2.1 Measurement of Systematic Odometry Errors 103
5.2.1.1 The Unidirectional Square-Path Test 103
5.2.1.2 The Bidirectional Square-Path Experiment 105
5.2.2 Measurement of Non-Systematic Errors 107
5.3 Reduction of Odometry Errors 108
5.3.1 Reduction of Systematic Odometry Errors 109
5.3.1.1 Auxiliary Wheels and Basic Encoder Trailer 109
5.3.1.2 The Basic Encoder Trailer 110
5.3.1.3 Systematic Calibration 110
5.3.2 Reducing Non-Systematic Odometry Errors 114
5.3.2.1 Mutual Referencing 114
5.3.2.2 Internal Position Error Correction 114
5.4 Inertial Navigation 116
5.4.1 Accelerometers 117
5.4.2 Gyros 117
5.4.2.1 Barshan and Durrant-Whyte 118
5.4.2.2 Komoriya and Oyama] 119
5.5 Summary 120
Chapter 6 Active Beacon Navigation Systems 123
6.1 Discussion on Triangulation Methods 124
6.1.1 Three-Point Triangulation 124
6.1.2 Triangulation with More Than Three Landmarks 125
6.2 Ultrasonic Transponder Trilateration 126
6.2.1 IS Robotics 2-D Location System 127
6.2.2 Tulane University 3-D Location System 127
6.3 Optical Positioning Systems 129
6.3.1 Cybermotion Docking Beacon 130
6.3.2 Hilare 131
6.3.3 NAMCO LASERNET 132
6.3.4 Denning Branch International Robotics LaserNav Position Sensor 133
6.3.5 TRC Beacon Navigation System 134
6.3.6 Siman Sensors & Intelligent Machines Ltd., ROBOSENSE 135
6.3.7 Imperial College Beacon Navigation System 136
6.3.8 MTI Research CONACTM 137
6.3.9 Lawnmower CALMAN 140
6.4 Summary 140
Chapter 7 Landmark Navigation 141
7.1 Natural Landmarks 142
7.2 Artificial Landmarks 143
7.2.1 Global Vision 144
7.3 Artificial Landmark Navigation Systems 144
7.3.1 MDARS Lateral-Post Sensor 145
7.3.2 Caterpillar Self Guided Vehicle 146
7.3.3 Komatsu Ltd, Z-Shaped Landmark 147
7.4 Line Navigation 148
7.4.1 Thermal Navigational Marker 149
7.4.2 Volatile Chemicals Navigational Marker 149
7.5 Summary 150
Chapter 8 Map-Based Positioning 153
8.1 Map-Building 154
8.1.1 Map-Building and Sensor-Fusion 155
8.1.2 Phenomenological vs. Geometric Representation, Engelson and McDermott 155
8.2 Map Matching 156
8.2.1 Schiele and Crowley 157
8.2.2 Hinkel and Knieriemen -- The Angle Histogram 158
8.2.3 Weiß, Wetzler, and Puttkamer -- More on the Angle Histogram 160
8.2.4 Siemens' Roamer 162
8.3 Geometric and Topological Maps 163
8.3.1 Geometric Maps for Navigation 164
8.3.1.1 Cox 165
8.3.1.2 Crowley 166
8.3.1.3 Adams and von Flüe 169
8.3.2 Topological Maps for Navigation1 70
8.3.2.1 Taylor 170
8.3.2.2 Courtney and Jain 170
8.3.2.3 Kortenkamp and Weymouth 171
8.4 Summary 173
Appendix A: A Word on Kalman Filters 174
Appendix B: Unit Conversions and Abbreviations 175
Appendix C: Systems-at-a-Glance Tables 177
References 195
Subject Index 209
Author Index 219
Company Index 223

This file last updated on 06/26/2009 by Johann Borenstein.

Email: johannb@umich.edu