“Where am I?”
`
`Sensors and Methods for
`Mobile Robot Positioning
`
`3
`eWiniversityofMichs
`
`Silver Star Exhibit 1017
`
`by
`J. Borenstein, H.R. Everett, and L.Feng
`Edited and Compiled by J Borenstein
`Contributing Authors: 5. VW. Lee and R.H. Byrne
`Prepared by
`TheUniversity ofMichiga
`for the
`Oak Ridge National _Lab D&B Program
`and for the
`
`Silver Star Exhibit 1017
`
`

`

`%0 &3;0789 41 .,3
`%0 &3;0789 41 .,3
`
`Where am I?
`Sensors and Methods for
`Mobile Robot Positioning
`
`by
`J. Borenstein , H. R. Everett , and L. Feng
`1
`2
`Contributing authors: S. W. Lee and R. H. Byrne
`
`3
`
`Edited and compiled by J. Borenstein
`
`April 1996
`
`Prepared by the University of Michigan
`For the Oak Ridge National Lab (ORNL) D&D Program
`and the
`United States Department of Energy's
`Robotics Technology Development Program
`Within the Environmental Restoration, Decontamination and Dismantlement Project
`
`1)
`
`Dr. Johann Borenstein
`The University of Michigan
`Department of Mechanical
`Engineering and Applied Mechanics
`Mobile Robotics Laboratory
`1101 Beal Avenue
`Ann Arbor, MI 48109
`Ph.: (313) 763-1560
`Fax: (313) 944-1113
`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
`The University of Michigan
`Department of Mechanical
`Engineering and Applied Mechanics
`Mobile Robotics Laboratory
`1101 Beal Avenue
`Ann Arbor, MI 48109
`Ph.: (313) 936-9362
`Fax: (313) 763-1260
`Email: Feng@engin.umich.edu
`
`Please direct all inquiries to Johann Borenstein.
`
`Silver Star Exhibit 1017 - 2
`
`

`

`How to Use this Document
`
`The use of the Acrobat Reader utility is straight-forward; if necessary, help is available from
`theHelp Menu. Here are some tips:
`
`You may wish to enable View => Bookmarks & Page to see a list of bookmarks besides the
`current page. Clicking on a bookmark will cause the Acrobat Reader to jump directly to the
`location marked by the bookmark (e.g., the first page in a specific chapter).
`
`You may wish to enable View => Thumbnails & Page to see each page as a small thumbnail-
`sized image besides the current page. This allows you to quickly locate a page that you remember
`because of a table or graphics element. Clicking on a thumbnail will cause the Acrobat Reader to
`jump directly to the page marked by the thumbnail.
`
`Occasionally a term will be marked by a red rectangle, indicating a reference to an external
`document. Clicking inside the rectangle will automatically load the referenced document and
`display it. Clicking on the (cid:128) key will return the Acrobat Reader to the original document.
`
`Occasionally a term will be marked by a blue rectangle. This indicates a link to an external
`video clip. Clicking inside the blue rectangle will bring up the video player (provided one is
`installed on your platform).
`
`If you would like to check the video clips,
`click here for a list and instructions:
`
`If you would like to contribute your own
`material for next year's edition of the
`"Where am I" Report, click here for instruc-
`tions.
`
`Silver Star Exhibit 1017 - 3
`
`

`

`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
`
`Significant portions of the text were adapted from
` "Sensors for Mobile Robots: Theory and Application"
`by H. R. Everett,
`A K Peters, Ltd., Wellesley, MA, Publishers, 1995.
`
`Chapter 9 was contributed entirely by
`Sang W. Lee from the Artificial Intelligence Lab
`at the University of Michigan
`
`Significant portions of Chapter 3 were adapted from
`“Global Positioning System Receiver Evaluation Results.”
`by Raymond H. Byrne, originally published as
`Sandia Report SAND93-0827, Sandia National Laboratories, 1993.
`
`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.
`
`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.
`
`4
`
`Silver Star Exhibit 1017 - 4
`
`

