WarpMPC: Large-Batch MPC on GPU via ADMM with Unrolled LDL Factorization

summary

The gist

WarpMPC introduces numerical optimizations for maximizing throughput on GPU when solving large batches of sequential quadratic programming (SQP) iterations where all problems have the same structure.

In short

WarpMPC is a JAX toolbox that maximizes GPU throughput for solving large batches of sequential quadratic programming (SQP) iterations used in model-predictive control (MPC). It achieves this by exploiting shared sparsity across problems using unrolled sparse linear factorizations and optimized memory layouts. This significantly boosts performance, reaching throughputs up to 250,000 SQP iterations per second on various robot benchmarks.

Key concepts

Sequential Quadratic Programming (SQP)
SQP is a method used to find optimal solutions for complex constrained optimization problems, like those in MPC. It works by iteratively solving a sequence of simpler quadratic subproblems that approximate the original nonlinear problem. In this context, it's the core solver being accelerated.
ADMM Solver
Alternating Direction Method of Multipliers (ADMM) is an optimization algorithm used to solve large-scale problems by breaking them down into smaller, more manageable subproblems. WarpMPC uses ADMM as a framework to manage and efficiently solve the large batch of MPC problems in parallel.
Unrolled Sparse LDL Factorization
This technique involves pre-calculating sparse linear factorizations based on the shared structure (sparsity) found across many MPC problems. By 'unrolling' these factorizations, WarpMPC avoids redundant computations and memory access bottlenecks during the online solving phase, leading to massive speed improvements.
Model Predictive Control (MPC)
MPC is a control strategy for nonlinear systems that uses a model to predict future system behavior and then optimizes a sequence of control actions over a future time horizon. It is crucial for robotics, allowing systems like quadrotors or humanoid robots to navigate while respecting physical constraints.

Terminology used across episodes

This episode discusses

The paper

WarpMPC: Large-Batch MPC on GPU via ADMM with Unrolled LDL Factorization · Read on arXiv

Henrik Hose, Se Hwan Jeon, Charles Khazoom, Sangbae Kim, Sebastian Trimpe

Institute for Data Science in Mechanical Engineering, RWTH Aachen University, Germany · Massachusetts Institute of Technology, Cambridge MA, USA

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: We're looking at the paper: "WarpMPC: Large-Batch MPC on GPU via ADMM with Unrolled LDL Factorization".

Dev: Here's the gist of the paper. WarpMPC introduces numerical optimizations for maximizing throughput on GPU when solving large batches of sequential quadratic programming (SQP) iterations where all problems have the same structure.

Rosa: Problem Context and Motivation Model-predictive control (MPC) is a popular method for controlling nonlinear systems subject to constraints.

Dev: Recently, there has been significant interest in integrating deep learning and MPC for robotics, which requires solving large batches of MPC problems.

Rosa: Most existing MPC toolboxes are optimized for single solve speed on CPU or GPU or if batched on GPU can not handle general constraints.

Paper summary: Rosa: So we're looking at this paper, "WarpMPC: Large-Batch MPC on GPU via ADMM with Unrolled LDL Factorization," and the main idea is that they've developed some numerical optimizations for when you have a really big batch of sequential quadratic programming iterations running on a GPU.

Dev: The core thesis is that if all those problems in your batch share the same structure—meaning they have the same sparsity in time, cost, and constraints—you can speed things up by unrolling sparse linear factorizations and solves that are part of the alternating direction method of multipliers solver.

Taro: So what does this mean for us? It suggests that instead of solving each problem individually one after another, we can exploit that shared structure across the whole batch to avoid wasting computation and memory access bottlenecks.

Rosa: Exactly. They propose three specific optimizations: an optimized memory layout, a padding-reducing way to segment that unrolled factorization, and dependency level scheduled backsolves. They also accelerate sensitivity computation.

Dev: And the results they show are pretty impressive for throughput; they achieved speeds of eight thousand to two hundred fifty thousand sequential quadratic programming iterations per second on benchmarks like the nonlinear cartpole, quadrotor, and humanoid robot.

Taro: Outperforming existing methods by three times to twenty-five times is a significant jump if you're dealing with those kinds of large batches. It's not just theoretical; they even show practical relevance by distilling a neural network approximation from an MPC in under five minutes that stabilizes a nano quadrotor in hardware experiments.

Rosa: That stabilization part is really interesting for me, because it moves this from just math on the screen to something that actually works outside the lab environment. So, we've seen how they claim it can handle large batches of sequential quadratic programming iterations on GPUs via ADMM with unrolled LDL factorization >

Conclusion: Dev: To wrap up, we're talking about this paper "WarpMPC: Large-Batch MPC on GPU via ADMM with Unrolled LDL Factorization" by Hose, Jeon, Khazoom, Kim, and Trimpe. The authors are showing how to tackle the throughput challenge when you need to solve a large batch of sequential quadratic programming iterations on a GPU.

Rosa: It boils down to them finding that by unrolling sparse linear factorizations and solves related to the alternating direction method of multipliers solver, they can significantly boost performance by avoiding memory access issues and wasting computation.

Taro: From what I'm hearing, this work suggests that for problems where you have a lot of sequential MPC tasks with the same underlying structure, this approach using unrolled LDL factorization is much faster than current state-of-the-art GPU libraries.

Dev: The implication is that we can handle larger batches of constrained nonlinear model predictive control problems on GPUs with much higher speeds. They show consistent throughput improvements ranging from three times up to twenty-five times compared to other top GPU solvers for large batches >

Rosa: It’s about taking that idea and making it practical, proving it works on real robot benchmarks like the cartpole and quadrotor, and even showing how it can be used in a fast distillation process for an MPC policy >

More episodes

← Home