Parallel-in-Time Nonlinear Optimal Control via GPU-native Sequential Convex Programming

This paper presents a fully GPU-native trajectory optimization framework that leverages sequential convex programming and consensus-based ADMM with temporal splitting to achieve real-time, high-throughput nonlinear optimal control for autonomous systems, demonstrating significant speedups and energy efficiency over CPU baselines while enabling scalable multi-trajectory and robust Model Predictive Control.

The Gist

Imagine you are the pilot of a super-agile drone or a rocket ship trying to land on Mars. Your computer needs to figure out the perfect path to get from Point A to Point B, avoiding obstacles, while obeying strict laws of physics and not running out of fuel. This is called trajectory optimization.

Usually, doing this math is like trying to solve a massive, 1,000-piece jigsaw puzzle where every piece depends on the one before it. You have to place piece #1, then piece #2, then piece #3, all the way to the end. If you do this on a standard computer (a CPU), it's like having one very smart person working on the puzzle. They are fast, but they can only do one thing at a time.

This paper introduces a new way to solve these puzzles using GPUs (the powerful chips usually found in gaming computers) and a clever strategy called "Parallel-in-Time."

Here is the breakdown of how they did it, using some everyday analogies:

1. The Old Problem: The Single-File Line

Traditional methods treat a flight path like a conveyor belt.

• To know where the drone will be at second 5, you must calculate where it was at second 4.
• To know second 4, you need second 3.
• This creates a "bottleneck." Even if you have a super-fast computer with 12 workers (CPU cores), they are stuck waiting in a single-file line. They can't work together because the math forces them to be sequential.

2. The New Solution: The "Team of Independent Contractors"

The authors, Yilin Zou and his team, realized that instead of a conveyor belt, they could treat every single moment in time as an independent contractor.

Imagine you are building a 100-story skyscraper.

• Old Way: You build the ground floor, wait for it to dry, then build the second floor, wait, then the third.
• New Way (This Paper): You hire 100 different construction crews. Crew #1 builds the ground floor, Crew #2 builds the 10th floor, Crew #3 builds the 50th floor. They all work at the exact same time.

But wait, how do they make sure the building doesn't collapse if everyone is working independently?

3. The Secret Sauce: The "Consensus Meeting"

This is where the magic happens. The paper uses a method called ADMM (Alternating Direction Method of Multipliers). Think of this as a daily stand-up meeting for the construction crews.