`

`Table of Contents
`
`Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
`
`PART I SENSORS FOR MOBILE ROBOT POSITIONING
`
`Chapter 1 Sensors for Dead Reckoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
`1.1 Optical Encoders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
`1.1.1 Incremental Optical Encoders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
`1.1.2 Absolute Optical Encoders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
`1.2 Doppler Sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
`1.2.1 Micro-Trak Trak-Star Ultrasonic Speed Sensor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
`1.2.2 Other Doppler-Effect Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
`1.3 Typical Mobility Configurations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
`1.3.1 Differential Drive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
`1.3.2 Tricycle Drive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
`1.3.3 Ackerman Steering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
`1.3.4 Synchro Drive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
`1.3.5 Omnidirectional Drive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
`1.3.6 Multi-Degree-of-Freedom Vehicles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
`1.3.7 MDOF Vehicle with Compliant Linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
`1.3.8 Tracked Vehicles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
`
`Chapter 2 Heading Sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
`2.1 Mechanical Gyroscopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
`2.1.1 Space-Stable Gyroscopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
`2.1.2 Gyrocompasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
`2.1.3 Commercially Available Mechanical Gyroscopes . . . . . . . . . . . . . . . . . . . . . . . . . . 32
`2.1.3.1 Futaba Model Helicopter Gyro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
`2.1.3.2 Gyration, Inc.
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
`2.2 Piezoelectric Gyroscopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
`2.3 Optical Gyroscopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
`2.3.1 Active Ring Laser Gyros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
`2.3.2 Passive Ring Resonator Gyros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
`2.3.3 Open-Loop Interferometric Fiber Optic Gyros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
`2.3.4 Closed-Loop Interferometric Fiber Optic Gyros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
`2.3.5 Resonant Fiber Optic Gyros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
`2.3.6 Commercially Available Optical Gyroscopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
`2.3.6.1 The Andrew “Autogyro" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
`2.3.6.2 Hitachi Cable Ltd. OFG-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
`2.4 Geomagnetic Sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
`2.4.1 Mechanical Magnetic Compasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
`2.4.2 Fluxgate Compasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
`2.4.2.1 Zemco Fluxgate Compasses
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
`
`5
`
`Silver Star Exhibit 1017 - 5
`
`

`

`2.4.2.2 Watson Gyrocompass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
`2.4.2.3 KVH Fluxgate Compasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
`2.4.3 Hall-Effect Compasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
`2.4.4 Magnetoresistive Compasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
`2.4.4.1 Philips AMR Compass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
`2.4.5 Magnetoelastic Compasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
`
`Chapter 3 Ground-Based RF-Beacons and GPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
`3.1 Ground-Based RF Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
`3.1.1 Loran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
`3.1.2 Kaman Sciences Radio Frequency Navigation Grid . . . . . . . . . . . . . . . . . . . . . . . 66
`3.1.3 Precision Location Tracking and Telemetry System . . . . . . . . . . . . . . . . . . . . . . . . . 67
`3.1.4 Motorola Mini-Ranger Falcon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
`3.1.5 Harris Infogeometric System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
`3.2 Overview of Global Positioning Systems (GPSs) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
`3.3 Evaluation of Five GPS Receivers by Byrne [1993]
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
`3.3.1 Project Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
`3.3.2 Test Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
`3.3.2.1 Parameters tested . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
`3.3.2.2 Test hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
`3.3.2.3 Data post processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
`3.3.3 Test Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
`3.3.3.1 Static test results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
`3.3.3.2 Dynamic test results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
`3.3.3.3 Summary of test results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
`3.3.4 Recommendations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
`3.3.4.1 Summary of problems encountered with the tested GPS receivers . . . . . . . . . . 92
`3.3.4.2 Summary of critical integration issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
`
`Chapter 4 Sensors for Map-Based Positioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
`4.1 Time-of-Flight Range Sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
`4.1.1 Ultrasonic TOF Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
`4.1.1.1 Massa Products Ultrasonic Ranging Module Subsystems . . . . . . . . . . . . . . . . . 97
`4.1.1.2 Polaroid Ultrasonic Ranging Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
`4.1.2 Laser-Based TOF Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
`4.1.2.1 Schwartz Electro-Optics Laser Rangefinders . . . . . . . . . . . . . . . . . . . . . . . . . 101
`4.1.2.2 RIEGL Laser Measurement Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
`4.1.2.3 RVSI Long Optical Ranging and Detection System . . . . . . . . . . . . . . . . . . . . 109
`4.2 Phase-Shift Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
`4.2.1 Odetics Scanning Laser Imaging System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
`4.2.2 ESP Optical Ranging System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
`4.2.3 Acuity Research AccuRange 3000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
`4.2.4 TRC Light Direction and Ranging System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
`4.2.5 Swiss Federal Institute of Technology's “3-D Imaging Scanner” . . . . . . . . . . . . . . 120
`4.2.6 Improving Lidar Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
`4.3 Frequency Modulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
`
`6
`
`Silver Star Exhibit 1017 - 6
`
`

