Nội dung

The University of Michigan Volume III: "Where am I?" Sensors and Methods for Autonomous Mobile Robot Positioning by 1 L. Feng , J. Borenstein 2, and H. R. Everett3 Edited and compiled by J. Borenstein December 1994 Copies of this report are available from the University of Michigan as: Technical Report UM-MEAM-94-21 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. 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 2) 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: 3) 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 Johann_Borenstein@um.cc.umich.edu Please direct all inquiries to Johann Borenstein D:\WP\DOE_94\ORNL\POSITION.RPT\POSITION.WP6, February 25, 1995 This page intentionally left blank. Acknowledgments: This work was done under the direction and on behalf of the Department of Energy Robotics Technology Development Program Within the Environmental Restoration, Decontamination, and Dismantlement Project. Parts of this report were adapted from: H. R. Everett, "Sensors for Mobile Robots." A. K. Peters, Ltd., Wellesley, expected publication date Spring 1995. The authors wish to thank Professors David K. Wehe and Yoram Koren for their support in preparing this report. The authors also wish to thank Dr. William R. Hamel, D&D Technical Coordinator and Dr. Linton W. Yarbrough, DOE Program Manager, for their continuing support in funding this report. The authors further wish to thank A. K. Peters, Ltd., for granting permission to publish (for limited distribution within Oak Ridge National Laboratories and the Department of Energy) selected parts of their soon-to-be published book "Sensors for Mobile Robots" by H. R. Everett. Thanks are also due to Todd Ashley Everett for making most of the line-art drawings, and to Photographer David A. Kother who shot most of the artful photographs on the front cover of this report. Last but not least, the authors are grateful to Mr. Brad Holt for proofreading the manuscript and providing many useful suggestions. i Table of Contents Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 1 Part I: Sensors for Mobile Robot Positioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 5 Chapter 1: Sensors for Dead Reckoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 7 1.1 Optical Encoders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 8 1.1.1 Incremental Optical Encoders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 8 1.1.2 Absolute Optical Encoders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 10 1.2 Doppler Sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 12 1.2.1 Micro-Trak Trak-Star Ultrasonic Speed Sensor . . . . . . . . . . . . . . . . . . . . . . Page 13 1.2.2 Other Doppler Effect Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 13 1.3 Typical Mobility Configurations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 14 1.3.1 Differential Drive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 14 1.3.2 Tricycle Drive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 15 1.3.3 Ackerman Steering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 16 1.3.4 Synchro-Drive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 17 1.3.5 Omni-Directional Drive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 20 1.3.6 Multi-Degree-of Freedom Vehicles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 21 1.3.7 Tracked Vehicles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 22 Chapter 2: Heading Sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Gyroscopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1 Mechanical Gyroscopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1.1 Space-Stable Gyroscopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1.2 Gyrocompasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 Optical Gyroscopes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2.1 Active Ring Laser Gyros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2.2 Passive Ring Resonator Gyros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2.3 Open-Loop Interferometric Fiber Optic Gyros . . . . . . . . . . . . . . . . . . . . 2.1.2.4 Closed-Loop Interferometric Fiber Optic Gyros . . . . . . . . . . . . . . . . . . . 2.1.2.5 Resonant Fiber Optic Gyros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Geomagnetic Sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Mechanical Magnetic Compasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dinsmore Starguide Magnetic Compass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Fluxgate Compasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2.1 Zemco Fluxgate Compasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2.2 Watson Gyro Compass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2.3 KVH Fluxgate Compasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Hall Effect Compasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.4 Magnetoresistive Compasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Page 24 Page 24 Page 24 Page 25 Page 26 Page 27 Page 28 Page 31 Page 32 Page 35 Page 35 Page 36 Page 37 Page 38 Page 39 Page 43 Page 45 Page 46 Page 47 Page 49 2.2.4.1 Philips AMR Compass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 49 2.2.5 Magnetoelastic Compasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 50 Chapter 3: Active Beacons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Navstar Global Positioning System (GPS) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Ground-Based RF Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Loran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Kaman Sciences Radio Frequency Navigation Grid . . . . . . . . . . . . . . . . . . . 3.2.3 Precision Location Tracking and Telemetry System . . . . . . . . . . . . . . . . . . . 3.2.4 Motorola Mini-Ranger Falcon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.5 Harris Infogeometric System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 53 Page 53 Page 60 Page 60 Page 61 Page 62 Page 62 Page 64 Chapter 4: Sensors for Map-based Positioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Time-of-Flight Range Sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Ultrasonic TOF Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1.1 National Semiconductor’s LM1812 Ultrasonic Transceiver . . . . . . . . . 4.1.1.2 Massa Products Ultrasonic Ranging Module Subsystems . . . . . . . . . . . 4.1.1.3 Polaroid Ultrasonic Ranging Modules . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2 Laser-Based TOF Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.2.1 Schwartz Electro-Optics Laser Rangefinders . . . . . . . . . . . . . . . . . . . . . 4.1.2.2 RIEGL Laser Measurement Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Phase Shift Measurement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 ERIM 3-D Vision Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Odetics Scanning Laser Imaging System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.3 ESP Optical Ranging System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.4 Acuity Research AccuRange 3000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.5 TRC Light Direction and Ranging System . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Frequency Modulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 VRSS Automotive Collision Avoidance Radar . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 VORAD Vehicle Detection and Driver Alert System . . . . . . . . . . . . . . . . . . 4.3.3 Safety First Systems Vehicular Obstacle Detection and Warning System . . . 4.3.4 Millitech Millimeter Wave Radar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 66 Page 66 Page 68 Page 68 Page 69 Page 71 Page 73 Page 73 Page 77 Page 82 Page 86 Page 89 Page 90 Page 91 Page 92 Page 94 Page 95 Page 96 Page 98 Page 98 Part II: Systems and Methods for Mobile Robot Positioning . . . . . . . . . . . . . . . . . . Page 100 Chapter 5: Dead-reckoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Systematic and Non-systematic Dead-reckoning Errors . . . . . . . . . . . . . . . . . . . . 5.2 Reduction of Dead-reckoning Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.1 Auxiliary Wheels and Basic Encoder Trailer . . . . . . . . . . . . . . . . . . . . . . . . 5.2.2 The Basic Encoder Trailer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.3 Mutual Referencing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.4 MDOF vehicle with Compliant Linkage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.5 Internal Position Error Correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Page 102 Page 103 Page 104 Page 105 Page 105 Page 106 Page 106 Page 107 5.3 Automatic Vehicle Calibration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Inertial Navigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Accelerometers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.2 Gyros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 109 Page 110 Page 111 Page 111 Page 112 Chapter 6: Active Beacon Navigation Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1 Discussion on Triangulation Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Ultrasonic Transponder Trilateration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 IS Robotics 2-D Location System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.2 Tulane University 3-D Location System . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Optical Positioning Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.1 Cybermotion Docking Beacon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.2 Hilare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.3 NAMCO LASERNET . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.4 Intelligent Solutions EZNav Position Sensor . . . . . . . . . . . . . . . . . . . . . . . . 6.3.5 TRC Beacon Navigation System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.5 Siman Sensors & Intelligent Machines Ltd., "ROBOSENSE" . . . . . . . . . . . . 6.3.7 Imperial College Beacon Navigation System . . . . . . . . . . . . . . . . . . . . . . . . 6.3.8 MacLeod Technologies CONAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.9 Lawnmower CALMAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 113 Page 115 Page 116 Page 116 Page 117 Page 119 Page 119 Page 121 Page 122 Page 123 Page 124 Page 125 Page 126 Page 127 Page 128 Page 129 Chapter 7: Landmark Navigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1 Natural Landmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Artificial Landmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 Artificial Landmark Navigation Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.1 MDARS Lateral-Post Sensor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.2 Caterpillar Self Guided Vehicle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.4 Line Navigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 130 Page 131 Page 131 Page 133 Page 134 Page 135 Page 135 Page 136 Chapter 8: Map-based Positioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1 Map-building . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1.1 Map-building and sensor-fusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.1.2 Phenomenological vs. geometric representation . . . . . . . . . . . . . . . . . . . . . . 8.2 Map matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2.1 Schiele and Crowley [1994] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2.2 Hinkel and Knieriemen [1988] — the Angle Histogram . . . . . . . . . . . . . . . . 8.2.3 Siemens' Roamer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Geometric and Topological Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.1 Geometric Maps for Navigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.1.1 Cox [1991] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 138 Page 139 Page 140 Page 141 Page 141 Page 142 Page 144 Page 145 Page 147 Page 148 Page 148 iv 8.3.1.2 Crowley [1989] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.2 Topological Maps for Navigation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.2.1 Taylor [1991] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.2.2 Courtney and Jain [1994] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.2.3 Kortenkamp and Weymouth [1993] . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 150 Page 153 Page 153 Page 154 Page 154 Page 157 Part III: References and "Systems-at-a-Glance" Tables . . . . . . . . . . . . . . . . . . . . . . Page 158 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 160 Systems-at-a-Glance Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Page 188 v This page intentionally left blank. vi Introduction Leonard and Durrant-Whyte [1991] summarized the problem of navigation by three questions: "where am I?", "where am I going?", and "how should I get there?" This report surveys the stateof-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 sub-groups. Relative Position Measurements: 1. Dead-reckoning uses encoders to measure wheel rotation and/or steering orientation. Deadreckoning 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 dead-reckoning is that the position error grows without bound unless an independent reference is used periodically to reduce the error [Cox, 1991]. 2. Inertial navigation 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 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-optics 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: 3. Active beacons — This methods 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 locations in the environment. 4. 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 pointPage 1 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 geometrical properties of the landmark, but this approach is computationally intensive and not very accurate. 5. Natural Landmark Recognition — Here the landmarks are distinctive features in the environment. There is no need for preparations of the environment, but the environment must be known in advance. The reliability of this method is not as high as with artificial landmarks. 6. Model matching — In this method information acquired from the robot's on-board 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. Mapbased 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 area. 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. The nodes of the network are distinctive places in the environment and the arcs represent paths between places [Kortenkamp and Weymouth, 1994]. There are large variations in terms of the information stored for each arc. Brooks [Brooks, 1985] argues persuasively for the use of topological maps as a means of dealing with uncertainty in mobile robot navigation. Indeed, the idea of a map that contains no metric or geometric information, but only the notion of proximity and order, is enticing because such an approach eliminates the inevitable problems of dealing with movement uncertainty in mobile robots. Movement errors do not accumulate globally in topological maps as they do in maps with a global coordinate system since the robot only navigate locally, between places. Topological maps are also much more compact in their representation of space, in that they represent only certain places and not the entire world [Kortenkamp and Weymouth, 1994]. However, this also makes a topological map unsuitable for any spatial reasoning over its entire environment, e.g., optimal global path planning. In the following survey we present and discuss the state-of-the-art in each one of the above categories. We compare and analyze different methods based on technical publications and on commercial product and patent information. Mobile robot navigation is a very diverse area, and a useful comparison of different approaches is difficult because of the lack of a commonly accepted test standards and procedures. The equipment used varies 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. Our comparison will be centered around the following criteria: accuracy of position and orientation measurements, equipment needed, cost, sampling rate, effective range, computational power required, processing needed, and other special features. We present this survey in three parts. Part I deals with the sensors used in mobile robot positioning, while Part II discusses the methods and techniques that use these sensors. The report is organized in 9 chapters. Part I: Sensors for Mobile Robot Positioning Page 2