| |
| |
| 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 | |