Numerical methods for optimal control of nonsmooth dynamical systems

Media type: E-Book

Title: Numerical methods for optimal control of nonsmooth dynamical systems

Contributor: Nurkanović, Armin [Verfasser]; Diehl, Moritz [Akademischer Betreuer]; Diehl, Moritz [Reviewer]; Brogliato, Bernard [Reviewer]

Corporation: Albert-Ludwigs-Universität Freiburg, Institut für Mikrosystemtechnik ; Albert-Ludwigs-Universität Freiburg, Fakultät für Angewandte Wissenschaften

imprint: Freiburg: Universität, 2024

Extent: Online-Ressource

Language: English

DOI: 10.6094/UNIFR/243755

Identifier:

Keywords: Optimale Kontrolle ; Numerische Mathematik ; Nichtglatte Mechanik ; Constrained optimization ; Nichtlineare modellprädiktive Regelung ; Hybrides System ; (local)doctoralThesis

Origination:

University thesis: Dissertation, Universität Freiburg, 2023

Footnote:

Description: Abstract: This thesis regards algorithmic, theoretical, and software aspects of numerically solving Optimal Control Problems (OCPs) subject to nonsmooth dynamical systems. When solving an optimal control problem, one selects the optimal control action while explicitly considering constraints and system dynamics. The ability to consider constraints and system dynamics increases the expressiveness in the controller design process. This expressiveness is further improved by considering hybrid systems. Hybrid systems are a class of nonsmooth dynamical systems characterized by closely coupled continuous and discrete behavior. This coupling results in dynamical systems with continuous but nondifferentiable vector fields, systems with discontinuous vector fields, and systems with state jumps. This allows, for example, the formulation of OCPs for complex robotic tasks or to incorporate Boolean logic relations between parts of the system. However, from a numerical point of view, such OCPs are difficult to solve. Standard direct methods for solving smooth OCPs applied to nonsmooth OCPs suffer from some fundamental limitations. We develop a toolchain of algorithms and reformulation methods that overcome these limitations and allow one to solve all mentioned classes of nonsmooth OCPs in a unified way. All methods in this toolchain are implemented in the open-source software package nosnoc. Some fundamental limitations of standard direct methods, including time-stepping discretizations, mixed-integer reformulations, and smoothing are highlighted. It is shown that all these approaches suffer from the same limitations unless the discontinuities are explicitly treated by switch detection. They will achieve only first-order accuracy, and the discrete-time numerical sensitivities do not converge to the correct values. As a consequence, the algorithms may converge to spurious local solutions or make almost no progress from a given initial guess. Furthermore, it is discussed why standard direct methods sometimes lead to feasible or seemingly reasonable solutions. In general, obtaining a highly accurate solution with some of these approaches may require a prohibitive computational effort. The application of direct optimal control methods, based on Newton-type optimization, requires the accurate numerical simulation of nonsmooth systems and the computation of numerical sensitivities. This thesis presents the Finite Elements with Switch Detection (FESD) method for Filippov systems, which achieves these two goals and thereby overcomes the fundamental limitation of standard methods. The focus is on Filippov systems, as they provide a sound solution concept for ODEs with a discontinuous right-hand side. The proposed approach reformulates these systems into equivalent Dynamic Complementarity Systems (DCSs). After the time discretization, mathematical programs with complementarity constraints are obtained, which can be solved efficiently with a homotopy approach using standard nonlinear programming solvers. We provide a detailed theoretical analysis of the FESD method and show that it is superior to time-stepping methods in terms of computation time and accuracy. For example, we achieve in an OCP benchmark up to one million times more accurate solutions for the same computational time. Systems with state jumps are not Filippov systems. Therefore, they cannot be treated with the methods developed for this class of nonsmooth systems. We introduce the time-freezing reformulation, which transforms systems with state jumps into equivalent Filippov systems. The main idea of time-freezing is to define a clock state and an auxiliary ODE in the infeasible region of the state space of the original system. The endpoints of the trajectory of the auxiliary ODE satisfy the state jump law of the original system. Moreover, the evolution of the clock state is frozen during the runtime of the auxiliary ODE. By considering only the parts of the trajectory where the clock state evolves, one can reconstruct the solution of the original system with state jumps. This allows one to seamlessly apply the FESD method and the theory of Filippov systems to systems with state jumps. As a somewhat isolated contribution from the topics above, we present several new real-time algorithms for nonlinear model predictive control for smooth dynamical systems. We extend the well-known Real-Time Iteration (RTI), by combining the algorithmic ideas from the Multi-Level Iteration (MLI) and the Advanced Step Controller (ASC). We call this method the Advanced-Step Real-Time Iteration (AS-RTI). The main idea is to improve the current linearization point between two samples by iterating with some MLI variant on an {advanced problem} with a predicted state while waiting for the next state estimate. The AS-RTI scheme bridges the gap between the two well-established algorithmic paradigms: the ASC which solves the OCP to convergence at every sampling time and the RTI which performs only one Newton-type iteration

