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 and Analysis for Constrained Piecewise Affine Systems


F.J. Christophersen

no. 16807

The main theme of this work revolves around the efficient and systematic computation, analysis, and post-processing of closed-form, optimal, stabilizing, exact state-feedback controllers for fast sampled discrete-time piecewise affine (PWA) systems, where the cost function of the respective optimal control problem is composed of (piecewise) linear vector norms.

One way to obtain the closed-form solution to the underlying constrained finite time optimal control (CFTOC) problem is by solving a multi-parametric mixed-integer linear program (mp-MILP). This, however, is in general a computationally challenging task. Here a novel algorithm, which combines a dynamic programming strategy with a multi-parametric linear program solver and some basic polyhedral manipulation, is presented and compared to the aforementioned mp-MILP approach.

Similar ideas are extended to the case of constrained infinite time optimal control problems for the same general system class. The equivalence of the dynamic programming generated solution with the solution to the infinite time optimal control problem is shown. Furthermore, new convergence results of the dynamic programming strategy for general nonlinear systems and stability guarantees for the resulting, possibly discontinuous, closed-loop system are given. A computationally efficient algorithm solves the Bellman equation by utilizing a particular dynamic programming exploration strategy with a multi-parametric linear programming solver and basic polyhedral manipulation. Intermediate solutions of the dynamic programming strategy give stabilizing suboptimal controllers with guaranteed optimality bounds.

A commonly used method of ensuring a priori closed-loop stability and feasibility when using RHC, based on (piecewise) linear cost, is to provide the RHC problem with a linear vector norm based final penalty cost function which is a control Lyapunov function and the terminal target set to be positively invariant. For this purpose a simple finitely terminating algorithm for a class of PWA systems is presented, which builds on a decomposition procedure and a finite and bounded sequence of feasibility LPs with few constraints or, equivalently, simple algebraic tests.

Without extending or modifying the underlying optimization problem, in general stability and/or feasibility for all time of the closed-loop system is not guaranteed a priori. An algorithm is presented that analyzes the CFTOC solution of a PWA system a posteriori and extracts regions of the state space for which closed-loop stability and feasibility for all time can be guaranteed. The algorithm computes the maximal positively invariant set and stability region of a PWA system by combining reachability analysis with some basic polyhedral manipulation.

The on-line evaluation of the above mentioned closed-form state feedback control law requires the determination of the state space region in which the measured state lies. The rate at which this point location problem can be solved determines the maximum sampling speed of the system allowed. A novel and computationally efficient algorithm based on bounding boxes and an n-dimensional interval tree is presented that significantly improves this point location search for piecewise state feedback control laws defined over a large number of possibly overlapping polyhedra.


Type of Publication:

(03)Ph.D. Thesis

M. Morari

File Download:

Request a copy of this publication.
(Uses JavaScript)
  author       = {F. J. Christophersen},
  title	       = {{Optimal Control and Analysis for Constrained Piecewise Affine Systems}},
  school       = {ETH Zurich},
  year	       = {2006},
  address      = {Zurich, Switzerland},
  month	       = aug,
  type	       = {{Dr. sc. ETH Zurich thesis}},
Permanent link