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

Events of Interest

• Nothing yet.

Course Description

• Jan 13: Introduction to the course.
  This years emphasis is the DARPA Robotics Challenge
• Jan 15: Function Optimization Example
  Robotics: redundant inverse kinematics. Using Matlab's fminsearch and fminunc. Using Matlab's fminsearch and fminunc, with desired posture. Using Matlab's fmincon. Relationship of Jacobian approach to gradient descent.
• Jan 15: 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 fminunc, 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 20: No Class
• Jan 22: Non-gradient ("derivative-free") optimization methods:
  hill climbing (including local search, local unimodal sampling, pattern search, random search, random optimization), Nelder Mead/Simplex/Amoeba method, Matlab fminsearch, simulated annealing, fit surfaces (for example Response Surface Methodology (RSM), Memory-based Stochastic Optimization, and Q2), evolutionary algorithms, genetic algorithms, and ...
  Paper: 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 22-27: Covariance Matrix Adaptation Evolution Strategy.
  See also Hansen web page. Example1, Ex2, Ex3, Ex4.
  
• Jan 27: Constraints.
  Soft/hard constraints, penalty functions, Barrier functions, Lagrange Multipliers, Augmented Lagrangian method, Interior point methods vs. Simplex methods vs. soft constraint methods,
• Jan 27-29: Quadratic Programming and Sequential quadratic programming, Matlab fmincon. SNOPT, CVXGEN
  
• Jan 29: Automatic differentiation
• Jan 29: Dynamics and Numerical Integration Continous time, discrete time. Euler integration, Forward and inverse dynamics. Linearization.
• Feb 3: 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: pend1-x-u, pend1-u, pend1-x
  Spacetime Optimization: Witkin paper text Witkin paper figures
  
• Feb 3: Use of splines in trajectory optimization.
  Cubic Hermite spline. Useful. Example 1,
  Collocation, Pseudospectral X.
• Feb 3: Policy optimization I: Use function optimization.
  What is a policy? Known in machine learning/reinforcement learning as policy search or refinement, ...
  slides See examples in CMA-ES section for policy optimization.
• Feb 5: 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, Trust regions, line search, scaling and preconditioning, regularize parameters, soft constraints, sparse methods, Continuation Methods, Paper on continuation methods, Hand of God, allow constraint violations, add aextra constraints,
  Matlab recommendations
• Feb 5: Dynamic Programming. Bellman equation,
  slides
• Feb 10: Linear Quadratic Regulator, Riccati Equation, Differential Dynamic Programming
• Feb 10: Receding Horizon Control (a.k.a. Model Predictive Control (MPC)).
• Feb 12-17: Ways to reduce the curse of dimensionality
  slides
• Feb 17: Policy Optimization II: Optimization using model-based gradients
  slides
• Feb 19: 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
• Feb 24: 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.
• Feb 24: Robustness: Policy Optimization with Multiple Models. Monte-Carlo, DP, and DDP approaches to Multiple Models.
• Feb 26: State Estimation, Uncertainty Propagation: Gaussian Propagation (like Kalman Filter), Unscented (like Unscented Filter), Second Order Kalman Filter (See Kendrick below).
  Review of Gaussians slides
  State estimation slides
  Matlab Kalman filter example and minimum jerk trajectory subroutine.
  Example mobile robot Kalman filter slides
  
• Feb 26: Dual Control. Simple example. Information state DP.
• March 3: Local Approaches to Dual Control/Stochastic DDP Information state trajectory optimization. Stochastic Control for Economic Models, David Kendrick, Second Edition 2002.
• March 3: Robustness and state estimation: Example of bad interactions, Loop Transfer Recovery (LTR), A paper on the topic, Policy optimization approaches.
• March 5: Case Study: Trajectory Optimization for Full-Body Movements with Complex Contacts
• March 5: Case Study: Discovery of Complex Behaviors through Contact-Invariant Optimization
• March 10-14: No Class
• March 17: Other ways in trajectory optimization to handle contact: Posa, Tedrake, Posa video Erez, Todorov
• March 17: Avoiding obstacles: CHOMP STOMP
• March 19: Sampling based methods: RRT, slides Projected RRT, RRT* slides LQR-RRT* Random Sampling DP
• March 24: A*-like algorithms: R*
• March 26: Reinforcement Learning: Model free policy optimization. Kober, J.; Peters, J. (2011). Policy Search for Motor Primitives in Robotics, Machine Learning, 84, 1-2, pp.171-203
• March 26: Comparison of various RL methods: CMA-ES, CEM, PI2. Freek Stulp and Olivier Sigaud. Path Integral Policy Improvement with Covariance Matrix Adaptation. In Proceedings of the 29th International Conference on Machine Learning (ICML), 2012.
• March 31: Adaptive Control
• March 31: Learning From Demonstration
• April 2: Case Study: Pareto Optimal Control for Natural and Supernatural Motions
• April 2: Case Study: Diverse Motion Variations for Physics-based Character Animation
• April 7: Inverse Optimal Control
  Sergey Levine, Vladlen Koltun. Continuous Inverse Optimal Control with Locally Optimal Examples. ICML 2012
  
• April 9: Case Study: Soft Body Locomotion
• April 9: Case Study: Interactive Spacetime Control of Deformable Objects
• April 14: 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, Karush-Kuhn-Tucker conditions
• April 14: Continuation Methods, Meta-optimization, Learning during optimization
• April 16: Case Study: Flexible Muscle-Based Locomotion for Bipedal Creatures
• April 16: Case Study: Animating Human Lower Limbs Using Contact-Invariant Optimization
• April 16: Case Study: Optimizing Locomotion Controllers Using Biologically-Based Actuators and Objectives
• April 21: Guest Lecture: Jiuguang Wang
• April 23: Case Study: Experiments with a hierarchical inverse dynamics controller on a torque-controlled humanoid.
• April 23: Case Study: An Efficiently Solvable Quadratic Program for Stabilizing Dynamic Locomotion.
• Apr. 28: No class
• Apr. 30: Project presentations
• May. 14: Final Projects Due