16-745: Dynamic Optimization
Instructor: Chris Atkeson, cga at cmu
TA: Ben Xinjilefu, xxinjile at andrew
MW 3-4:20 NSH 3002
Events of Interest
Last year's course
Jan 18: Introduction to the course.
Jan 23: Function Optimization Example
Robotics: redundant inverse kinematics.
Using Matlab's fminsearch and fminunc.
Using Matlab's fminsearch and fminunc, with
Using Matlab's fmincon.
Relationship of Jacobian approach to gradient descent.
Function optimization using
order gradient methods.
A nice chapter on function optimization techniques:
Numerical Recipes in C, chapter 10
(2nd or 3rd edition, 2nd edition is electronically available for free
under Obsolete Versions):
Minimization or Maximization of Functions,
This material from any other numerical methods book is also fine.
software list 1,
conjugate gradient v2,
quasi-Newton/variable metric methods, and
Jan 25: Non-gradient ("derivative-free") optimization methods:
local unimodal sampling,
Nelder Mead/Simplex/Amoeba method,
fit surfaces (for example
Response Surface Methodology (RSM),
Memory-based Stochastic Optimization, and
Derivative-free optimization: A review of algorithms and comparison of software implementations by Luis Miguel Rios and Nikolaos V. Sahinidis,
Book: Introduction to Derivative-Free Optimization
Jan 30: Constraints.
Soft/hard constraints, penalty functions,
Augmented Lagrangian method,
Interior point methods vs. Simplex methods vs. soft constraint methods,
Jan 30: Formulating trajectory optimization as function optimization.
Examples of formulating a trajectory optimization problem
as a function optimization problem:
Case Studies In Trajectory Optimization: Trains, Planes, And Other
Robert J. Vanderbei
Example use of AMPL
A free trial version of AMPL is available from here.
AMPL is also available for remote use through the Neos Server.
Click on SNOPT/[AMPL Input] under Nonlinearly Constrained Optimization.
Example use of Matlab
Sequential quadratic programming,
Spacetime Optimization: Witkin paper text
Witkin paper figures
Feb 1: Use of splines in trajectory optimization.
Cubic Hermite spline.
Need paper reference.
Feb 1: Ways to robustify function optimization:
Problems: How choose method?, more of an art than a science, local minima, bad answers, discontinuities, redundant/rank deficient constraints,
bad scaling, no formulas for derivatives, you are lazy, computational cost.
Techniques: Levenberg Marquardt,
scaling and preconditioning, regularize parameters, soft constraints,
Policy optimization I: Use function optimization.
What is a policy?
Known in machine learning/reinforcement learning as policy search or refinement, ...
Covariance Matrix Adaptation Evolution Strategy.
See also Hansen web page.
Differential Dynamic Programming,
Linear Quadratic Regulator
Feb 20: Case Study: Assignment 2
Feb 22: Model Predictive Control (MPC), (a.k.a. receding horizon control).
Feb 22-27: Ways to reduce the curse of dimensionality
Feb 29: Policy Optimization II: Optimization using model-based gradients
March 5: Robustness using Linear Matrix Inequalities
Robustness to parametric uncertainty in the linear(ized) model.
I can't find a good reference on robustness using linear matrix inequalities,
but here is a tutorial on LMIs
March 7: Robustness
Robustness to random disturbances, varying initial conditions, parametric
model error, structural modeling error such as
high frequency unmodelled dynamics,
and model jumps (touchdown and liftoff during walking, for example).
Monte Carlo trajectory/policy optimization.
March 7: Robustness: Policy Optimization with Multiple Models.
Monte-Carlo, DP, and DDP approaches to Multiple Models.
Information state DP.
Gaussian Propagation (like Kalman Filter),
Unscented (like Unscented Filter), Second Order Kalman Filter (See Kendrick below).
Local Approaches to Dual Control/Stochastic DDP
Information state trajectory optimization.
Stochastic Control for Economic Models,
David Kendrick, Second Edition 2002.
March 26: Robustness and state estimation:
loop transfer recovery (LTR).
March 28 - April 2: Robustness and state estimation:
Example of bad interactions,
Policy optimization approaches.
April 4: Model free policy optimization.
Kober, J.; Peters, J. (2011). Policy Search for Motor Primitives in Robotics, Machine Learning, 84, 1-2, pp.171-203
April 9: Adaptive Control
April 11: A*-like algorithms: R*
April 16: CHOMP, RRT, RRT*
April 18: Continuation Methods,
Optimizing similar tasks,
Learning during optimization
Trajectory optimization based on integrating the dynamics:
calculus of variations,
Pontryagin's minimum principle,
multiple shooting methods,
Learning From Demonstration
Learning Heuristic Functions
THE FOLLOWING DATES ARE CORRECT
Apr. 30: Project presentations
May 2: Project presentations
Assignment 0 (Due Jan. 22): Send CGA email:
Who are you?
Why are you here?
What research do you do?
Describe any optimization you have done (point me to papers or
web pages if they exist).
Any project ideas?
What topics would you especially like the course to cover?
Be sure your name is obvious in the email, and you mention the course
name or number. I teach more than one course, and a random email from
firstname.lastname@example.org is hard for me to process.
Assignment 1: Trajectory Optimization (Due Feb. 12)
Assignment 2: Policy Design I (Due Mar. 11)
Assignment 3 (Due March. 26): Send TA and CGA email:
What is your project?
Assignment 4: Robustness (Due Apr. 29)
May 13: Graduating Students: last day to turn in overdue assignments and projects
May 17: All Other Students: last day to turn in overdue assignments and projects