Next:
Overview of Part II:
Up:
Planning Algorithms
Previous:
Exercises
II
. Motion Planning
Subsections
Overview of Part II: Motion Planning
Planning in Continuous Spaces
1. Implicit representations
2. Continuous
discrete
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
.
1
.
1
Solution concepts
8
.
4
.
1
.
2
Navigation functions
8
.
4
.
2
Vector Fields Over Cell Complexes
8
.
4
.
3
Optimal Navigation Functions
8
.
4
.
4
A Step Toward Considering Dynamics
8
.
4
.
4
.
1
An acceleration-based control model
8
.
4
.
4
.
2
Velocity and acceleration constraints
8
.
4
.
4
.
3
Navigation function in the sense of Rimon-Koditschek
8
.
4
.
4
.
4
Harmonic potential functions
8
.
5
Sampling-Based Methods for Continuous Spaces
8
.
5
.
1
Computing a Composition of Funnels
8
.
5
.
1
.
1
An approximate cover
8
.
5
.
1
.
2
Defining a feedback plan over a cover
8
.
5
.
1
.
3
A sampling-based approach
8
.
5
.
2
Dynamic Programming with Interpolation
8
.
5
.
2
.
1
Using interpolation for continuous state spaces
8
.
5
.
2
.
2
The connection to feedback motion planning
8
.
5
.
2
.
3
Obtaining Dijkstra-like algorithms
Further Reading
Exercises
Steve M LaValle 2008-06-13
