Principles of Robot Motion : Theory, Algorithms, and Implementations.pdf

【实例截图】

【核心代码】

Contents
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
Choset-79066 book February 23, 2005 13:40
viii Contents
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 Rn 59
3.5.1 Matrix Repre
Choset-79066 book February 23, 2005 13:40
Contents ix
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
Choset-79066 book February 23, 2005 13:40
x Contents
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 Rd 243
7.4.2 (
, α, β)-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
Choset-79066 book February 23, 2005 13:40
Contents xi
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
Choset-79066 book February 23, 2005 13:40
xii Contents
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 
Choset-79066 book February 23, 2005 13:40
Contents xiii
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 = R2:
The Star Algorithm 507
F.4 Configuration Space Obstacles in Q = SE(2) 508
F.5 Computing Distances between Polytopes in R2 and R3 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
Choset-79066 book February 23, 2005 13:40
xiv Contents
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