Introduction to Autonomous Mobile Robots Roland Siegwart_Illah Reza Nourbakhsh_etc.pdf

Introduction to Autonomous Mobile Robots Intelligent Robotics and Autonomous Agents Edited by Ronald C. Arkin A list of the books published in the Intelligent Robotics and Autonomous Agents series can be found at the back of the book. Introduction to Autonomous Mobile Robots second edition Rol...

Introduction to Autonomous Mobile Robots Intelligent Robotics and Autonomous Agents Edited by Ronald C. Arkin A list of the books published in the Intelligent Robotics and Autonomous Agents series can be found at the back of the book. Introduction to Autonomous Mobile Robots second edition Roland Siegwart, Illah R. Nourbakhsh, and Davide Scaramuzza The MIT Press Cambridge, Massachusetts London, England © 2011 Massachusetts Institute of Technology Original edition © 2004 All rights reserved. No part of this book may be reproduced in any form by any electronic or mechan- ical means (including photocopying, recording, or information storage and retrieval) without permis- sion in writing from the publisher. For information about special quantity discount, please email [email protected] This book was set in Times Roman by the authors using Adobe FrameMaker 9.0. Printed and bound in the United States of America. Library of Congress Cataloging-in-Publication Data Siegwart, Roland. Introduction to autonomous mobile robots. - 2nd ed. / Roland Siegwart, Illah R. Nourbakhsh, and Da- vide Scaramuzza. p. cm. - (Intelligent robotics and autonomous agents series) Includes bibliographical references and index. ISBN 978-0-262-01535-6 (hardcover : alk. paper) 1. Mobile robots. 2. Autonomous robots. I. Nour- bakhsh, Illah Reza, 1970- II. Scaramuzza, Davide. III. Title. TJ211.415.S54 2011 629.8'932-dc22 2010028053 10 9 8 7 6 5 4 3 2 1 To Luzia and my children, Janina, Malin, and Yanik, who give me their support and free- dom to grow every day — RS To my parents, Susi and Yvo, who opened my eyes — RS To Marti, Mitra, and Nikou, who are my love and my inspiration — IRN To my parents, Fatemeh and Mahmoud, who let me disassemble and investigate everything in our home — IRN To my parents, Paola and Ermanno, who encouraged and supported my choices every day and introduced me to robotics at the age of three — DS To my sisters, Lisa and Silvia, for their love — DS Slides and exercises that go with this book are available at: http://www.mobilerobots.org Contents Acknowledgments xiii Preface xv 1 Introduction 1 1.1 Introduction 1 1.2 An Overview of the Book 11 2 Locomotion 13 2.1 Introduction 13 2.1.1 Key issues for locomotion 16 2.2 Legged Mobile Robots 17 2.2.1 Leg configurations and stability 18 2.2.2 Consideration of dynamics 21 2.2.3 Examples of legged robot locomotion 25 2.3 Wheeled Mobile Robots 35 2.3.1 Wheeled locomotion: The design space 35 2.3.2 Wheeled locomotion: Case studies 43 2.4 Aerial Mobile Robots 50 2.4.1 Introduction 50 2.4.2 Aircraft configurations 52 2.4.3 State of the art in autonomous VTOL 52 2.5 Problems 56 3 Mobile Robot Kinematics 57 3.1 Introduction 57 3.2 Kinematic Models and Constraints 58 viii Contents 3.2.1 Representing robot position 58 3.2.2 Forward kinematic models 61 3.2.3 Wheel kinematic constraints 63 3.2.4 Robot kinematic constraints 71 3.2.5 Examples: Robot kinematic models and constraints 73 3.3 Mobile Robot Maneuverability 77 3.3.1 Degree of mobility 77 3.3.2 Degree of steerability 81 3.3.3 Robot maneuverability 82 3.4 Mobile Robot Workspace 84 3.4.1 Degrees of freedom 84 3.4.2 Holonomic robots 85 3.4.3 Path and trajectory considerations 87 3.5 Beyond Basic Kinematics 90 3.6 Motion Control (Kinematic Control) 91 3.6.1 Open loop control (trajectory-following) 91 3.6.2 Feedback control 92 3.7 Problems 99 4 Perception 101 4.1 Sensors for Mobile Robots 101 4.1.1 Sensor classification 101 4.1.2 Characterizing sensor performance 103 4.1.3 Representing uncertainty 109 4.1.4 Wheel/motor sensors 115 4.1.5 Heading sensors 116 4.1.6 Accelerometers 119 4.1.7 Inertial measurement unit (IMU) 121 4.1.8 Ground beacons 122 4.1.9 Active ranging 125 4.1.10 Motion/speed sensors 140 4.1.11 Vision sensors 142 4.2 Fundamentals of Computer Vision 142 4.2.1 Introduction 142 4.2.2 The digital camera 142 4.2.3 Image formation 148 4.2.4 Omnidirectional cameras 159 4.2.5 Structure from stereo 169 4.2.6 Structure from motion 180 Contents ix 4.2.7 Motion and optical flow 189 4.2.8 Color tracking 192 4.3 Fundamentals of Image Processing 195 4.3.1 Image filtering 196 4.3.2 Edge detection 199 4.3.3 Computing image similarity 207 4.4 Feature Extraction 208 4.5 Image Feature Extraction: Interest Point Detectors 212 4.5.1 Introduction 212 4.5.2 Properties of the ideal feature detector 213 4.5.3 Corner detectors 215 4.5.4 Invariance to photometric and geometric changes 220 4.5.5 Blob detectors 227 4.6 Place Recognition 234 4.6.1 Introduction 234 4.6.2 From bag of features to visual words 235 4.6.3 Efficient location recognition by using an inverted file 236 4.6.4 Geometric verification for robust place recognition 237 4.6.5 Applications 237 4.6.6 Other image representations for place recognition 238 4.7 Feature Extraction Based on Range Data (Laser, Ultrasonic) 242 4.7.1 Line fitting 243 4.7.2 Six line-extraction algorithms 248 4.7.3 Range histogram features 259 4.7.4 Extracting other geometric features 260 4.8 Problems 262 5 Mobile Robot Localization 265 5.1 Introduction 265 5.2 The Challenge of Localization: Noise and Aliasing 266 5.2.1 Sensor noise 267 5.2.2 Sensor aliasing 268 5.2.3 Effector noise 269 5.2.4 An error model for odometric position estimation 270 5.3 To Localize or Not to Localize: Localization-Based Navigation Versus Programmed Solutions 275 5.4 Belief Representation 278 5.4.1 Single-hypothesis belief 278 5.4.2 Multiple-hypothesis belief 280 x Contents 5.5 Map Representation 284 5.5.1 Continuous representations 284 5.5.2 Decomposition strategies 287 5.5.3 State of the art: Current challenges in map representation 294 5.6 Probabilistic Map-Based Localization 296 5.6.1 Introduction 296 5.6.2 The robot localization problem 297 5.6.3 Basic concepts of probability theory 299 5.6.4 Terminology 302 5.6.5 The ingredients of probabilistic map-based localization 304 5.6.6 Classification of localization problems 306 5.6.7 Markov localization 307 5.6.8 Kalman filter localization 322 5.7 Other Examples of Localization Systems 342 5.7.1 Landmark-based navigation 344 5.7.2 Globally unique localization 345 5.7.3 Positioning beacon systems 346 5.7.4 Route-based localization 347 5.8 Autonomous Map Building 348 5.8.1 Introduction 348 5.8.2 SLAM: The simultaneous localization and mapping problem 349 5.8.3 Mathematical definition of SLAM 351 5.8.4 Extended Kalman Filter (EKF) SLAM 353 5.8.5 Visual SLAM with a single camera 356 5.8.6 Discussion on EKF SLAM 359 5.8.7 Graph-based SLAM 361 5.8.8 Particle filter SLAM 363 5.8.9 Open challenges in SLAM 364 5.8.10 Open source SLAM software and other resources 365 5.9 Problems 366 6 Planning and Navigation 369 6.1 Introduction 369 6.2 Competences for Navigation: Planning and Reacting 370 6.3 Path Planning 371 6.3.1 Graph search 373 6.3.2 Potential field path planning 386 6.4 Obstacle avoidance 393 6.4.1 Bug algorithm 393 Contents xi 6.4.2 Vector field histogram 397 6.4.3 The bubble band technique 399 6.4.4 Curvature velocity techniques 401 6.4.5 Dynamic window approaches 402 6.4.6 The Schlegel approach to obstacle avoidance 404 6.4.7 Nearness diagram 405 6.4.8 Gradient method 405 6.4.9 Adding dynamic constraints 406 6.4.10 Other approaches 406 6.4.11 Overview 406 6.5 Navigation Architectures 409 6.5.1 Modularity for code reuse and sharing 410 6.5.2 Control localization 410 6.5.3 Techniques for decomposition 411 6.5.4 Case studies: tiered robot architectures 416 6.6 Problems 423 Bibliography 425 Books 425 Papers 427 Referenced Webpages 444 Index 447 Acknowledgments This book is the result of inspirations and contributions from many researchers and students at the Swiss Federal Institutes of Technology Zurich (ETH) and Lausanne (EPFL), Carne- gie Mellon University’s Robotics Institute, Pittsburgh (CMU), and many others around the globe. We would like to thank all the researchers in mobile robotics who make this field so rich and stimulating by sharing their goals and visions with the community. It is their work that enabled us to collect the material for this book. The most valuable and direct support and contribution for this second edition came from our current collaborators at ETH. We would like to thank Friedrich Fraundorfer for his con- tribution to the section on location recognition; Samir Bouabdallah for his contribution to the section on flying robots; Christian David Remy for his contribution to the section on considerations of dynamics; Martin Rufli for his contribution to path planning; Agostino Martinelli for his careful checking of some of the equations; Deon Sabatta and Jonathan Claassens for their careful review of some sections and their fruitful discussions; and Sarah Bulliard for her useful suggestions. Furthermore, we would like to renew our acknowledg- ments to the people who contributed to the first edition. In particular Kai Arras for his con- tribution to uncertainty representation and Kalman filter localization; Matt Mason for his contribution to kinematics; Al Rizzi for his guidance on feedback control; Roland Philippsen and Jan Persson for their contribution to obstacle avoidance; Gilles Caprari and Yves Piguet for their input and suggestions on motion control; Marco Lauria for offering his talent for some of the figures; Marti Louw for her efforts on the cover design; and Nicola Tomatis, Remy Blank, and Marie-Jo Pellaud. This book was also inspired by other courses, especially by the lecture notes on mobile robotics at the Swiss Federal Institutes of Technology, both in Lausanne (EPFL) and Zurich (ETH). The material for this book has been used for lectures at EPFL, ETH, and CMU since 1997. We thank the hundreds of students who followed the lecture and contributed through their corrections and comments. It has been a pleasure to work with MIT Press, the publisher of this book. Thanks to Gregory McNamee for his careful and valuable copy-editing, and to Ada Brunstein, Kath- erine Almeida, Abby Streeter Roake, Marc Lowenthal, and Susan Clark from MIT Press for their help in editing and finalizing the book. Preface Mobile robotics is a young field. Its roots include many engineering and science disci- plines, from mechanical, electrical, and electronics engineering to computer, cognitive, and social sciences. Each of these parent fields has its share of introductory textbooks that excite and inform prospective students, preparing them for future advanced coursework and research. Our objective in writing this textbook is to provide mobile robotics with such a preparatory guide. This book presents an introduction to the fundamentals of mobile robotics, spanning the mechanical, motor, sensory, perceptual, and cognitive layers that comprise our field of study. A collection of workshop proceedings and journal publications could present the new student with a snapshot of the state of the art in all aspects of mobile robotics. But here we aim to present a foundation—a formal introduction to the field. The formalism and anal- ysis herein will prove useful even as the frontier of the state-of-the-art advances due to the rapid progress in all of the subdisciplines of mobile robotics. This second edition largely extends the content of the first edition. In particular, chapters 2, 4, 5, and 6 have been notably expanded and updated to the most recent, state-of-the-art acquisitions in both computer vision and robotics. In particular, we have added in chapter 2 the most recent and popular examples of mobile, legged, and micro aerial robots. In chap- ter 4, we have added the description of new sensors—such as 3D laser rangefinders, time- of-flight cameras, IMUs, and omnidirectional cameras—and tools—such as image filter- ing, camera calibration, structure-from-stereo, structure-from-motion, visual odometry, the most popular feature detectors for camera (Harris, FAST, SURF, SIFT) and laser images, and finally bag-of-feature approaches for place recognition and image retrieval. In chapter 5, we have added an introduction to probability theory, and improved and expanded the description of Markov and Kalman filter localization using a better formalism and more examples. Furthermore, we have also added the description of the Simultaneous Localiza- tion and Mapping (SLAM) problem along with a description of the most popular approaches to solve it such as extended-Kalman-filter SLAM, graph-based SLAM, particle filter SLAM, and the most recent monocular visual SLAM. Finally, in chapter 6 we have added the description of graph-search algorithms for path planning such as breadth-first, depth first, Dijkstra, A*, D*, and rapidly exploring random trees. Besides these many new additions, we have also provided state-of-the-art references and links to online resources xvi Preface and downloadable software. We hope that this book will empower both undergraduate and graduate robotics students with the background knowledge and analytical tools they will need to evaluate and even criticize mobile robot proposals and artifacts throughout their careers. This textbook is suit- able as a whole for introductory mobile robotics coursework at both the undergraduate and graduate level. Individual chapters such as those on perception or kinematics can be useful as overviews in more focused courses on specific subfields of robotics. The origins of this book bridge the Atlantic Ocean. The authors have taught courses on mobile robotics at the undergraduate and graduate level at Stanford University, ETH Zur- ich, Carnegie Mellon University and EPFL. Their combined set of curriculum details and lecture notes formed the earliest versions of this text. We have combined our individual notes, provided overall structure and then test-taught using this textbook for two additional years before settling on the first edition in 2004, and another six years for the current, pub- lished text. For an overview of the organization of the book and summaries of individual chapters, refer to section 1.2. Finally, for the teacher and the student: we hope that this textbook will prove to be a fruitful launching point for many careers in mobile robotics. That would be the ultimate reward. 1 Introduction 1.1 Introduction Robotics has achieved its greatest success to date in the world of industrial manufacturing. Robot arms, or manipulators, comprise a $ 2 billion industry. Bolted at its shoulder to a spe- cific position in the assembly line, the robot arm can move with great speed and accuracy to perform repetitive tasks such as spot welding and painting (figure 1.1). In the electronics industry, manipulators place surface-mounted components with superhuman precision, making the portable telephone and laptop computer possible. Yet, for all of their successes, these commercial robots suffer from a fundamental dis- advantage: lack of mobility. A fixed manipulator has a limited range of motion that depends © KUKA Inc. © SIG Demaurex SA Figure 1.1 Picture of auto assembly plant-spot welding robot of KUKA and a parallel robot Delta of SIG Dem- aurex SA (invented at EPFL ) during packaging of chocolates. 2 Chapter 1 on where it is bolted down. In contrast, a mobile robot would be able to travel throughout the manufacturing plant, flexibly applying its talents wherever it is most effective. This book focuses on the technology of mobility: how can a mobile robot move unsu- pervised through real-world environments to fulfill its tasks? The first challenge is locomo- tion itself. How should a mobile robot move, and what is it about a particular locomotion mechanism that makes it superior to alternative locomotion mechanisms? Hostile environments such as Mars trigger even more unusual locomotion mechanisms (figure 1.2). In dangerous and inhospitable environments, even on Earth, such teleoperated systems have gained popularity (figures 1.3-1.6). In these cases, the low-level complexities of the robot often make it impossible for a human operator to control its motions directly. The human performs localization and cognition activities but relies on the robot’s control scheme to provide motion control. For example, Plustech’s walking robot provides automatic leg coordination while the human operator chooses an overall direction of travel (figure 1.3). Figure 1.6 depicts an underwater vehicle that controls three propellers to stabilize the robot submarine autono- mously in spite of underwater turbulence and water currents while the operator chooses position goals for the submarine to achieve. Other commercial robots operate not where humans cannot go, but rather share space with humans in human environments (figure 1.7). These robots are compelling not for rea- sons of mobility but because of their autonomy, and so their ability to maintain a sense of position and to navigate without human intervention is paramount. Figure 1.2 The mobile robot Sojourner was used during the Pathfinder mission to explore Mars in summer 1997. It was almost completely teleoperated from Earth. However, some on-board sensors allowed for obstacle detection (http://ranier.oact.hq.nasa.gov/telerobotics_page/telerobotics.shtm). © NASA/JPL. Introduction 3 Figure 1.3 Plustech developed the first application-driven walking robot. It is designed to move wood out of the forest. The leg coordination is automated, but navigation is still done by the human operator on the robot. (http://www.plustech.fi). © Plustech. Figure 1.4 The MagneBike robot developed by ASL (ETH Zurich) and ALSTOM. MagneBike is a magnetic wheeled robot with high mobility for inspecting complex shaped structures such as ferromagnetic pipes and turbines (http://www.asl.ethz.ch/). © ALSTOM / ETH Zurich. 4 Chapter 1 Figure 1.5 Picture of Pioneer, a robot designed to explore the Sarcophagus at Chernobyl. © Wide World Photos. Figure 1.6 The autonomous underwater vehicle (AUV) Sirius being retrieved after a mission aboard the RV Southern Surveyor © Robin Beaman—James Cook University. Introduction 5 Figure 1.7 Tour-guide robots are able to interact and present exhibitions in an educational way [85, 251, 288, 310,]. Ten Roboxes have operated during five months at the Swiss exhibition EXPO.02, meeting hun- dreds of thousands of visitors. They were developed by EPFL (http://robotics.epfl.ch) and com- mercialized by BlueBotics (http://www.bluebotics.com). For example, AGV (autonomous guided vehicle) robots (figure 1.8) autonomously deliver parts between various assembly stations by following special electrical guidewires installed in the floor (figure 1.8a) or, differently, by using onboard lasers to localize within a user-specified map (figure 1.8b). The Helpmate service robot transports food and medi- cation throughout hospitals by tracking the position of ceiling lights, which are manually specified to the robot beforehand (figure 1.9). Several companies have developed autono- mous cleaning robots, mainly for large buildings (figure 1.10). One such cleaning robot is in use at the Paris Metro. Other specialized cleaning robots take advantage of the regular geometric pattern of aisles in supermarkets to facilitate the localization and navigation tasks. Research into high-level questions of cognition, localization, and navigation can be per- formed using standard research robot platforms that are tuned to the laboratory environ- ment. This is one of the largest current markets for mobile robots. Various mobile robot platforms are available for programming, ranging in terms of size and terrain capability. Very popular research robots are the Pioneer, BIBA, and the e-puck (figures 1.11-1.13) and also very small robots like the Alice from EPFL (Swiss Federal Institute of Technology at Lausanne) (figure 1.14). 6 Chapter 1 a) b) Figure 1.8 (a) Autonomous guided vehicle (AGV) by SWISSLOG used to transport motor blocks from one assembly station to another. It is guided by an electrical wire installed in the floor. © Swisslog. (b) Equipped with the Autonomous Navigation Technology (ANT) from BlueBotics, Paquito, the autonomous forklift by Esatroll, does not rely on electrical wires, magnetic plots, or reflectors, but rather uses the onboard safety lasers to localize itself with respect to the shape of the environment. Image courtesy of BlueBotics (http://www.bluebotics.com). front back Figure 1.9 HELPMATE is a mobile robot used in hospitals for transportation tasks. It has various on-board sen- sors for autonomous navigation in the corridors. The main sensor for localization is a camera looking to the ceiling. It can detect the lamps on the ceiling as references, or landmarks (http:// www.pyxis.com). © Pyxis Corp. Introduction 7 a) b) Figure 1.10 (a) The Robot40 is a consumer robot developed and sold by Cleanfix for cleaning large gymnasiums. The navigation system of Robo40 is based on a sophisticated sonar and infrared system (http:// www.cleanfix.com). © Cleanfix. (b) The RoboCleaner RC 3000 covers badly soiled areas with a spe- cial driving strategy until it is really clean. Optical sensors measure the degree of pollution of the aspi- rated air (http://www.karcher.de). © Alfred Kärcher GmbH & Co. Figure 1.11 PIONEER is a modular mobile robot offering various options like a gripper or an on-board camera. It is equipped with a sophisticated navigation library developed at SRI, Stanford, CA. Reprinted with permission from ActivMedia Robotics, http://www.MobileRobots.com. 8 Chapter 1 Figure 1.12 BIBA is a very sophisticated mobile robot developed for research purposes and built by BlueBotics (http://www.bluebotics.com/). It has a large variety of sensors for high-performance navigation tasks. Figure 1.13 The e-puck is an educational desktop mobile robot developed at the EPFL. It is only about 70 mm in diameter. As extensions to the basic capabilities, various modules such as additional sensors, actuators, or computational power have been developed. In this picture, two example extensions are shown: (center) an omnidirectional camera and (right) an infrared distance scanner (http://www.e- puck.org/). © Ecole Polytechnique Fédérale de Lausanne (EPFL). Introduction 9 Figure 1.14 Alice is one of the smallest fully autonomous robots. It is approximately 2  2  2 cm, it has an autonomy of about 8 hours and uses infrared distance sensors, tactile whiskers, or even a small camera for navigation. Although mobile robots have a broad set of applications and markets as summarized above, there is one fact that is true of virtually every successful mobile robot: its design involves the integration of many different bodies of knowledge. No mean feat, this makes mobile robotics as interdisciplinary a field as there can be. To solve locomotion problems, the mobile roboticist must understand mechanism and kinematics, dynamics and control theory. To create robust perceptual systems, the mobile roboticist must leverage the fields of signal analysis and specialized bodies of knowledge such as computer vision to properly employ a multitude of sensor technologies. Localization and navigation demand knowl- edge of computer algorithms, information theory, artificial intelligence, and probability theory. Figure 1.15 depicts an abstract control scheme for mobile robot systems that we will use throughout this text. This figure identifies many of the main bodies of knowledge associ- ated with mobile robotics. This book provides an introduction to all aspects of mobile robotics, including software and hardware design considerations, related technologies, and algorithmic techniques. The intended audience is broad, including both undergraduate and graduate students in intro- ductory mobile robotics courses, as well as individuals fascinated by the field. Although it is not absolutely required, a familiarity with matrix algebra, calculus, probability theory, and computer programming will significantly enhance the reader’s experience. 10 Chapter 1 Knowledge, Mission Data Base Commands Localization “Position” Cognition Map Building Global Map Path Planning Environment Model Path Local Map Information Path Extraction and Execution Interpretation Motion Control Perception Raw data Actuator Commands Sensing Acting Real World Environment Figure 1.15 Reference control scheme for mobile robot systems used throughout this book. Mobile robotics is a large field, and this book focuses not on robotics in general, or on mobile robot applications, but rather on mobility itself. From mechanism and perception to localization and navigation, this book focuses on the techniques and technologies that enable robust mobility. Clearly, a useful, commercially viable mobile robot does more than just move. It pol- ishes the supermarket floor, keeps guard in a factory, mows the golf course, provides tours in a museum, or provides guidance in a supermarket. The aspiring mobile roboticist will start with this book but will quickly graduate to coursework and research specific to the desired application, integrating techniques from fields as disparate as human-robot interac- tion, computer vision, and speech understanding. Introduction 11 1.2 An Overview of the Book This book introduces the different aspects of a robot in modules, much like the modules shown in figure 1.15. Chapters 2 and 3 focus on the robot’s low-level locomotive ability. Chapter 4 presents an in-depth view of perception. Chapters 5 and 6 take us to the higher- level challenges of localization and mapping and even higher-level cognition, specifically the ability to navigate robustly. Each chapter builds upon previous chapters, and so the reader is encouraged to start at the beginning, even if his or her interest is primarily at the high level. Robotics is peculiar in that solutions to high-level challenges are most meaning- ful only in the context of a solid understanding of the low-level details of the system. Chapter 2, “Locomotion,” begins with a survey of the most important mechanisms that enable locomotion: wheels, legs, and flight. Numerous robotic examples demonstrate the particular talents of each form of locomotion. But designing a robot’s locomotive system properly requires the ability to evaluate its overall motion capabilities quantitatively. Chap- ter 3, “Mobile Robot Kinematics,” applies principles of kinematics to the whole robot, beginning with the kinematic contribution of each wheel and graduating to an analysis of robot maneuverability enabled by each mobility mechanism configuration. The greatest single shortcoming in conventional mobile robotics is, without doubt, per- ception: mobile robots can travel across much of earth’s man-made surfaces, but they cannot perceive the world nearly as well as humans and other animals. Chapter 4, “Percep- tion,” begins a discussion of this challenge by presenting a clear language for describing the performance envelope of mobile robot sensors. With this language in hand, chapter 4 goes on to present many of the off-the-shelf sensors available to the mobile roboticist, describing their basic principles of operation as well as their performance limitations. The most promising sensor for the future of mobile robotics is vision, and chapter 4 includes an overview of the theory of camera image formation, omnidirectional vision, camera calibra- tion, structure from stereovision, structure from motion, and visual odometry. But percep- tion is more than sensing. Perception is also the interpretation of sensed data in meaningful ways. The second half of chapter 4 describes strategies for feature extraction that have been most useful in both computer vision and mobile robotics applications, including extraction of geometric shapes from range sensing data, as well as point features (such as Harris, SIFT, SURF, FAST, and so on) from camera images. Furthermore, a section is dedicated to the description of the most recent bag-of-feature approach that became popular for place recognition and image retrieval. Armed with locomotion mechanisms and outfitted with hardware and software for per- ception, the mobile robot can move and perceive the world. The first point at which mobil- ity and sensing must meet is localization: mobile robots often need to maintain a sense of position. Chapter 5, “Mobile Robot Localization,” describes approaches that obviate the need for direct localization, then delves into fundamental ingredients of successful local- 12 Chapter 1 ization strategies: belief representation and map representation. Case studies demonstrate various localization schemes, including both Markov localization and Kalman filter local- ization. The final part of chapter 5 is devoted to a description of the Simultaneous Local- ization and Mapping (SLAM) problem along with a description of the most popular approaches to solve it such as extended-Kalman-filter SLAM, graph-based SLAM, particle filter SLAM, and the most recent monocular visual SLAM. Mobile robotics is so young a discipline that it lacks a standardized architecture. There is as yet no established robot operating system. But the question of architecture is of para- mount importance when one chooses to address the higher-level competences of a mobile robot: how does a mobile robot navigate robustly from place to place, interpreting data, and localizing and controlling its motion all the while? For this highest level of robot compe- tence, which we term navigation competence, there are numerous mobile robots that show- case particular architectural strategies. Chapter 6, “Planning and Navigation,” surveys the state of the art of robot navigation, showing that today’s various techniques are quite sim- ilar, differing primarily in the manner in which they decompose the problem of robot con- trol. But first, chapter 6 addresses two skills that a competent, navigating robot usually must demonstrate: obstacle avoidance and path planning. There is far more to know about the cross-disciplinary field of mobile robotics than can be contained in a single book. We hope, though, that this broad introduction will place the reader in the context of the collective wisdom of mobile robotics. This is only the begin- ning. With luck, the first robot you program or build will have only good things to say about you. 2 Locomotion 2.1 Introduction A mobile robot needs locomotion mechanisms that enable it to move unbounded through- out its environment. But there are a large variety of possible ways to move, and so the selec- tion of a robot’s approach to locomotion is an important aspect of mobile robot design. In the laboratory, there are research robots that can walk, jump, run, slide, skate, swim, fly, and, of course, roll. Most of these locomotion mechanisms have been inspired by their bio- logical counterparts (see figure 2.1). There is, however, one exception: the actively powered wheel is a human invention that achieves extremely high efficiency on flat ground. This mechanism is not completely for- eign to biological systems. Our bipedal walking system can be approximated by a rolling polygon, with sides equal in length d to the span of the step (figure 2.2). As the step size decreases, the polygon approaches a circle or wheel. But nature did not develop a fully rotating, actively powered joint, which is the technology necessary for wheeled locomo- tion. Biological systems succeed in moving through a wide variety of harsh environments. Therefore, it can be desirable to copy their selection of locomotion mechanisms. However, replicating nature in this regard is extremely difficult for several reasons. To begin with, mechanical complexity is easily achieved in biological systems through structural replica- tion. Cell division, in combination with specialization, can readily produce a millipede with several hundred legs and several tens of thousands of individually sensed cilia. In man- made structures, each part must be fabricated individually, and so no such economies of scale exist. Additionally, the cell is a microscopic building block that enables extreme min- iaturization. With very small size and weight, insects achieve a level of robustness that we have not been able to match with human fabrication techniques. Finally, the biological energy storage system and the muscular and hydraulic activation systems used by large ani- mals and insects achieve torque, response time, and conversion efficiencies that far exceed similarly scaled man-made systems. 14 Chapter 2 Type of motion Resistance to motion Basic kinematics of motion Flow in a Channel Hydrodynamic forces Eddies Crawl Friction forces Longitudinal vibration Sliding Friction forces Transverse vibration Periodic bouncing Running Loss of kinetic energy on a spring Rolling of a polygon Walking Loss of kinetic energy (see ( figure 2.2) Figure 2.1 Locomotion mechanisms used in biological systems. Owing to these limitations, mobile robots generally locomote either using wheeled mechanisms, a well-known human technology for vehicles, or using a small number of articulated legs, the simplest of the biological approaches to locomotion (see figure 2.2). In general, legged locomotion requires higher degrees of freedom and therefore greater mechanical complexity than wheeled locomotion. Wheels, in addition to being simple, are extremely well suited to flat ground. As figure 2.3 depicts, on flat surfaces wheeled loco- motion is one to two orders of magnitude more efficient than legged locomotion. The rail- way is ideally engineered for wheeled locomotion because rolling friction is minimized on a hard and flat steel surface. But as the surface becomes soft, wheeled locomotion accumu- lates inefficiencies due to rolling friction, whereas legged locomotion suffers much less because it consists only of point contacts with the ground. This is demonstrated in figure 2.3 by the dramatic loss of efficiency in the case of a tire on soft ground. In effect, the efficiency of wheeled locomotion depends greatly on environmental qual- ities, particularly the flatness and hardness of the ground, while the efficiency of legged Locomotion 15 h O l   d Figure 2.2 A biped walking system can be approximated by a rolling polygon, with sides equal in length d to the span of the step. As the step size decreases, the polygon approaches a circle or wheel with the radius l. 100 ft so n eo nd ou tir gr ng di s li g/ 10 lin unit power (hp/ton) g n aw ki al cr w g in f l ow nn ru 1 el he w ay ilw ra 0.1 1 10 100 speed (miles/hour) Figure 2.3 Specific power versus attainable speed of various locomotion mechanisms. 16 Chapter 2 Figure 2.4 RoboTrac, a hybrid wheel-leg vehicle for rough terrain. locomotion depends on the leg mass and body mass, both of which the robot must support at various points in a legged gait. It is understandable, therefore, that nature favors legged locomotion, since locomotion systems in nature must operate on rough and unstructured terrain. For example, in the case of insects in a forest, the vertical variation in ground height is often an order of magnitude greater than the total height of the insect. By the same token, the human environment fre- quently consists of engineered, smooth surfaces, both indoors and outdoors. Therefore, it is also understandable that virtually all industrial applications of mobile robotics utilize some form of wheeled locomotion. Recently, for more natural outdoor environments, there has been some progress toward hybrid and legged industrial robots such as the forestry robot shown in figure 2.4. In section 2.1.1, we present general considerations that concern all forms of mobile robot locomotion. Following this, in sections 2.2. 2.3, and 2.4 we present overviews of legged locomotion, wheeled locomotion, and aerial locomotion techniques for mobile robots. 2.1.1 Key issues for locomotion Locomotion is the complement of manipulation. In manipulation, the robot arm is fixed but moves objects in the workspace by imparting force to them. In locomotion, the environ- ment is fixed and the robot moves by imparting force to the environment. In both cases, the scientific basis is the study of actuators that generate interaction forces and mechanisms Locomotion 17 that implement desired kinematic and dynamic properties. Locomotion and manipulation thus share the same core issues of stability, contact characteristics, and environmental type: stability - number and geometry of contact points - center of gravity - static/dynamic stability - inclination of terrain characteristics of contact - contact point/path size and shape - angle of contact - friction type of environment - structure - medium (e.g., water, air, soft or hard ground) A theoretical analysis of locomotion begins with mechanics and physics. From this start- ing point, we can formally define and analyze all manner of mobile robot locomotion sys- tems. However, this book focuses on the mobile robot navigation problem, particularly stressing perception, localization, and cognition. Thus, we will not delve deeply into the physical basis of locomotion. Nevertheless, the three remaining sections in this chapter present overviews of issues in legged locomotion , wheeled locomotion, and aerial locomotion. Chapter 3 presents a more detailed analysis of the kinematics and control of wheeled mobile robots. 2.2 Legged Mobile Robots Legged locomotion is characterized by a series of point contacts between the robot and the ground. The key advantages include adaptability and maneuverability in rough terrain (fig- ure 2.5). Because only a set of point contacts is required, the quality of the ground between those points does not matter as long as the robot can maintain adequate ground clearance. In addition, a walking robot is capable of crossing a hole or chasm so long as its reach exceeds the width of the hole. A final advantage of legged locomotion is the potential to manipulate objects in the environment with great skill. An excellent insect example, the dung beetle, is capable of rolling a ball while locomoting by way of its dexterous front legs. The main disadvantages of legged locomotion include power and mechanical complex- ity. The leg, which may include several degrees of freedom, must be capable of sustaining part of the robot’s total weight, and in many robots it must be capable of lifting and lower- ing the robot. Additionally, high maneuverability will only be achieved if the legs have a 18 Chapter 2 Figure 2.5 Legged robots are particularly suited for rough terrain, where they are able to traverse obstacles such as steps (a), gaps (b), or sandy patches (c) that are impassable for wheeled systems. Additionally, the high number of degrees of freedom allows the robot to stand up when fallen (d) and keep its payload leveled (e). Because legged systems do not require a continuous path for sup- port, they can rely on a few selected footholds, which also reduces the environmental impact (f). Image courtesy of D. Remy. sufficient number of degrees of freedom to impart forces in a number of different direc- tions. 2.2.1 Leg configurations and stability Because legged robots are biologically inspired, it is instructive to examine biologically successful legged systems. A number of different leg configurations have been successful in a variety of organisms (figure 2.6). Large animals, such as mammals and reptiles, have four legs, whereas insects have six or more legs. In some mammals, the ability to walk on only two legs has been perfected. Especially in the case of humans, balance has progressed to the point that we can even jump with one leg.1 This exceptional maneuverability comes at a price: much more complex active control to maintain balance. 1. In child development, one of the tests used to determine if the child is acquiring advanced loco- motion skills is the ability to jump on one leg. Locomotion 19 mammals reptiles insects two or four legs four legs six legs Figure 2.6 Arrangement of the legs of various animals. In contrast, a creature with three legs can exhibit a static, stable pose provided that it can ensure that its center of gravity is within the tripod of ground contact. Static stability, dem- onstrated by a three-legged stool, means that balance is maintained with no need for motion. A small deviation from stability (e.g., gently pushing the stool) is passively cor- rected toward the stable pose when the upsetting force stops. But a robot must be able to lift its legs in order to walk. In order to achieve static walk- ing, a robot must have at least four legs, moving one of it at a time. For six legs, it is possible to design a gait in which a statically stable tripod of legs is in contact with the ground at all times (figure 2.9). Insects and spiders are immediately able to walk when born. For them, the problem of balance during walking is relatively simple. Mammals, with four legs, can achieve static walking, which, however, is less stable due to the high center of gravity than, for example, reptile walking. Fawns, for example, spend several minutes attempting to stand before they are able to do so, then spend several more minutes learning to walk without falling. Humans, with two legs, can also stand statically stable due to their large feet. Infants require months to stand and walk, and even longer to learn to jump, run, and stand on one leg. There is also the potential for great variety in the complexity of each individual leg. Once again, the biological world provides ample examples at both extremes. For instance, in the case of the caterpillar, each leg is extended using hydraulic pressure by constricting the body cavity and forcing an increase in pressure, and each leg is retracted longitudinally by relaxing the hydraulic pressure, then activating a single tensile muscle that pulls the leg in toward the body. Each leg has only a single degree of freedom, which is oriented longi- tudinally along the leg. Forward locomotion depends on the hydraulic pressure in the body, which extends the distance between pairs of legs. The caterpillar leg is therefore mechani- cally very simple, using a minimal number of extrinsic muscles to achieve complex overall locomotion. 20 Chapter 2 hip abduction angle () abduction-adduction  knee flexion angle () lift  upper thigh link  main drive hip flexion angle () lower thigh link shank link Figure 2.7 Two examples of legs with three degrees of freedom. At the other extreme, the human leg has more than seven major degrees of freedom, combined with further actuation at the toes. More than fifteen muscle groups actuate eight complex joints. In the case of legged mobile robots, a minimum of two degrees of freedom is generally required to move a leg forward by lifting the leg and swinging it forward. More common is the addition of a third degree of freedom for more complex maneuvers, resulting in legs such as those shown in figure 2.7. Recent successes in the creation of bipedal walking robots have added a fourth degree of freedom at the ankle joint. The ankle enables the robot to shift the resulting force vector of the ground contact by actuating the pose of the sole of the foot. In general, adding degrees of freedom to a robot leg increases the maneuverability of the robot, both augmenting the range of terrains on which it can travel and the ability of the robot to travel with a variety of gaits. The primary disadvantages of additional joints and actuators are, of course, energy, control, and mass. Additional actuators require energy and control, and they also add to leg mass, further increasing power and load requirements on existing actuators. In the case of a multilegged mobile robot, there is the issue of leg coordination for loco- motion, or gait control. The number of possible gaits depends on the number of legs. The gait is a sequence of lift and release events for the individual legs. For a mobile robot with k legs, the total number of distinct event sequences N for a walking machine is: N =  2k – 1 ! (2.1) For a biped walker k = 2 legs, the number of distinct event sequences N is: Locomotion 21 N =  2k – 1 ! = 3! = 3  2  1 = 6 (2.2) The six distinct event sequences that can be combined for more complex sequences are: 1. both legs down – right down / left up – both legs down; 2. both legs down – right leg up / left leg down – both legs down; 3. both legs down – both legs up – both legs down; 4. right leg down / left leg up – right leg up / left leg down – right leg down / left leg up; 5. right leg down / left leg up – both legs up – right leg down / left leg up; 6. right leg up / left leg down – both legs up – right leg up / left leg down. Of course, this quickly grows quite large. For example, a robot with six legs has far more events: N = 11! = 39916800 , (2.3) with an even higher number of theoretically possible gaits. Figures 2.8 and 2.9 depict several four-legged gaits and the static six-legged tripod gait. 2.2.2 Consideration of dynamics The cost of transportation expresses how much energy a robot uses to travel a certain dis- tance. To better compare differently sized systems, this value is usually normalized by the robot’s weight and expressed in J /  N  m  —a dimensionless quantity—where J stands for joule, N for newton, and m for meter. When a robot moves with constant speed on a level surface, its potential and kinetic energy remain constant. In theory, no physical work is nec- essary to keep it moving, which makes it possible to get from one place to another with zero cost of transportation. In reality, however, some energy is always dissipated, and robots have to be equipped with actuators and batteries to compensate for the losses. For a wheeled robot, the main causes for such losses are the friction in the drive train and the rolling resis- tance of the wheels on the ground. Similarly, friction is present in the joints of legged sys- tems and energy is dissipated by the foot-ground interaction. However, these effects cannot explain why legged systems usually consume considerably more energy than their wheeled counterparts. The bulk part of energy loss actually originates in the fact that legs—in con- trast to wheels or tracks—are not performing a continuous motion, but are periodically moving back and forth. Joints have to undergo alternating phases of acceleration and decel- eration, and, as we have only a very limited ability to recuperate the negative work of decel- eration, energy is irrecoverably lost in the process. Because of the segmented structure of 22 Chapter 2 flight trot bound Figure 2.8 Two gaits with four legs. the legs, it can even happen that energy that is fed into one joint (e.g., the knee) is simulta- neously dissipated in another joint (e.g., the hip) without creating any net work at the feet. Therefore, actuators are working against each other. A solution to this problem is a better exploitation of the dynamics of the mechanical structure. The natural oscillations of pendula and springs, can—if they are well designed— automatically create the required periodic motions. For example, the motion of a swinging leg can be grasped by the dynamics of a simple double pendulum. If the lengths and the inertial properties of the leg segments are correctly selected, such a pendulum will automat- ically swing forward, clear the ground, and extend the leg to touch the ground in front of the main body. If, on the other side, a foot is on the ground and the leg is kept stiff, an inverted pendulum motion will efficiently propel the main body forward. During running, these inverted pendulum dynamics are additionally enhanced by springs, which store Locomotion 23 Figure 2.9 Static walking with six legs. A tripod formed by three legs always exists. energy during the ground phase and allow the main body to take off for the subsequent flight phase (figure 2.10). With this approach it is, in fact, possible to build legged robots that do not have actuation of any kind. Such passive dynamic walkers [211,344] walk down a shallow incline (which compensates for frictional losses), but, because no actuators are present, no negative work is performed and energetic losses due to braking are eliminated. In addition to creating a periodic motion, the dynamics of such walkers must be designed to ensure dynamic stabil- ity. The mechanical structure must passively reject small disturbances which would other- wise accumulate over time and eventually cause the robot to fall. Actuated robots built according to these principles can walk with a remarkable efficiency and one of them, the Cornell Ranger, currently holds the distance record for autonomous legged robots (figure 2.11). Passive dynamic walkers also have a striking similarity to the physique and motion pat- ters of human gait. During the evolution, humans and animals have become quite efficient walkers, and a look at electromyography recordings shows that during walking our muscles 24 Chapter 2 Figure 2.10 Dynamic elements that are exploited in energy efficient walking include the double-pen- dulum for leg swing, the inverted pendulum for the stance phase of walking, and springy legs for run- ning gaits. Image courtesy of D. Remy. Figure 2.11 The Cornell powered two-legged and four-legged biped robots. In April 2008, the four- legged bipedal robot Ranger walked a distance of 9.07 km without being touched by a person. Image courtesy of the Biorobotics and Locomotion Lab—Cornell University. are far less active than one would expect for a task in which most of our limbs are in con- stant motion. To some degree, humans are passive dynamic walkers. It is obvious that such an exploitation of the mechanical dynamics can only work at spe- cific velocities. When the locomotion speed changes, characteristic properties such as stride length or stride frequency change as well, and—because these have to be matched with the spring and pendulum oscillations of the mechanical structure—more and more actuator effort is needed to force the joints to follow their required trajectories. For human walking, the optimal walking speed is approximately 1 m/s, which is also the range that subjectively feels most comfortable. For both higher and lower speeds, the cost of transpor- tation will increase, and more energy is needed to travel the same distance. For this reason, humans change their gait from walking to running when they want to travel at higher speeds, which is more efficient than just performing the same motion faster and faster. Locomotion 25 Figure 2.12 Metabolic cost of transportation (here normalized by body mass) for different gaits of horses: walking (W), running (R), and galloping (G). Each gait has a specific velocity that minimizes energy expenditure. This explains why animals and humans change their gait when traveling at dif- ferent speeds. Image courtesy of A. E. Minetti. Changing the gait allows us to use a different set of natural dynamics, which better matches the stride frequency and step length that are needed for higher velocities. Likewise, the wide variety of gaits found in animals can be explained by the use of different sets of dynamic elements, which minimize the energy necessary for transportation (figure 2.12). 2.2.3 Examples of legged robot locomotion Although there are no high-volume industrial applications to date, legged locomotion is an important area of long-term research. Several interesting designs are presented here, begin- ning with the one-legged robot and finishing with six-legged robots. 2.2.3.1 One leg The minimum number of legs a legged robot can have is, of course, one. Minimizing the number of legs is beneficial for several reasons. Body mass is particularly important to walking machines, and the single leg minimizes cumulative leg mass. Leg coordination is required when a robot has several legs, but with one leg no such coordination is needed. Perhaps most important, the one-legged robot maximizes the basic advantage of legged locomotion: legs have single points of contact with the ground in lieu of an entire track, as 26 Chapter 2 Figure 2.13 The Raibert hopper [42, 264]. Image courtesy of the LegLab and Marc Raibert. © 1983. with wheels. A single-legged robot requires only a sequence of single contacts, making it amenable to the roughest terrain. Furthermore, a hopping robot can dynamically cross a gap that is larger than its stride by taking a running start, whereas a multilegged walking robot that cannot run is limited to crossing gaps that are as large as its reach. The major challenge in creating a single-legged robot is balance. For a robot with one leg, static walking is not only impossible, but static stability when stationary is also impos- sible. The robot must actively balance itself by either changing its center of gravity or by imparting corrective forces. Thus, the successful single-legged robot must be dynamically stable. Figure 2.13 shows the Raibert hopper [42, 264], one of the best-known single-legged hopping robots created. This robot makes continuous corrections to body attitude and to robot velocity by adjusting the leg angle with respect to the body. The actuation is hydrau- lic, including high-power longitudinal extension of the leg during stance to hop back into the air. Although powerful, these actuators require a large, off-board hydraulic pump to be connected to the robot at all times. Figure 2.14 shows a more energy-efficient design that takes advantage of well-designed mechanical dynamics. Instead of supplying power by means of an off-board hydraulic pump, the bow leg hopper is designed to capture the kinetic energy of the robot as it lands, Locomotion 27 Figure 2.14 The 2D single bow leg hopper. Image courtesy of H. Benjamin Brown and Garth Zeglin, CMU. using an efficient bow spring leg. This spring returns approximately 85% of the energy, meaning that stable hopping requires only the addition of 15% of the required energy on each hop. This robot, which is constrained along one axis by a boom, has demonstrated con- tinuous hopping for 20 minutes using a single set of batteries carried on board the robot. As with the Raibert hopper, the bow leg hopper controls velocity by changing the angle of the leg to the body at the hip joint. Ringrose demonstrates the very important duality of mechanics and controls as applied to a single-legged hopping machine. Often clever mechanical design can perform the same operations as complex active control circuitry. In this robot, the physical shape of the foot is exactly the right curve so that when the robot lands without being perfectly ver- tical, the proper corrective force is provided from the impact, making the robot vertical by the next landing. This robot is dynamically stable, and is furthermore passive. The correc- tion is provided by physical interactions between the robot and its environment, with no computer or any active control in the loop. 2.2.3.2 Two legs (biped) A variety of successful bipedal robots have been demonstrated over the past ten years. Two legged robots have been shown to run, jump, travel up and down stairways, and even do aerial tricks such as somersaults. In the commercial sector, both Honda and Sony have made significant advances over the past decade that have enabled highly capable bipedal robots. Both companies designed small, powered joints that achieve power-to-weight per- 28 Chapter 2 Specifications: Weight: 7 kg Height: 58 cm Neck DOF: 4 Body DOF: 2 Arm DOF: 2 5 Legs DOF: 2 6 Five-finger Hands Figure 2.15 The Sony SDR-4X II. © 2003 Sony Corporation. formance unheard of in commercially available servomotors. These new “intelligent” servos provide not only strong actuation but also compliant actuation by means of torque sensing and closed-loop control. The Sony Dream Robot, model SDR-4X II, is shown in figure 2.15. This current model is the result of research begun in 1997 with the basic objective of motion entertainment and communication entertainment (i.e., dancing and singing). This robot with thirty-eight degrees of freedom has seven microphones for fine localization of sound, image person rec- ognition, on-board miniature stereo depth-map reconstruction, and limited speech recogni- tion. Given the goal of fluid and entertaining motion, Sony spent considerable effort designing a motion prototyping application system to enable their engineers to script dances in a straightforward manner. Note that the SDR-4X II is relatively small, standing at 58 cm and weighing only 7 kg. The Honda humanoid project has a significant history, but, again, it has tackled the very important engineering challenge of actuation. Figure 2.16 shows model P2, which is an immediate predecessor to the most recent Asimo (advanced step in innovative mobility) model. Note that the latest Honda Asimo model is still much larger than the SDR-4X at 120 cm tall and 52 kg. This enables practical mobility in the human world of stairs and ledges while maintaining a nonthreatening size and posture. Perhaps the first robot to demonstrate Locomotion 29 Specifications: Maximum speed: 2 km/h Autonomy: 15 min Weight: 210 kg Height: 1.82 m Leg DOF: 2 6 Arm DOF: 2 7 Figure 2.16 The humanoid robot P2 from Honda, Japan. © Honda Motor Cooperation. biomimetic bipedal stair climbing and descending, these Honda humanoid series robots are being designed not for entertainment purposes but as human aids throughout society. Honda refers, for instance, to the height of Asimo as the minimum height that enables it to manage nonetheless operation of the human world, for instance, control of light switches. An important feature of bipedal robots is their anthropomorphic shape. They can be built to have the same approximate dimensions as humans, and this makes them excellent vehi- cles for research in human-robot interaction. WABIAN-2R is a robot built at Waseda Uni- versity, Japan (figure 2.17) for just such research. WABIAN-2R is designed to emulate human motion, and it is even designed to dance like a human. Bipedal robots can only be statically stable within some limits, and so robots such as P2 and WABIAN-2R generally must perform continuous balance-correcting servoing even when standing still. Furthermore, each leg must have sufficient capacity to support the full weight of the robot. In the case of four-legged robots, the balance problem is facilitated along with the load requirements of each leg. An elegant design of a biped robot is the Spring Flamingo of MIT (figure 2.18). This robot inserts springs in series with the leg actu- ators to achieve a more elastic gait. Combined with “kneecaps” that limit knee joint angles, the Flamingo achieves surprisingly biomimetic motion. 30 Chapter 2 Specifications: Weight: 64 [kg] (with batteries) Height: 1.55 [m] DOF: Leg: 6 2 Foot: 1  2 (passive) Waist: 2 Trunk: 2 Arm: 7 2 Hand: 3 2 Neck: 3 Figure 2.17 The humanoid robot WABIAN-2R developed at Waseda University in Japan (http:// www.takanishi.mech.waseda.ac.jp/). © Atsuo Takanishi Lab, Waseda University. Figure 2.18 The Spring Flamingo developed at MIT. Image courtesy of Jerry Pratt, MIT Leg Laboratory. Locomotion 31 ERS-110 © 1999 Sony Corporation 1 Stereo microphone: Allows AIBO to pick up surrounding sounds. 2 Head sensor: Senses when a person taps or pets AIBO on the head. 3 Mode indicator: Shows AIBO’s operation mode. 4 Eye lights: These light up in blue-green or red to indicate AIBO’s emotional state. 5 Color camera: Allows AIBO to search for objects and recognize them by color and movement. ERS-210 © 2000 Sony Corporation 6 Speaker: Emits various musical tones and sound effects. 7 Chin sensor: Senses when a person touches AIBO on the chin. 8 Pause button: Press to activate AIBO or to pause AIBO. 9 Chest light: Gives information about the status of the robot. 10 Paw sensors: Located on the bottom of each paw. 11 Tail light: Lights up blue or orange to show AIBO’s emotional state. 12 Back sensor: Senses when a person touches AIBO on the back. Figure 2.19 AIBO, the artificial dog from Sony, Japan. 2.2.3.3 Four legs (quadruped) Although standing still on four legs is passively stable, walking remains challenging because to remain stable, the robot’s center of gravity must be actively shifted during the gait. Sony invested several million dollars to develop a four-legged robot called AIBO (fig- ure 2.19). To create this robot, Sony produced both a new robot operating system that is near real-time and new geared servomotors that are of sufficiently high torque to support the robot, yet are back-drivable for safety. In addition to developing custom motors and software, Sony incorporated a color vision system that enables AIBO to chase a brightly colored ball. The robot is able to function for at most one hour before requiring recharging. Early sales of the robot have been very strong, with more than 60,000 units sold in the first year. Nevertheless, the number of motors and the technology investment behind this robot dog resulted in a very high price of approximately $1,500. 32 Chapter 2 Specifications: Weight: 19 kg Height: 0.25 m DOF: 4 3 Figure 2.20 Titan VIII, a quadruped robot developed at Tokyo Institute of Technology (http://www-robot.mes.titech.ac.jp). © Tokyo Institute of Technology. Four-legged robots have the potential to serve as effective artifacts for research in human-robot interaction (figure 2.20). Humans can treat the Sony robot, for example, as a pet and might develop an emotional relationship similar to that between man and dog. Fur- thermore, Sony has designed AIBO’s walking style and general behavior to emulate learn- ing and maturation, resulting in dynamic behavior over time that is more interesting for the owner who can track the changing behavior. As the challenges of high energy storage and motor technology are solved, it is likely that quadruped robots much more capable than AIBO will become common throughout the human environment. BigDog and LittleDog (figure 2.21) are two recent examples of quadruped robots devel- oped by Boston Dynamics and commissioned by the American Defense Advanced Research Projects Agency (DARPA). BigDog is a rough-terrain robot that walks, runs, climbs, and carries heavy loads. It is powered by an engine that drives a hydraulic actuation system. Its legs are articulated like an animal’s, with compliant elements to absorb shock and recycle energy between two steps. The goal of this project is to make it able go any- where people and animals can go. The program is funded by the Tactical Technology Office at DARPA. Conversely, LittleDog is a small-size robot designed for research on learning locomotion. Each leg has a large range of motion and is powered by three electric motors. Therefore, the robot is strong enough for climbing and dynamic locomotion gaits. Another example four-legged robot is ALoF, the quadruped developed at the ASL (ETH Zurich) (figure 2.22).This robot serves as a platform to study energy-efficient locomotion. This is done by exploiting passive dynamic in ways that have shown to be effective in bipedal robots, as has been explained in section 2.2.2. Locomotion 33 Figure 2.21 LittleDog and BigDog quadruped robots developed by Boston Dynamics. Image cour- tesy of Boston Dynamics (http://www.bostondynamics.com). Figure 2.22 ALoF, the quadruped robot developed at the ASL (ETH Zurich), has been built to inves- tigate energy efficient locomotion. This is done by exploiting passive dynamics (http:// www.asl.ethz.ch/). © ASL-ETH Zurich. 2.2.3.4 Six legs (hexapod) Six-legged configurations have been extremely popular in mobile robotics because of their static stability during walking, thus reducing the control complexity (figures 2.23 and 1.3). In most cases, each leg has three degrees of freedom, including hip flexion, knee flexion, 34 Chapter 2 Specifications: Maximum speed: 0.5 m/s Weight: 16 kg Height: 0.3 m Length: 0.7 m No. of legs: 6 DOF in total: 6 3 Power consumption:10 W Figure 2.23 Lauron II, a hexapod platform developed at the University of Karlsruhe, Germany. © University of Karlsruhe. Figure 2.24 Genghis, one of the most famous walking robots from MIT, uses hobby servomotors as its actuators (http://www.ai.mit.edu/projects/genghis). © MIT AI Lab. and hip abduction (see figure 2.7). Genghis is a commercially available hobby robot that has six legs, each of which has two degrees of freedom provided by hobby servos (figure 2.24). Such a robot, which consists only of hip flexion and hip abduction, has less maneu- verability in rough terrain but performs quite well on flat ground. Because it consists of a straightforward arrangement of servomotors and straight legs, such robots can be readily built by a robot hobbyist. Insects, which are arguably the most successful locomoting creatures on earth, excel at traversing all forms of terrain with six legs, even upside down. Currently, the gap between Locomotion 35 the capabilities of six-legged insects and artificial six-legged robots is still quite large. Interestingly, this is not due to a lack of sufficient numbers of degrees of freedom on the robots. Rather, insects combine a small number of active degrees of freedom with passive structures, such as microscopic barbs and textured pads, that increase the gripping strength of each leg significantly. Robotic research into such passive tip structures has only recently begun. For example, a research group is attempting to re-create the complete mechanical function of the cockroach leg. It is clear from these examples that legged robots have much progress to make before they are competitive with their biological equivalents. Nevertheless, significant gains have been realized recently, primarily due to advances in motor design. Creating actuation sys- tems that approach the efficiency of animal muscles remains far from the reach of robotics, as does energy storage with the energy densities found in organic life forms. 2.3 Wheeled Mobile Robots The wheel has been by far the most popular locomotion mechanism in mobile robotics and in man-made vehicles in general. It can achieve very good efficiencies, as demonstrated in figure 2.3, and it does so with a relatively simple mechanical implementation. In addition, balance is not usually a research problem in wheeled robot designs, because wheeled robots are almost always designed so that all wheels are in ground contact at all times. Thus, three wheels are sufficient to guarantee stable balance, although, as we shall see below, two-wheeled robots can also be stable. When more than three wheels are used, a suspension system is required to allow all wheels to maintain ground contact when the robot encounters uneven terrain. Instead of worrying about balance, wheeled robot research tends to focus on the prob- lems of traction and stability, maneuverability, and control: can the robot wheels provide sufficient traction and stability for the robot to cover all of the desired terrain, and does the robot’s wheeled configuration enable sufficient control over the velocity of the robot? 2.3.1 Wheeled locomotion: The design space As we shall see, there is a very large space of possible wheel configurations when one con- siders possible techniques for mobile robot locomotion. We begin by discussing the wheel in detail, since there are a number of different wheel types with specific strengths and weak- nesses. We then examine complete wheel configurations that deliver particular forms of locomotion for a mobile robot. 2.3.1.1 Wheel design There are four major wheel classes, as shown in figure 2.25. They differ widely in their kinematics, and therefore the choice of wheel type has a large effect on the overall kinemat- 36 Chapter 2 a) b) c) d) Swedish 90° Swedish 45° Swedish 45° Figure 2.25 The four basic wheel types. (a) Standard wheel: two degrees of freedom; rotation around the (motor- ized) wheel axle and the contact point.(b) castor wheel: two degrees of freedom; rotation around an offset steering joint. (c) Swedish wheel: three degrees of freedom; rotation around the (motorized) wheel axle, around the rollers, and around the contact point. (d) Ball or spherical wheel: realization technically difficult. ics of the mobile robot. The standard wheel and the castor wheel have a primary axis of rotation and are thus highly directional. To move in a different direction, the wheel must be steered first along a vertical axis. The key difference between these two wheels is that the standard wheel can accomplish this steering motion with no side effects, since the center of rotation passes through the contact patch with the ground, whereas the castor wheel rotates around an offset axis, causing a force to be imparted to the robot chassis during steering. The Swedish wheel and the spherical wheel are both designs that are less constrained by directionality than the conventional standard wheel. The Swedish wheel functions as a normal wheel but provides low resistance in another direction as well, sometimes perpen- dicular to the conventional direction, as in the Swedish 90, and sometimes at an intermedi- ate angle, as in the Swedish 45. The small rollers attached around the circumference of the wheel are passive and the wheel’s primary axis serves as the only actively powered joint. The key advantage of this design is that, although the wheel rotation is powered only along the one principal axis (through the axle), the wheel can kinematically move with very little friction along many possible trajectories, not just forward and backward. The spherical wheel is a truly omnidirectional wheel, often designed so that it may be actively powered to spin along any direction. One mechanism for implementing this spher- ical design imitates the computer mouse, providing actively powered rollers that rest against the top surface of the sphere and impart rotational force. Locomotion 37 Figure 2.26 The Tartan Racing self-driving vehicle developed at CMU, which won the 2007 DARPA Urban Chal- lenge. Image courtesy of the Tartan Racing Team—http://www.tartanracing.org. Regardless of what wheel is used, in robots designed for all-terrain environments and in robots with more than three wheels, a suspension system is normally required to maintain wheel contact with the ground. One of the simplest approaches to suspension is to design flexibility into the wheel itself. For instance, in the case of some four-wheeled indoor robots that use castor wheels, manufacturers have applied a deformable tire of soft rubber to the wheel to create a primitive suspension. Of course, this limited solution cannot compete with a sophisticated suspension system in applications where the robot needs a more dynamic suspension for significantly nonflat terrain. 2.3.1.2 Wheel geometry The choice of wheel types for a mobile robot is strongly linked to the choice of wheel arrangement, or wheel geometry. The mobile robot designer must consider these two issues simultaneously when designing the locomoting mechanism of a wheeled robot. Why do wheel type and wheel geometry matter? Three fundamental characteristics of a robot are governed by these choices: maneuverability, controllability, and stability. Unlike automobiles, which are largely designed for a highly standardized environment (the road network), mobile robots are designed for applications in a wide variety of situa- tions. Automobiles all share similar wheel configurations because there is one region in the design space that maximizes maneuverability, controllability, and stability for their stan- dard environment: the paved roadway. However, there is no single wheel configuration that maximizes these qualities for the variety of environments faced by different mobile robots. So you will see great variety in the wheel configurations of mobile robots. In fact, few robots use the Ackerman wheel configuration of the automobile because of its poor maneu- verability, with the exception of mobile robots designed for the road system (figure 2.26). 38 Chapter 2 Table 2.1 gives an overview of wheel configurations ordered by the number of wheels. This table shows both the selection of particular wheel types and their geometric configu- ration on the robot chassis. Note that some of the configurations shown are of little use in mobile robot applications. For instance, the two-wheeled bicycle arrangement has moder- ate maneuverability and poor controllability. Like a single-legged hopping machine, it can never stand still. Nevertheless, this table provides an indication of the large variety of wheel configurations that are possible in mobile robot design. The number of variations in table 2.1 is quite large. However, there are important trends and groupings that can aid in comprehending the advantages and disadvantages of each configuration. We next identify some of the key trade-offs in terms of the three issues we identified earlier: stability, maneuverability, and controllability. 2.3.1.3 Stability Surprisingly, the minimum number of wheels required for static stability is two. As shown above, a two-wheel differential-drive robot can achieve static stability if the center of mass is below the wheel axle. Cye is a commercial mobile robot that uses this wheel configura- tion (figure 2.27). However, under ordinary circumstances such a solution requires wheel diameters that are impractically large. Dynamics can also cause a two-wheeled robot to strike the floor with a third point of contact, for instance, with sufficiently high motor torques from stand- still. Conventionally, static stability requires a minimum of three wheels, with the addi- tional caveat that the center of gravity must be contained within the triangle formed by the ground contact points of the wheels. Stability can be further improved by adding more wheels, although once the number of contact points exceeds three, the hyperstatic nature of the geometry will require some form of flexible suspension on uneven terrain. 2.3.1.4 Maneuverability Some robots are omnidirectional, meaning that they can move at any time in any direction along the ground plane  x y  regardless of the orientation of the robot around its vertical axis. This level of maneuverability requires wheels that can move in more than just one direction, and so omnidirectional robots usually employ Swedish or spherical wheels that are powered. A good example is Uranus (figure 2.30), a robot that uses four Swedish wheels to rotate and translate independently and without constraints. In general, the ground clearance of robots with Swedish and spherical wheels is some- what limited due to the mechanical constraints of constructing omnidirectional wheels. An interesting recent solution to the problem of omnidirectional navigation while solving this ground-clearance problem is the four-castor wheel configuration in which each castor wheel is actively steered and actively translated. In this configuration, the robot is truly omnidirectional because, even if the castor wheels are facing a direction perpendicular to Locomotion 39 Table 2.1 Wheel configurations for rolling vehicles # of Arrangement Description Typical examples wheels 2 One steering wheel in the front, Bicycle, motorcycle one traction wheel in the rear Two-wheel differential drive Cye personal robot with the center of mass (COM) below the axle 3 Two-wheel centered differen- Nomad Scout, smartRob tial drive with a third point of EPFL contact Two independently driven Many indoor robots, wheels in the rear/front, one including the EPFL robots unpowered omnidirectional Pygmalion and Alice wheel in the front/rear Two connected traction wheels Piaggio minitrucks (differential) in rear, one steered free wheel in front Two free wheels in rear, one Neptune (Carnegie Mellon steered traction wheel in front University), Hero-1 Three motorized Swedish or Stanford wheel spherical wheels arranged in a Tribolo EPFL, triangle; omnidirectional move- Palm Pilot Robot Kit ment is possible (CMU) Three synchronously motorized “Synchro drive” and steered wheels; the orienta- Denning MRV-2, Georgia tion is not controllable Institute of Technology, I- Robot B24, Nomad 200 40 Chapter 2 Table 2.1 Wheel configurations for rolling vehicles # of Arrangement Description Typical examples wheels 4 Two motorized wheels in the Car with rear-wheel drive rear, two steered wheels in the front; steering has to be differ- ent for the two wheels to avoid slipping/skidding. Two motorized and steered Car with front-wheel drive wheels in the front, two free wheels in the rear; steering has to be different for the two wheels to avoid slipping/skid- ding. Four steered and motorized Four-wheel drive, four- wheels wheel steering Hyperion (CMU) Two traction wheels (differen- Charlie (DMT-EPFL) tial) in rear/front, two omnidi- rectional wheels in the front/ rear Four omnidirectional wheels Carnegie Mellon Uranus Two-wheel differential drive EPFL Khepera, Hyperbot with two additional points of Chip contact Four motorized and steered Nomad XR4000 castor wheels Locomotion 41 Table 2.1 Wheel configurations for rolling vehicles # of Arrangement Description Typical exampl