Principles of Robot Motion Theory, Algorithms, and Implementations

by Choset, Howie; Lynch, Kevin M.; Hutchinson, Seth; Kantor, George A.; Burgard, Wolfram

ISBN13: 9780262033275

ISBN10: 0262033275

Format: Hardcover

Pub. Date: 2005-05-20

Publisher(s): MIT PRESS

Other versions by this Author

Free Shipping on All Orders!

*excludes Marketplace items.

List Price: ~~$90.66~~

Buy New

Usually Ships in 8 - 10 Business Days.

$85.14

Add to Cart

Rent Textbook

Select for Price

Add to Cart

There was a problem. Please try again later.

Used Textbook

We're Sorry
Sold Out

eTextbook

We're Sorry
Not Available

Buy from our Marketplace starting at $38.77

Summary

Robot motion planning has become a major focus of robotics. Research findings can be applied not only to robotics but to planning routes on circuit boards, directing digital actors in computer graphics, robot-assisted surgery and medicine, and in novel areas such as drug design and protein folding. This text reflects the great advances that have taken place in the last ten years, including sensor-based planning, probabalistic planning, localization and mapping, and motion planning for dynamic and nonholonomic systems. Its presentation makes the mathematical underpinnings of robot motion accessible to students of computer science and engineering, rleating low-level implementation details to high-level algorithmic concepts.

Author Biography

Howie Choset is Associate Professor in the Robotics Institute at Carnegie Mellon University.

Kevin M. Lynch is Associate Professor in the Mechanical Engineering Department, Northwestern University.

Seth Hutchinson is Professor in the Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign.

George Kantor is Project Scientist in the Center for the Foundations of Robotics, Robotics Institute, Carnegie Mellon University.

Wolfram Burgard is Professor of Computer Science and Head of the research lab for Autonomous Intelligent Systems at the University of Freiburg.

Lydia E. Kavraki is Professor of Computer Science and Bioengineering, Rice University.

Sebastian Thrun is Associate Professor in the Computer Science Department at Stanford University and Director of the Stanford AI Lab.

Foreword

Preface

xvii

Acknowledgments

xxi

Introduction

(16)

Overview of Concepts in Motion Planning

(3)

Overview of the Book

(1)

Mathematical Style

(4)

Bug Algorithms

(22)

Bug1and Bug2

(6)

Tangent Bug

(7)

Implementation

(9)

What Information: The Tangent Line

(1)

How to Infer Information with Sensors: Distance and Gradient

(3)

How to Process Sensor Information: Continuation Methods

(4)

Configuration Space

(38)

Specifying a Robot's Configuration

(3)

Obstacles and the Configuration Space

(4)

Circular Mobile Robot

(2)

Two-Joint Planar Arm

(2)

The Dimension of the Configuration Space

(3)

The Topology of the Configuration Space

(9)

Homeomorphisms and Diffeomorphisms

(4)

Differentiable Manifolds

(3)

Connectedness and Compactness

(1)

Not All Configuration Spaces Are Manifolds

(1)

Embeddings of Manifolds in Rn

(7)

Matrix Representations of Rigid-Body Configuration

(6)

Parameterizations of SO(3)

(2)

Example Configuration Spaces

(1)

Transforming Configuration and Velocity Representations

(8)

Potential Functions

(30)

Additive Attractive/Repulsive Potential

(4)

Gradient Descent

(1)

Computing Distance for Implementation in the Plane

(4)

Mobile Robot Implementation

(1)

Brushfire Algorithm: A Method to Compute Distance on a Grid

(3)

Local Minima Problem

(1)

Wave-Front Planner

(3)

Navigation Potential Functions

(6)

Sphere-Space

(3)

Star-Space

(3)

Potential Functions in Non-Euclidean Spaces

(8)

Relationship between Forces in the Workspace and Configuration Space

100

(1)

Potential Functions for Rigid-Body Robots

101

(3)

Path Planning for Articulated Bodies

104

(3)

Roadmaps

107

(54)

Visibility Maps: The Visibility Graph

