September 19, 2014: Seminar - Dr. Nathan Ratliff: "Behavior as an Optimality Principle: Exploiting kth-order Markov structure to leverage generic optimization for efficient representation transforms"

Seminar Announcement

Behavior as an Optimality Principle: Exploiting kth-order Markov structure to leverage generic optimization for efficient representation transforms

Dr. Nathan Ratliff
Max Planck Institute for Intelligent System and the University of Stuttgart
Friday, September 19, 2014
11:00 a.m., 1000 SEO Building


Over the past half decade we've seen a convergence of motion generation approaches toward pure optimization. For many practical problems, these approaches move away from traditional probabilistic planning techniques (PRMs, RRTs), toward methods built around probabilistic inference (AICO), trajectory optimization (CHOMP, STOMP, iTOMP, TrajOpt), and nonlinear optimal control (DDP, iLQG). Interestingly, all of these methods leverage to varying degrees second-order nonlinear optimization at their core, and we're increasingly understanding that the more we move toward pure constrained second-order optimization, the better performance we achieve. In this talk, I'll present a motion optimization framework which we call kth-order Markov Optimization (KOMO) that builds on that central connection. Viewing motion generation as an optimality principle with the role of optimization as a transformation of representation for practical and efficient control, KOMO poses motion planning as a generic nonlinear constrained optimization problem and solves it using an straightforward implementation of the Augmented Lagrangian algorithm. This approach is a more formal rendition of prior optimization-based approaches to exploiting structure in the motion optimization problem for efficient planning. It exploits the inherent kth-order Markov structure of the objective simply by noting that the resulting Hessian is band-diagonal and leveraging fast specialized band-diagonal solvers (implemented in LAPACK) to solve for Newton steps in time linear in the trajectory's horizon. This optimizer is fast and clean, and, importantly, it models environmental obstacles as explicitly constraints and calculates estimates of the constraint's Lagrange multipliers. These Lagrange multipliers encode explicitly where and how the robot should be contacting and interacting with the environment at any moment in time. In a technique we call Dual Execution, we send this information down to control to leverage the inherent resilience to problem variation and modeling inaccuracies of our underlying force controllers and local interaction policies. I'll present an experimental analysis of Dual Execution using KOMO performed on the Max Planck Institute's dual arm torque-controlled manipulation platform, Apollo. This is joint work with a number of collaborators between the Max Planck Institute and the University of Stuttgart.


Nathan Ratliff has been working with robots for over a decade at institutions all around the world. He is currently a Research Scientist at the Max Planck Institute for Intelligent System in Germany and jointly a postdoc at the University of Stuttgart. Between the two institutes he teaches regularly and works on projects spanning motion optimization, dynamic control, inverse optimal control, and machine learning. His PhD thesis at Carnegie Mellon University, written under the advisement of Dr. J. Andrew Bagnell between 2004 and 2009, proposed the first general class of inverse optimal control algorithms forming a link between structured classification in machine learning and the inversion of optimal control methods. Between then and now, he has worked at the Toyota Technological Institute in Chicago (an independent Computer Science department on the University of Chicago campus) as a Research Assistant Professor, at Intel Research in both Pittsburgh and Seattle as a Research Scientist, and at Google as a Software Engineer building large-scale machine learning systems to prevent fraudulent and malicious websites from advertising on Google's ads network. He currently lives with his wife in a quaint rustic paradise called T?bingen, Germany, which he swears is not a movie set.

For meetings: please contact Prof. Brian Ziebart ( to schedule meetings on Friday with Dr. Ratliff

Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF