TL;DR
This paper introduces a novel greedy algorithm for aggressively truncating controller coefficients while ensuring that performance constraints are still met. By leveraging Lyapunov certificates formulated as Linear Matrix Inequalities (LMIs), the method efficiently finds controllers with significantly reduced complexity, making them more practical for hardware implementation.
What Problem Does This Paper Address?
In control systems, especially those implemented on hardware with limited precision (e.g., fixed-point arithmetic), controller coefficients often need to be truncated or quantized. This process can degrade performance or even lead to instability. The challenge is to reduce the complexity of controller coefficients (e.g., the number of bits required to represent them) while guaranteeing that the closed-loop system still meets a predefined set of performance specifications, which are often relaxed versions of the nominal performance. Existing methods for this "controller coefficient truncation problem" can be computationally expensive, especially for high-dimensional controllers. This paper aims to provide an efficient and scalable method for this problem.
Methods
The core of the paper is a greedy algorithm that iteratively truncates controller coefficients. The algorithm works as follows:
- Initialization: Start with a nominal controller design that meets performance specifications.
- Coefficient Selection: Randomly permute the order of controller coefficients to be truncated.
- Interval Computation (
interv): For a selected coefficient, determine an interval of acceptable values that, if the coefficient is set to any value within this interval (while keeping others fixed), the closed-loop system will still satisfy the performance constraints. This is achieved using a Lyapunov performance certificate, typically formulated as a Linear Matrix Inequality (LMI). The LMI defines a convex set $\hat{C}$ that contains the set of acceptable controllers $C$. - Coefficient Truncation (
trunc): Within the computed interval, find a new value for the coefficient that minimizes its complexity measure (e.g., number of bits). - Iteration: Repeat steps 2-4 until no further coefficient can be truncated without violating performance constraints.
The paper also details how to compute the interval using LMIs and how to find the coefficient with minimum complexity within that interval, considering various complexity measures like the number of ones in the binary expansion or the number of bits in the fractional part.
Datasets
Not discussed in the paper. The paper uses randomly generated plant matrices and parameters for its numerical examples.
Key Insights and Ideas
- Lyapunov Certificates as Performance Guarantees: The paper elegantly demonstrates how Lyapunov functions, expressed as LMIs, can serve as powerful certificates to guarantee performance during coefficient truncation. This allows for a rigorous way to check if a truncated controller is still admissible.
- Greedy Truncation for Efficiency: Instead of global optimization, a greedy, sequential approach is employed. By randomly ordering the coefficients and iteratively truncating them, the algorithm efficiently explores the space of acceptable controllers and finds aggressively truncated designs.
- Scalability: The LMI-based approach and the greedy strategy make the method scalable to controllers with a large number of coefficients, which is a significant advantage over exhaustive search or other computationally intensive methods.
- Trade-off Management: The method explicitly manages the trade-off between controller complexity and performance degradation, allowing users to specify a tolerance ($\epsilon$) for performance loss.
Key Results
The paper presents numerical examples for two main scenarios:
- State-Feedback Controller (LQR Cost): For a 10th-order plant with 5 inputs, the algorithm achieved a complexity reduction from 2000 bits to as low as 75 bits (with 1.5 bits per coefficient) while maintaining performance within 15% of the nominal LQR cost.
- Dynamic Controller (Decay Rate): For a 5th-order plant with 2 inputs and 2 outputs, the algorithm reduced complexity from 1800 bits to 164 bits (approximately 1.5 bits per coefficient) with a performance degradation of about 3.6%.
These results show that the method can produce controllers with very aggressive coefficient truncation while meeting relaxed performance criteria.
Limitations and Future Work
- Local vs. Global Optimality: The greedy nature of the algorithm means it does not guarantee finding the globally optimal solution for minimum complexity. However, the authors note that the designs produced are "very likely not globally optimal, they appear to be quite good." Running the algorithm multiple times with different random permutations can help find better solutions.
- Nonlinearities: The current method is primarily for linear systems. While the authors mention that the Lyapunov-based methods can be extended to handle nonlinearities, this is not fully explored in the paper.
- Saturation and Signal Constraints: The paper acknowledges that it does not consider the effects of saturation or quantization of control signals themselves, which can introduce nonlinearities and affect stability. Future work could incorporate these aspects.
- Complexity Measures: The paper explores a few common complexity measures. Investigating other or more sophisticated complexity measures could be a direction for future research.
Summary updated