Abstract: Diese Arbeit befasst sich mit algorithmischen, theoretischen und softwaretechnischen Aspekten der numerischen Lösung von Optimalsteuerungsproblemen (Englisch: Optimal Control Problem (OCP)), mit nicht-glatten dynamischen Systemen. Bei der Lösung eines OCPs wird der optimale Steuerungseingang unter expliziter Berücksichtigung von Nebenbedingungen und der Systemdynamik ausgewählt. Der Entwurfsprozess eines Reglers auf der Grundlage von OCPs ist durch die explizite Formulierung der Systemdynamik und der Nebenbedingungen besonders ausdrucksstark. Diese Ausdrucksfähigkeit wird weiter verbessert, wenn sogenannte hybride Systeme berücksichtigt werden. Hybride Systeme sind eine Klasse nicht-glatter dynamischer Systeme, die sich durch eng gekoppeltes kontinuierliches und diskretes Verhalten auszeichnen. Dies führt zu dynamischen Systemen mit kontinuierlichen, aber nicht differenzierbaren Vektorfeldern, Systemen mit diskontinuierlichen Vektorfeldern und Systemen mit Zustandssprüngen. Dadurch wird beispielsweise die Formulierung von OCPs für komplexe Robotikaufgaben oder die Abbildung logischer Beziehungen zwischen Systemteilen ermöglicht. Aus numerischer Sicht sind solche Probleme jedoch schwierig zu lösen. Herkömmliche direkte Methoden zur Lösung glatter OCPs, angewendet auf nicht-glatte OCPs, haben grundlegende Einschränkungen. In dieser Arbeit wird eine Werkzeugkette von Algorithmen und Umformulierungsmethoden entwickelt, um diese Einschränkungen zu überwinden und die einheitliche Lösung aller zuvor genannten Arten von nicht-glatten OCPs zu ermöglichen. Alle Methoden dieser Werkzeugkette sind in dem Open Source Softwarepaket nosnoc implementiert. Es werden einige grundlegende Einschränkungen konventioneller direkter Methoden aufgezeigt, einschließlich der Diskretisierung mit Zeitschrittmethoden, gemischt-ganzzahliger Umformulierung und Glättung, um nur einige Beispiele zu nennen. Es wird gezeigt, dass alle diese Ansätze unter den gleichen Einschränkungen leiden, es sei denn, die Unstetigkeiten werden explizit durch Schalterkennung behandelt. Herkömmliche direkte Methoden erreichen nur eine Genauigkeit erster Ordnung, und die zeitdiskreten numerischen Sensitivitäten konvergieren nicht zu den richtigen Werten. Infolgedessen können die Algorithmen zu lokalen Scheinlösungen konvergieren oder von einer gegebenen Lösungsschätzung kaum Fortschritte machen. Es wird auch diskutiert, warum konventionelle direkte Methoden manchmal zu scheinbar vernünftigen Lösungen konvergieren. Im Allgemeinen kann das Erreichen einer hochgenauen Lösung mit einigen dieser Ansätze einen inakzeptablen Rechenaufwand erfordern. Direkte Methoden zur Lösung von OCPs, die auf Newton-basierten Optimierungsalgorithmen basieren, erfordern die genaue numerische Simulation von nicht-glatten Systemen und die Berechnung numerischer Sensitivitäten. In dieser Arbeit wird die Finite Elemente Methode mit Schalterkennung (FESD) für Filippov Systeme entwickelt, die beide Ziele erreicht und damit die grundlegenden Einschränkungen der Standardmethoden überwindet. Filippov-Systeme sind von besonderem Interesse, da sie ein solides Lösungskonzept für gewöhnliche Differentialgleichungen mit diskontinuierlicher rechter Seite liefern. Unser Ansatz besteht darin, diese Systeme in äquivalente dynamische Komplementaritätssysteme (Englisch: Dynamic Complementarity System (DCS)) umzuformulieren. Nach der zeitlichen Diskretisierung erhält man mathematische Programme mit Komplementaritätsbeschränkungen (Englisch: Mathematical Program with Complementarity Constraints (MPCC)), die mit einem Homotopie-Ansatz unter Verwendung von Standardlösern für nichtlineare Optimierung effizient gelöst werden können. Eine detaillierte theoretische Analyse der FESD-Methode wird vorgestellt und es wird gezeigt, dass diese den Zeitschrittmethoden in Bezug auf Rechenzeit und Genauigkeit überlegen ist. Beispielsweise werden in einem OCP-Benchmark bis zu einer Million Mal genauere Lösungen bei gleicher Rechenzeit erreicht. Systeme mit Zustandssprüngen sind keine Filippov-Systeme. Daher können sie nicht mit den Methoden behandelt werden, die für diese Klasse von nicht-glatten Systemen entwickelt wurden. Um diese Beschränkung zu überwinden, wird die Time-Freezing-Reformulation eingeführt, um Systeme mit Zustandssprüngen in äquivalente Filippov-Systeme umzuformulieren. Die Hauptidee des Time-Freezing besteht darin, einen Uhrenzustand und eine Hilfsdifferentialgleichung im unzulässigen Bereich des Zustandsraums des ursprünglichen Systems zu definieren. Die Endpunkte der Trajektorie der Hilfsdifferentialgleichung erfüllen das Zustandssprunggesetz des ursprünglichen Systems. Außerdem ist die Evolution des Uhrzustands während der Laufzeit der Hilfsdifferentialgleichung eingefroren. Betrachtet man nur die Teile der Trajektorie, in denen sich der Uhrenzustand entwickelt hat, so kann man die Lösung des ursprünglichen Systems mit Zustandssprüngen rekonstruieren. Dies ermöglicht die Anwendung der FESD-Methode und der Theorie der Filippov-Systeme auf Systeme mit Zustandssprüngen. Als etwas isolierter Beitrag zu den oben genannten Themen werden mehrere neue Echtzeit-Algorithmen für nichtlineare modellprädiktive Regelung für glatte dynamische Systeme vorgestellt. Die bekannte Real-Time Iteration (RTI) wird erweitert, indem die algorithmischen Ideen der Multi-Level Iteration (MLI) und des Advanced Step Controllers (ASC) kombiniert werden. Diese neue Methode wird Advanced-Step Real-Time Iteration (AS-RTI) genannt. Die Hauptidee besteht darin, den aktuellen Linearisierungspunkt zwischen zwei Samples zu verbessern, indem eine MLI-Variante auf einem fortgeschrittenen Problem mit einem vorhergesagten Zustand iteriert wird, während auf die nächste Zustandsschätzung gewartet wird. Der AS-RTI-Algorithmus schließt die Lücke zwischen zwei etablierten Algorithmen: dem ASC-Algorithmus, der das OCP in jedem Sample bis zur Konvergenz löst, und dem RTI-Algorithmus, der nur eine Newton-Iteration durchführt

Access State: Open Access

Search in field:

Recently searched for: