추가 적립 안내

Chapter Page
Foreword xv
Preface xvii
Acknowledgments xxi
1. Introduction 1
1.1 Overview of Concepts in Motion Planning 9
1.2 Overview of the Book 12
1.3 Mathematical Style 13
2. Bug Algorithms 17
2.1 Bug1 and Bug2 17
2.2 Tangent Bug 23
2.3 Implementation 30
2.3.1 What Information: The Tangent Line 31
2.3.2 How to Infer Information with Sensors: Distance and Gradient 32
2.3.3 How to Process Sensor Information: Continuation Methods 35
3. Configuration Space 39
3.1 Specifying a Robot's Configuration 40
3.2 Obstacles and the Configuration Space 43
3.2.1 Circular Mobile Robot 43
3.2.2 Two-Joint Planar Arm 45
3.3 The Dimension of the Configuration Space 47
3.4 The Topology of the Configuration Space 50
3.4.1 Homeomorphisms and Diffeomorphisms 51
3.4.2 Differentiable Manifolds 55
3.4.3 Connectedness and Compactness 58
3.4.4 Not All Configuration Spaces Are Manifolds 59
3.5 Embeddings of Manifolds in R[superscript n] 59
3.5.1 Matrix Representations of Rigid-Body Configuration 60
3.6 Parameterizations of SO(3) 66
3.7 Example Configuration Spaces 68
3.8 Transforming Configuration and Velocity Representations 69
4. Potential Functions 77
4.1 Additive Attractive/Repulsive Potential 80
4.2 Gradient Descent 84
4.3 Computing Distance for Implementation in the Plane 85
4.3.1 Mobile Robot Implementation 86
4.3.2 Brushfire Algorithm: A Method to Compute Distance on a Grid 86
4.4 Local Minima Problem 89
4.5 Wave-Front Planner 90
4.6 Navigation Potential Functions 93
4.6.1 Sphere-Space 93
4.6.2 Star-Space 96
4.7 Potential Functions in Non-Euclidean Spaces 99
4.7.1 Relationship between Forces in the Workspace and Configuration Space 100
4.7.2 Potential Functions for Rigid-Body Robots 101
4.7.3 Path Planning for Articulated Bodies 104
5. Roadmaps 107
5.1 Visibility Maps: The Visibility Graph 110
5.1.1 Visibility Graph Definition 110
5.1.2 Visibility Graph Construction 113
5.2 Deformation Retracts: Generalized Voronoi Diagram 117
5.2.1 GVD Definition 118
5.2.2 GVD Roadmap Properties 119
5.2.3 Deformation Retract Definition 121
5.2.4 GVD Dimension: The Preimage Theorem and Critical Points 123
5.2.5 Construction of the GVD 126
5.3 Retract-like Structures: The Generalized Voronoi Graph 129
5.3.1 GVG Dimension: Transversality 130
5.3.2 Retract-like Structure Connectivity 133
5.3.3 Lyapunov Control: Sensor-Based Construction of the HGVG 136
5.4 Piecewise Retracts: The Rod-Hierarchical Generalized Voronoi Graph 138
5.5 Silhouette Methods 141
5.5.1 Canny's Roadmap Algorithm 142
5.5.2 Opportunistic Path Planner 151
6. Cell Decompositions 161
6.1 Trapezoidal Decomposition 162
6.2 Morse Cell Decompositions 168
6.2.1 Boustrophedon Decomposition 169
6.2.2 Morse Decomposition Definition 170
6.2.3 Examples of Morse Decomposition: Variable Slice 172
6.2.4 Sensor-Based Coverage 178
6.2.5 Complexity of Coverage 182
6.3 Visibility-Based Decompositions for Pursuit/Evasion 187
7. Sampling-Based Algorithms 197
7.1 Probabilistic Roadmaps 202
7.1.1 Basic PRM 203
7.1.2 A Practical Implementation of Basic PRM 208
7.1.3 PRM Sampling Strategies 216
7.1.4 PRM Connection Strategies 225
7.2 Single-Query Sampling-Based Planners 227
7.2.1 Expansive-Spaces Trees 230
7.2.2 Rapidly-Exploring Random Trees 233
7.2.3 Connection Strategies and the SBL Planner 238
7.3 Integration of Planners: Sampling-Based Roadmap of Trees 238
7.4 Analysis of PRM 242
7.4.1 PRM Operating in R[superscript d] 243
7.4.2 ([epsilon, alpha, beta])-Expansiveness 246
7.4.3 Abstract Path Tiling 250
7.5 Beyond Basic Path Planning 253
7.5.1 Control-Based Planning 253
7.5.2 Multiple Robots 254
7.5.3 Manipulation Planning 257
7.5.4 Assembly Planning 259
7.5.5 Flexible Objects 260
7.5.6 Biological Applications 262
8. Kalman Filtering 269
8.1 Probabilistic Estimation 270
8.2 Linear Kalman Filtering 272
8.2.1 Overview 273
8.2.2 A Simple Observer 274
8.2.3 Observing with Probability Distributions 277
8.2.4 The Kalman Filter 282
8.2.5 Kalman Filter Summary 284
8.2.6 Example: Kalman Filter for Dead Reckoning 285
8.2.7 Observability in Linear Systems 287
8.3 Extended Kalman Filter 289
8.3.1 EKF for Range and Bearing Localization 290
8.3.2 Data Association 292
8.3.3 EKF for Range-Only Localization 294
8.4 Kalman Filter for SLAM 294
8.4.1 Simple SLAM 294
8.4.2 Range and Bearing SLAM 296
9. Bayesian Methods 301
9.1 Localization 301
9.1.1 The Basic Idea of Probabilistic Localization 302
9.1.2 Probabilistic Localization as Recursive Bayesian Filtering 304
9.1.3 Derivation of Probabilistic Localization 308
9.1.4 Representations of the Posterior 310
9.1.5 Sensor Models 322
9.2 Mapping 328
9.2.1 Mapping with Known Locations of the Robot 328
9.2.2 Bayesian Simultaneous Localization and Mapping 337
10. Robot Dynamics 349
10.1 Lagrangian Dynamics 349
10.2 Standard Forms for Dynamics 353
10.3 Velocity Constraints 357
10.4 Dynamics of a Rigid Body 361
10.4.1 Planar Rotation 362
10.4.2 Spatial Rotation 363
11. Trajectory Planning 373
11.1 Preliminaries 374
11.2 Decoupled Trajectory Planning 374
11.2.1 Zero Inertia Points 378
11.2.2 Global Time-Optimal Trajectory Planning 384
11.3 Direct Trajectory Planning 384
11.3.1 Optimal Control 385
11.3.2 Nonlinear Optimization 389
11.3.3 Grid-Based Search 392
12. Nonholonomic and Underactuated Systems 401
12.1 Preliminaries 402
12.1.1 Tangent Spaces and Vector Fields 405
12.1.2 Distributions and Constraints 407
12.1.3 Lie Brackets 409
12.2 Control Systems 414
12.3 Controllability 416
12.3.1 Local Accessibility and Controllability 419
12.3.2 Global Controllability 422
12.4 Simple Mechanical Control Systems 424
12.4.1 Simplified Controllability Tests 425
12.4.2 Kinematic Reductions for Motion Planning 434
12.4.3 Simple Mechanical Systems with Nonholonomic Constraints 438
12.5 Motion Planning 440
12.5.1 Optimal Control 440
12.5.2 Steering Chained-Form Systems Using Sinusoids 444
12.5.3 Nonlinear Optimization 445
12.5.4 Gradient Methods for Driftless Systems 446
12.5.5 Differentially Flat Systems 447
12.5.6 Cars and Cars Pulling Trailers 450
12.5.7 Kinematic Reductions of Mechanical Systems 462
12.5.8 Other Approaches 465
A Mathematical Notation 473
B Basic Set Definitions 475
C Topology and Metric Spaces 478
C.1 Topology 478
C.2 Metric Spaces 479
C.3 Normed and Inner Product Spaces 480
C.4 Continuous Functions 481
C.5 Jacobians and Gradients 483
D Curve Tracing 487
D.1 Implicit Function Theorem 487
D.2 Newton-Raphson Convergence Theorem 488
E Representations of Orientation 489
E.1 Euler Angles 489
E.2 Roll, Pitch, and Yaw Angles 491
E.3 Axis-Angle Parameterization 492
E.4 Quaternions 494
F Polyhedral Robots in Polyhedral Worlds 499
F.1 Representing Polygons in Two Dimensions 499
F.2 Intersection Tests for Polygons 502
F.3 Configuration Space Obstacles in Q = R[superscript 2]: The Star Algorithm 507
F.4 Configuration Space Obstacles in Q = SE(2) 508
F.5 Computing Distances between Polytopes in R[superscript 2] and R[superscript 3] 509
G Analysis of Algorithms and Complexity Classes 513
G.1 Running Time 513
G.2 Complexity Theory 515
G.3 Completeness 520
H Graph Representation and Basic Search 521
H.1 Graphs 521
H.2 A* Algorithm 527
H.2.1 Basic Notation and Assumptions 530
H.2.2 Discussion: Completeness, Efficiency, and Optimality 531
H.2.3 Greedy-Search and Dijkstra's Algorithm 532
H.2.4 Example of A* on a Grid 533
H.2.5 Nonoptimistic Example 535
H.3 D* Algorithm 536
H.4 Optimal Plans 546
I Statistics Primer 547
I.1 Distributions and Densities 548
I.2 Expected Values and Covariances 550
I.3 Multivariate Gaussian Distributions 551
J Linear Systems and Control 552
J.1 State Space Representation 552
J.2 Stability 554
J.3 LTI Control Systems 557
J.4 Observing LTI Systems 559
J.5 Discrete Time Systems 562
J.5.1 Stability 562
J.5.2 Controllability and Observability 563
Bibliography 565
Index 597

A text that makes the mathematical underpinnings of robot motion accessible and relates low-level details of implementation to high-level algorithmic concepts.

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.