16-745: Dynamic Optimization
Spring 2011
Instructor: Chris Atkeson, cga at cmu
MW 3-4:20 NSH 3002

Events of Interest

• PhD Thesis Defense: G. Ayorkor Korsah Exploring bounded optimal coordination for heterogeneous teams with cross-schedule dependencies
  January 18, 2011, 12:00 p.m., GHC 6501

Course Description

Resources and Readings

• Jan 10: Introduction to the course.
  
• Jan 12: 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 Pastimes, 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
  
• Jan 17: MLK holiday.
  
• Jan 19: Function optimization using first and second 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.
  Resources: Matlab, Numerical Recipes, GSL, AMPL, NEOS, software list 1, Useful software guide,
  gradient method, line search, conjugate gradient, conjugate gradient v2, quasi-Newton/variable metric methods, and Newton's method.
• Jan 19: Ways to robustify function optimization:
  Problems: local minima, discontinuities, redundant/rank deficient constraints, bad scaling, no formulas for derivatives,
  Techniques: Levenberg Marquardt, Trust regions, scaling and preconditioning, regularize parameters, soft constraints, line search, sparse methods,
• Jan 24: Constraints.
  Lagrange Multipliers.
• Jan 24: Non-gradient optimization methods:
  hill climbing (including local search, local unimodal sampling, pattern search, random search, random optimization), Nelder Mead/Simplex/Amoeba method, simulated annealing, fit surfaces (for example Response Surface Methodology (RSM), Memory-based Stochastic Optimization, and Q2), evolutionary algorithms, and ...
• Jan 26: Use of splines in trajectory optimization.
  Cubic Hermite spline. Need paper reference.
• Jan 26: Sequential quadratic programming.
  SNOPT Witkin paper text Witkin paper figures
  Collocation
• Jan 26: Covariance Matrix Adaptation Evolution Strategy.
  See also Hansen web page. Example of use.
  
• Jan 31 - Feb. 9: Policy optimization I: Use function optimization.
  Known in machine learning/reinforcement learning as policy search, policy refinement, policy gradient, ...
• Feb. 7: No class
• Feb. 9-23: Dynamic Programming. Bellman equation, Linear Quadratic Regulator, Differential Dynamic Programming,
• Feb. 16: Anca Dragan CHOMP and goal sets.
• Feb. 28: trajectory optimization based on integrating the dynamics: calculus of variations, Euler-Lagrange equation, Pontryagin's minimum principle, Hamilton-Jacobi-Bellman equation, costate equations, shooting methods, multiple shooting methods,
• Mar. 2: SeungJoon Lee Airfoil optimization.
• Mar. 2: Model Predictive Control (MPC), (a.k.a. receding horizon control).
• Mar. 7. 9: No class
• Mar. 14: Robustness Be robust to random disturbances, varying initial conditions, parametric model error, high frequency unmodelled dynamics, and model jumps (touchdown and liftoff during walking, for example). Monte Carlo trajectory/policy optimization.
• Mar. 16: Dual Control. Information state DP. Simple example.
• Mar. 21: Uncertainty Propagation Gaussian Propagation (like Kalman Filter), Unscented (like Unscented Filter), Second Order Kalman Filter (See Kendrick).
• Mar. 23: Local Approaches to Dual Control/Stochastic DDP Information state trajectory optimization. Stochastic Control for Economic Models, David Kendrick, Second Edition 2002.
• Mar. 23: Erhan Arisoy
• Mar. 28: Modeling Techniques and Modeling Error
• Mar. 30: High Frequency Unmodeled Dynamics How model-based techniques can fail. Why policy X techniques also fail. What reinforcement learning (RL) can learn from adaptive control theory.
• Mar. 30: Kyle Strabala
• Apr. 4: Monte-Carlo, DP, and DDP approaches to Multiple Models
• Apr. 6: Learning From Demonstration
• Apr. 11: X. Xinjilefu
• Apr. 11: Optimizing similar tasks
• Apr. 13: Feng Zhou
• Apr. 13: A*-like algorithms
• Apr. 18: Meta-optimization
• Apr. 20: Jiuguang Wang
• Apr. 25: Project presentations
• Apr. 27: Project presentations

Assignments

• Assignment 0 (Due Jan. 11): 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?
  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 robotlover@cs.cmu.edu is hard for me to process.
• Assignment 1: Trajectory Optimization (Due Feb. 3)
• Assignment 2: Optimizing Probabilities (Due Feb. 24)

Project Info