| |
| |
Foreword | |
| |
| |
Preface | |
| |
| |
Acknowledgments | |
| |
| |
| |
Introduction | |
| |
| |
| |
Overview of Concepts in Motion Planning | |
| |
| |
| |
Overview of the Book | |
| |
| |
| |
Mathematical Style | |
| |
| |
| |
Bug Algorithms | |
| |
| |
| |
Bug1 and Bug2 | |
| |
| |
| |
Tangent Bug | |
| |
| |
| |
Implementation | |
| |
| |
| |
What Information: The Tangent Line | |
| |
| |
| |
How to Infer Information with Sensors: Distance and Gradient | |
| |
| |
| |
How to Process Sensor Information: Continuation Methods | |
| |
| |
| |
Configuration Space | |
| |
| |
| |
Specifying a Robot's Configuration | |
| |
| |
| |
Obstacles and the Configuration Space | |
| |
| |
| |
Circular Mobile Robot | |
| |
| |
| |
Two-Joint Planar Arm | |
| |
| |
| |
The Dimension of the Configuration Space | |
| |
| |
| |
The Topology of the Configuration Space | |
| |
| |
| |
Homeomorphisms and Diffeomorphisms | |
| |
| |
| |
Differentiable Manifolds | |
| |
| |
| |
Connectedness and Compactness | |
| |
| |
| |
Not All Configuration Spaces Are Manifolds | |
| |
| |
| |
Embeddings of Manifolds in R[superscript n] | |
| |
| |
| |
Matrix Representations of Rigid-Body Configuration | |
| |
| |
| |
Parameterizations of SO(3) | |
| |
| |
| |
Example Configuration Spaces | |
| |
| |
| |
Transforming Configuration and Velocity Representations | |
| |
| |
| |
Potential Functions | |
| |
| |
| |
Additive Attractive/Repulsive Potential | |
| |
| |
| |
Gradient Descent | |
| |
| |
| |
Computing Distance for Implementation in the Plane | |
| |
| |
| |
Mobile Robot Implementation | |
| |
| |
| |
Brushfire Algorithm: A Method to Compute Distance on a Grid | |
| |
| |
| |
Local Minima Problem | |
| |
| |
| |
Wave-Front Planner | |
| |
| |
| |
Navigation Potential Functions | |
| |
| |
| |
Sphere-Space | |
| |
| |
| |
Star-Space | |
| |
| |
| |
Potential Functions in Non-Euclidean Spaces | |
| |
| |
| |
Relationship between Forces in the Workspace and Configuration Space | |
| |
| |
| |
Potential Functions for Rigid-Body Robots | |
| |
| |
| |
Path Planning for Articulated Bodies | |
| |
| |
| |
Roadmaps | |
| |
| |
| |
Visibility Maps: The Visibility Graph | |
| |
| |
| |
Visibility Graph Definition | |
| |
| |
| |
Visibility Graph Construction | |
| |
| |
| |
Deformation Retracts: Generalized Voronoi Diagram | |
| |
| |
| |
GVD Definition | |
| |
| |
| |
GVD Roadmap Properties | |
| |
| |
| |
Deformation Retract Definition | |
| |
| |
| |
GVD Dimension: The Preimage Theorem and Critical Points | |
| |
| |
| |
Construction of the GVD | |
| |
| |
| |
Retract-like Structures: The Generalized Voronoi Graph | |
| |
| |
| |
GVG Dimension: Transversality | |
| |
| |
| |
Retract-like Structure Connectivity | |
| |
| |
| |
Lyapunov Control: Sensor-Based Construction of the HGVG | |
| |
| |
| |
Piecewise Retracts: The Rod-Hierarchical Generalized Voronoi Graph | |
| |
| |
| |
Silhouette Methods | |
| |
| |
| |
Canny's Roadmap Algorithm | |
| |
| |
| |
Opportunistic Path Planner | |
| |
| |
| |
Cell Decompositions | |
| |
| |
| |
Trapezoidal Decomposition | |
| |
| |
| |
Morse Cell Decompositions | |
| |
| |
| |
Boustrophedon Decomposition | |
| |
| |
| |
Morse Decomposition Definition | |
| |
| |
| |
Examples of Morse Decomposition: Variable Slice | |
| |
| |
| |
Sensor-Based Coverage | |
| |
| |
| |
Complexity of Coverage | |
| |
| |
| |
Visibility-Based Decompositions for Pursuit/Evasion | |
| |
| |
| |
Sampling-Based Algorithms | |
| |
| |
| |
Probabilistic Roadmaps | |
| |
| |
| |
Basic PRM | |
| |
| |
| |
A Practical Implementation of Basic PRM | |
| |
| |
| |
PRM Sampling Strategies | |
| |
| |
| |
PRM Connection Strategies | |
| |
| |
| |
Single-Query Sampling-Based Planners | |
| |
| |
| |
Expansive-Spaces Trees | |
| |
| |
| |
Rapidly-Exploring Random Trees | |
| |
| |
| |
Connection Strategies and the SBL Planner | |
| |
| |
| |
Integration of Planners: Sampling-Based Roadmap of Trees | |
| |
| |
| |
Analysis of PRM | |
| |
| |
| |
PRM Operating in R[superscript d] | |
| |
| |
| |
([epsilon, alpha, beta])-Expansiveness | |
| |
| |
| |
Abstract Path Tiling | |
| |
| |
| |
Beyond Basic Path Planning | |
| |
| |
| |
Control-Based Planning | |
| |
| |
| |
Multiple Robots | |
| |
| |
| |
Manipulation Planning | |
| |
| |
| |
Assembly Planning | |
| |
| |
| |
Flexible Objects | |
| |
| |
| |
Biological Applications | |
| |
| |
| |
Kalman Filtering | |
| |
| |
| |
Probabilistic Estimation | |
| |
| |
| |
Linear Kalman Filtering | |
| |
| |
| |
Overview | |
| |
| |
| |
A Simple Observer | |
| |
| |
| |
Observing with Probability Distributions | |
| |
| |
| |
The Kalman Filter | |
| |
| |
| |
Kalman Filter Summary | |
| |
| |
| |
Example: Kalman Filter for Dead Reckoning | |
| |
| |
| |
Observability in Linear Systems | |
| |
| |
| |
Extended Kalman Filter | |
| |
| |
| |
EKF for Range and Bearing Localization | |
| |
| |
| |
Data Association | |
| |
| |
| |
EKF for Range-Only Localization | |
| |
| |
| |
Kalman Filter for SLAM | |
| |
| |
| |
Simple SLAM | |
| |
| |
| |
Range and Bearing SLAM | |
| |
| |
| |
Bayesian Methods | |
| |
| |
| |
Localization | |
| |
| |
| |
The Basic Idea of Probabilistic Localization | |
| |
| |
| |
Probabilistic Localization as Recursive Bayesian Filtering | |
| |
| |
| |
Derivation of Probabilistic Localization | |
| |
| |
| |
Representations of the Posterior | |
| |
| |
| |
Sensor Models | |
| |
| |
| |
Mapping | |
| |
| |
| |
Mapping with Known Locations of the Robot | |
| |
| |
| |
Bayesian Simultaneous Localization and Mapping | |
| |
| |
| |
Robot Dynamics | |
| |
| |
| |
Lagrangian Dynamics | |
| |
| |
| |
Standard Forms for Dynamics | |
| |
| |
| |
Velocity Constraints | |
| |
| |
| |
Dynamics of a Rigid Body | |
| |
| |
| |
Planar Rotation | |
| |
| |
| |
Spatial Rotation | |
| |
| |
| |
Trajectory Planning | |
| |
| |
| |
Preliminaries | |
| |
| |
| |
Decoupled Trajectory Planning | |
| |
| |
| |
Zero Inertia Points | |
| |
| |
| |
Global Time-Optimal Trajectory Planning | |
| |
| |
| |
Direct Trajectory Planning | |
| |
| |
| |
Optimal Control | |
| |
| |
| |
Nonlinear Optimization | |
| |
| |
| |
Grid-Based Search | |
| |
| |
| |
Nonholonomic and Underactuated Systems | |
| |
| |
| |
Preliminaries | |
| |
| |
| |
Tangent Spaces and Vector Fields | |
| |
| |
| |
Distributions and Constraints | |
| |
| |
| |
Lie Brackets | |
| |
| |
| |
Control Systems | |
| |
| |
| |
Controllability | |
| |
| |
| |
Local Accessibility and Controllability | |
| |
| |
| |
Global Controllability | |
| |
| |
| |
Simple Mechanical Control Systems | |
| |
| |
| |
Simplified Controllability Tests | |
| |
| |
| |
Kinematic Reductions for Motion Planning | |
| |
| |
| |
Simple Mechanical Systems with Nonholonomic Constraints | |
| |
| |
| |
Motion Planning | |
| |
| |
| |
Optimal Control | |
| |
| |
| |
Steering Chained-Form Systems Using Sinusoids | |
| |
| |
| |
Nonlinear Optimization | |
| |
| |
| |
Gradient Methods for Driftless Systems | |
| |
| |
| |
Differentially Flat Systems | |
| |
| |
| |
Cars and Cars Pulling Trailers | |
| |
| |
| |
Kinematic Reductions of Mechanical Systems | |
| |
| |
| |
Other Approaches | |
| |
| |
| |
Mathematical Notation | |
| |
| |
| |
Basic Set Definitions | |
| |
| |
| |
Topology and Metric Spaces | |
| |
| |
| |
Topology | |
| |
| |
| |
Metric Spaces | |
| |
| |
| |
Normed and Inner Product Spaces | |
| |
| |
| |
Continuous Functions | |
| |
| |
| |
Jacobians and Gradients | |
| |
| |
| |
Curve Tracing | |
| |
| |
| |
Implicit Function Theorem | |
| |
| |
| |
Newton-Raphson Convergence Theorem | |
| |
| |
| |
Representations of Orientation | |
| |
| |
| |
Euler Angles | |
| |
| |
| |
Roll, Pitch, and Yaw Angles | |
| |
| |
| |
Axis-Angle Parameterization | |
| |
| |
| |
Quaternions | |
| |
| |
| |
Polyhedral Robots in Polyhedral Worlds | |
| |
| |
| |
Representing Polygons in Two Dimensions | |
| |
| |
| |
Intersection Tests for Polygons | |
| |
| |
| |
Configuration Space Obstacles in Q = R[superscript 2]: The Star Algorithm | |
| |
| |
| |
Configuration Space Obstacles in Q = SE(2) | |
| |
| |
| |
Computing Distances between Polytopes in R[superscript 2] and R[superscript 3] | |
| |
| |
| |
Analysis of Algorithms and Complexity Classes | |
| |
| |
| |
Running Time | |
| |
| |
| |
Complexity Theory | |
| |
| |
| |
Completeness | |
| |
| |
| |
Graph Representation and Basic Search | |
| |
| |
| |
Graphs | |
| |
| |
| |
A* Algorithm | |
| |
| |
| |
Basic Notation and Assumptions | |
| |
| |
| |
Discussion: Completeness, Efficiency, and Optimality | |
| |
| |
| |
Greedy-Search and Dijkstra's Algorithm | |
| |
| |
| |
Example of A* on a Grid | |
| |
| |
| |
Nonoptimistic Example | |
| |
| |
| |
D* Algorithm | |
| |
| |
| |
Optimal Plans | |
| |
| |
| |
Statistics Primer | |
| |
| |
| |
Distributions and Densities | |
| |
| |
| |
Expected Values and Covariances | |
| |
| |
| |
Multivariate Gaussian Distributions | |
| |
| |
| |
Linear Systems and Control | |
| |
| |
| |
State Space Representation | |
| |
| |
| |
Stability | |
| |
| |
| |
LTI Control Systems | |
| |
| |
| |
Observing LTI Systems | |
| |
| |
| |
Discrete Time Systems | |
| |
| |
| |
Stability | |
| |
| |
| |
Controllability and Observability | |
| |
| |
Bibliography | |
| |
| |
Index | |