Parallel Branch Model Predictive Control on GPUs

arXiv:2506.13624 · eess.SY, cs.RO, cs.SY · Submitted 2025-06-16 · Read on arXiv

Listen

Radio episode about this paper

Transcript

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

Rosa: We're looking at the paper: "Parallel Branch Model Predictive Control on GPUs".

Paper summary: Rosa: The paper we're looking at, "Parallel Branch Model Predictive Control on GPUs," shows how to build a GPU-based solver for trajectory planning problems using branch Model Predictive Control.

Dev: They are building on iterative LQR methods and they use an augmented Lagrangian method to handle general stage-wise constraints in this design.

Rosa: The main idea is that when you deal with uncertainty, instead of just picking one path, you construct a tree of possibilities where every branch represents a different scenario.

Dev: That specific branching structure means the solver can avoid those overly cautious plans that just crawl because they can't guarantee anything about the outcome.

Rosa: They also introduce two tailored inner LQR solvers designed to exploit the tree-sparse structure, which lets you choose different levels of parallelism based on how big your problem is.

Dev: Specifically, they have a solver called SLQR that handles nonanticipativity constraints exactly and runs on both CPU and GPU hardware.

Rosa: Then there's STLQR which supports those exact nonanticipativity constraints plus time steps, also running on both CPU and GPU devices.

Dev: So the key claim they make is that compared to a high-performance CPU-based solver, their approach achieves superior performance when dealing with large scale problems.

Rosa: We saw results on the unicycle benchmark where the average iteration time was reduced from three point eighty milliseconds down to one point eighty-seven milliseconds.

Dev: And on the quad pendulum benchmark, they showed a reduction in solve time from eight point seven five milliseconds down to four point one seven milliseconds.

Rosa: This performance drop is what shows the practical benefit of using this GPU approach for trajectory planning.

Dev: It really points toward this being a viable way to get planning done fast enough for real-time control loops when you're dealing with complex constraints and uncertainty.

Rosa: The paper also discusses how they handle those stage-wise constraints using an augmented Lagrangian method where the inner loop penalizes them with a Powell-Hestenes-Rockafellar function.

Dev: That inner loop is then paired with an outer loop that adapts the dual variables and penalty weight based on how much those constraints are being violated.

Rosa: This whole setup enables straightforward warm-starting, which should make it easier to restart calculations when things change in real time.

Conclusion: Rosa: We've been looking at "Parallel Branch Model Predictive Control on GPUs" from the authors of that paper and what it actually means for planning in uncertain worlds.

Dev: Basically, they're showing how to use a GPU to solve trajectory planning problems using branch Model Predictive Control.

Dev: The numbers we saw were pretty solid, like solving a unicycle problem in about one thousand iterations instead of three thousand for example.

Dev: It points toward this being a viable way to get planning done fast enough for real-time control loops when you're dealing with complex constraints and uncertainty.

Dev: That choice between those two solvers is important because it lets the user tailor the solver to their specific hardware setup.

Rosa: So what this means for us right now is that we can start thinking about deploying more complex autonomy in environments where things are unpredictable, because the planning side of things gets much faster.

Dev: But we still have to look at how that solver handles those tough real-world failures and what happens when the world misbehaves outside of a perfect simulation.

Luyao Zhang, Chenghuai Lin, Sergio Grammatico

Delft Center for Systems and Control, TU Delft

eess.SY, cs.RO, cs.SY

Submitted: 2025-06-16

Updated: 2026-11-16

Comments: 11 pages, 8 figures

Code: https://github.com/Luyao787/ilqrx

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 83/100

The gist: Parallel Branch Model Predictive Control on GPUs presents a GPU-based solver for trajectory planning problems using branch Model Predictive Control.

Key concepts

Model Predictive Control (MPC)
MPC is a planning method that solves optimal control problems repeatedly over a future time horizon. It determines the best sequence of actions by constantly re-planning based on the current state, making it excellent for dynamic systems.
Branch Model Predictive Control (BMPC)
BMPC models uncertainty using a discrete distribution by creating a tree of trajectories, where each branch represents a different possible future scenario. This allows the planner to avoid overly cautious plans that traditional methods might produce when facing uncertainty.
Tree LQR Solvers
These are parallel solvers used within the BMPC framework to find optimal control sequences. The paper introduces two versions, SLQR and STLQR, designed with different levels of parallelism to suit various problem sizes and available computational resources on GPUs.

Terminology

Summary

Parallel Branch Model Predictive Control on GPUs presents a GPU-based solver for trajectory planning problems using branch Model Predictive Control. p. 0

Where the paper says it

JOURNAL OF LATEX CLASS FILES, VOL. 8, AUGUST 2021 1 Parallel Branch Model Predictive Control on GPUs Luyao Zhang, Chenghuai Lin, Sergio Grammatico Abstract—We present a GPU-based solver for trajectory planning problems using branch Model Predictive Control.

This design enables straightforward warm-starting. p. 0
Where the paper says it

