Planning Algorithms

Preface......Page 9
I Introductory Material......Page 17
Planning to Plan......Page 19
Motivational Examples and Applications......Page 21
Basic Ingredients of Planning......Page 33
Algorithms, Planners, and Plans......Page 35
Organization of the Book......Page 40
Discrete Planning......Page 43
Introduction to Discrete Feasible Planning......Page 44
Searching for Feasible Plans......Page 48
Discrete Optimal Planning......Page 59
Using Logic to Formulate Discrete Planning......Page 73
Logic-Based Planning Methods......Page 79
II Motion Planning......Page 93
Geometric Modeling......Page 97
Rigid-Body Transformations......Page 108
Transforming Kinematic Chains of Bodies......Page 116
Transforming Kinematic Trees......Page 128
Nonrigid Transformations......Page 136
Basic Topological Concepts......Page 143
Defining the Configuration Space......Page 161
Configuration Space Obstacles......Page 171
Closed Kinematic Chains......Page 183
Sampling-Based Motion Planning......Page 201
Distance and Volume in C-Space......Page 202
Sampling Theory......Page 211
Collision Detection......Page 225
Incremental Sampling and Searching......Page 233
Rapidly Exploring Dense Trees......Page 244
Roadmap Methods for Multiple Queries......Page 253
Introduction......Page 265
Polygonal Obstacle Regions......Page 267
Cell Decompositions......Page 280
Computational Algebraic Geometry......Page 296
Complexity of Motion Planning......Page 314
Time-Varying Problems......Page 327
Multiple Robots......Page 334
Mixing Discrete and Continuous Spaces......Page 343
Planning for Closed Kinematic Chains......Page 353
Folding Problems in Robotics and Biology......Page 363
Coverage Planning......Page 370
Optimal Motion Planning......Page 373
Motivation......Page 385
Discrete State Spaces......Page 387
Vector Fields and Integral Curves......Page 397
Complete Methods for Continuous Spaces......Page 414
Sampling-Based Methods for Continuous Spaces......Page 428
III Decision-Theoretic Planning......Page 449
Basic Decision Theory......Page 453
Preliminary Concepts......Page 454
A Game Against Nature......Page 462
Two-Player Zero-Sum Games......Page 475
Nonzero-Sum Games......Page 484
Decision Theory Under Scrutiny......Page 493
Sequential Decision Theory......Page 511
Introducing Sequential Games Against Nature......Page 512
Algorithms for Computing Feedback Plans......Page 524
Infinite-Horizon Problems......Page 538
Reinforcement Learning......Page 543
Sequential Game Theory......Page 552
Continuous State Spaces......Page 567
Sensors and Information Spaces......Page 575
Discrete State Spaces......Page 577
Derived Information Spaces......Page 587
Examples for Discrete State Spaces......Page 597
Continuous State Spaces......Page 605
Examples for Continuous State Spaces......Page 614
Computing Probabilistic Information States......Page 630
Information Spaces in Game Theory......Page 635
Planning Under Sensing Uncertainty......Page 649
General Methods......Page 650
Localization......Page 656
Environment Uncertainty and Mapping......Page 671
Visibility-Based Pursuit-Evasion......Page 700
Manipulation Planning with Sensing Uncertainty......Page 707
IV Planning Under Differential Constraints......Page 727
Differential Models......Page 731
Velocity Constraints on the Configuration Space......Page 732
Phase Space Representation of Dynamical Systems......Page 751
Basic Newton-Euler Mechanics......Page 761
Advanced Mechanics Concepts......Page 778
Multiple Decision Makers......Page 796
Sampling-Based Planning Under Differential Constraints......Page 803
Introduction......Page 804
Reachability and Completeness......Page 814
Sampling-Based Motion Planning Revisited......Page 826
Incremental Sampling and Searching Methods......Page 836
Feedback Planning Under Differential Constraints......Page 853
Decoupled Planning Approaches......Page 857
Gradient-Based Trajectory Optimization......Page 871
System Theory and Analytical Techniques......Page 877
Basic System Properties......Page 878
Continuous-Time Dynamic Programming......Page 886
Optimal Paths for Some Wheeled Vehicles......Page 896
Nonholonomic System Theory......Page 904
Steering Methods for Nonholonomic Systems......Page 926