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