Parallel Dynamic Programming for Conic Linear Quadratic Control

📄 arXiv: 2606.24632v1 📥 PDF

作者: Luyao Zhang, Gabriel Bravo-Palacios, Brian Plancher, Sergio Grammatico

分类: math.OC, cs.RO

发布日期: 2026-06-23

备注: This paper was accepted for presentation at the IFAC World Congress 2026 (IFAC WC 2026)

💡 一句话要点

提出并行动态规划方法以解决锥形线性二次控制问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 线性二次控制 并行计算 动态规划 模型预测控制 交替方向乘子法 实时系统 优化算法

📋 核心要点

  1. 现有的线性二次控制方法由于其串行特性，无法充分利用现代多核CPU的并行计算能力，限制了实时应用的扩展性。
  2. 本文提出了一种基于时间并行的ADMM方法，通过将LQ问题重构并沿时间轴分割，从而实现了高效的并行计算。
  3. 在两个实际应用的数值基准测试中，所提方法相比现有方法实现了高达5倍的速度提升，展示了其优越性。

📝 摘要（中文）

线性二次（LQ）控制问题是线性控制理论和模型预测控制（MPC）的核心。尽管现有方法性能优越，但其固有的串行特性限制了实时可扩展性。为了解决这一挑战，本文提出了一种基于时间并行的策略，通过交替方向乘子法（ADMM）解决计算密集型的锥形最优控制问题。具体而言，本文将ADMM的内层原始更新形式化为LQ问题，并沿时间轴对重构问题进行分割，从而利用动态规划推导出一种变体的Riccati递归，以并行方式解决每个子问题。数值基准测试表明，与现有相关方法相比，在多核CPU硬件上实现了高达5倍的加速。

🔬 方法详解

问题定义：本文旨在解决线性二次控制问题的计算效率低下，现有方法由于串行计算限制了实时性能，无法充分利用多核CPU的优势。

核心思路：通过将ADMM的内层原始更新视为LQ问题，并沿时间轴对其进行分割，利用动态规划的思想实现并行计算，从而提高计算效率。

技术框架：整体方法分为几个主要模块：首先，重构LQ问题；其次，应用ADMM进行优化；最后，利用动态规划解决每个子问题，确保并行处理。

关键创新：本文的主要创新在于将ADMM与动态规划结合，提出了一种新的Riccati递归变体，使得每个子问题能够独立并行解决，这与传统的串行方法形成鲜明对比。

关键设计：在设计过程中，关键参数包括时间分割的粒度、ADMM的收敛性设置等，确保在并行计算中保持高效性和准确性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

在数值基准测试中，所提出的方法在两个实际应用场景中相比于现有相关方法实现了高达5倍的速度提升，充分展示了其在多核CPU硬件上的高效性和优越性。

🎯 应用场景

该研究的潜在应用领域包括自动驾驶、机器人控制和工业自动化等实时系统，能够显著提升控制算法的响应速度和处理能力，具有重要的实际价值和广泛的应用前景。

📄 摘要（原文）

Linear Quadratic (LQ) control problems are at the heart of linear control theory and Model Predictive Control (MPC). While performant, standard approaches to solving such problems are inherently serial, limiting real-time scalability despite the parallel computing power available on modern multi-core CPUs. Contributing to addressing this challenge and motivated by ``divide and conquer'' strategies, we present a parallel-in-time approach that solves computationally demanding conic optimal control problems through the use of the alternating direction method of multipliers (ADMM). In particular, we formulate the inner primal update of ADMM as an LQ problem and split the reformulated problem along the time horizon. This enables us to derive a variant of the Riccati recursion using dynamic programming to solve each subproblem in parallel. Numerical benchmarks on two real-world applications demonstrate as much as a 5x speedup compared to existing related approaches on multi-core CPU hardware.