PaperlayerView exact revision on arXiv

Source-linked AI summary

Safe Large-Scale Robust Nonlinear MPC in Milliseconds via Reachability-Constrained System Level Synthesis on the GPU

Jeffrey Fang, Glen Chou

arXiv:2604.07644v1cs.ROcs.AIeess.SYmath.OC

TL;DR

Safe real-time robotic control requires trajectory and controller synthesis that satisfy constraints and remain robust to disturbances, but existing optimization and reachability methods struggle with large systems. GPU-SLS unifies constrained trajectory optimization with disturbance-feedback synthesis using GPU-parallelized ADMM, SQP, associative scans, caching, and SLS. It achieves substantial solver speedups while certifying safety across tested high-dimensional systems.

  • Problem

    Large robotic systems make constrained nonlinear MPC and reachability too slow or intractable for real-time control, while data-driven reachability estimates can compromise safety.

  • Method

    GPU-SLS jointly solves constrained nominal trajectory optimization and robust feedback-controller synthesis, using GPU-parallelized ADMM, SQP, associative scans, factorization caching, and SLS.

  • Results

    GPU-SLS reduces long-horizon NMPC solve times by 99.8% versus OSQP, 98.9% versus HPIPM, and 71.8% versus a GPU-accelerated augmented-Lagrangian solver, while achieving 100% empirical safety across tested high-dimensional systems.

  • Takeaways & Limitations

    GPU-SLS enables millisecond-scale robust constrained control by combining trajectory optimization, reachability, and disturbance-feedback synthesis in one real-time pipeline.

Abstract

from arXiv · show

We present GPU-SLS, a GPU-parallelized framework for safe, robust nonlinear model predictive control (MPC) that scales to high-dimensional uncertain robotic systems and long planning horizons. Our method jointly optimizes an inequality-constrained, dynamically-feasible nominal trajectory, a tracking controller, and a closed-loop reachable set under disturbance, all in real-time. To efficiently compute nominal trajectories, we develop a sequential quadratic programming procedure with a novel GPU-accelerated quadratic program (QP) solver that uses parallel associative scans and adaptive caching within an alternating direction method of multipliers (ADMM) framework. The same GPU QP backend is used to optimize robust tracking controllers and closed-loop reachable sets via system level synthesis (SLS), enabling reachability-constrained control in both fixed- and receding-horizon settings. We achieve substantial performance gains, reducing nominal trajectory solve times by 97.7% relative to state-of-the-art CPU solvers and 71.8% compared to GPU solvers, while accelerating SLS-based control and reachability by 237x. Despite large problem scales, our method achieves 100% empirical safety, unlike high-dimensional learning-based reachability baselines. We validate our approach on complex nonlinear systems, including whole-body quadrupeds (61D) and humanoids (75D), synthesizing robust control policies online on the GPU in 20 milliseconds on average and scaling to problems with 2 x 10^5 decision variables and 8 x 10^4 constraints. The implementation of our method is available at https://github.com/Jeff300fang/gpu_sls.

I. INTRODUCTION

GPU-SLS addresses the difficulty of safe, real-time control for high-dimensional uncertain robots by combining constrained trajectory optimization, robust controller synthesis, and reachability on the GPU. Its parallel ADMM/SLS framework targets large-scale problems while preserving constraint satisfaction under disturbance.

  • Motivation: Safe robotic operation requires jointly synthesizing constrained trajectories and controllers and verifying robustness to disturbances.NMPC addresses synthesis, while reachability analysis verifies closed-loop behavior.
  • Motivation: High-dimensional NMPC and nonlinear reachability are difficult to scale, while data-driven reachability can provide inaccurate safety estimates.Existing GPU NMPC methods also largely omit inequality constraints and reachability under uncertainty.
  • Approach: GPU-SLS jointly optimizes a constrained nominal trajectory and robust tracking controller using ADMM, temporal structure, caching, and parallel associative scans.The framework computes reachable sets with SLS and uses resulting margins to tighten nominal trajectory constraints.
  • Approach: The method unifies real-time reachability, trajectory optimization, and disturbance-feedback synthesis through SLS with per-iteration complexity O(log N log2 nx+log2 nu).Its GPU LQR backend supports the inequality-constrained SQP subproblems used for nonlinear trajectory optimization.
  • Evaluation: GPU-SLS is evaluated on humanoid and quadruped systems, including problems with 2 × 10^5 decision variables and 8 × 10^4 constraints.The evaluation includes 75D humanoid control and 61D whole-body quadruped hardware validation.
  • Related work: The paper positions GPU-SLS against reachability and GPU-MPC methods that face scalability, conservatism, constraint-handling, or robustness limitations.The related work discusses HJ reachability, CBFs, data-driven methods, and GPU-accelerated MPC solvers.

