PaperlayerView exact revision on arXiv

Source-linked AI summary

Embedded Online Optimization for Model Predictive Control at Megahertz Rates

Juan L. Jerez, Paul J. Goulart, Stefan Richter, George A. Constantinides, Eric C. Kerrigan, Manfred Morari

arXiv:1303.1090v1eess.SYmath.OC

TL;DR

MPC deployment on resource-constrained embedded platforms requires faster, cheaper, and more power-efficient optimization than general-purpose solvers provide. The paper proposes custom architectures for first-order methods, analyzes reliable reduced-precision fixed-point operation, and demonstrates satisfactory control performance beyond 1 MHz on FPGAs.

  • Problem

    Faster, cheaper, and more power-efficient solvers are needed to extend MPC to resource-constrained embedded platforms.

  • Method

    The paper develops custom computational architectures for first-order methods, with fast gradient methods for input-constrained MPC and ADMM for input- and state-constrained MPC, plus fixed-point reliability analyses.

  • Results

    FPGA implementations achieve satisfactory control performance at sampling rates beyond 1 MHz for several linear-quadratic MPC problems, including low-cost devices.

  • Takeaways & Limitations

    The proposed architectures support MPC implementation on low-cost embedded hardware at megahertz-rate sampling.

Abstract

from arXiv · show

Faster, cheaper, and more power efficient optimization solvers than those currently offered by general-purpose solutions are required for extending the use of model predictive control (MPC) to resource-constrained embedded platforms. We propose several custom computational architectures for different first-order optimization methods that can handle linear-quadratic MPC problems with input, input-rate, and soft state constraints. We provide analysis ensuring the reliable operation of the resulting controller under reduced precision fixed-point arithmetic. Implementation of the proposed architectures in FPGAs shows that satisfactory control performance at a sample rate beyond 1 MHz is achievable even on low-end devices, opening up new possibilities for the application of MPC on embedded systems.

I. INTRODUCTION

The paper develops custom first-order optimization architectures, fixed-point reliability analyses, and implementation rules to extend MPC on resource-constrained embedded platforms. FPGA demonstrations report controller sampling rates beyond 1 MHz for several linear-quadratic MPC problems.

  • Larger MPC problems make offline solution-map approaches impractical because of substantial memory requirements, necessitating online optimization.
  • First-order methods avoid solving a linear system at every iteration, while supporting fixed-point implementation, parallelization, and implementation-oriented analysis.
  • Architectures: The paper presents parameterized generators for custom architectures using Nesterov’s fast gradient method for input constraints and ADMM for state-constrained problems.
  • Analysis: The authors derive fixed-point analyses guaranteeing no overflow in fast gradient variables and analyze arithmetic errors for fast gradient and ADMM computations.
  • Analysis: The analysis determines minimum bit widths a priori for specified solution accuracy, enabling numerical stability and minimal resource usage.
  • Implementation: FPGA solver instances for several linear-quadratic MPC problems achieve controller sampling rates in excess of 1 MHz on low-cost embeddable hardware.

Outline

The paper develops an MPC formulation with mixed hard and soft constraints, then establishes exact-penalty conditions and assumptions for its analysis. It focuses on first-order methods and fixed-point implementation for embedded control.

  • MPC solves a constrained N-stage optimal control problem online for a discrete-time linear time-invariant system.
  • The formulation includes interval input constraints and free, hard-constrained, and soft-constrained state components.
  • The analysis assumes convex penalty structure and notes that a nonzero quadratic penalty term is needed for fixed-point numerical-stability results.
  • Soft constraints add a penalty on auxiliary slack variables, helping avoid infeasibility in the presence of disturbances.
  • If σ1 exceeds the largest relevant Lagrange multiplier and σ2 ≥ 0, the penalty reformulation has the same minimizers as the original hard-constrained problem.
  • The paper presents results in regulator form, while stating that they generalize readily to setpoint tracking problems.

III. FIRST-ORDER SOLUTION METHODS

