Algorithms for Walking, Running, Swimming, Flying, and Manipulation

© Russ Tedrake, 2020

How to cite these notes |
Send me your feedback

**Note:** These are working notes used for a course being taught
at MIT. They will be updated throughout the Spring 2020 semester. Lecture videos are available on YouTube.

- Preface
- Chapter 1: Fully-actuated vs Underactuated Systems
- Motivation
- Honda's ASIMO vs. passive dynamic walkers
- Birds vs. modern aircraft
- Manipulation
- The common theme
- Definitions
- Feedback Equivalence
- Input and State Constraints
- Nonholonomic constraints
- Underactuated robotics
- Goals for the course
- Exercises
- Chapter 2: The Simple Pendulum
- Introduction
- Nonlinear dynamics with a constant torque
- The overdamped pendulum
- The undamped pendulum with zero torque
- The undamped pendulum with a constant torque
- The torque-limited simple pendulum
- Energy-shaping control
- Exercises
- Chapter 3: Acrobots, Cart-Poles, and Quadrotors
- The Acrobot
- Equations of motion
- The Cart-Pole system
- Equations of motion
- Quadrotors
- The Planar Quadrotor
- The Full 3D Quadrotor
- Balancing
- Linearizing the manipulator equations
- Controllability of linear systems
- LQR feedback
- Partial feedback linearization
- PFL for the Cart-Pole System
- General form
- Swing-up control
- Energy shaping
- Cart-Pole
- Acrobot
- Discussion
- Differential Flatness
- Other model systems
- Exercises
- Chapter 4: Simple Models of Walking and Running
- Limit Cycles
- PoincarĂ© Maps
- Simple Models of Walking
- The Rimless Wheel
- The Compass Gait
- The Kneed Walker
- Curved feet
- And beyond...
- Simple Models of Running
- The Spring-Loaded Inverted Pendulum
- Hopping Robots from the MIT Leg Laboratory
- A Simple Model That Can Walk and Run
- Exercises
- Chapter 5: Highly-articulated Legged Robots
- Center of Mass Dynamics
- A hovercraft model
- Robots with (massless) legs
- Capturing the full robot dynamics
- Impact dynamics
- The special case of flat terrain
- An aside: the zero-moment point derivation
- ZMP planning
- From a CoM plan to a whole-body plan
- Whole-Body Control
- Footstep planning and push recovery
- Beyond ZMP planning
- Exercises
- Chapter 6: Model Systems with Stochasticity
- The Master Equation
- Stationary Distributions
- Extended Example: The Rimless Wheel on Rough Terrain
- Noise models for real robots/systems.
- Analysis (a preview)
- Control Design (a preview)
- Chapter 7: Dynamic Programming
- Formulating control design as an optimization
- Additive cost
- Optimal control as graph search
- Continuous dynamic programming
- The Hamilton-Jacobi-Bellman Equation
- Solving for the minimizing control
- Numerical solutions for $J^*$
- Extensions
- Linear Programming Approach
- Exercises
- Chapter 8: Linear Quadratic Regulators
- Basic Derivation
- Local stabilization of nonlinear systems
- Finite-horizon formulations
- Finite-horizon LQR
- Time-varying LQR
- Linear Quadratic Optimal Tracking
- Linear Final Boundary Value Problems
- Variations and extensions
- Discrete-time Riccati Equations
- LQR with input and state constraints
- LQR as a convex optimization
- Finite-horizon LQR via least squares
- Exercises
- Notes
- Finite-horizon LQR derivation (general form)
- Chapter 9: Lyapunov Analysis
- Lyapunov Functions
- Global Stability
- LaSalle's Invariance Principle
- Relationship to the Hamilton-Jacobi-Bellman equations
- Lyapunov analysis with convex optimization
- Lyapunov analysis for linear systems
- Lyapunov analysis as a semi-definite program (SDP)
- Lyapunov analysis for polynomial systems
- Lyapunov functions for estimating regions of attraction
- Robustness analysis using "common Lyapunov functions"
- Region of attraction estimation for polynomial systems
- Rigid-body dynamics are (rational) polynomial
- Exercises
- Chapter 10: Trajectory Optimization
- Problem Formulation
- Convex Formulations for Linear Systems
- Direct Transcription
- Direct Shooting
- Computational Considerations
- Continuous Time
- Nonconvex Trajectory Optimization
- Direct Transcription and Direct Shooting
- Direct Collocation
- Pseudo-spectral Methods
- Solution techniques
- Local Trajectory Feedback Design
- Time-varying LQR
- Model-Predictive Control
- Case Study: A glider that can land on a perch like a bird
- The Flat-Plate Glider Model
- Trajectory optimization
- Trajectory stabilization
- Beyond a single trajectory
- Pontryagin's Minimum Principle
- Lagrange multiplier derivation of the adjoint equations
- Necessary conditions for optimality in continuous time
- Variations and Extensions
- Iterative LQR and Differential Dynamic Programming
- Mixed-integer convex optimization for non-convex constraints
- Explicit model-predictive control
- Exercises
- Chapter 11: Motion Planning as Search
- Artificial Intelligence as Search
- Randomized motion planning
- Rapidly-Exploring Random Trees (RRTs)
- RRTs for robots with dynamics
- Variations and extensions
- Discussion
- Decomposition methods
- Exercises
- Chapter 12: Feedback Motion Planning
- Chapter 13: Policy Search
- Problem formulation
- Controller parameterizations
- Trajectory-based policy search
- Lyapunov-based approaches to policy search.
- Approximate Dynamic Programming
- Chapter 14: Robust and Stochastic Control
- Discrete states and actions
- Graph search -- stochastic shortest path problems
- Stochastic interpretation of deterministic, continuous-state value iteration
- Linear Quadratic Gaussian (LQG)
- Linear Exponential-Quadratic Gaussian (LEQG)
- Chapter 15: Output Feedback (aka Pixels-to-Torques)
- The Classical Perspective
- Observer-based Feedback
- Luenberger Observer
- Linear Quadratic Regulator w/ Gaussian Noise (LQG)
- Partially-observable Markov Decision Processes
- Static Output Feedback
- For Linear Systems
- Disturbance-based feedback
- System-Level Synthesis
- Chapter 16: Algorithms for Limit Cycles
- Trajectory optimization
- Lyapunov analysis
- Transverse coordinates
- Transverse linearization
- Region of attraction estimation using sums-of-squares
- Feedback design
- For underactuation degree one.
- Transverse LQR
- Orbital stabilization for non-periodic trajectories
- Chapter 17: Planning and Control through Contact
- (Autonomous) Hybrid Systems
- Hybrid trajectory optimization
- Stabilizing hybrid models.
- Deriving hybrid models: minimal vs floating-base coordinates
- Chapter 18: System Identification
- Equation Error vs Simulation Error
- Linear State-Space Models
- From state observations
- From input-output data
- Adding stability constraints
- Linear ARMAX Models
- Nonlinear System Identification
- Parameter Identification for Mechanical Systems
- Optimal Experiment Design
- Chapter 19: State Estimation
- Chapter 20: Model-Free Policy Search
- Policy Gradient Methods
- The Likelihood Ratio Method (aka REINFORCE)
- Sample efficiency
- Stochastic Gradient Descent
- The Weight Pertubation Algorithm
- Weight Perturbation with an Estimated Baseline
- REINFORCE w/ additive Gaussian noise
- Summary
- Sample performance via the signal-to-noise ratio.
- Performance of Weight Perturbation
- Appendix A: Drake
- Appendix B: Multi-Body Dynamics
- Deriving the equations of motion (an example)
- The Manipulator Equations
- Recursive Dynamics Algorithms
- Bilateral Position Constraints
- Bilateral Velocity Constraints
- The Dynamics of Contact
- Compliant Contact Models
- Rigid Contact with Event Detection
- Time-stepping Approximations for Rigid Contact
- Parameter Estimation
- Appendix C: Optimization and Mathematical Programming
- Optimization software
- General concepts
- Convex vs nonconvex optimization
- Constrained optimization with Lagrange multipliers
- Convex optimization
- Linear Programs/Quadratic Programs/Second-Order Cones
- Semidefinite Programming and Linear Matrix Inequalities
- Sums-of-squares optimization
- Solution techniques
- Nonlinear programming
- Second-order methods (SQP / Interior-Point)
- First-order methods (SGD / ADMM)
- Zero-order methods (CMA)
- Example: Inverse Kinematics
- Combinatorial optimization
- Search, SAT, First order logic, SMT solvers, LP interpretation
- Mixed-integer convex optimization
- "Black-box" optimization
- Appendix D: An Optimization Playbook

