Optimal control and analysis for constrained piecewise affine systems

Abstract

One of the most important and challenging problems in control is the derivation of systematic tools for the computation of controllers for general constrained nonlinear or hybrid systems (combining continuous-valued dynamics with logic rules) that can guarantee (among others) closed-loop stability, feasibility, and optimality. The most successful modern control strategy both in theory and in practice for this class of systems is undoubtedly Receding Horizon Control (RHC), often also interchangeably called Model (Based) Predictive Control (MPC). In this thesis the focus lies on the class of constrained discrete-time piecewise affine (PWA) systems,which is equivalent to a variety of other hybrid system modeling frameworks reported in the literature. PWA systems are obtained by partitioning the extended state-input space into regions and associating with each region a different affine state update equation. This paradigm is a powerful modeling tool that can capture general nonlinearities (e.g. by local approximation), constraints, saturations, switches, discrete inputs and states, and other hybrid modeling phenomena in dynamical systems. Although PWA systems are a subclass of general nonlinear systems, most of the control theory developed for nonlinear control does not apply, due to commonly made continuity and smoothness requirements. By utilizing multi-parametric programming, the RHC problem for PWA systems can be solved off-line in order to obtain a closed-form optimal controller solution. Once the closed-form solution is computed, the resulting controller can be implemented as a simple lookup table. Thus the on-line computational effort is reduced to a simple evaluation of the lookup table at the current measured state and enables the control of complex fast sampled systems in the range of milli- or microseconds. 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 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.<br/><br/> Eine der wichtigsten und herausfordernsten Aufgabenstellung der Regelungstechnik ist der Entwurf systematischer Werkzeuge zur Synthese von Reglern für allgemeine nichtlineare und Hybride Systeme mit Beschränkungen auf der Zustands und Eingangsvariable des Systems. Optimalität, Stabilität und die Einhaltung von Beschränkungen sind dabei nur einige der Anforderungen an den geschlossenen Regelkreis. Die erfolgreichste, moderne Regelungsmethode für diese Systemklassen in Theorie und Praxis ist die Modellprädiktive Regelung (engl.: Model (Based) Predictive Control, MPC), auch bekannt unter dem Namen Receding Horizon Control (RHC). Der Fokus dieser Dissertation liegt auf der Klasse der beschränkten, zeitdiskreten, abschnittsweise definierten Systeme (engl.: piecewise affine systems, PWA systems). Diese Klasse ist zu einer Vielzahl anderer, in der Literatur erwähnten, Darstellungsformen von Hybriden Systemen äquivalent und zeichnet sich durch ihr äusserst flexibles Systemmodell aus, welches allgemeine Nichtlinearitäten (z.B. durch lokale Approximation), Begrenzungen, Sättigungskennlinien, Schaltungen, diskretwertige Eingänge und Zustände und weitere hybride Modellierungsphänomene dynamischer Systeme darstellen kann. Die Dynamik eines PWA Systems wird durch eine affine Differenzengleichung über einer Partition des erweiterten Zustands-/Eingangsraum definiert, welche die Zustands-Updategleichung beschreibt. Obwohl PWA Systeme damit eine Unterklasse allgemeiner nichtlinearer Systeme darstellen, ist ein Grossteil der Regelungtheorie für nichtlineare Regelsysteme für die Klasse der PWA Systeme nicht anwendbar, da im Allgemeinen Stetigkeits- und Glätteannahmen nicht erfüllt sind. Mittels multi-parametrischer Programmierung kann das RHC Problem für PWA Systeme offline zum Erhalt einer expliziten Reglerstruktur gelöst werden. Diese geschlossene, optimale Lösung ermöglicht eine einfache Implementierung des resultierenden Reglers mittels eines sogenannten Look-up Tables. Der online benötigte Aufwand zur Bestimmung einer optimalen Stellgrösse reduziert sich damit auf eine einfache Evaluierung eines Look-up Tables an dem momentan gemessenen Zustand. Dies ermöglicht die Regelung von komplexen, schnell abgetasteten Regelsystemen im Bereich von Milli- oder Mikrosekunden. Der Kern dieser Arbeit befasst sich mit der effizienten und systematischen Berechnung, Analyse und Nachbearbeitung (Postprocessing) eines optimalen, stabilisierenden, sowie exakten Zustandsrückfühungsreglers in geschlossener Form für schnell abgetastete zeitdiskrete PWA Systeme, wobei das Kostenfunktional des respektiven optimalen Regelungsproblems aus (abschnittsweise) linearen Vektornormen besteht. Eine Methode die geschlossene Lösungsform des zugrundeliegenden optimalen Regelungsproblems mit endlichem Zeithorizont und Beschränkungen zu berechnen, ist die direkte Lösung eines multi-parametrischen, gemischt-ganzzahligen linearen Programms (engl.: multi-parametric mixed-integer program, mp-MILP). Auf Grund des im Allgemeinen recht hohen Rechenaufwandes ist dies jedoch nur bedingt praktikabel. In dieser Arbeit wird ein neuartiger Algorithmus präsentiert, der dynamische Programmierung mit einem Lösungsalgorithmus für multiparametrische linear Programme sowie einfache polyhedrische Manipulationen verbindet, um das Regelungsproblem zu lösen. Die erhaltene Lösung wird mit denen der vorher erwähnten mp-MILP basierten Methode verglichen. Ähnliche Konzeptewerden für den Fall optimaler Regelungsproblememit unendlichem Zeithorizont und Beschränkungen für die gleiche Systemklasse erweitert. Die Äquivalenz zwischen der Lösung mittels dynamischer Programmierung und der Lösung des optimaler Regelungsproblems mit unendlichem Zeithorizont wird gezeigt. Darüber hinaus werden neue Konvergenzresultate der dynamischen Programmierungsmethode für allgemeine nichtlineare Systeme und Stabilitätsgarantien für das resultierende, möglicherweise diskontinuierliche, geschlossene System angegeben. Ein rechnerisch effizienter Algorithmus löst die Bellman Gleichung unter Verwendung einer speziellen dynamischen Programmierungsstrategie, welche durch Lösung multi-parametrischer linearer Programme und einfache polyhedrischer Manipulationen den Zustandsraum exploriert und die Lösung schrittweise aufbaut. Dabei stellen die Zwischenlösungen der dynamischen Programmierungsstrategie stabilisierende, suboptimale Lösungen mit garantierter Optimalitätsobergrenze dar. Eine häufig verwendete Methode um a priori Stabilität und Lösbarkeit des unter RHC (mit abschnittsweise linearen Kostenfunktional) geschlossenen Regelkreises zu garantieren, besteht darin, das RHC Problemum eine Beschränkung des Endzustandes sowie einen (abschnittsweise) linearen, vektornormbasierenden Kostenterm als Kontrol-Lyapunovfunktion zu erweitern, welcher den Zustand am Ende des Horizonts gewichtet. Eine Zerlegungsprozedur und eine endliche und beschränkte Sequenz von einfachen linearen Programmen, oder äquivalent, einfache algebraische Tests bilden die Basis eines endlich terminierenden Algorithmus zur Berechnung dieses Kostenterms und der Beschränkung des Endzustandes für eine Klasse von PWA Systemen. Ohne Erweiterung oder Modifizierung des Optimierungsproblems kann im allgemeinen keine a priori Aussage oder Garantie bzgl. der Stabilität und Lösbarkeit des mittels RHC geschlossenen Regelkreises gemacht werden. Ein Algorithmus, der die Lösung zum zugrundeliegenden optimalen Regelungsproblems mit endlichem Zeithorizont und Beschränkungen für PWA Systeme a posteriori analysiert und die grösste Region in Zustandsraum extrahiert, für die Stabilität und Lösbarkeit des geschlossenen Regelkreises garantiert werden kann, wird in dieser Arbeit ebenfalls präsesntiert. Hierfür wird eine Erreichbarkeitsanalyse mit einfacher polyhedrischer Manipulation verbunden. Die online Evaluation des oben genannten Zustandsrückführungsreglers in geschlossener Form benötigt die Bestimmung der Zustandsraumregion, in welcher der gemessene Zustand liegt. Die Geschwindigkeit, mit welcher diese Lokalisierungsbestimmung durchgeführt werden kann limitiert die Abtastrate des geregelten Systems. Ein neuer, effizienter Algorithmus, basierend auf Bounding Boxen und einem n-dimensionalen Intervall-Suchbaum, ist dargestellt, welcher die Lokalisierung des Messzustandes für abschnittsweise und über einer grossen Anzahl von möglicherweise überlappenden Polyhedra definierten Zustandsrückfühungsregler, signifikant verbessert.