Control synthesis
- Model Predictive Control (MPC)
- Online MPC vs. Offline MPC (Explicit Solution)
- Constrained Finite Time Optimal Control (CFTOC)
- Constrained Infinite Time Optimal Control (CITOC)
- Nominal vs. Robust Control
Even though discrete-time hybrid systems (and in particular Piecewise Affine (PWA) systems) are a special class of nonlinear systems most of the nonlinear system and control theory does not apply because it requires certain smoothness assumptions. For the same reason we also cannot simply use linear control theory in some approximate manner to design controllers for PWA systems. In the past most tools for the analysis and control of hybrid systems were ad hoc supported by extensive simulation.
Our aim is to further advance systematic procedures and develop efficient algorithmic implementations, see e.g. external page MPT, that give the exact solution to optimal control problems for the above mentioned constrained or hybrid systems.
Model Predictive Control (MPC)
Model predictive control, or MPC, is a control paradigm with a motley background. The underlying ideas for MPC originated already in the sixties as a natural application of optimal control theory.
The true birth of MPC took place in industry in the mid 70's to mid 80's where the MPC strategy became popular in the petro-chemical industry. During this period, there was a flood of new variants of MPC. Despite the vast number of variants, not much differed between the algorithms. Typically, they differed in the process model (impulse response, step response, state-space, etc.), disturbance (constant, decaying, altered white noise, etc.), and adaptation to time varying models. During the 90's, the theory of MPC has matured substantially, the main reason being the use of state-space models instead of input-output models.
MPC is an optimization based control law, and the performance measure J is almost always based on quadratic forms or linear norms. By using a quadratic or linear performance measure efficient optimization problems arise and mathematical analysis simplifies.
By defining the performance weight L(x,u) our underlying goal is to find the optimal control input that minimizes an infinite horizon performance measure subject to system dynamics (the prediction model) and constraints:
In the general constrained case, there does not exist any simple closed-form expression for the solution. Instead, the first step in MPC is to define a prediction horizon T and approximate the performance measure by using a finite horizon:
The solution to the CFTOC problem is a finite input sequence UT(x(t)). Due to the finite horizon the optimization problem is finite dimensional and easier to solve.
The second idea is to apply only the first control move of the obtained sequence UT(x(t)) to the plant and resolve a new finite horizon problem when we obtain new measurements of the current state x(t). Putting this conceptual idea of the so-called receding horizon policy into an algorithm yields the following basic MPC controller
1. Measure x(t) at sampling instance t.
2. Solve the finite optimization problem and obtain the optimal input sequence UT(x(t)) .
3. Apply the first element of the sequence u0 to the system.
4. Back to step 1.
The finite horizon approximation used in the MPC scheme introduces lack of guaranteed stability. To enforce closed-loop stability in an MPC framework, the above mentioned finite dimensional optimization problem usually is modified by choosing an appropriate terminal cost and constraint set.
As outlined above, MPC is usually performed by solving an optimization problem online in between two sampling instances and applying the first optimal control move to the plant. Due to the computational complexity of the optimization problem, MPC is limited to systems with long sampling periods, systems with only few state variables and rather short prediction horizons, although significant advances in the development of online solvers have been made in the last decade. Nevertheless, it can be beneficial to move computational burden from the online implementation to an offline stage.
However, the optimal control problem of a constrained PWA system can be formulated as a multi-parametric program by treating the current state x(t) as a parameter. Solving such a multi-parametric program yields an explicit solution, i.e. an optimal look-up table, for the MPC problem which inherits all the stability and performance properties of the original MPC problem. This optimal solution for the considered problem class is a piecewise affine state-feedback control law that is defined over a partition of the feasible state-space. Therefore, the time-consuming and complex computation can be carried out offline, while the online implementation (control action computation) reduces to a simple set-membership test and evaluation of a linear function. Depending on the type of performance measure used, either multi-parametric linear or quadratic programs have to be solved.
external page A. Bemporad, M. Morari, V. Dua, and E.N. Pistikopoulos, "The Explicit Solution of Model Predictive Control via Multiparametric Quadratic Programming". In Proceedings of the American Control Conference, vol. 2, pp. 872-876, Chicago, USA, June 2000.
D. Frick, A. Domahidi, and M. Morari, "Embedded Optimization for Mixed Logical Dynamical Systems". To appear in Computers and Chemical Engineering, 2014.
Constrained Finite Time Optimal Control (CFTOC)
The research results of our group include:
- CFTOC for discrete-time MLD systems: The optimization problem solved in each time instance is a mixed-integer linear or quadratic program. In the seminal paper [external page Bemporad and Morari 1999], the CFTOC for MLD systems is defined as a generic mixed-integer optimization problem. Recently, an efficient online solution method has been proposed in [Frick et.al. 2014].
- Explicit solution to CFTOC for constrained LTI systems: Solving multi-parametric linear or quadratic programs for constrained LTI systems gives an explicit solution to the CFTOC problem [external page Bemporad et.al. 2000a, external page Bemporad et.al. 2000b].
- CFTOC for hybrid systems as bilevel optimization problems: By writing PWA systems as optimizing processes, the CFTOC problem can be written as a bilevel optimization problem or, equivalently, as a mathematical program with equilibrium constraints [Hempel et.al. 2015].
- Explicit solution to CFTOC for hybrid systems: For MLD systems and cost functions based on linear norms, an explicit solution to the problem may be obtained by solving a multi-parametric mixed integer program (mp-MILP). Using an equivalent Piecewise Affine representation of the MLD model, computationally more efficient algorithm based on dynamic programming is developed, both for linear norms as well for costs based on norm-2 [Borrelli et.al. 2005].
- Minimum-time controller: The goal of the optimal control in this formulation is to drive the state vector of the system to the predefined target set in minimal number of steps. Due to the simple cost function which assumes only integer values, the explicit solution to this type of problems is generally less complex than the solution to the usual formulation of the CFTOC with norm-based costs. Computationally efficient algorithms based on multi-parametric programming are developed for constrained LTI and PWA systems [Grieder 2004].
- Interpolating controller: This is a suboptimal control strategy for constrained LTI systems, whose primary goal is a significant complexity reduction of the explicit solution on the expense of the control performance, while maintaining the stability of the closed-loop system [Grieder 2004]. The main idea is to keep only a part of the explicit solution solution, while the rest is computed on-line for a specific state-space vector by interpolating preserved control laws.
- Polynomial systems: We consider nonlinear dynamical systems whose nonlinearities are described by polynomial functions. Our goal is to extend the concept of the explicit solution for model predictive control to this class of systems. The crucial point in this direction is being able to analytically solve the equations that arise in the optimal control problem. In general, this is not possible.
However, using algebraic techniques, it is possible to partially pre-solve these equations, i.e. the nonlinear parametric optimal control problem. Then, an online algorithm uses this precomputed information to obtain the optimizer (control input) of the original optimization problem fast and efficiently in real time. The techniques used include, but are not limited to, Groebner bases, cylindrical algebraic decomposition (CAD) and generalized companion matrices [Fotiou et.al. 2005].
An extension of this framework to Piecewise Polynomial Hybrid Systems (PWP) is also possible, although the computational complexity grows accordingly.
Explicit CITOC solution of a PWA system
(Click picture for an animated version [1.2MB])
In contrast to the aforementioned constrained finite time optimal control the Constrained Infinite Time Optimal Control (CITOC) problem focuses on the optimization problem defined over an infinite prediction/control horizon. The main advantages of the infinite time solution, compared to the corresponding finite time solution, are the inherent guaranteed stability and feasibility as well as optimality of the closed-loop system.
We have studied the explicit solution of the CITOC problem for
- Constrained linear systems with quadratic stage cost (also called Constrained Linear Quadratic Regulator) [Grieder et.al. 2004]
- Constrained linear systems with a stage cost based on linear norms [Baotic et.al. 2004]
- PWA systems with a stage cost based on linear norms [Baotic et.al. 2004].
Nominal vs. Robust Control
Although a rich theory has been developed for the robust control of linear systems, relatively few results exist for the robust control of constrained linear systems and even less for hybrid systems. Therefore, this remains a hot topic of an ongoing research. A seminal early result, presented in [external page Kothare et.al. 1996], defines the problem of robust optimal control for constrained linear systems as an LMI problem.
Later results of our research group address the problem of robust optimal control with an emphasis on the explicit solution. The most relevant results are listed below:
- MIN-MAX: A classical approach to the design of a robust controller assumes the worst case scenario in which the controller is designed to be able to cope with all possible realizations of the disturbances and uncertainties. The optimality criterion for the controller is defined as a min-max optimization problem, where a maximal value of the performance cost (corresponding to an extreme realization of the disturbance or uncertainty) is minimized. An algorithm for the computation of min-max explicit controller for constrained linear systems with an optimality criterion based on linear norms is proposed in [external page Bemporad et.al. 2003].
- Invariant Set Based Strategies: The key concept of many algorithms is a maximal robust invariant set, i.e. a set of states for which infinite time feasibility is guaranteed for a specific type of disturbances/uncertainties. Algorithms for the simultaneous computation of the maximal robust invariant set and the explicit control law guaranteeing robust convergence, i.e. convergence under disturbances/uncertainties, to the robust invariant set for constrained linear and PWA systems have been developed in [external page Rakovic et.al. 2004, Grieder et.al. 2004].
- N-Step Controller: This sub-optimal robust control strategy aims at reducing the complexity and feasibility problems affecting the standard min-max problem formulation. The N-step controller relaxes the min-max formulation by enforcing the robust constraints only for the first time step while using the nominal system dynamics for the subsequent predictions. Inherently, the N-step controller guarantees robust constraints satisfaction, while the robust convergence has to be verified a posteriori, cf. [Grieder et.al. 2003].