Armin Nurkanović

University of Freiburg

Thursday, November 30, 2023, 16:00 - 18:00

SR 03-026, Building 051

This thesis regards algorithmic, theoretical, and software aspects of numerically solving Optimal Control Problems (OCPs) subject to nonsmooth dynamical systems. The ability to consider constraints and system dynamics in OCPs increases the expressiveness in the controller design process. This 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 compare some of these methods, including time-stepping discretizations, mixed-integer reformulations, and smoothing. It is shown that all these approaches suffer from the same limitations unless the discontinuities are explicitly treated by switch detection. Namely, 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. In general, obtaining a highly accurate solution with some of these approaches may require a prohibitive computational effort. 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.

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.