B. Nonlinear Model Predictive Control (NMPC)

NMPC repeatedly solves a constrained nonlinear optimal-control problem over a finite horizon. SQP linearizes the dynamics and constraints, solves structured quadratic subproblems, and updates the nominal trajectory using their search directions.

  • Problem formulation: NMPC minimizes running and terminal costs over a horizon subject to nominal dynamics and state-input constraints.The problem is repeatedly solved from the current initial state.
  • Sequential quadratic programming: SQP linearizes nonlinear dynamics and constraints and forms a quadratic approximation of the Lagrangian around the nominal trajectory.The resulting problem has linear time-varying dynamics and quadratic-program structure.
  • Trajectory update: The LTV-QP solution provides the search direction δξ := (δx, δu) for updating the nominal state and control trajectories.The update uses step size α ∈(0, 1].
  • Trajectory update: NMPC therefore reduces nonlinear trajectory optimization to a sequence of constrained LTV quadratic programs whose solutions iteratively update nominal trajectories.This reduction is the interface used by the GPU QP solver in the broader framework.

C. Alternating Direction Method of Multipliers (ADMM)

ADMM reformulates constrained quadratic programs with split variables and alternates primal, projection, and dual updates. In GPU-SLS, this framework supports robust controller synthesis and disturbance-induced constraint tightening within SLS.

  • ADMM formulation: ADMM solves constrained QPs by splitting set constraints into a variable and indicator-function term, then using an augmented Lagrangian.The split formulation separates optimization over the primal variables from projection onto the convex constraint set.
  • ADMM updates: ADMM alternates primal minimization, constraint-set projection, and dual ascent updates.For QPs, the primal step is an unconstrained QP, the split-variable step is projection onto C, and the dual variable is updated by ascent.
  • System level synthesis: SLS optimizes causal disturbance-feedback controllers and represents closed-loop state responses through matrices capturing disturbance propagation.Distinct feedback matrices describe how each disturbance affects later controls and states under uncertain linearized dynamics.
  • Robust constraints: Constraint-tightening vectors quantify conservative margins from disturbance propagation and robustly enforce linearized state and input constraints.These margins are incorporated into tightened nominal trajectory optimization.
  • Alternating optimization: FastSLS alternates between constraint-tightened nominal trajectory optimization and robust-controller optimization.GPU-SLS uses this alternating structure to solve trajectory and controller updates together.

IV. METHOD

The method combines GPU-parallelized NMPC and SLS to accelerate nominal trajectory optimization, robust controller synthesis, and reachability analysis.

  • Method overview: GPU-SLS uses NMPC and SLS on the GPU to solve the paper’s robust control problem.The framework first accelerates structured LTV-QPs for nominal NMPC, then parallelizes robust SLS synthesis and reachability analysis.

A. GPU ADMM QP Solver

The GPU ADMM QP solver reformulates linearized inequality-constrained optimal control problems with split variables, enabling parallel constraint updates and GPU-parallel primal solves.

  • QP formulation: GPU-SLS solves structured LTV-QPs through a GPU-parallelized ADMM QP solver.The solver is used for the QPs arising in each SQP iteration.
  • Constraint splitting: The split variable z tracks the left-hand side of the linearized inequality constraints.Stacked constraint offsets f allow the inequalities to be written elementwise as z ≤ f.
  • ADMM updates: ADMM expresses the split constraints as G(δx, δu)=z with z projected onto the convex set C.The augmented Lagrangian uses consensus between the trajectory variables and the split variable.
  • ADMM updates: The primal ADMM update is an equality-constrained QP, while scaled dual variables support the alternating updates.The z-update is a projection and the dual ascent step consists of vector operations.
  • GPU parallelization: Parallel z- and λ-updates leave the structured primal solve as the dominant ADMM cost, motivating temporal parallelism via associative scans.The scan-based approach exploits the temporal structure of optimal control problems on GPUs.