110

(7)

Visibility Graph Definition

110

(3)

Visibility Graph Construction

113

(4)

Deformation Retracts: Generalized Voronoi Diagram

117

(12)

GVD Definition

118

(1)

GVD Roadmap Properties

119

(2)

Deformation Retract Definition

121

(2)

GVD Dimension: The Preimage Theorem and Critical Points

123

(3)

Construction of the GVD

126

(3)

Retract-like Structures: The Generalized Voronoi Graph

129

(9)

GVG Dimension: Transversality

130

(3)

Retract-like Structure Connectivity

133

(3)

Lyapunov Control: Sensor-Based Construction of the HGVG

136

(2)

Piecewise Retracts: The Rod-Hierarchical Generalized Voronoi Graph

138

(3)

Silhouette Methods

141

(20)

Canny's Roadmap Algorithm

142

(9)

Opportunistic Path Planner

151

(10)

Cell Decompositions

161

(36)

Trapezoidal Decomposition

162

(6)

Morse Cell Decompositions

168

(19)

Boustrophedon Decomposition

169

(1)

Morse Decomposition Definition

170

(2)

Examples of Morse Decomposition: Variable Slice

172

(6)

Sensor-Based Coverage

178

(4)

Complexity of Coverage

182

(5)

Visibility-Based Decompositions for Pursuit/Evasion

187

(10)

Sampling-Based Algorithms

197

(72)

Probabilistic Roadmaps

202

(25)

Basic PRM

203

(5)

A Practical Implementation of Basic PRM

208

(8)

PRM Sampling Strategies

216

(9)

PRM Connection Strategies

225

(2)

Single-Query Sampling-Based Planners

227

(11)

Expansive-Spaces Trees

230

(3)

Rapidly-Exploring Random Trees

233

(5)

Connection Strategies and the SBL Planner

238

(1)

Integration of Planners: Sampling-Based Roadmap of Trees

238

(4)

Analysis of PRM

242

(11)

PRM Operating in Rd

243

(3)

(ε, α, β)-Expansiveness

246

(4)

Abstract Path Tiling

250

(3)

Beyond Basic Path Planning

253

(16)

Control-Based Planning

253

(1)

Multiple Robots

254

(3)

Manipulation Planning

257

(2)

Assembly Planning

259

(1)

Flexible Objects

260

(2)

Biological Applications

262

(7)

Kalman Filtering

269

(32)

Probabilistic Estimation

270

(2)

Linear Kalman Filtering

272

(17)

Overview

273

(1)

A Simple Observer

274

(3)

Observing with Probability Distributions

277

(5)

The Kalman Filter

282

(2)

Kalman Filter Summary

284

(1)

Example: Kalman Filter for Dead Reckoning

285

(2)

Observability in Linear Systems

287

(2)

Extended Kalman Filter

289

(5)

EKF for Range and Bearing Localization

290

(2)

Data Association

292

(2)

EKF for Range-Only Localization

294

(1)

Kalman Filter for SLAM

294

(7)

Simple SLAM

294

(2)

Range and Bearing SLAM

296

(5)

Bayesian Methods

301

(48)

Localization

301

(27)

The Basic Idea of Probabilistic Localization

302

(2)

Probabilistic Localization as Recursive Bayesian Filtering

304

(4)

Derivation of Probabilistic Localization

308

(2)

Representations of the Posterior

310

(12)

Sensor Models

322

(6)

Mapping

328

(21)

Mapping with Known Locations of the Robot

328

(9)

Bayesian Simultaneous Localization and Mapping

337

(12)

Robot Dynamics

349

(24)

Lagrangian Dynamics

349

(4)

Standard Forms for Dynamics

353

(4)

Velocity Constraints

357

(4)

Dynamics of a Rigid Body

361

(12)

Planar Rotation

362

(1)

Spatial Rotation

363

(10)

Trajectory Planning

373

(28)

Preliminaries

374

(1)

Decoupled Trajectory Planning

374

(10)

Zero Inertia Points

378

(6)

