Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Optimal Control of Piecewise Affine Systems -- a Multi-parametric Approach


M. Baotic


This thesis addresses the problem of constrained optimal control of discrete-time linear hybrid systems. In their most general form hybrid systems are characterized by the interaction of continuous-valued components (governed by differential or difference equations) and logic rules. Among the variety of equivalent descriptions of discrete-time hybrid systems reported in the literature we focus on the class of constrained piecewise affine (PWA) systems. Discrete-time PWA models can describe a large number of processes. Moreover, they can approximate nonlinear discrete-time dynamics via multiple linearizations at different operating points. Even though 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. The aim of this thesis is to further advance systematic procedures and develop algorithmic implementations that give the exact solution to the optimal control problems. A recurring theme in the thesis is the construction of efficient algorithms for solving various instances of optimal control problems. An instrumental tool in the development of such algorithms is the concept of multi-parametric programming, where a quadratic (or linear) optimization problem is solved off-line for a range of parameters. Specifically, an efficient implementation of a general multi-parametric quadratic program is described together with the in-depth analysis of the properties of the solution. The optimal control problem of a constrained linear discrete-time system can now be formulated as a multi-parametric quadratic program by treating the state vector as a parameter. The optimal solution is a piecewise affine state-feedback control law that is defined over a polyhedral partition of the feasible state-space. This allows users to carry out most of the time-consuming/complex computation off-line, while on-line implementation (control action computation) reduces to a simple set-membership test. By exploiting the properties of the value function and the optimal control law, new algorithms are developed that avoid storing the polyhedral regions. The new algorithms significantly reduce the on-line storage demands and computational complexity during evaluation of the PWA feedback control law. Next, the finite time optimal control problem for constrained discrete-time linear hybrid systems based on quadratic or linear performance criteria is tackled. Basic theoretical results on the structure of the optimal state-feedback solution and of the value function are given. An algorithm for construction of the solution -- a piecewise affine state-feedback control law defined over possibly non-convex regions -- combines multi-parametric programming, dynamic programming and basic polyhedral manipulation. Similar ideas are extended to the infinite time optimal control problems with linear performance index. A novel algorithm solves the Hamilton-Jacobi-Bellman equation by using the multi-parametric linear programming solver in a dynamic programming fashion. The resulting solution when applied in a receding horizon fashion guarantees stability of the closed-loop system. The important issue of stability guarantees is also addressed with the introduction of sub-optimal control strategies that generate solutions of lower complexity. Most of the developed algorithms were tested in two real-life automotive applications: electronic throttle control and adaptive cruise control. The electronic throttle is used in automotive applications to control the inflow of air to the vehicle engine by positioning a throttle plate. The nonlinearities present in the throttle body make the control of the plate position a challenging task. The electronic throttle is firstly modelled as a PWA system and then the control strategies developed in this thesis are applied to it. In a multi-object adaptive cruise control problem the optimal acceleration of the car is to be found respecting traffic rules, safety distances and driver intentions. The hybrid nature of the problem arises from the multiple objectives that introduce integer variables. Finally, the MPT toolbox is presented. The MPT toolbox for MATLAB contains all of the algorithms presented in this thesis as well as a wide range of additional algorithms and tools developed by the academic community.


Type of Publication:

(03)Ph.D. Thesis

M. Morari

File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@PhDThesis { Xxx:2005:IFA_2235,
    author={M. Baotic},
    title={{Optimal Control of Piecewise Affine Systems -- a
	  Multi-parametric Approach}},
Permanent link