**Model Systems**

**Nonlinear Planning and Control**

**Estimation and Learning**

**Appendix**

This book is about building robots that move with speed, efficiency, and grace. I believe that this can only be achieve through a tight coupling between mechanical design, passive dynamics, and nonlinear control synthesis. Therefore, these notes contain selected material from dynamical systems theory, as well as linear and nonlinear control.

These notes also reflect a deep belief in computational algorithms playing an essential role in finding and optimizing solutions to complex dynamics and control problems. Algorithms play an increasingly central role in modern control theory; these days even rigorous mathematicians consider finding convexity in a problem (therefore making it amenable to an efficient computational solution) almost tantamount to an analytical result. Therefore, the notes necessarily also cover selected material from optimization theory, motion planning, and machine learning.

Although the material in the book comes from many sources, the presentation is targeted very specifically at a handful of robotics problems. Concepts are introduced only when and if they can help progress the capabilities we are trying to develop. Many of the disciplines that I am drawing from are traditionally very rigorous, to the point where the basic ideas can be hard to penetrate for someone that is new to the field. I've made a conscious effort in these notes to keep a very informal, conversational tone even when introducing these rigorous topics, and to reference the most powerful theorems but only to prove them when that proof would add particular insights without distracting from the mainstream presentation. I hope that the result is a broad but reasonably self-contained and readable manuscript that will be of use to any enthusiastic roboticist.

The material in these notes is organized into a few main parts. "Model Systems" introduces a series of increasingly complex dynamical systems and overviews some of the relevant results from the literature for each system. "Nonlinear Planning and Control" introduces quite general computational algorithms for reasoning about those dynamical systems, with optimization theory playing a central role. Many of these algorithms treat the dynamical system as known and deterministic until the last chapters in this part which introduce stochasticity and robustness. "Estimation and Learning" follows this up with techniques from statistics and machine learning which capitalize on this viewpoint to introduce additional algorithms which can operate with less assumptions on knowing the model or having perfect sensors. The book closes with an "Appendix" that provides slightly more introduction (and references) for the main topics used in the course.

The order of the chapters was chosen to make the book valuable as a reference. When teaching the course, however, I take a spiral trajectory through the material, introducing robot dynamics and control problems one at a time, and introducing only the techniques that are required to solve that particular problem.

All of the examples and algorithms in this book, plus many more, are now
available as a part of our open-source software project:

Please see the appendix
for specific instructions for using