Parallel Branch Model Predictive Control on GPUs
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 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. 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 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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, 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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/ρ)∥∞.Where the paper says it
Where the paper says it
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 Moreover, ILQRJAX achieves significantly
lower per-iteration computation time than IPOPT. For the
unicycle benchmark, the average iteration time is reduced from
3. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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
-
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.
-
The proposed solver can handle general stage-wise constraints by incorporating an augmented Lagrangian method, which enables straightforward warm-starting for MPC problems.
-
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.
-
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.
-
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.
-
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.
-
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.
-
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
- Industrial Load Modeling and Optimization for Market-Based Interaction with Power Systems
- Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints
- Certified Set Convergence for Piecewise Affine Systems
- Symbolic Control for Stochastic Systems via Finite Parity Games
- Multiobjective optimization-based design and dispatch of islanded, hybrid microgrids for remote, off-grid communities in sub-Saharan Africa
- Physiology-informed layered sensing for intelligent human-exoskeleton interaction