`

`. . . . . . . . . . . . . . . . . 125
`4.3.1 Eaton VORAD Vehicle Detection and Driver Alert System
`4.3.2 Safety First Systems Vehicular Obstacle Detection and Warning System . . . . . . . 127
`
`PART II SYSTEMS AND METHODS FOR MOBILE ROBOT POSITIONING
`
`Chapter 5 Odometry and Other Dead-Reckoning Methods . . . . . . . . . . . . . . . . . . . . . . . 130
`5.1 Systematic and Non-Systematic Odometry Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
`5.2 Measurement of Odometry Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
`5.2.1 Measurement of Systematic Odometry Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
`5.2.1.1 The Unidirectional Square-Path Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
`5.2.1.2 The Bidirectional Square-Path Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
`5.2.2 Measurement of Non-Systematic Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
`5.3 Reduction of Odometry Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
`5.3.1 Reduction of Systematic Odometry Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
`5.3.1.1 Auxiliary Wheels and Basic Encoder Trailer
`. . . . . . . . . . . . . . . . . . . . . . . . . 138
`5.3.1.2 The Basic Encoder Trailer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
`5.3.1.3 Systematic Calibration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
`5.3.2 Reducing Non-Systematic Odometry Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
`5.3.2.1 Mutual Referencing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
`5.3.2.2 Internal Position Error Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
`5.4 Inertial Navigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
`5.4.1 Accelerometers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
`5.4.2 Gyros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
`5.4.2.1 Barshan and Durrant-Whyte [1993; 1994; 1995] . . . . . . . . . . . . . . . . . . . . . . 147
`5.4.2.2 Komoriya and Oyama [1994]
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
`5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
`
`Chapter 6 Active Beacon Navigation Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
`6.1 Discussion on Triangulation Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
`6.1.1 Three-Point Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
`6.1.2 Triangulation with More Than Three Landmarks . . . . . . . . . . . . . . . . . . . . . . . . . . 153
`6.2 Ultrasonic Transponder Trilateration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
`6.2.1 IS Robotics 2-D Location System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
`6.2.2 Tulane University 3-D Location System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
`6.3 Optical Positioning Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
`6.3.1 Cybermotion Docking Beacon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
`6.3.2 Hilare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
`6.3.3 NAMCO LASERNET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
`6.3.3.1 U.S. Bureau of Mines' application of the LaserNet sensor . . . . . . . . . . . . . . . 161
`6.3.4 Denning Branch International Robotics LaserNav Position Sensor . . . . . . . . . . . 163
`6.3.5 TRC Beacon Navigation System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
`6.3.6 Siman Sensors and Intelligent Machines Ltd., ROBOSENSE . . . . . . . . . . . . . . . . . 164
`6.3.7 Imperial College Beacon Navigation System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
`TM
`6.3.8 MTI Research CONAC
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
`6.3.9 Spatial Positioning Systems, inc.: Odyssey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
`
`7
`
`Silver Star Exhibit 1017 - 7
`
`

`

