Parallel and Proximal Constrained Linear-Quadratic Methods for Real-Time Nonlinear MPC

📄 arXiv: 2405.09197v2 📥 PDF

作者: Wilson Jallet, Ewen Dantec, Etienne Arlaud, Justin Carpentier, Nicolas Mansard

分类: cs.RO, math.OC

发布日期: 2024-05-15 (更新: 2024-06-03)

备注: new version after title change, camera-ready version sent to R:SS 2024

💡 一句话要点

提出并行近端约束线性二次方法，用于实时非线性模型预测控制

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

关键词: 非线性模型预测控制 线性二次调节器 并行算法 最优控制 机器人控制

📋 核心要点

  1. 大规模最优控制问题变量众多，传统方法难以在毫秒级时间内完成计算，限制了NMPC的应用。
  2. 论文提出一种并行LQR算法，通过重写LQR递归并利用块消元，实现决策变量的拆分和并行计算。
  3. 在ALIGATOR库中实现该算法，并在四足机器人模型预测控制中验证了其有效性，性能优于串行方法。

📝 摘要（中文）

非线性模型预测控制(NMPC)的最新进展强调了对数值算法进步的依赖，以便高效准确地解决大规模问题。典型全身最优控制(OC)问题通常包含数千个变量，因此利用数值问题的稀疏结构对于满足通常在几毫秒范围内的计算需求至关重要。解决线性二次调节器(LQR)问题是计算直接最优控制方法中牛顿或序列二次规划(SQP)步骤的基本组成部分。本文重点关注具有隐式系统动力学和对偶正则化的等式约束问题，这是高级内点或增广拉格朗日求解器的特征。本文提出了一种用于求解具有对偶正则化的LQR问题的并行算法。通过块消元重写LQR递归，首先提高了串行算法的效率，然后将其推广以处理参数化问题。这种扩展使我们能够拆分决策变量并同时解决多个子问题。该算法在非线性数值最优控制库ALIGATOR中实现，展示了优于先前串行公式的性能，并通过将其部署在真实四足机器人的模型预测控制中验证了其有效性。

🔬 方法详解

问题定义：论文旨在解决非线性模型预测控制（NMPC）中，大规模线性二次调节器（LQR）问题求解效率低下的问题。现有方法在处理具有大量变量和复杂约束的全身最优控制问题时，计算量巨大，难以满足实时性要求，尤其是在需要进行快速迭代的场景下，例如机器人运动控制。

核心思路：论文的核心思路是将LQR问题进行分解，利用并行计算来加速求解过程。通过对LQR递归公式进行重写，并采用块消元技术，将原问题分解为多个独立的子问题，这些子问题可以并行地进行求解。此外，论文还考虑了对偶正则化，这在高级内点法或增广拉格朗日方法中很常见。

技术框架：整体框架包括以下几个主要步骤：1) 对原始LQR问题进行建模，包括系统动力学、约束条件和目标函数；2) 对LQR递归公式进行重写，利用块消元技术将其分解为多个独立的子问题；3) 将这些子问题分配到不同的计算单元上进行并行求解；4) 将各个子问题的解进行合并，得到原始LQR问题的解。该框架基于ALIGATOR库实现。

关键创新：最重要的技术创新在于提出了针对LQR问题的并行求解算法。与传统的串行算法相比，该算法能够充分利用多核处理器的计算能力，显著缩短计算时间。此外，该算法还考虑了对偶正则化，使其能够适用于更广泛的NMPC问题。

关键设计：论文的关键设计包括：1) LQR递归公式的重写方式，确保分解后的子问题能够独立求解；2) 块消元技术的具体实现，用于高效地分解LQR问题；3) 并行计算任务的分配策略，以最大程度地利用计算资源；4) 对偶正则化项的选择，以保证算法的稳定性和收敛性。具体参数设置和损失函数细节未在摘要中详细说明。

📊 实验亮点

论文在ALIGATOR库中实现了所提出的并行LQR算法，并通过在真实四足机器人上进行模型预测控制实验验证了其有效性。实验结果表明，该算法的性能优于先前的串行算法，能够显著缩短计算时间，从而实现更快速、更稳定的机器人运动控制。具体的性能提升数据未在摘要中给出。

🎯 应用场景

该研究成果可广泛应用于机器人控制领域，尤其是在需要进行实时运动规划和控制的场景中，例如四足机器人、人形机器人、无人驾驶车辆等。通过提高NMPC的计算效率，可以实现更复杂、更灵活的运动控制策略，从而提升机器人的自主性和适应性。此外，该方法还可以应用于其他需要求解大规模LQR问题的领域，例如金融建模、电力系统优化等。

📄 摘要（原文）

Recent strides in nonlinear model predictive control (NMPC) underscore a dependence on numerical advancements to efficiently and accurately solve large-scale problems. Given the substantial number of variables characterizing typical whole-body optimal control (OC) problems - often numbering in the thousands - exploiting the sparse structure of the numerical problem becomes crucial to meet computational demands, typically in the range of a few milliseconds. Addressing the linear-quadratic regulator (LQR) problem is a fundamental building block for computing Newton or Sequential Quadratic Programming (SQP) steps in direct optimal control methods. This paper concentrates on equality-constrained problems featuring implicit system dynamics and dual regularization, a characteristic of advanced interiorpoint or augmented Lagrangian solvers. Here, we introduce a parallel algorithm for solving an LQR problem with dual regularization. Leveraging a rewriting of the LQR recursion through block elimination, we first enhanced the efficiency of the serial algorithm and then subsequently generalized it to handle parametric problems. This extension enables us to split decision variables and solve multiple subproblems concurrently. Our algorithm is implemented in our nonlinear numerical optimal control library ALIGATOR. It showcases improved performance over previous serial formulations and we validate its efficacy by deploying it in the model predictive control of a real quadruped robot.