1. Independent Work: Each "time-step" crew works on their own floor, ignoring the others for a moment. They solve their own small math problem very quickly.
2. The Check-in: At the end of the day, they all gather (in the computer's memory) and say, "Hey, I built my floor assuming you were here. Did you actually build your floor?"
3. The Adjustment: If Crew #10 says, "I'm too far to the left," Crew #9 and Crew #11 gently nudge their plans to match.
4. Repeat: They go back to work, check in again, and nudge again. Within a few rounds, everyone agrees on a perfect, continuous building.

Because the "checking in" part is simple math, the computer can do it for thousands of time steps simultaneously on the GPU.

4. Why This Matters: Speed and Efficiency

The authors tested this on two crazy-hard scenarios:

• A Quadrotor (Drone): Flying through a forest of obstacles, dodging them at high speed.
• Mars Landing: A rocket trying to land on Mars with uncertain wind and gravity, needing to be perfect every time.

The Results:

• Speed: Their new system was 4 times faster than the best 12-core computer they could find. It could plan new paths over 100 times per second (100 Hz). That's like making a decision faster than a human eye can blink.
• Energy: It used 51% less electricity. This is huge for robots on batteries or spacecraft where every watt counts.
• Safety: They showed it could plan for 1,000 different "what-if" scenarios at once. Imagine a self-driving car asking, "What if it rains? What if a kid runs out? What if the tire blows?" It can answer all those questions instantly to pick the safest route.

The Big Picture

Think of this paper as the invention of the assembly line for the future.
Before, we calculated the future one second at a time. Now, we can calculate the whole future, second by second, all at once, by breaking the problem into tiny, independent pieces that talk to each other briefly to stay in sync.

This means robots can finally be agile, safe, and smart enough to handle the real world, running on small, battery-powered computers right on the robot itself, rather than needing a giant server farm to do the thinking for them.

Technical Summary

Here is a detailed technical summary of the paper "Parallel-in-Time Nonlinear Optimal Control via GPU-native Sequential Convex Programming".

1. Problem Statement

The paper addresses the critical bottleneck in real-time trajectory optimization for nonlinear, constrained autonomous systems (e.g., quadrotors, Mars landers).

• Current Limitations: Existing solvers rely on CPU-based sequential algorithms (e.g., iLQR, IPOPT). These methods are hindered by:
  • Serial Dependencies: Dynamic programming and Riccati recursions are inherently sequential, preventing full utilization of massive parallel hardware like GPUs.
  • Sparse Linear Algebra: Solving large-scale Nonlinear Programming (NLP) problems often requires sparse matrix factorization (KKT systems), which involves random memory access and sequential pivoting. These operations map poorly to Single Instruction Multiple Threads (SIMT) GPU architectures.
  • Scalability: Generating data for reinforcement learning or solving robust Model Predictive Control (MPC) with stochastic disturbances requires solving thousands of trajectories simultaneously, which is computationally prohibitive on CPUs.

2. Methodology

The authors propose ucenter, a fully GPU-native framework that combines Sequential Convex Programming (SCP) with a Consensus-based Alternating Direction Method of Multipliers (ADMM).

Core Architecture

The framework employs a two-layer hierarchical approach (illustrated in Fig. 1 of the paper):

A. Outer Loop: Sequential Convex Programming (SCP)

• Function: Handles nonlinearity by iteratively linearizing the dynamics and convexifying the cost function around a nominal trajectory $(\bar{x}_k, \bar{u}_k)$.
• Parallelization: The evaluation of dynamics, costs, and their derivatives at each time step is independent. The entire linear-quadratic approximation is computed simultaneously by mapping each collocation node to a separate GPU thread block.

B. Inner Loop: Parallel Consensus ADMM
Instead of solving the resulting Quadratic Program (QP) via global sparse factorization, the problem is reformulated using variable splitting to decouple time steps:

1. Variable Splitting: Three sets of variables are introduced for each time node:
   • Physical Variables ($x, u$): Minimize local quadratic costs and satisfy linearized dynamics.
   • Dynamic Auxiliary Variables ($z$): Decouple temporal dependencies between time steps $i$ and $i+1$.
   • Geometric Mirror Variables ($\hat{x}, \hat{u}$): Handle hard inequality constraints (e.g., thrust limits, trust regions) via proximal projection.
2. Augmented Lagrangian: The problem is minimized using an augmented Lagrangian that enforces consistency between these variable sets via penalty terms ($\rho_{eq}, \rho_{dyn}, \rho_{geo}$).
3. Parallel Update Steps:
   • Physical Layer: Solves a small, dense, unconstrained quadratic minimization for each time step. Crucially, the Hessian is strictly positive definite due to regularization, allowing for pivoting-free Cholesky factorization (ideal for GPUs).
   • Dynamic Layer: Updates $z$ via a closed-form weighted average (least-squares solution).
   • Geometric Layer: Updates $\hat{x}, \hat{u}$ via simple element-wise clamping (proximal operator) for box constraints.
   • Dual Update: Updates multipliers in parallel.

This structure eliminates global sparse factorizations and Riccati recursions, replacing them with independent, dense solves and closed-form updates that execute massively in parallel.

3. Key Contributions

1. ucenter Framework: A fully GPU-native trajectory optimization solver that executes the entire algorithmic loop on the GPU, minimizing CPU-GPU synchronization overhead.
2. ADMM-based Time Splitting: Reformulates SCP subproblems to avoid global sparse KKT factorizations. Each iteration consists of independent per-time-step dense solves and analytical projections.
3. Scalable Multi-Trajectory Optimization: The architecture naturally supports "ensemble solving," allowing simultaneous optimization of hundreds of trajectories across different initial conditions, goals, or uncertainty realizations.
4. Empirical Validation: Extensive testing on edge computing hardware (Nvidia Jetson AGX Orin) for complex aerospace and robotics tasks.

4. Results

The solver was validated on an Nvidia Jetson AGX Orin (64GB) edge platform, comparing performance against a heavily optimized 12-core CPU baseline (using iLQR).

• Quadrotor Agile Flight:

  • Throughput: Achieved a peak throughput of 101.1 Hz for batch sizes of 5,000 trajectories, compared to the CPU's saturation at ~24.6 Hz.
  • Speedup: Sustained a 4.1× speedup over the 12-core CPU.
  • Energy Efficiency: Reduced energy consumption by 51% (119 J vs. 243 J for a batch of 1,000 trajectories).
  • Utilization: Maintained >96% active GPU utilization, effectively saturating the hardware.
  • Robustness: Successfully solved 93.9% of randomized, obstacle-cluttered scenarios with strict dynamics and collision constraints.

• Mars Powered Descent:

  • Scenario Optimization: Successfully optimized 1,000 perturbed descent scenarios simultaneously to verify safety under uncertainty.
  • Success Rate: Achieved a 99.8% success rate in finding fuel-optimal trajectories respecting strict glide slope and thrust constraints.
  • Throughput: Sustained 268.63 Hz throughput for the batch optimization.

• Robust MPC: Demonstrated the ability to jointly optimize 15 dynamically coupled scenarios under stochastic crosswinds, generating a safe "prediction tube" in ~200ms per step.

5. Significance

• Real-Time Feasibility: By achieving planning rates exceeding 100 Hz on embedded edge hardware, this work makes computationally heavy paradigms like Robust MPC and Scenario Optimization feasible for real-world autonomous systems.
• Energy Efficiency: The significant reduction in energy consumption is critical for battery-powered mobile robots and aerospace missions.
• Data Generation: The ability to batch-process thousands of trajectories simultaneously drastically reduces the time required to generate expert demonstration datasets for Reinforcement Learning (from days/weeks to minutes).
• Hardware Utilization: The paper demonstrates a paradigm shift from serial sparse solvers to parallel dense solvers, fully leveraging modern GPU architectures for control theory applications.

The source code is packaged as a reusable Python library and will be made publicly available, fostering further research in parallel optimal control.