The paper uses the fast gradient method for input-constrained MPC and ADMM for problems that also include state constraints. These methods are tailored to separable projections and parallel embedded execution, with certifiable convergence emphasized for the fast gradient approach.

  • The primal fast gradient method handles input-only constraints, whereas dual ADMM handles MPC with both state and input constraints.
  • After condensing future states, the fast gradient problem has decision vector z=(u0,...,uN−1) and feasible set K=U×...×U.
  • For box-constrained inputs, projections separate across stages and scalar intervals, requiring only multiplication and addition rather than division.
  • The fast gradient method provides a certifiable iteration bound guaranteeing specified suboptimality for all initial states in a bounded set.
  • The method is attractive for embedded MPC because implementation is relatively easy and performance-certification guarantees are available.
  • State constraints make fast-gradient projection as difficult as the original problem because the constraints are no longer separable in the inputs.

B. Input- and State-Constrained MPC Using ADMM

ADMM reformulates input- and state-constrained MPC by duplicating variables, separating equality and inequality operations, and enabling parallel hardware implementations. Its practical convergence can be strong, but parameter selection and convergence-rate guarantees remain less straightforward.

  • ADMM maintains state variables and slack variables explicitly, avoiding the condensed representation used for input-only problems.
  • The method duplicates decision variables so equality constraints and separable inequality projections can be handled in separate computational steps.
  • The regularizing term (ρ/2)∥y−z∥2 preserves the solution while removing the need for smoothness and strong convexity assumptions.
  • The penalty parameter ρ lacks universally accepted selection rules and is typically tuned during implementation.
  • ADMM’s core operations are an equality-constrained solve and a separable inequality-constrained solve, both optimized for parallel hardware.
  • The fixed KKT matrix can be inverted offline, leaving an online update using precomputed matrices and a single evaluation of M12b(x).
  • Soft-state projections reduce to independent truncated two-dimensional cone projections that can be parallelized without divisions.
  • ADMM is known to converge, while reported rates include 1/i for one error function versus 1/i2 for dual fast gradient, despite often faster practical behavior.

C. ADMM, Lagrange multipliers and soft constraints

The paper identifies multiplier scaling as a convergence issue for ADMM with soft constraints and proposes rescaling matching constraints to avoid excessively large optimal multipliers.

  • ADMM convergence can be very slow when optimal equality-constraint multipliers greatly exceed the primal iterates’ magnitude.
  • Large optimal multipliers require many iterations when primal differences remain small and ρ is near one.
  • Soft constraints are especially affected because their penalty parameter σ1 is typically very large, creating large multiplier magnitudes.
  • Rescaling the soft-constraint matching condition by 1/σ1 avoids difficulties caused by excessively large optimal multipliers.

IV. FIXED-POINT ASPECTS OF FIRST-ORDER SOLUTION METHODS

The section motivates fixed-point arithmetic for efficient first-order optimization hardware and analyzes the errors that reduced precision introduces. Under stated assumptions, the analysis supports reliable operation on fixed-point platforms.

  • Assumptions and guarantees: Arithmetic round-off errors in both algorithms have a converging upper bound, supporting reliable first-order optimization under fixed-point computation.The bounds are derived under the assumptions stated for the fixed-point implementation.
  • Motivation and arithmetic choice: Fixed-point arithmetic uses simple, fast digital circuitry, enabling power efficiency and parallelization in custom hardware.The paper targets FPGAs and other low-cost, low-power devices without floating-point support.
  • Motivation and arithmetic choice: 1 clock cycle versus 14 cycles: fixed-point addition is substantially faster than single-precision floating-point addition on a typical FPGA.The floating-point adder also uses one order of magnitude more resources for the same number of bits.
  • Error sources: Reduced-precision conversion can cause loss of convexity, changes in the optimal solution, infeasibility, overflow, and arithmetic errors.Overflow occurs when the integer field is too small; fixed-point addition and subtraction avoid round-off when overflow is absent and operand fraction widths match.
  • Assumptions and guarantees: The analyses choose fraction-bit widths large enough to preserve the relevant convexity and stability conditions for fast gradient and ADMM methods.For fast gradient, the assumptions keep the objective strongly convex; for ADMM, they keep the objective convex despite quantization error.

