Next:
Overview of Part IV:
Up:
Planning Algorithms
Previous:
Exercises
IV
. Planning Under Differential Constraints
Subsections
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
.
1
.
1
Implicit representation
13
.
1
.
1
.
2
Parametric constraints
13
.
1
.
1
.
3
Conversion from implicit to parametric form
13
.
1
.
2
Kinematics for Wheeled Systems
13
.
1
.
2
.
1
A simple car
13
.
1
.
2
.
2
A differential drive
13
.
1
.
2
.
3
A simple unicycle
13
.
1
.
2
.
4
A car pulling trailers
13
.
1
.
3
Other Examples of Velocity Constraints
13
.
1
.
3
.
1
Pushing a box
13
.
1
.
3
.
2
Flying an airplane
13
.
1
.
3
.
3
Rolling a ball
13
.
1
.
3
.
4
Trapped on a surface
13
.
2
Phase Space Representation of Dynamical Systems
13
.
2
.
1
Reducing Degree by Increasing Dimension
13
.
2
.
1
.
1
The scalar case
13
.
2
.
1
.
2
The vector case
13
.
2
.
1
.
3
Higher order differential constraints
13
.
2
.
2
Linear Systems
13
.
2
.
3
Nonlinear Systems
13
.
2
.
4
Extending Models by Adding Integrators
13
.
2
.
4
.
1
Better unicycle models
13
.
2
.
4
.
2
A continuous-steering car
13
.
2
.
4
.
3
Smooth differential drive
13
.
3
Basic Newton-Euler Mechanics
13
.
3
.
1
The Newtonian Model
13
.
3
.
2
Motions of Particles
13
.
3
.
2
.
1
Motion of a single particle
13
.
3
.
2
.
2
Motion of a set of particles
13
.
3
.
3
Motion of a Rigid Body
13
.
4
Advanced Mechanics Concepts
13
.
4
.
1
Lagrangian Mechanics
13
.
4
.
1
.
1
Calculus of variations
13
.
4
.
1
.
2
Hamilton's principle of least action
13
.
4
.
1
.
3
Applying actions
13
.
4
.
1
.
4
Procedure for deriving the state transition equation
13
.
4
.
2
General Lagrangian Expressions
13
.
4
.
2
.
1
Conversion to a phase transition equation
13
.
4
.
3
Extensions of the Euler-Lagrange Equations
13
.
4
.
3
.
1
Incorporating velocity constraints
13
.
4
.
3
.
2
Nonconservative forces
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
.
2
.
1
Terms from planning literature
14
.
1
.
2
.
2
Terms from control theory
14
.
1
.
3
Obstacles in the Phase Space
14
.
1
.
3
.
1
Additional constraints on phase variables
14
.
1
.
3
.
2
The region of inevitable collision
14
.
2
Reachability and Completeness
14
.
2
.
1
Reachable Sets
14
.
2
.
1
.
1
Reachable set
14
.
2
.
1
.
2
Time-limited reachable set
14
.
2
.
1
.
3
Backward reachable sets
14
.
2
.
2
The Discrete-Time Model
14
.
2
.
2
.
1
Reachability graph
14
.
2
.
2
.
2
Resolution completeness for
14
.
2
.
2
.
3
Resolution completeness for
14
.
2
.
3
Motion Primitives
14
.
3
Sampling-Based Motion Planning Revisited
14
.
3
.
1
Basic Components
14
.
3
.
1
.
1
Distance and volume in
14
.
3
.
1
.
2
Sampling theory
14
.
3
.
1
.
3
Collision detection
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
.
1
.
1
A double-integrator lattice
14
.
4
.
1
.
2
Extensions and other considerations
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
.
6
.
3
.
1
Expressing systems in terms of
,
, and
14
.
6
.
3
.
2
Determining the allowable accelerations
14
.
6
.
3
.
3
The path-constrained phase space
14
.
6
.
3
.
4
Computing optimal solutions via dynamic programming
14
.
6
.
3
.
5
A bang-bang approach for time optimality
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
.
1
.
1
The discrete case
15
.
2
.
1
.
2
The continuous case
15
.
2
.
1
.
3
Variants of the HJB 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
.
2
.
1
Completely integrable or nonholonomic?
15
.
4
.
2
.
2
Distributions
15
.
4
.
2
.
3
Lie brackets
15
.
4
.
2
.
4
The Frobenius Theorem
15
.
4
.
3
Determining Controllability
15
.
4
.
3
.
1
The Lie algebra
15
.
4
.
3
.
2
Lie algebra of the system distribution
15
.
4
.
3
.
3
Philip Hall basis of a Lie algebra
15
.
4
.
3
.
4
Controllability of driftless systems
15
.
4
.
3
.
5
Handling Control-Affine Systems with Drift
15
.
5
Steering Methods for Nonholonomic Systems
15
.
5
.
1
Using the P. Hall Basis
15
.
5
.
2
Using Sinusoidal Action Trajectories
15
.
5
.
2
.
1
Steering the nonholonomic integrator
15
.
5
.
2
.
2
First-order controllable systems
15
.
5
.
2
.
3
Chained-form systems
15
.
5
.
3
Other Steering Methods
Further Reading
Exercises
Steven M LaValle 2011-09-05