`6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
`
`Chapter 7 Landmark Navigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
`7.1 Natural Landmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
`7.2 Artificial Landmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
`7.2.1 Global Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
`7.3 Artificial Landmark Navigation Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
`7.3.1 MDARS Lateral-Post Sensor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
`7.3.2 Caterpillar Self Guided Vehicle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
`7.3.3 Komatsu Ltd, Z-shaped landmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
`7.4 Line Navigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
`7.4.1 Thermal Navigational Marker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
`7.4.2 Volatile Chemicals Navigational Marker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
`7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
`
`Chapter 8 Map-based Positioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
`8.1 Map Building . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
`8.1.1 Map-Building and Sensor Fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
`8.1.2 Phenomenological vs. Geometric Representation, Engelson & McDermott [1992] 186
`8.2 Map Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
`8.2.1 Schiele and Crowley [1994]
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
`8.2.2 Hinkel and Knieriemen [1988] — The Angle Histogram . . . . . . . . . . . . . . . . . . . . 189
`8.2.3 Weiß, Wetzler, and Puttkamer — More on the Angle Histogram . . . . . . . . . . . . . 191
`8.2.4 Siemens' Roamer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
`8.2.5 Bauer and Rencken: Path Planning for Feature-based Navigation . . . . . . . . . . . . . 194
`8.3 Geometric and Topological Maps
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
`8.3.1 Geometric Maps for Navigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
`8.3.1.1 Cox [1991] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
`8.3.1.2 Crowley [1989] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
`8.3.1.3 Adams and von Flüe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
`8.3.2 Topological Maps for Navigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
`8.3.2.1 Taylor [1991] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
`8.3.2.2 Courtney and Jain [1994]
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
`8.3.2.3 Kortenkamp and Weymouth [1993] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
`8.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
`
`8
`
`Silver Star Exhibit 1017 - 8
`
`

`

`Chapter 9 Vision-Based Positioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
`9.1 Camera Model and Localization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
`9.2 Landmark-Based Positioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
`9.2.1 Two-Dimensional Positioning Using a Single Camera . . . . . . . . . . . . . . . . . . . . . 209
`9.2.2 Two-Dimensional Positioning Using Stereo Cameras . . . . . . . . . . . . . . . . . . . . . . 211
`9.3 Camera-Calibration Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
`9.4 Model-Based Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
`9.4.1 Three-Dimensional Geometric Model-Based Positioning . . . . . . . . . . . . . . . . . . . 214
`9.4.2 Digital Elevation Map-Based Localization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
`9.5 Feature-Based Visual Map Building . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
`9.6 Summary and Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
`
`Appendix A A Word on Kalman Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
`
`Appendix B Unit Conversions and Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
`
`Appendix C Systems-at-a-Glance Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
`
`References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
`
`Subject Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
`
`Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
`
`Company Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
`
`Bookmark Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
`
`Video Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
`
`Full-length Papers Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
`
`9
`
`Silver Star Exhibit 1017 - 9
`
`

`

`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 report
`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
`
`10
`
`Silver Star Exhibit 1017 - 10
`
`

`

`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.
`
`11
`
`Silver Star Exhibit 1017 - 11
`
`

`

`Part I
`Sensors for
`Mobile Robot Positioning
`
`CARMEL, the University of Michigan's first mobile robot, has been in service since 1987. Since then, CARMEL
`has served as a reliable testbed for countless sensor systems. In the extra “shelf” underneath the robot is an
`8086 XT compatible single-board computer that runs U of M's ultrasonic sensor firing algorithm. Since this code
`was written in 1987, the computer has been booting up and running from floppy disk. The program was written
`in FORTH and was never altered; should anything ever go wrong with the floppy, it will take a computer historian
`to recover the code...
`
`12
`
`Silver Star Exhibit 1017 - 12
`
`

`

`CHAPTER 1
`SENSORS FOR DEAD RECKONING
`
`Dead reckoning (derived from “deduced reckoning” of sailing days) is a simple mathematical
`procedure for determining the prese