C. Overflow Errors

The overflow analysis determines integer-bit requirements by bounding static and dynamic quantities. Fast gradient admits analytical bounds, whereas ADMM requires simulation-based estimates and safety factors.

  • Integer-bit allocation: A priori upper bounds on iterates and intermediate variables determine the integer bits needed to avoid overflow.Static expressions can be sized from their maximum absolute values.
  • Fast gradient method: Fast gradient permits analytical bounds on the largest absolute intermediate elements and cumulative sums in matrix-vector products.Most bounds in Proposition 1 are reported as tight.
  • Fast gradient method: The initial fixed-point state set is selected so every exactly feasible state has a corresponding fixed-point representation.Normalization of the objective does not affect the maximum absolute values of the iterates.
  • ADMM: ADMM lacks a general analytical bound for Lagrange multiplier iterates and related dynamic expressions.The undetermined bounds are estimated through simulation with an added safety factor for integer-bit allocation.

D. Arithmetic Round-Off Errors

The paper compares fixed-point iterates with exact-arithmetic iterates and uses Lyapunov and spectral-stability arguments to bound arithmetic error. For fast gradient, the error dynamics are stable under the stated eigenvalue and momentum conditions.

  • Error formulation: Lyapunov-based control analysis derives bounds on solution error arising specifically from fixed-point arithmetic error.The exposition neglects quantization errors, which the paper states does not substantively alter the presented results.
  • Error formulation: The analysis defines fixed-point solution error as η_i = ˆz_i − z_i relative to the exact-arithmetic iterate.It seeks bounds whose limiting value remains finite.
  • Consequence: The resulting arithmetic errors remain bounded, a prerequisite for reliable first-order methods on fixed-point platforms.The paper presents this as a contribution beyond prior analyses that did not explicitly address arithmetic round-off errors.
  • Fast gradient stability: Matrix-vector multiplication introduces componentwise errors in [−n2^-b, 0], while projection can only reduce the error under the box constraint assumption.The error recurrence accounts for these per-iteration effects.
  • Fast gradient stability: The fast-gradient error dynamics are Schur stable when the normalized Hessian eigenvalues lie in (0, 1] and γ lies in [0, 1].Schur stability means the spectral radius of the recurrence matrix is less than one.

2) Stability of Arithmetic Errors in ADMM:

The ADMM analysis establishes stability of its arithmetic-error dynamics under the stated assumptions and derives bounds on accumulated round-off error. These bounds can guide the choice of fraction bits for accuracy specifications.

  • Error dynamics: ADMM arithmetic errors are bounded by the constraint set, while projection can further reduce them.The analysis also considers the unconstrained case to establish boundedness through eigenvalue analysis.
  • Error dynamics: The ADMM recurrence includes multiplication errors, projection-related error scalings, and multiplier-update errors.The projection scaling is componentwise in [0, 1], while the multiplication errors depend on b and n.
  • Stability result: The matrix N in the ADMM error dynamics is Schur stable for any ρ > 0.Its eigenvalues are either zero or ρλ_i( M̂_11), under the assumptions used in the proof.
  • Stability result: The ADMM proof establishes strict stability using positive-semidefinite structure, constraint nullspaces, system dynamics, and positive-definite input penalties.The contradiction argument rules out an eigenvalue at 1/ρ.
  • Error bound: The round-off accumulation bound converges because the associated matrix is Schur stable.The result provides an upper bound on accumulated error through iteration i and can be used to choose b a priori.

V. EMBEDDED HARDWARE ARCHITECTURES FOR FIRST-ORDER SOLUTION METHODS