Global Time-Optimal Trajectory Planning

384

(1)

Direct Trajectory Planning

384

(17)

Optimal Control

385

(4)

Nonlinear Optimization

389

(3)

Grid-Based Search

392

(9)

Nonholonomic and Underactuated Systems

401

(72)

Preliminaries

402

(12)

Tangent Spaces and Vector Fields

405

(2)

Distributions and Constraints

407

(2)

Lie Brackets

409

(5)

Control Systems

414

(2)

Controllability

416

(8)

Local Accessibility and Controllability

419

(3)

Global Controllability

422

(2)

Simple Mechanical Control Systems

424

(16)

Simplified Controllability Tests

425

(9)

Kinematic Reductions for Motion Planning

434

(4)

Simple Mechanical Systems with Nonholonomic Constraints

438

(2)

Motion Planning

440

(33)

Optimal Control

440

(4)

Steering Chained-Form Systems Using Sinusoids

444

(1)

Nonlinear Optimization

445

(1)

Gradient Methods for Driftless Systems

446

(1)

Differentially Flat Systems

447

(3)

Cars and Cars Pulling Trailers

450

(12)

Kinematic Reductions of Mechanical Systems

462

(3)

Other Approaches

465

(8)

A Mathematical Notation

473

(2)

B Basic Set Definitions

475

(3)

C Topology and Metric Spaces

478

(9)

C.1 Topology

478

(1)

C.2 Metric Spaces

479

(1)

C.3 Normed and Inner Product Spaces

480

(1)

C.4 Continuous Functions

481

(2)

C.5 Jacobians and Gradients

483

(4)

D Curve Tracing

487

(2)

D.1 Implicit Function Theorem

487

(1)

D.2 Newton-Raphson Convergence Theorem

488

(1)

E Representations of Orientation

489

(10)

E.1 Euler Angles

489

(2)

E.2 Roll, Pitch, and Yaw Angles

491

(1)

E.3 Axis-Angle Parameterization

492

(2)

E.4 Quaternions

494

(5)

F Polyhedral Robots in Polyhedral Worlds

499

(14)

F.1 Representing Polygons in Two Dimensions

499

(3)

F.2 Intersection Tests for Polygons

502

(5)

F.3 Configuration Space Obstacles in Q = R2: The Star Algorithm

507

(1)

F.4 Configuration Space Obstacles in Q = SE(2)

508

(1)

F.5 Computing Distances between Polytopes in R2 and R3

509

(4)

G Analysis of Algorithms and Complexity Classes

513

(8)

G.1 Running Time

513

(2)

G.2 Complexity Theory

515

(5)

G.3 Completeness

520

(1)

H Graph Representation and Basic Search

521

(26)

H.1 Graphs

521

(6)

H.2 A* Algorithm

527

(9)

H.2.1 Basic Notation and Assumptions

530

(1)

H.2.2 Discussion: Completeness, Efficiency, and Optimality

531

(1)

H.2.3 Greedy-Search and Dijkstra's Algorithm

532

(1)

H.2.4 Example of A* on a Grid

533

(2)

H.2.5 Nonoptimistic Example

535

(1)

H.3 D* Algorithm

536

(10)

H.4 Optimal Plans

546

(1)

I Statistics Primer

547

(5)

I.1 Distributions and Densities

548

(2)

I.2 Expected Values and Covariances

550

(1)

I.3 Multivariate Gaussian Distributions

551

(1)

J Linear Systems and Control

552

(13)

J.1 State Space Representation

552

(2)

J.2 Stability

554

(3)

J.3 LTI Control Systems

557

(2)

J.4 Observing LTI Systems

559

(3)

J.5 Discrete Time Systems

562

(3)

J.5.1 Stability

562

(1)

J.5.2 Controllability and Observability

563

(2)

Bibliography

565

(32)

Index

597

Principles of Robot Motion Theory, Algorithms, and Implementations

Buy New

Rent Textbook

Used Textbook

eTextbook

How Marketplace Works:

Summary

Author Biography

Table of Contents