| Foreword | p. xv |
| Preface | p. xvii |
| Acknowledgments | p. xxi |
| Introduction | p. 1 |
| Overview of Concepts in Motion Planning | p. 9 |
| Overview of the Book | p. 12 |
| Mathematical Style | p. 13 |
| Bug Algorithms | p. 17 |
| Bug1 and Bug2 | p. 17 |
| Tangent Bug | p. 23 |
| Implementation | p. 30 |
| What Information: The Tangent Line | p. 31 |
| How to Infer Information with Sensors: Distance and Gradient | p. 32 |
| How to Process Sensor Information: Continuation Methods | p. 35 |
| Configuration Space | p. 39 |
| Specifying a Robot's Configuration | p. 40 |
| Obstacles and the Configuration Space | p. 43 |
| Circular Mobile Robot | p. 43 |
| Two-Joint Planar Arm | p. 45 |
| The Dimension of the Configuration Space | p. 47 |
| The Topology of the Configuration Space | p. 50 |
| Homeomorphisms and Diffeomorphisms | p. 51 |
| Differentiable Manifolds | p. 55 |
| Connectedness and Compactness | p. 58 |
| Not All Configuration Spaces Are Manifolds | p. 59 |
| Embeddings of Manifolds in R[superscript n] | p. 59 |
| Matrix Representations of Rigid-Body Configuration | p. 60 |
| Parameterizations of SO(3) | p. 66 |
| Example Configuration Spaces | p. 68 |
| Transforming Configuration and Velocity Representations | p. 69 |
| Potential Functions | p. 77 |
| Additive Attractive/Repulsive Potential | p. 80 |
| Gradient Descent | p. 84 |
| Computing Distance for Implementation in the Plane | p. 85 |
| Mobile Robot Implementation | p. 86 |
| Brushfire Algorithm: A Method to Compute Distance on a Grid | p. 86 |
| Local Minima Problem | p. 89 |
| Wave-Front Planner | p. 90 |
| Navigation Potential Functions | p. 93 |
| Sphere-Space | p. 93 |
| Star-Space | p. 96 |
| Potential Functions in Non-Euclidean Spaces | p. 99 |
| Relationship between Forces in the Workspace and Configuration Space | p. 100 |
| Potential Functions for Rigid-Body Robots | p. 101 |
| Path Planning for Articulated Bodies | p. 104 |
| Roadmaps | p. 107 |
| Visibility Maps: The Visibility Graph | p. 110 |
| Visibility Graph Definition | p. 110 |
| Visibility Graph Construction | p. 113 |
| Deformation Retracts: Generalized Voronoi Diagram | p. 117 |
| GVD Definition | p. 118 |
| GVD Roadmap Properties | p. 119 |
| Deformation Retract Definition | p. 121 |
| GVD Dimension: The Preimage Theorem and Critical Points | p. 123 |
| Construction of the GVD | p. 126 |
| Retract-like Structures: The Generalized Voronoi Graph | p. 129 |
| GVG Dimension: Transversality | p. 130 |
| Retract-like Structure Connectivity | p. 133 |
| Lyapunov Control: Sensor-Based Construction of the HGVG | p. 136 |
| Piecewise Retracts: The Rod-Hierarchical Generalized Voronoi Graph | p. 138 |
| Silhouette Methods | p. 141 |
| Canny's Roadmap Algorithm | p. 142 |
| Opportunistic Path Planner | p. 151 |
| Cell Decompositions | p. 161 |
| Trapezoidal Decomposition | p. 162 |
| Morse Cell Decompositions | p. 168 |
| Boustrophedon Decomposition | p. 169 |
| Morse Decomposition Definition | p. 170 |
| Examples of Morse Decomposition: Variable Slice | p. 172 |
| Sensor-Based Coverage | p. 178 |
| Complexity of Coverage | p. 182 |
| Visibility-Based Decompositions for Pursuit/Evasion | p. 187 |
| Sampling-Based Algorithms | p. 197 |
| Probabilistic Roadmaps | p. 202 |
| Basic PRM | p. 203 |
| A Practical Implementation of Basic PRM | p. 208 |
| PRM Sampling Strategies | p. 216 |
| PRM Connection Strategies | p. 225 |
| Single-Query Sampling-Based Planners | p. 227 |
| Expansive-Spaces Trees | p. 230 |
| Rapidly-Exploring Random Trees | p. 233 |
| Connection Strategies and the SBL Planner | p. 238 |
| Integration of Planners: Sampling-Based Roadmap of Trees | p. 238 |
| Analysis of PRM | p. 242 |
| PRM Operating in R[superscript d] | p. 243 |
| ([epsilon, alpha, beta])-Expansiveness | p. 246 |
| Abstract Path Tiling | p. 250 |
| Beyond Basic Path Planning | p. 253 |
| Control-Based Planning | p. 253 |
| Multiple Robots | p. 254 |
| Manipulation Planning | p. 257 |
| Assembly Planning | p. 259 |
| Flexible Objects | p. 260 |
| Biological Applications | p. 262 |
| Kalman Filtering | p. 269 |
| Probabilistic Estimation | p. 270 |
| Linear Kalman Filtering | p. 272 |
| Overview | p. 273 |
| A Simple Observer | p. 274 |
| Observing with Probability Distributions | p. 277 |
| The Kalman Filter | p. 282 |
| Kalman Filter Summary | p. 284 |
| Example: Kalman Filter for Dead Reckoning | p. 285 |
| Observability in Linear Systems | p. 287 |
| Extended Kalman Filter | p. 289 |
| EKF for Range and Bearing Localization | p. 290 |
| Data Association | p. 292 |
| EKF for Range-Only Localization | p. 294 |
| Kalman Filter for SLAM | p. 294 |
| Simple SLAM | p. 294 |
| Range and Bearing SLAM | p. 296 |
| Bayesian Methods | p. 301 |
| Localization | p. 301 |
| The Basic Idea of Probabilistic Localization | p. 302 |
| Probabilistic Localization as Recursive Bayesian Filtering | p. 304 |
| Derivation of Probabilistic Localization | p. 308 |
| Representations of the Posterior | p. 310 |
| Sensor Models | p. 322 |
| Mapping | p. 328 |
| Mapping with Known Locations of the Robot | p. 328 |
| Bayesian Simultaneous Localization and Mapping | p. 337 |
| Robot Dynamics | p. 349 |
| Lagrangian Dynamics | p. 349 |
| Standard Forms for Dynamics | p. 353 |
| Velocity Constraints | p. 357 |
| Dynamics of a Rigid Body | p. 361 |
| Planar Rotation | p. 362 |
| Spatial Rotation | p. 363 |
| Trajectory Planning | p. 373 |
| Preliminaries | p. 374 |
| Decoupled Trajectory Planning | p. 374 |
| Zero Inertia Points | p. 378 |
| Global Time-Optimal Trajectory Planning | p. 384 |
| Direct Trajectory Planning | p. 384 |
| Optimal Control | p. 385 |
| Nonlinear Optimization | p. 389 |
| Grid-Based Search | p. 392 |
| Nonholonomic and Underactuated Systems | p. 401 |
| Preliminaries | p. 402 |
| Tangent Spaces and Vector Fields | p. 405 |
| Distributions and Constraints | p. 407 |
| Lie Brackets | p. 409 |
| Control Systems | p. 414 |
| Controllability | p. 416 |
| Local Accessibility and Controllability | p. 419 |
| Global Controllability | p. 422 |
| Simple Mechanical Control Systems | p. 424 |
| Simplified Controllability Tests | p. 425 |
| Kinematic Reductions for Motion Planning | p. 434 |
| Simple Mechanical Systems with Nonholonomic Constraints | p. 438 |
| Motion Planning | p. 440 |
| Optimal Control | p. 440 |
| Steering Chained-Form Systems Using Sinusoids | p. 444 |
| Nonlinear Optimization | p. 445 |
| Gradient Methods for Driftless Systems | p. 446 |
| Differentially Flat Systems | p. 447 |
| Cars and Cars Pulling Trailers | p. 450 |
| Kinematic Reductions of Mechanical Systems | p. 462 |
| Other Approaches | p. 465 |
| Mathematical Notation | p. 473 |
| Basic Set Definitions | p. 475 |
| Topology and Metric Spaces | p. 478 |
| Topology | p. 478 |
| Metric Spaces | p. 479 |
| Normed and Inner Product Spaces | p. 480 |
| Continuous Functions | p. 481 |
| Jacobians and Gradients | p. 483 |
| Curve Tracing | p. 487 |
| Implicit Function Theorem | p. 487 |
| Newton-Raphson Convergence Theorem | p. 488 |
| Representations of Orientation | p. 489 |
| Euler Angles | p. 489 |
| Roll, Pitch, and Yaw Angles | p. 491 |
| Axis-Angle Parameterization | p. 492 |
| Quaternions | p. 494 |
| Polyhedral Robots in Polyhedral Worlds | p. 499 |
| Representing Polygons in Two Dimensions | p. 499 |
| Intersection Tests for Polygons | p. 502 |
| Configuration Space Obstacles in Q = R[superscript 2]: The Star Algorithm | p. 507 |
| Configuration Space Obstacles in Q = SE(2) | p. 508 |
| Computing Distances between Polytopes in R[superscript 2] and R[superscript 3] | p. 509 |
| Analysis of Algorithms and Complexity Classes | p. 513 |
| Running Time | p. 513 |
| Complexity Theory | p. 515 |
| Completeness | p. 520 |
| Graph Representation and Basic Search | p. 521 |
| Graphs | p. 521 |
| A* Algorithm | p. 527 |
| Basic Notation and Assumptions | p. 530 |
| Discussion: Completeness, Efficiency, and Optimality | p. 531 |
| Greedy-Search and Dijkstra's Algorithm | p. 532 |
| Example of A* on a Grid | p. 533 |
| Nonoptimistic Example | p. 535 |
| D* Algorithm | p. 536 |
| Optimal Plans | p. 546 |
| Statistics Primer | p. 547 |
| Distributions and Densities | p. 548 |
| Expected Values and Covariances | p. 550 |
| Multivariate Gaussian Distributions | p. 551 |
| Linear Systems and Control | p. 552 |
| State Space Representation | p. 552 |
| Stability | p. 554 |
| LTI Control Systems | p. 557 |
| Observing LTI Systems | p. 559 |
| Discrete Time Systems | p. 562 |
| Stability | p. 562 |
| Controllability and Observability | p. 563 |
| Bibliography | p. 565 |
| Index | p. 597 |
| Table of Contents provided by Ingram. All Rights Reserved. |