The paper develops parameterized FPGA architectures for first-order MPC solvers, emphasizing parallel matrix-vector computation and predictable execution timing. The fast gradient design’s delay grows only logarithmically with problem size in the worst case when sufficient hardware resources are available.

  • Architectural rationale: First-order methods are well suited to custom parallel hardware because much of their computation is a readily parallelizable matrix-vector multiplication.The implementations modify fast gradient and ADMM algorithms to reduce sequential dependencies, with independent computation of individual vector components.
  • Parameterized generation: The architecture generator accepts numeric representation, bit width, parallelism, and arithmetic delays, then produces a VHDL digital architecture.This parameterization supports design-space choices tailored to resource and timing requirements.
  • Core datapaths: Dot products use parallel multipliers and an adder reduction tree, while projection compares each component with bounds and saturates or leaves it unchanged.FIFO storage and multiplexing support reuse of iterates and matrix-vector products across iterations.
  • Parallelization: Increasing parallelism replicates computation blocks and distributes odd and even vector components through serial-to-parallel shift registers.The parallelism level is controlled by P; P = 1 retains parallelism within each dot product while processing dot products sequentially.
  • Timing: The fast gradient iteration delay exhibits diminishing returns from parallelization, while problem-size effects are logarithmic in the worst case with enough resources.This behavior reflects sequential dependencies and Amdahl’s law.

B. Hardware Architecture for ADMM

The ADMM architecture reuses the fast gradient design’s computational patterns while adding support for larger, more general constrained problems. Its custom implementation trades resource use and delay for this broader capability and provides cycle-accurate completion guarantees.

  • Architecture: ADMM shares the fast gradient architecture’s computational patterns, with dense matrices determining the high-level implementation structure.Differences between the methods arise primarily from matrix sizes and the resulting iteration delay.
  • Constraint handling: The ADMM design supports warm-starting and projection for soft state constraints, including the set {|x − c| ≤ r + δ, δ ≥ 0}.The soft-constraint projection uses an explicit solution map.
  • Projection delay: ADMM’s search procedure requires only lA extra cycles compared with the standard hard-constrained projection.The projection block implements comparisons that control a multiplexer.
  • Hardware simplification: Restricting ρ to a power of two removes the need for hardware multipliers outside the matrix-vector multiplication block.Multiplication and division by powers of two are implemented by reinterpretation of signal arrays.
  • Design trade-off: ADMM trades higher resource requirements and longer delays for the capability to solve more general problems.The trade-off is especially relevant in hard real-time implementations where predictable completion must be preserved.
  • Real-time operation: The designs use a fixed iteration count rather than a numerical convergence test, enabling exact execution-cycle counts and cycle-accurate completion guarantees.This avoids convergence tests that can become computational bottlenecks in hard real-time contexts.

VI. NUMERICAL BENCHMARK STUDY

The benchmark evaluates fixed-point fast gradient and ADMM controllers on oscillating-mass MPC problems with input, input-rate, and soft state constraints. Fixed-point trajectories can match double-precision behavior, while FPGA implementations reach sampling rates beyond 1 MHz for the fast gradient case.

  • Benchmark setup: The oscillating-masses benchmark includes input-constrained MPC with 40 optimization variables and an extended problem with input-rate and soft state constraints.The constrained extension augments the state and yields 216 optimization variables solved via ADMM.
  • Closed-loop behavior: Fixed-point controller trajectories are indistinguishable from the double-precision optimal-controller trajectories in the reported closed-loop simulation.The reference simulation activates all constraints for a significant portion of the run.
  • Error analysis: Theoretical round-off error bounds enable practical predictions for a given bit width, and the error converges to a finite value.Error can increase with iteration count because round-off errors accumulate.
  • Fixed-point precision: 15 solver iterations and 16 fraction bits are suitable for the fast gradient method when relative error below 0.05% is desired.The reported criterion concerns the percentage difference in average closed-loop cost relative to a standard double-precision implementation.
  • Fixed-point precision: The ADMM problem is more vulnerable to reduced precision, although satisfactory control performance is achieved with a surprisingly small number of bits.More than 18 fraction bits or 40 ADMM iterations produces insignificant improvements in this case.
  • FPGA performance: Fast gradient FPGA implementations achieve sampling rates beyond 1 MHz on Virtex 6 devices with modest parallelization.Spartan 6 implementations reach about 700 kHz while consuming about 1 W.
Loading 1303.1090v1…