Building on iterative LQR methods, we adopt a multiple-shooting formulation for the system dynamics and use an augmented Lagrangian method to handle general stage-wise constraints. This design enables straightforward warm-starting.

The numerical results demonstrate that, compared to a high-performance CPU-based solver, our approach achieves superior performance on large-scale problems. p. 0
Where the paper says it

The solvers offer different levels of parallelism, making them appropriate for different tree sizes. The numerical results demonstrate that, compared to a high-performance CPU-based solver, our approach achieves superior performance on large-scale problems.

Model Predictive Control and Uncertainty Modeling

Model Predictive Control (MPC) is a state-of-the-art planning method that numerically solves optimal control problems in a receding horizon fashion. Nominal MPC does not explicitly account for uncertainty, often resulting in undesirable planning performance. p. 0

Where the paper says it

In recent years, this approach has achieved significant success in its application to mobile robots [1], [2], [3], [4]. Nominal MPC does not explicitly account for uncertainty, often resulting in undesirable planning performance.

Branch Model Predictive Control (BMPC) has been proposed to model uncertainty via a discrete distribution. p. 0
Where the paper says it

If the automated vehicle misinterprets the surrounding vehicle’s driving intention, it may need to make abrupt braking maneuvers to ensure safety, resulting in an uncomfortable ride. By modeling uncertainty via a discrete distribution, Branch Model Predictive Control (BMPC) [5], also known as contingency MPC in [6], [7], scenario tree MPC in [8], or multistage MPC in [9], [10], has been proposed in recent years.

Specifically, BMPC plans a trajectory tree with multiple branches, each corresponding to a different uncertainty realization. p. 0
Where the paper says it

In the context of automated driving, an advantage of BMPC planners is their ability to leverage multi-modal predictions generated by motion prediction modules. Specifically, BMPC plans a trajectory tree with multiple branches, each corresponding to a different uncertainty realization.

In contrast to traditional robust motion planners which attempt to generate a single motion plan that accommodates all predicted scenarios, BMPC can avoid overly conservative motion plans. p. 0
Where the paper says it

In contrast, traditional robust motion planners [11], [12] attempt to generate a single motion plan that accommodates all predicted scenarios. Consequently, BMPC can avoid overly conservative motion plans.

Parallel Tree LQR Solvers

The paper introduces two parallel tree LQR solvers that achieve different levels of parallelism, allowing users to choose based on the problem size and available computational resources. These solvers are summarized in Table I. p. 1

Where the paper says it

Unlike [14], our approach satisfies the nonanticipativity constraints induced by the tree structure exactly. Our contributions are summarized as follows: 1) Inspired by the LQR solver in [25], we develop two parallel tree LQR solvers that achieve different levels of parallelism, as summarized in Table I, allowing users to choose based on the problem size and available computational resources.

The SLQR solver is classified as NT MPC Exact SC CPU/GPU. p. 1
Where the paper says it

NC: NONANTICIPATIVITY CONSTRAINT. SC: SCENARIO Solver Problem Type NC handling Parallelization Devices SLQR (Ours) NT MPC Exact SC CPU/GPU STLQR (Ours) NT MPC Exact SC + Time CPU/GPU CT [14] NT MPC Inexact SC CPU HPIPM [9] LT MPC Exact × CPU TREEQP [10] LT MPC Exact SC CPU NAMA [15] LT MPC Exact SC GPU Building on prior work, we introduce a parallel BMPC solver that supports nonlinear dynamics and general stage-wise constraints.

The STLQR solver supports NT MPC Exact SC + Time CPU/GPU. p. 1
Where the paper says it

NC: NONANTICIPATIVITY CONSTRAINT. SC: SCENARIO Solver Problem Type NC handling Parallelization Devices SLQR (Ours) NT MPC Exact SC CPU/GPU STLQR (Ours) NT MPC Exact SC + Time CPU/GPU CT [14] NT MPC Inexact SC CPU HPIPM [9] LT MPC Exact × CPU TREEQP [10] LT MPC Exact SC CPU NAMA [15] LT MPC Exact SC GPU Building on prior work, we introduce a parallel BMPC solver that supports nonlinear dynamics and general stage-wise constraints.

Constraint Handling via Augmented Lagrangian Method

The authors introduce a multiple-shooting iterative tree LQR solver for nonlinear BMPC problems and incorporate constraint handling using an augmented Lagrangian method. The inner loop penalizes stage-wise constraints using the Powell-Hestenes-Rockafellar (PHR) function. p. 3

Where the paper says it

Next, we describe the nested loops in our AL-based method. Inner Loop In the inner loop, stage-wise constraints are penalized using the Powell-Hestenes-Rockafellar (PHR) function [33]: La(x,u; ye , ρ) = X i∈L ℓf,i (xi) + ρ 2 max 0, gi(xi) + ye,i ρ 2 + X i∈N \L ℓi (xi , ui) + ρ 2 max 0, gi(xi , ui) + ye,i ρ 2 , (17) where ye,i denotes the estimated Lagrange multiplier, and ρ > 0 is the penalty weight.

