提出并行树结构模型预测控制的新解法，大幅降低计算时间。
Rake-Compress Riccati Recursions for Parallel Scenario-Tree Model Predictive Control
- 用剃刀压缩法并行收缩树结构，突破传统算法高度依赖瓶颈。
- 在固定维数下实现线性算力与对数级跨度，不依赖树高或分支数。
- 支持无正则化和半正定正则化，适合大规模实时控制应用。
场景树模型预测控制（MPC）通过有根树表示未来信息，并在此树上优化非提前策略。求解此类非线性规划的数值方法通常通过一系列分叉的线性二次调节器（LQR）子问题计算搜索方向。标准树 Riccati 递推需要线性工作量，但存在与树高成比例的依赖链。本文提出一种代数精确的并行求解器，基于耙式压缩树收缩。在独立局部控制凝聚后，其两个操作分别作用于节点和边数据，表示条件二次函数。耙操作消除叶节点及其父边，将其约化贡献合并至父节点数据；压缩操作消除单子节点，用相同条件值组合方式将相邻两条边合并为一条，类似链式并行 Riccati 方法。二者协同将任意有根树收缩至根节点；反向收缩可恢复所有 Riccati 系数、状态、控制与乘子。给定可复用的拓扑计划，具有 $N$ 个节点且状态与控制维度固定的求解，具备 $O(N)$ 算术工作量与存储，$O("log N$) 跨度，独立于树高、平衡性与最大出度。该公式支持半正定对偶正则化（含无正则化情形），且精确线性尺寸提升覆盖标准场景 MPC 中每信息节点一个控制的约定。证明了收缩恒等式与 KKT 系统的等价性。三个 MIT 许可证的 JAX 包实现了双向收缩、对偶正则化 LQR 求解器，以及面向用户的原-对偶内点法求解器，用于树结构最优控制。
原文摘要 · Abstract (English)
Scenario-tree model predictive control (MPC) represents future information by a rooted tree and optimizes a nonanticipative policy over that tree. Numerical methods for solving the resulting nonlinear program typically compute their search directions through a sequence of branched linear-quadratic regulator (LQR) subproblems. The standard tree Riccati recursion requires linear work but has a dependency chain proportional to tree height. We present an algebraically exact parallel solver based on rake-compress tree contraction. After independent local control condensation, its two operations act on node and edge data that represent conditional quadratic functions. A rake eliminates a leaf and its parent edge, adding their reduced contribution to the parent-node data. A compress eliminates a unary node and replaces its two adjacent edges by one edge, using the same conditional-value composition as parallel Riccati methods on a chain. Together they contract an arbitrary rooted tree to its root; reversing the contraction recovers every Riccati coefficient, state, control, and multiplier. Given a reusable topology plan, a solve with $N$ nodes and fixed state and control dimensions has $O(N)$ arithmetic work and storage and $O(\log N)$ span, independently of tree height, balance, and maximum out-degree. The formulation allows positive-semidefinite dual regularization, including the unregularized case, and an exact linear-size lifting covers the standard scenario-MPC convention of one control per information node. We prove the contraction identities and equivalence to the Karush-Kuhn-Tucker (KKT) system. Three MIT-licensed JAX packages implement the bidirectional contraction, the dual-regularized LQR solver, and a user-facing primal-dual interior-point solver for tree-structured optimal control.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。