1) Efficiently Solving (28) via Associative Scans:

The equality-constrained primal update is an LQR problem whose sequential Riccati recursion is replaced by reverse and forward parallel associative scans.

  • LQR structure: The primal update is an LQR problem whose conventional Riccati solution has sequential time-step dependencies.Its solution has the affine feedback form δu = Kδx + k.
  • Associative scans: Reverse parallel associative scans combine temporal operators through suffix reductions with logarithmic depth.The scan operates on associative elements and their combination rules.
  • Parallel recovery: The scan initialization defines terminal and interval quantities needed to recover Riccati terms and feedback components in parallel.The method recovers the Riccati terms through a reverse scan and then obtains nominal trajectory updates using a forward scan.
  • Parallel recovery: The resulting state and control updates are reconstructed from scan products and affine feedback relations.State updates use accumulated transition operators, while controls use Kiδxi + ki.
  • Complexity: The parallel solution costs O(log N log2 nx + log2 nu) time on parallel hardware.The bound combines O(log N) scan depth with parallel matrix-inversion costs and initialization inversions.

2) Caching to Accelerate Associative Scans:

The method accelerates GPU associative-scan optimization by caching terms that remain unchanged while the ADMM penalty parameter is fixed. Parallel scans compute robust SLS controllers and reduce per-iteration complexity.

  • Caching to Accelerate Associative Scans:: Caching invariant factorizations and intermediate quantities avoids repeated matrix inversions when the ADMM penalty parameter ρ remains fixed.Only augmented linear terms are recomputed between such iterations.
  • Caching to Accelerate Associative Scans:: The reverse parallel associative scan recomputes only the changing terms while reusing cached quantities needed to obtain feedback terms and nominal updates.The cached quantities include ˜Pi,j, ˜Ci,j, Υi,j, and Ψi,j.
  • Caching to Accelerate Associative Scans:: Caching reduces one ADMM iteration from O(log N log2 nx + log2 nu) to O(log N log nx + log nu).The reduced complexity applies because the cached procedures require no matrix inverses.
  • Caching to Accelerate Associative Scans:: Parallel associative scans independently process disturbance responses to recover the Riccati terms and feedback gains required for robust SLS control.The j-th disturbance indexes the corresponding Riccati variables and responses.
  • Caching to Accelerate Associative Scans:: The robust control policy is calculated in O(log N log2 nx + log2 nu) time on parallel hardware.The scan-based procedure obtains the solution to the robust SLS problem.

C. Real-Time Iteration

The real-time solver uses a single linearization and update per control step, combining RTI with GPU-accelerated constrained optimization. Experiments show strong long-horizon scaling and faster solves than CPU and GPU baselines.

  • C. Real-Time Iteration: RTI performs one SQP iteration per control step, trading linearization accuracy for computational speed and correcting errors through subsequent relinearization.The newly executed state is used for the next MPC update.
  • C. Real-Time Iteration: Each RTI update consists of one dynamics linearization, one controller update, and one tightened nominal trajectory update.Previous τ variables warm-start the controller and determine new constraint tightenings.
  • C. Real-Time Iteration: 99.8% and 98.9% lower solve times are achieved than OSQP and HPIPM, respectively, in long-horizon 10-link pendulum scenarios.The method also improves solve time by 71.8% over the GPU-accelerated primal-dual iLQR AL baseline.
  • C. Real-Time Iteration: 237.5× is the largest reported speedup over FastSLS as the prediction horizon increases.The comparison attributes the widening gap to logarithmic scaling for GPU-SLS versus cubic scaling for FastSLS.
  • C. Real-Time Iteration: N = 3000 horizons with more than 1.35 × 10^5 decision variables are solved within 73 milliseconds.The reported scaling covers state, control, constraint, and horizon dimensions.

B. SLS Benchmarks