The outer loop adapts the dual variables and penalty weight based on the constraint violation c. p. 4
Where the paper says it

Outer Loop In the outer loop, we adopt the BCL rule proposed in [41] and implemented in [42]. This heuristic adaptively updates the dual variables ye and the penalty weight ρ based on the constraint violation c := ∥max (g(x,u), −ye/ρ)∥∞.

Numerical Performance Evaluation

Numerical experiments evaluate the computational performance of SLQR and STLQR against other solvers like TRAJAX and MPX. For the unicycle benchmark, the average iteration time is reduced from 3. p. 5

Where the paper says it

Moreover, ILQRJAX achieves significantly lower per-iteration computation time than IPOPT. For the unicycle benchmark, the average iteration time is reduced from 3.

80 ms to 1.87 ms. The quad-pendulum benchmark shows a reduction in solve time from 8. p. 6
Where the paper says it

that our solver provides comparable convergence behavior while substantially reducing computational time per iteration. In contrast, TRAJAX struggles to solve the quad-pendulum planning problems due to its single-shooting formulation.

75 ms to 4.17 ms. The solver ILQRJAX achieves performance comparable to IPOPT in terms of iteration count while reducing per-iteration computation time. p. 5
Where the paper says it

Our solver ILQRJAX and IPOPT solve all test problems to the target tolerance, and ILQRJAX achieves performance comparable to IPOPT in terms of iteration count. Moreover, ILQRJAX achieves significantly lower per-iteration computation time than IPOPT.

Conclusion and Future Work

The tree LQR solver supports different levels of parallelism, enabling it to handle problems at different scales. One limitation is that the parallel scan–based solver has high GPU resource demands. p. 6

Where the paper says it

Our solver showcases exceptional performance on large-scale problems and can handle general stage-wise constraints in challenging trajectory planning tasks. One limitation of the current method is that the parallel scan–based solver has high GPU resource demands, which can hinder computational performance.

In the future, they plan to implement the method in CUDA C++ to fully harness the computational power of GPUs. p. 6
Where the paper says it

One limitation of the current method is that the parallel scan–based solver has high GPU resource demands, which can hinder computational performance. In the future, we plan to implement the method in CUDA C++ to fully harness the computational power of GPUs.

The authors also note that it may be beneficial to implement mixed-precision computation or develop tailored algorithms that improve numerical stability of FP32. p. 6
Where the paper says it

To further optimize GPU resource utilization, it may be beneficial to implement the parallel algorithm directly in a kernel-based programming language such as CUDA C/C++. Finally, since most GPUs are optimized for FP32 arithmetic, it may be worthwhile to implement mixedprecision computation or to develop tailored algorithms that improve the numerical stability of FP32.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Parallel Branch Model Predictive Control on GPUs allows for solving trajectory planning problems using branch MPC on GPUs, achieving superior performance on large-scale problems compared to high-performance CPU-based solvers.

  2. The proposed solver can handle general stage-wise constraints by incorporating an augmented Lagrangian method, which enables straightforward warm-starting for MPC problems.

  3. The solver develops two tailored inner LQR solvers that exploit the tree-sparse structure, offering different levels of parallelism suitable for various tree sizes to optimize computational efficiency.

  4. The system can perform exact satisfaction of nonanticipativity constraints induced by the tree structure, unlike methods that use Lagrangian relaxation which increase iterations and make them unsuitable for real-time applications.

  5. The solver implements a parallel scan algorithm applied to the one-step CVFs derived from the LQR problem to determine an affine control law in O(1) parallel time, accelerating trajectory recovery.

  6. The solver can handle complex constrained nonlinear BMPC problems by employing a nested loop structure where the inner loop solves an iLQR-type method using a parallel linear rollout to compute optimal perturbations of the state and input trees.

  7. The outer loop utilizes a BCL rule that adaptively updates dual variables and penalty weights based on constraint violation, allowing the solver to maintain convergence while balancing cost reduction and constraint satisfaction.

  8. The solver can be used for trajectory planning problems involving dynamic models like a unicycle or quad-pendulum, enforcing input bounds and collision-avoidance constraints using an augmented Lagrangian merit function.

Abstract

We present a GPU-based solver for trajectory planning problems using branch model predictive control. Building on iterative LQR methods, we adopt a multiple-shooting formulation for the system dynamics and use an augmented Lagrangian method to handle general stage-wise constraints. This design enables straightforward warm-starting. The constraint-handling capability of our solver is validated on two challenging trajectory planning problems. In addition, we develop two tailored inner LQR solvers that exploit the tree-sparse structure. The solvers offer different levels of parallelism, making them appropriate for different tree sizes. The numerical results demonstrate that, compared to a high-performance CPU-based solver, our approach achieves superior performance on large-scale problems.

Related papers