Autonomous Mobile Robots

Autonomous Mobile Robots: Sensing, Control, Decision Making and Applications......Page 4 Preface......Page 6 Editors......Page 9 Contributors......Page 10 Abstract......Page 13 Contents......Page 14 Table of Contents......Page 0 Part I: Sensors and Sensor Fusion......Page 17 CONTENTS......Page 20 1.1.1 Context......Page 21 1.1.2 Classes of UGV......Page 22 1.2.1 Visual Sensors......Page 23 1.2.1.1 Passive imaging......Page 24 1.2.1.2 Active sensors......Page 25 1.2.2.1 The ideal pinhole model......Page 27 1.2.2.2 Calibration......Page 28 1.3.2 World Model Representation......Page 30 1.3.3 Physical Limitations......Page 32 1.3.4.1 State-of-the-art......Page 34 1.3.4.2 A road camera model......Page 36 1.3.5.1 Obstacle detection using range data......Page 38 1.3.5.2 Stereo vision......Page 39 1.3.5.2.1 Rectification......Page 40 1.3.5.3 Application examples......Page 41 1.3.6 Sensor Fusion......Page 43 1.4.1 Terrain Classification......Page 48 1.4.2 Localization and 3D Model Building from Vision......Page 49 1.5 CONCLUSION......Page 51 REFERENCES......Page 52 BIOGRAPHIES......Page 55 CONTENTS......Page 56 2.1 INTRODUCTION......Page 57 2.2 RELATED WORK......Page 59 2.3 FMCW RADAR OPERATION AND RANGE NOISE......Page 60 2.3.1 Noise in FMCW Receivers and Its Effect on Range Detection......Page 62 2.4 RADAR RANGE SPECTRA INTERPRETATION......Page 63 2.4.2 Interpretation of RADAR Noise......Page 65 2.4.2.2 Phase noise......Page 66 2.4.3.1 Power-noise estimation in target absence......Page 68 2.4.3.2 Power-noise estimation in target presence......Page 72 2.4.4 Initial Range Spectra Prediction......Page 75 2.5 CONSTANT FALSE ALARM RATE PROCESSOR FOR TRUE TARGET RANGE DETECTION......Page 79 2.5.1 The Effect of the High Pass Filter on CFAR......Page 80 2.5.1.1 Missed detections with CFAR......Page 81 2.5.1.2 False alarms with CFAR......Page 82 2.6 TARGET PRESENCE PROBABILITY ESTIMATION FOR TRUE TARGET RANGE DETECTION......Page 83 2.6.1 Target Presence Probability Results......Page 87 2.6.2 Merits of the Proposed Algorithm over Other Feature Extraction Techniques......Page 89 2.7 MULTIPLE LINE-OF-SIGHT TARGETS — RADAR PENETRATION......Page 91 2.8 RADAR-BASED AUGMENTED STATE VECTOR......Page 94 2.8.1 Process Model......Page 95 2.8.2 Observation (Measurement) Model......Page 99 2.8.2.1 Predicted power observation formulation......Page 100 2.9 MULTI-TARGET RANGE BIN PREDICTION — RESULTS......Page 104 2.10 CONCLUSIONS......Page 108 ACKNOWLEDGMENTS......Page 109 REFERENCES......Page 110 BIOGRAPHIES......Page 112 CONTENTS......Page 114 3.1 INTRODUCTION......Page 115 3.1.1 Data Fusion — GPS and INS......Page 116 3.2.1 Stochastic Process Models......Page 117 3.2.1.1 Computation of Phi and Qk......Page 119 3.2.2 Basic KF......Page 120 3.2.2.1 Implementation issues......Page 122 3.2.3 Extended KF......Page 124 3.3.1 GPS Measurements......Page 128 3.3.2 Single-Point GPS Navigation Solution......Page 130 3.3.3 KF for Stand-Alone GPS Solutions......Page 134 3.3.3.1 Clock model......Page 135 3.3.3.2 Stationary user (P model)......Page 136 3.3.3.4 High dynamic user (PVA model)......Page 137 3.3.3.5 GPS KF examples......Page 138 3.3.3.6 Summary......Page 142 3.4 INERTIAL NAVIGATION SYSTEM......Page 143 3.4.1 Strapdown System Mechanizations......Page 144 3.4.3 EKF Latency Compensation......Page 146 3.5 INTEGRATION OF GPS AND INS......Page 147 3.5.2 GPS Aided INS......Page 148 3.5.2.1 Loosely coupled system......Page 149 3.5.2.2 Tightly coupled system......Page 150 3.6 CHAPTER SUMMARY......Page 157 ACKNOWLEDGMENTS......Page 158 REFERENCES......Page 159 BIOGRAPHIES......Page 161 CONTENTS......Page 163 4.1 INTRODUCTION......Page 164 4.2 LANDMARK-BASED NAVIGATION......Page 166 4.3.1 Laser Scanner and Angle Observation......Page 168 4.3.2 Triangulation Algorithm......Page 169 4.3.3 KF-Based Navigation Algorithm......Page 171 4.3.4 Implementation and Results......Page 173 4.4 VISION AND DIGITAL LANDMARKS......Page 174 4.4.1.1 Region finding module......Page 175 4.4.1.3 Digits recognition module......Page 177 4.4.2 Position Estimation......Page 179 4.4.2.1 Triangulation method......Page 180 4.4.3 Least Square Estimator (LSE)......Page 182 4.4.3.2 Dual-landmark LSE (DLSE)......Page 183 4.4.4 Implementation and Results......Page 184 4.5 SICK LASER SCANNER AND GEOMETRIC LANDMARKS......Page 187 4.5.1 Circular Hough Transform......Page 188 4.5.2 Least Squares Fitting of Circles......Page 189 4.5.3 Cooperative Position Estimation......Page 193 4.5.4 Implementation and Results......Page 194 4.6 CONCLUSIONS......Page 197 REFERENCES......Page 198 BIOGRAPHIES......Page 200 Part II: Modeling and Control......Page 201 CONTENTS......Page 204 5.1 INTRODUCTION......Page 205 5.2 PRELIMINARIES AND DEFINITIONS......Page 206 5.3 DISCONTINUOUS STABILIZATION......Page 210 5.3.1 Stabilization of Discontinuous Nonholonomic Systems......Page 211 5.3.2 The sigma Process......Page 216 5.3.3 The Issue of Asymptotic Stability......Page 217 5.3.4 An Algorithm to Design Almost Stabilizers......Page 220 5.4 CHAINED SYSTEMS AND POWER SYSTEMS......Page 221 5.5 DISCONTINUOUS CONTROL OF CHAINED SYSTEMS......Page 222 5.5.1 An Example: A Car-Like Vehicle......Page 223 5.6 ROBUST STABILIZATION — PART I......Page 226 5.7.1 The Local Controller......Page 229 5.7.2 The Global Controller......Page 230 5.7.4 Discussion......Page 231 5.8.1 Robust Sampled-Data Control of Power Systems......Page 232 5.8.2 An Example: A Car-Like Vehicle Revisited......Page 233 5.9 CONCLUSIONS......Page 234 REFERENCES......Page 236 BIOGRAPHY......Page 239 6.1 INTRODUCTION......Page 241 6.2 DYNAMICS OF NONHOLONOMIC MOBILE ROBOTS......Page 244 6.3 MULTI-LAYER NF SYSTEMS......Page 249 6.4 ADAPTIVE NF CONTROL DESIGN......Page 254 6.5 SIMULATION STUDIES......Page 268 6.6 CONCLUSION......Page 273 REFERENCES......Page 274 BIOGRAPHIES......Page 276 7.1 INTRODUCTION......Page 278 7.2 DYNAMIC MODELING AND PROPERTIES......Page 280 7.3.1 Kinematic and Dynamic Subsystems......Page 288 7.3.2 Control Design at the Actuator Level......Page 290 7.4 SIMULATION......Page 296 7.5 CONCLUSION......Page 300 REFERENCES......Page 301 BIOGRAPHIES......Page 303 8.1 INTRODUCTION......Page 305 8.2.1 Vehicle Kinematics and Dynamics......Page 307 8.2.2 Dynamics of Tracking Maneuvers......Page 308 8.3 A UNIFIED TRACKING CONTROLLER......Page 309 8.3.1 Kinematics-Based Tracking Controller......Page 318 8.3.2 Dynamics-Based Tracking Controller......Page 320 8.3.3 Requirement of Measurements......Page 323 8.4 TRACKING PERFORMANCE EVALUATION......Page 324 8.4.1.1 Influence of parameter p......Page 325 8.4.1.2 Influence of parameter l......Page 328 8.4.2 Backward Tracking Control......Page 330 8.4.2.1 Influence of parameter p......Page 331 8.5 CONCLUSIONS......Page 334 REFERENCES......Page 337 BIOGRAPHIES......Page 338 Part III: Map Building and Path Planning......Page 340 CONTENTS......Page 343 9.1 INTRODUCTION......Page 344 9.2 SLAM USING THE EXTENDED KALMAN FILTER......Page 347 9.2.1 Initialization......Page 348 9.2.2 Vehicle Motion: The EKF Prediction Step......Page 349 9.2.3 Data Association......Page 350 9.2.5 Adding Newly Observed Features......Page 352 9.2.6 Consistency of EKF–SLAM......Page 353 9.3.1 Individual Compatibility Nearest Neighbor......Page 354 9.3.2 Joint Compatibility......Page 355 9.3.3 Relocation......Page 358 9.3.4 Locality......Page 362 9.4 MAPPING LARGE ENVIRONMENTS......Page 366 9.4.2 Local Map Joining......Page 367 9.4.4 Closing a Large Loop......Page 369 9.4.5 Multi-robot SLAM......Page 373 9.5 CONCLUSIONS......Page 374 APPENDIX: TRANSFORMATIONS IN 2D......Page 375 REFERENCES......Page 376 BIOGRAPHIES......Page 379 CONTENTS......Page 380 10.1 INTRODUCTION......Page 381 10.2 PATH PLANNING......Page 382 10.2.1 Configuration Space......Page 383 10.2.2 Early Approaches......Page 384 10.2.2.1 Roadmap......Page 385 10.2.2.2 Cell decomposition......Page 386 10.2.2.3 Potential field......Page 387 10.2.3 Random Sampling......Page 388 10.2.3.1 Multi-query planning......Page 389 10.2.3.2 Single-query planning......Page 390 10.2.3.3 Probabilistic completeness......Page 392 10.3.1 Kinematic and Dynamic Constraints......Page 393 10.3.2 General Approaches......Page 396 10.3.4 Case Studies on Real Robotic Systems......Page 397 10.3.4.1 Motion planning of trailer-trucks for transporting Airbus A380 components......Page 398 10.3.4.2 A space robotics test-bed......Page 399 10.4 MOTION PLANNING UNDER VISIBILITY CONSTRAINTS......Page 400 10.4.1 Sensor Placement......Page 401 10.4.1.1 Sampling......Page 402 10.4.1.3 Extensions......Page 404 10.4.2.1 Constraints on the NBV......Page 405 10.4.2.2 Safe regions......Page 406 10.4.2.3 Image registration......Page 407 10.4.2.5 Computing the NBV......Page 408 10.4.2.6 Extensions......Page 409 10.4.3.1 State transition equations......Page 410 10.4.3.3 Tracking strategies......Page 411 10.4.3.5 Escape-time approximations......Page 414 10.4.3.7 Other results and extensions......Page 415 10.5 OTHER IMPORTANT ISSUES......Page 416 10.6 CONCLUSION......Page 417 REFERENCES......Page 418 BIOGRAPHIES......Page 423 CONTENTS......Page 424 11.1 INTRODUCTION......Page 425 11.2 COOPERATIVE MULTI-ROBOT SYSTEMS......Page 426 11.2.1.1 Explicit approaches......Page 428 11.2.2 Graph Theory Preliminaries......Page 429 11.3 FORMATION CONTROL......Page 430 11.3.1 Full-State Linearization via Dynamic Feedback......Page 432 11.3.2 Formation Reconfiguration......Page 435 11.4 OPTIMIZATION-BASED COOPERATIVE CONTROL......Page 439 11.4.1 Control of a Chain of Robots......Page 444 11.5.1.1 Dynamic role assignment......Page 447 11.5.1.2 Modeling......Page 449 11.5.2 Multi-Robot Perimeter Detection and Tracking......Page 453 11.5.2.2 Random coverage controller......Page 456 11.5.2.3 Potential field controller......Page 459 11.6 CONCLUSIONS......Page 460 REFERENCES......Page 462 BIOGRAPHIES......Page 465 Part IV: Decision Making and Autonomy......Page 467 CONTENTS......Page 470 12.2.1 Grounding Representation......Page 471 12.2.2.1 Spatial representations......Page 472 12.2.2.3 Symbolic representations......Page 477 12.2.3 Multi-Representational Systems......Page 479 12.2.4 Decision Making......Page 480 12.3 CASE STUDY: KNOWLEDGE REPRESENTATION AND DECISION MAKING WITHIN A 4D/RCS......Page 482 12.3.1.1 Procedural knowledge......Page 485 12.3.1.2.2 Spatial level knowledge......Page 488 12.3.1.2.3 Symbolic knowledge......Page 489 12.3.2.1 Integration considerations......Page 490 12.3.2.3 Integration among disparate representations......Page 491 12.3.2.5 Implications for system maintainability......Page 493 12.4 AN IMPLEMENTATION EXAMPLE......Page 494 12.5 CONCLUSION......Page 498 REFERENCES......Page 499 BIOGRAPHIES......Page 503 CONTENTS......Page 505 13.1 INTRODUCTION AND PRELIMINARIES......Page 506 13.2 PLANNING UNDER PREDICTION UNCERTAINTY......Page 508 13.2.1 Making a Single Decision......Page 509 13.2.1.1 Including an observation......Page 510 13.2.1.2 Criticisms of decision theory......Page 511 13.2.2 Making a Sequence of Decisions......Page 512 13.2.3.1 Value iteration......Page 515 13.2.3.2 Policy iteration......Page 518 13.2.3.3 Other methods......Page 519 13.2.4.2 Limited lookahead......Page 520 13.2.5 Conquering Continuous Spaces......Page 521 13.2.6.1 Infinite horizon models......Page 524 13.2.6.2 Reinforcement learning......Page 525 13.2.6.3 Additional decision makers......Page 527 13.3 PLANNING UNDER SENSING UNCERTAINTY......Page 529 13.3.1.1 Sensors......Page 530 13.3.1.2 Definition of the information space......Page 531 13.3.2 Deriving Information States......Page 532 13.3.3.2 Discrete-stage information spaces......Page 537 13.3.3.3 Continuous-time information spaces......Page 538 13.3.4.1 Moving in an L-shaped corridor......Page 539 13.3.4.2 The Kalman filter......Page 541 13.3.4.3 Sensorless manipulation......Page 543 REFERENCES......Page 545 BIOGRAPHIES......Page 550 CONTENTS......Page 552 14.1.1 Single Robot Control......Page 553 14.1.2 Behavior-Based Control......Page 555 14.2 FROM SINGLE ROBOT CONTROL TO MULTI-ROBOT CONTROL......Page 556 14.2.2 Necessity of Coordination in MRS......Page 557 14.3.1 Interaction through the Environment......Page 558 14.3.2 Interaction through the Environment Case Study: Object Clustering......Page 559 14.3.3 Interaction through Sensing......Page 560 14.3.4 Interaction through Sensing Case Study: Formation Marching......Page 561 14.3.5 Interaction through Communication......Page 562 14.3.6 Interaction through Communication Case Study: Multiple Target Tracking......Page 563 14.4.1 Analysis of MRS Using Macroscopic Models......Page 564 14.4.3 Principled Synthesis of MRS Controllers......Page 565 REFERENCES......Page 567 BIOGRAPHIES......Page 571 Part V: System Integration and Applications......Page 573 CONTENTS......Page 575 15.1 INTRODUCTION......Page 576 15.2 BACKGROUND......Page 577 15.3 RELATED WORK......Page 579 15.4.1 Complexity......Page 580 15.4.3 Price......Page 581 15.5.1.1 Hardware vs. software......Page 582 15.5.1.2 Generalization vs. specialization......Page 583 15.5.1.3 Abstraction and aggregation......Page 584 15.5.2 Testing, Testing, Testing.........Page 585 15.6 INTEGRATION THROUGH ARCHITECTURE......Page 586 15.7 A SOFTWARE ARCHITECTURE FOR CONSUMER ROBOTIC SYSTEMS......Page 589 15.7.1 ERSP in the Role of the System Integration Architecture?......Page 591 15.7.2 Development Tools......Page 596 15.8 CASE STUDY 1: SONY AIBO......Page 597 15.9 CASE STUDY 2: AUTONOMOUS CAPABILITIES FOR VACUUM CLEANING......Page 600 15.9.1 Lessons Learned......Page 608 15.9.2 Embedded Implementation of vSLAM......Page 609 REFERENCES......Page 611 BIOGRAPHIES......Page 612 CONTENTS......Page 614 16.1.1 A Key Product of the 20th Century......Page 615 16.1.2 Problems with Safety......Page 616 16.1.3 Problems of Congestion......Page 617 16.1.4 Problems with Emissions and Nuisances......Page 618 16.1.5 Car-Sharing and Cybercars......Page 620 16.1.6 The Future of the Automobile......Page 621 16.2.1 Ultrasound Sensors......Page 623 16.2.2.1 Gyroscopes — gyrometers......Page 624 16.2.3 Laser Detection and Ranging......Page 625 16.2.3.2 Azimuth measurement......Page 626 16.2.4.1 Range measurement......Page 628 16.2.4.2 Azimuth measurement......Page 629 16.2.5.2 Specificities of automotive applications......Page 630 16.2.5.3 Stereovision systems......Page 631 16.2.5.4 Future vision processors......Page 632 16.2.6.1 Global positioning system......Page 633 16.2.6.4 GPS receiver-based localization......Page 634 16.2.6.6 Code range positioning......Page 635 16.2.6.8 Augmented differential GPS......Page 636 16.2.6.10 Carrier phase differential GPS......Page 637 16.3 AUTOMOTIVE ACTUATORS......Page 638 16.3.1 Power Train Actuators......Page 639 16.3.2 Brake Actuators......Page 640 16.3.3 Steering Actuators......Page 641 16.4 VEHICLE CONTROL......Page 643 16.4.1.1 Adaptive cruise control......Page 644 16.4.1.2 Precrash system/automatic emergency braking......Page 645 16.4.2 Lateral Control......Page 647 16.4.3 Full Vehicle Control......Page 648 REFERENCES......Page 652 BIOGRAPHIES......Page 655 CONTENTS......Page 656 17.1 ARCHITECTURAL REQUIREMENTS FOR INTELLIGENT UGVs......Page 657 17.2 BACKGROUND ON INTELLIGENT SYSTEMS......Page 658 17.3.1 4D/RCS Architecture......Page 659 17.3.2 4D/RCS Methodology......Page 664 17.3.3 Representing Knowledge in 4D/RCS......Page 666 17.3.3.1 Procedural knowledge......Page 669 17.3.3.2 Declarative knowledge......Page 672 17.4 EXPERIMENTAL RESULTS......Page 677 17.4.1.1 AL2 architecture......Page 678 17.4.1.2 Hardware and software design methodology......Page 681 17.4.1.3 Design and implementation of UGV teams......Page 682 (b) Dynamic Fault Tolerance......Page 683 (c) Built-In Self Test, System Retasking, and Fault Accommodation......Page 684 (d) Low Level Learning for Improving the Performance of the Controller......Page 685 (e) Software Implementation for Reconfigurable Computing......Page 686 17.4.2 Demo III Experimental Unmanned Vehicle (XUV) Project at NIST......Page 687 17.5 CURRENT RESEARCH AND FUTURE DIRECTIONS......Page 691 17.6 CONCLUSIONS......Page 692 REFERENCES......Page 693 BIOGRAPHIES......Page 697