Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a novel parallel solver for scenario-tree model predictive control (MPC) that utilizes rake-compress tree contraction to optimize the computational efficiency of Riccati recursions. By transforming the problem into a series of independent local control condensations, the approach achieves linear arithmetic work and storage, with logarithmic span, regardless of the tree's height or structure. The method not only maintains the integrity of the Riccati coefficients but also allows for dual regularization, significantly enhancing the performance of MPC in complex scenarios.
Achieving linear time complexity in scenario-tree MPC could revolutionize real-time decision-making in dynamic environments.
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.