Next:
Contents
Planning Algorithms
Steven M. LaValle
Contents
I
. Introductory Material
1
. Introduction
1
.
1
Planning to Plan
1
.
2
Motivational Examples and Applications
1
.
3
Basic Ingredients of Planning
1
.
4
Algorithms, Planners, and Plans
1
.
4
.
1
Algorithms
1
.
4
.
2
Planners
1
.
4
.
3
Plans
1
.
5
Organization of the Book
2
. Discrete Planning
2
.
1
Introduction to Discrete Feasible Planning
2
.
1
.
1
Problem Formulation
2
.
1
.
2
Examples of Discrete Planning
2
.
2
Searching for Feasible Plans
2
.
2
.
1
General Forward Search
2
.
2
.
2
Particular Forward Search Methods
2
.
2
.
3
Other General Search Schemes
2
.
2
.
4
A Unified View of the Search Methods
2
.
3
Discrete Optimal Planning
2
.
3
.
1
Optimal Fixed-Length Plans
2
.
3
.
2
Optimal Plans of Unspecified Lengths
2
.
3
.
3
Dijkstra Revisited
2
.
4
Using Logic to Formulate Discrete Planning
2
.
4
.
1
A STRIPS-Like Representation
2
.
4
.
2
Converting to the State-Space Representation
2
.
5
Logic-Based Planning Methods
2
.
5
.
1
Searching in a Space of Partial Plans
2
.
5
.
2
Building a Planning Graph
2
.
5
.
3
Planning as Satisfiability
Further Reading
Exercises
II
. Motion Planning
Overview of Part II: Motion Planning
Planning in Continuous Spaces
3
. Geometric Representations and Transformations
3
.
1
Geometric Modeling
3
.
1
.
1
Polygonal and Polyhedral Models
3
.
1
.
2
Semi-Algebraic Models
3
.
1
.
3
Other Models
3
.
2
Rigid-Body Transformations
3
.
2
.
1
General Concepts
3
.
2
.
2
2D Transformations
3
.
2
.
3
3D Transformations
3
.
3
Transforming Kinematic Chains of Bodies
3
.
3
.
1
A 2D Kinematic Chain
3
.
3
.
2
A 3D Kinematic Chain
3
.
4
Transforming Kinematic Trees
3
.
5
Nonrigid Transformations
Further Reading
Exercises
4
. The Configuration Space
4
.
1
Basic Topological Concepts
4
.
1
.
1
Topological Spaces
4
.
1
.
2
Manifolds
4
.
1
.
3
Paths and Connectivity
4
.
2
Defining the Configuration Space
4
.
2
.
1
2D Rigid Bodies:
4
.
2
.
2
3D Rigid Bodies:
4
.
2
.
3
Chains and Trees of Bodies
4
.
3
Configuration Space Obstacles
4
.
3
.
1
Definition of the Basic Motion Planning Problem
4
.
3
.
2
Explicitly Modeling
: The Translational Case
4
.
3
.
3
Explicitly Modeling
: The General Case
4
.
4
Closed Kinematic Chains
4
.
4
.
1
Mathematical Concepts
4
.
4
.
2
Kinematic Chains in
4
.
4
.
3
Defining the Variety for General Linkages
Further Reading
Exercises
5
. Sampling-Based Motion Planning
5
.
1
Distance and Volume in C-Space
5
.
1
.
1
Metric Spaces
5
.
1
.
2
Important Metric Spaces for Motion Planning
5
.
1
.
3
Basic Measure Theory Definitions
5
.
1
.
4
Using the Correct Measure
5
.
2
Sampling Theory
5
.
2
.
1
Motivation and Basic Concepts
5
.
2
.
2
Random Sampling
5
.
2
.
3
Low-Dispersion Sampling
5
.
2
.
4
Low-Discrepancy Sampling
5
.
3
Collision Detection
5
.
3
.
1
Basic Concepts
5
.
3
.
2
Hierarchical Methods
5
.
3
.
3
Incremental Methods
5
.
3
.
4
Checking a Path Segment
5
.
4
Incremental Sampling and Searching
5
.
4
.
1
The General Framework
5
.
4
.
2
Adapting Discrete Search Algorithms
5
.
4
.
3
Randomized Potential Fields
5
.
4
.
4
Other Methods
5
.
5
Rapidly Exploring Dense Trees
5
.
5
.
1
The Exploration Algorithm
5
.
5
.
2
Efficiently Finding Nearest Points
5
.
5
.
3
Using the Trees for Planning
5
.
6
Roadmap Methods for Multiple Queries
5
.
6
.
1
The Basic Method
5
.
6
.
2
Visibility Roadmap
5
.
6
.
3
Heuristics for Improving Roadmaps
Further Reading
Exercises
6
. Combinatorial Motion Planning
6
.
1
Introduction
6
.
2
Polygonal Obstacle Regions
6
.
2
.
1
Representation
6
.
2
.
2
Vertical Cell Decomposition
6
.
2
.
3
Maximum-Clearance Roadmaps
6
.
2
.
4
Shortest-Path Roadmaps
6
.
3
Cell Decompositions
6
.
3
.
1
General Definitions
6
.
3
.
2
2D Decompositions
6
.
3
.
3
3D Vertical Decomposition
6
.
3
.
4
A Decomposition for a Line-Segment Robot
6
.
4
Computational Algebraic Geometry
6
.
4
.
1
Basic Definitions and Concepts
6
.
4
.
2
Cylindrical Algebraic Decomposition
6
.
4
.
3
Canny's Roadmap Algorithm
6
.
5
Complexity of Motion Planning
6
.
5
.
1
Lower Bounds
6
.
5
.
2
Davenport-Schinzel Sequences
6
.
5
.
3
Upper Bounds
Further Reading
Exercises
7
. Extensions of Basic Motion Planning
7
.
1
Time-Varying Problems
7
.
1
.
1
Problem Formulation
7
.
1
.
2
Direct Solutions
7
.
1
.
3
The Velocity-Tuning Method
7
.
2
Multiple Robots
7
.
2
.
1
Problem Formulation
7
.
2
.
2
Decoupled planning
7
.
3
Mixing Discrete and Continuous Spaces
7
.
3
.
1
Hybrid Systems Framework
7
.
3
.
2
Manipulation Planning
7
.
4
Planning for Closed Kinematic Chains
7
.
4
.
1
Adaptation of Motion Planning Algorithms
7
.
4
.
2
Active-Passive Link Decompositions
7
.
5
Folding Problems in Robotics and Biology
7
.
6
Coverage Planning
7
.
7
Optimal Motion Planning
7
.
7
.
1
Optimality for One Robot
7
.
7
.
2
Multiple-Robot Optimality
Further Reading
Exercises
8
. Feedback Motion Planning
8
.
1
Motivation
8
.
2
Discrete State Spaces
8
.
2
.
1
Defining a Feedback Plan
8
.
2
.
2
Feedback Plans as Navigation Functions
8
.
2
.
3
Grid-Based Navigation Functions for Motion Planning
8
.
3
Vector Fields and Integral Curves
8
.
3
.
1
Vector Fields on
8
.
3
.
2
Smooth Manifolds
8
.
4
Complete Methods for Continuous Spaces
8
.
4
.
1
Feedback Motion Planning Definitions
8
.
4
.
2
Vector Fields Over Cell Complexes
8
.
4
.
3
Optimal Navigation Functions
8
.
4
.
4
A Step Toward Considering Dynamics
8
.
5
Sampling-Based Methods for Continuous Spaces
8
.
5
.
1
Computing a Composition of Funnels
8
.
5
.
2
Dynamic Programming with Interpolation
Further Reading
Exercises
III
. Decision-Theoretic Planning
Overview of Part III:
Decision-Theoretic Planning
Planning Under Uncertainty
9
. Basic Decision Theory
9
.
1
Preliminary Concepts
9
.
1
.
1
Optimization
9
.
1
.
2
Probability Theory Review
9
.
1
.
3
Randomized Strategies
9
.
2
A Game Against Nature
9
.
2
.
1
Modeling Nature
9
.
2
.
2
Nondeterministic vs. Probabilistic Models
9
.
2
.
3
Making Use of Observations
9
.
2
.
4
Examples of Optimal Decision Making
9
.
3
Two-Player Zero-Sum Games
9
.
3
.
1
Game Formulation
9
.
3
.
2
Deterministic Strategies
9
.
3
.
3
Randomized Strategies
9
.
4
Nonzero-Sum Games
9
.
4
.
1
Two-Player Games
9
.
4
.
2
More Than Two Players
9
.
5
Decision Theory Under Scrutiny
9
.
5
.
1
Utility Theory and Rationality
9
.
5
.
2
Concerns Regarding the Probabilistic Model
9
.
5
.
3
Concerns Regarding the Nondeterministic Model
9
.
5
.
4
Concerns Regarding Game Theory
Further Reading
Exercises
10
. Sequential Decision Theory
10
.
1
Introducing Sequential Games Against Nature
10
.
1
.
1
Model Definition
10
.
1
.
2
Forward Projections and Backprojections
10
.
1
.
3
A Plan and Its Execution
10
.
2
Algorithms for Computing Feedback Plans
10
.
2
.
1
Value Iteration
10
.
2
.
2
Policy Iteration
10
.
2
.
3
Graph Search Methods
10
.
3
Infinite-Horizon Problems
10
.
3
.
1
Problem Formulation
10
.
3
.
2
Solution Techniques
10
.
4
Reinforcement Learning
10
.
4
.
1
The General Philosophy
10
.
4
.
2
Evaluating a Plan via Simulation
10
.
4
.
3
Q-Learning: Computing an Optimal Plan
10
.
5
Sequential Game Theory
10
.
5
.
1
Game Trees
10
.
5
.
2
Sequential Games on State Spaces
10
.
5
.
3
Other Sequential Games
10
.
6
Continuous State Spaces
10
.
6
.
1
Extending the value-iteration method
10
.
6
.
2
Motion planning with nature
Further Reading
Exercises
11
. Sensors and Information Spaces
11
.
1
Discrete State Spaces
11
.
1
.
1
Sensors
11
.
1
.
2
Defining the History Information Space
11
.
1
.
3
Defining a Planning Problem
11
.
2
Derived Information Spaces
11
.
2
.
1
Information Mappings
11
.
2
.
2
Nondeterministic Information Spaces
11
.
2
.
3
Probabilistic Information Spaces
11
.
2
.
4
Limited-Memory Information Spaces
11
.
3
Examples for Discrete State Spaces
11
.
3
.
1
Basic Nondeterministic Examples
11
.
3
.
2
Nondeterministic Finite Automata
11
.
3
.
3
The Probabilistic Case: POMDPs
11
.
4
Continuous State Spaces
11
.
4
.
1
Discrete-Stage Information Spaces
11
.
4
.
2
Continuous-Time Information Spaces
11
.
4
.
3
Derived Information Spaces
11
.
5
Examples for Continuous State Spaces
11
.
5
.
1
Sensor Models
11
.
5
.
2
Simple Projection Examples
11
.
5
.
3
Examples with Nature Sensing Actions
11
.
5
.
4
Gaining Information Without Sensors
11
.
6
Computing Probabilistic Information States
11
.
6
.
1
Kalman Filtering
11
.
6
.
2
Sampling-Based Approaches
11
.
7
Information Spaces in Game Theory
11
.
7
.
1
Information States in Game Trees
11
.
7
.
2
Information Spaces for Games on State Spaces
Further Reading
Exercises
12
. Planning Under Sensing Uncertainty
12
.
1
General Methods
12
.
1
.
1
The Information Space as a Big State Space
12
.
1
.
2
Algorithms for Nondeterministic I-Spaces
12
.
1
.
3
Algorithms for Probabilistic I-Spaces (POMDPs)
12
.
2
Localization
12
.
2
.
1
Discrete Localization
12
.
2
.
2
Combinatorial Methods for Continuous Localization
12
.
2
.
3
Probabilistic Methods for Localization
12
.
3
Environment Uncertainty and Mapping
12
.
3
.
1
Grid Problems
12
.
3
.
2
Stentz's Algorithm (D
)
12
.
3
.
3
Planning in Unknown Continuous Environments
12
.
3
.
4
Optimal Navigation Without a Geometric Model
12
.
3
.
5
Probabilistic Localization and Mapping
12
.
4
Visibility-Based Pursuit-Evasion
12
.
4
.
1
Problem Formulation
12
.
4
.
2
A Complete Algorithm
12
.
4
.
3
Other Variations
12
.
5
Manipulation Planning with Sensing Uncertainty
12
.
5
.
1
Preimage Planning
12
.
5
.
2
Nonprehensile Manipulation
Further Reading
Exercises
IV
. Planning Under Differential Constraints
Overview of Part IV:
Planning Under Differential Constraints
13
. Differential Models
13
.
1
Velocity Constraints on the Configuration Space
13
.
1
.
1
Implicit vs. Parametric Representations
13
.
1
.
2
Kinematics for Wheeled Systems
13
.
1
.
3
Other Examples of Velocity Constraints
13
.
2
Phase Space Representation of Dynamical Systems
13
.
2
.
1
Reducing Degree by Increasing Dimension
13
.
2
.
2
Linear Systems
13
.
2
.
3
Nonlinear Systems
13
.
2
.
4
Extending Models by Adding Integrators
13
.
3
Basic Newton-Euler Mechanics
13
.
3
.
1
The Newtonian Model
13
.
3
.
2
Motions of Particles
13
.
3
.
3
Motion of a Rigid Body
13
.
4
Advanced Mechanics Concepts
13
.
4
.
1
Lagrangian Mechanics
13
.
4
.
2
General Lagrangian Expressions
13
.
4
.
3
Extensions of the Euler-Lagrange Equations
13
.
4
.
4
Hamiltonian Mechanics
13
.
5
Multiple Decision Makers
13
.
5
.
1
Differential Decision Making
13
.
5
.
2
Differential Game Theory
Further Reading
Exercises
14
. Sampling-Based Planning Under Differential Constraints
14
.
1
Introduction
14
.
1
.
1
Problem Formulation
14
.
1
.
2
Different Kinds of Planning Problems
14
.
1
.
3
Obstacles in the Phase Space
14
.
2
Reachability and Completeness
14
.
2
.
1
Reachable Sets
14
.
2
.
2
The Discrete-Time Model
14
.
2
.
3
Motion Primitives
14
.
3
Sampling-Based Motion Planning Revisited
14
.
3
.
1
Basic Components
14
.
3
.
2
System Simulator
14
.
3
.
3
Local Planning
14
.
3
.
4
General Framework Under Differential Constraints
14
.
4
Incremental Sampling and Searching Methods
14
.
4
.
1
Searching on a Lattice
14
.
4
.
2
Incorporating State Space Discretization
14
.
4
.
3
RDT-Based Methods
14
.
4
.
4
Other Methods
14
.
5
Feedback Planning Under Differential Constraints
14
.
5
.
1
Problem Definition
14
.
5
.
2
Dynamic Programming with Interpolation
14
.
6
Decoupled Planning Approaches
14
.
6
.
1
Different Ways to Decouple the Big Problem
14
.
6
.
2
Plan and Transform
14
.
6
.
3
Path-Constrained Trajectory Planning
14
.
7
Gradient-Based Trajectory Optimization
Further Reading
Exercises
15
. System Theory and Analytical Techniques
15
.
1
Basic System Properties
15
.
1
.
1
Stability
15
.
1
.
2
Lyapunov Functions
15
.
1
.
3
Controllability
15
.
2
Continuous-Time Dynamic Programming
15
.
2
.
1
Hamilton-Jacobi-Bellman Equation
15
.
2
.
2
Linear-Quadratic Problems
15
.
2
.
3
Pontryagin's Minimum Principle
15
.
3
Optimal Paths for Some Wheeled Vehicles
15
.
3
.
1
Dubins Curves
15
.
3
.
2
Reeds-Shepp Curves
15
.
3
.
3
Balkcom-Mason Curves
15
.
4
Nonholonomic System Theory
15
.
4
.
1
Control-Affine Systems
15
.
4
.
2
Determining Whether a System Is Nonholonomic
15
.
4
.
3
Determining Controllability
15
.
5
Steering Methods for Nonholonomic Systems
15
.
5
.
1
Using the P. Hall Basis
15
.
5
.
2
Using Sinusoidal Action Trajectories
15
.
5
.
3
Other Steering Methods
Further Reading
Exercises
Bibliography
Index
About this document ...
Steve M LaValle 2008-06-13