GPU-SLS is evaluated across constrained, uncertain robotic systems, where it maintains safety while scaling to dense environments, high-dimensional robots, and real-time hardware control. The benchmarks compare robust control, solver speed, and trajectory optimization against classical MPC, DeepReach, FastSLS, and OSQP.

  • Safety benchmarks: GPU-SLS certified safety in all tested Dubins-car rollouts, whereas DeepReach crashed into the obstacle in 6 of 31 rollouts.The paper attributes the difference to GPU-SLS disturbance-feedback synthesis versus DeepReach’s offline value-function approximations.
  • Safety benchmarks: Classical MPC collided in 6/31 planar-quadrotor executions, while robust MPC avoided all obstacles across the rollouts.The robustness procedure accounted for approximately 3% of total computation time.
  • Solver benchmarks: 237.5× speedup was achieved by GPU-SLS over FastSLS at the largest tested prediction horizon.The paper relates this improvement to parallelized computation versus FastSLS’s cubic scaling with problem dimensions.
  • Scalability: GPU-SLS retained safety through a 20 m trajectory containing 30 obstacles while remaining within calculated reachable tubes under external disturbances.This benchmark tests large-scale trajectory optimization in a dense constraint field.
  • Hardware and solver benchmarks: 95% speedup was achieved over OSQP at the longest quadruped horizon, with GPU-SLS requiring fewer ADMM iterations.The reported mean/median iteration counts were 27/25 for GPU-SLS versus 107/50 for OSQP.
  • Hardware validation: The Unitree Go2 EDU quadruped navigated two obstacles collision-free at 50 Hz with a 16 ms average solve time.A separate robust reachability experiment kept the quadruped within its tubes while navigating around an obstacle.

APPENDIX

The appendix explains the parallel associative scan and its role in GPU acceleration, then describes FastSLS dual variables used to focus robust controller synthesis on active constraints. The scan achieves logarithmic complexity through an upsweep followed by a downsweep.

  • Parallel associative scan: Parallel associative scans use a balanced binary tree whose leaves preserve the ordered input sequence.The tree supports parallel reductions through associative combinations of child nodes.
  • Parallel associative scan: The upsweep combines child values bottom-up and has O(log n) complexity because each tree level can be processed in parallel.The operation relies on an associative operator.
  • Parallel associative scan: The downsweep propagates prefixes top-down using the partial reductions computed during the upsweep.The root prefix is initialized with the operator’s identity element, and prefixes are passed through the tree.
  • Parallel associative scan: Both scan phases together give parallel associative scans an overall O(log n) complexity on parallel hardware.The final leaf values combine with their associated prefixes to recover the desired elements.
  • FastSLS dual variables: FastSLS alternates tightened nominal-trajectory optimization with robust-policy optimization around that trajectory.The two stages are linked through dual information about currently tight constraints.
  • FastSLS dual variables: The dual variables τ identify constraints that are costly to violate under disturbances, guiding the controller to reduce disturbance effects there.They are calculated from the unscaled dual variable with a small nondifferentiability offset.

APPENDIX C DUBINS CAR

The appendices specify the Dubins-car and planar-quadrotor models, disturbance assumptions, obstacle constraints, and legged-robot environments used for evaluation. They also document the state and control dimensions of the quadruped and humanoid systems.

  • Dubins car: The Dubins car uses planar position and heading as its state, with angular velocity as the control input and constant forward speed.Its formulation includes bounded angular velocity and position-based obstacle constraints.
  • Dubins car: The Dubins-car disturbance scaling matrix is E = 2.5 · 10^-2I3.This is the constant disturbance model used for the canonical system.
  • Planar quadrotor: The planar quadrotor has a 6D state and 2 rotor-thrust inputs, with disturbances applied to translational velocities.The model specifies mass, gravity, arm length, inertia, and a diagonal disturbance matrix.
  • Legged environments: Legged simulations use MuJoCo rigid-body dynamics, explicit ground-reaction-force computation, and reference gait trajectories defining leg phases and foot placements.Obstacle constraints follow the same formulation described for the benchmark environments.
  • Humanoid experiment: The humanoid RTI experiment uses a 75D, 19-control system navigating two obstacles with obstacle inflation to account for physical footprint.The associated rollout visualizes robust tubes around the trajectory.

APPENDIX F HUMANOID RTI

The humanoid RTI appendix reports robust navigation between two obstacles and verifies that the rollout remains inside computed tubes. GPU-SLS computes robust policies at millisecond-scale speed across the experiment.

  • RTI performance: 22 ms average policy computation was achieved across 700 RTI MPC steps for the humanoid experiment.The experiment used a Unitree H1 humanoid navigating between two obstacles under a constant disturbance.
  • Robustness verification: The humanoid remained within computed robust tubes for all states in the displayed disturbed rollouts.The appendix presents these tubes as evidence of SLS robustness guarantees.
Loading 2604.07644v1…