Publications
2024
- Implementation of Polyhedral Operations in CORA 2024Mark Wetzlinger, Viktor Kotsev, Adrian Kulmburg, and Matthias Althoff
Tool presentation: Polyhedra are a common set representation with widespread appli- cations in many areas of research, including convex geometry, reachability analysis, and invariant set computation. Their popularity stems from a tight relation to linear program- ming. Apart from some basic set operations with analytic formulae, the implementation of many polyhedral set operations in tools is not well documented. For this reason, we describe the evaluation of common set operations on polyhedra, including their runtime complexity, and provide an overview of their implementation as a dedicated class in the MATLAB tool Continuous Reachability Analyzer (CORA) for set-based computing. In particular, we highlight the handling of unbounded and degenerate sets. Finally, we com- pare our implementation to the popular multi-parametric toolbox.
@inproceedings{wetzlinger2024_polytopes, author = {Wetzlinger, Mark and Kotsev, Viktor and Kulmburg, Adrian and Althoff, Matthias}, title = {Implementation of Polyhedral Operations in CORA 2024}, booktitle = {Proceedings of the 11th Int. Workshop on Applied Verification for Continuous and Hybrid Systems}, volume = {103}, publisher = {EasyChair}, doi = {10.29007/wb9s}, pages = {163-181}, year = {2024}, } - Inner Approximations of Reachable Sets for Nonlinear Systems Using the Minkowski DifferenceMark Wetzlinger, Adrian Kulmburg, and Matthias Althoff
Reachability analysis is a formal method that rigorously proves whether a dynamical system can reach certain states. Inner approximations of the exact reachable set contain only states that are definitely reachable and are therefore used to falsify specifications. While the majority of state-of-the-art approaches for nonlinear systems obtain an inner approximation via first computing an outer approximation of the reachable set, we directly obtain sound inner approximations by using the Minkowski difference in a reachability algorithm for nonlinear systems. Our implementation uses a combination of polytopes and constrained zonotopes as set representations, resulting in a low polynomial time complexity in the state dimension. A comparison with state-of-the-art approaches on several benchmarks demonstrates the advantages of our approach.
@article{wetzlinger2024, author = {Wetzlinger, Mark and Kulmburg, Adrian and Althoff, Matthias}, journal = {IEEE Control Systems Letters}, title = {Inner Approximations of Reachable Sets for Nonlinear Systems Using the Minkowski Difference}, year = {2024}, volume = {8}, pages = {2033-2038}, doi = {10.1109/LCSYS.2024.3421194}, } - Approximability of the Containment Problem for Zonotopes and EllipsotopesAdrian Kulmburg, Lukas Schäfer, and Matthias AlthoffAccepted/Provisionally accepted, preparing final version
The zonotope containment problem, i.e., whether one zonotope is contained in another, is a central problem in control theory to compute invariant sets, obtain fixed points of reachable sets, detect faults, and robustify controllers. Despite the inherent co-NP-hardness of this problem, an approximation algorithm developed by S. Sadraddini and R. Tedrake has gained widespread recognition for its swift execution and consistent reliability in practical scenarios. In our study, we substantiate the precision of the algorithm with a definitive proof, elucidating the empirical accuracy observed in practice. Our proof hinges on establishing a connection between the containment problem and the computation of matrix norms, thereby enabling the extension of the approximation algorithm to encompass ellipsotopes, a broader class of sets derived from zonotopes. Moreover, we explore the computational complexity of the ellipsotope containment problem, focusing on approximability. Finally, we present new methods to calculate robust control invariant sets for linear dynamical systems, demonstrating the practical relevance of approximations to the ellipsotope containment problem.
@misc{kulmburg2024approximability, title = {{Approximability of the Containment Problem for Zonotopes and Ellipsotopes}}, author = {Kulmburg, Adrian and Schäfer, Lukas and Althoff, Matthias}, year = {2024}, eprint = {2404.11185}, archiveprefix = {arXiv}, } - Search-based and Stochastic Solutions to the Zonotope and Ellipsotope Containment ProblemsAdrian Kulmburg, Ivan Brkan, and Matthias Althoff
We introduce new techniques to check whether a zonotope is contained in another zonotope. This fundamental problem in control theory has many applications, such as the verification of invariant sets, formal verification of controllers, and fault detection. Our first method uses a search-based vertex enumeration to quickly and efficiently check containment. We also propose two stochastic methods that are able to rapidly disprove or confirm containment with a certain probability. Furthermore, we generalize the first approach to the case where the circumbody is an ellipsotope and generalize the stochastic methods to the case where both the inbody and the circumbody are ellipsotopes. We conclude by comparing the efficiency of our algorithms to currently available ones.
@inproceedings{kulmburg2024, author = {Kulmburg, Adrian and Brkan, Ivan and Althoff, Matthias}, booktitle = {European Control Conference (ECC)}, title = {Search-based and Stochastic Solutions to the Zonotope and Ellipsotope Containment Problems}, year = {2024}, }
2023
- The Generalized Matrix Norm ProblemAdrian KulmburgAccepted/Provisionally accepted, preparing final version
We investigate the problem of computing the operator norm of a matrix with respect to norms induced by linear operators. We show that the dual formulation of this problem can be expressed as a max-min problem which can, for some specific cases, be solved in polynomial time. In other instances, we show that the problem is approximable. Along the way, we develop the concept of push-forward and pull-back of seminorms, and deduce new duality results when optimizing over the unit ball of various norms.
@article{kulmburg2023, archiveprefix = {arXiv}, title = {{The Generalized Matrix Norm Problem}}, author = {Kulmburg, Adrian}, year = {2023}, eprint = {2310.00605}, }
2022
- Adaptive reachability algorithms for nonlinear systems using abstraction error analysisMark Wetzlinger, Adrian Kulmburg, Alexis Le Penven, and Matthias Althoff
In many reachability algorithms for nonlinear ordinary differential equations (ODEs), the tightness of the computed reachable sets mainly depends on abstraction errors and the choice of the set representation. One has to mitigate the resulting wrapping effects by suitable tuning of internally-used algorithm parameters since there exists no wrapping-free algorithm to date. In this work, we investigate the fundamentals governing the abstraction error in reachability algorithms – which we also refer to as set-based solvers – and its dependence on the time step size, leading to the introduction of a gain order. This order is related to measures for local and global abstraction errors and thus relates the well-known concept of convergence order from classical ODE solvers to set-based solvers. Furthermore, the simplification of the set representation is tackled by limiting the Hausdorff distance between the original and reduced sets; we demonstrate this for zonotopes. Both these theoretical advancements are incorporated in a modular adaptive parameter tuning algorithm suited for multiple classes of nonlinear ODEs whose efficiency is demonstrated on a wide range of benchmarks.
@article{wetzlinger2022, title = {Adaptive reachability algorithms for nonlinear systems using abstraction error analysis}, journal = {Nonlinear Analysis: Hybrid Systems}, volume = {46}, pages = {101252}, year = {2022}, doi = {10.1016/j.nahs.2022.101252}, author = {Wetzlinger, Mark and Kulmburg, Adrian and {Le Penven}, Alexis and Althoff, Matthias}, }
2021
- Adaptive parameter tuning for reachability analysis of nonlinear systemsMark Wetzlinger, Adrian Kulmburg, and Matthias Althoff
Reachability analysis fails to produce tight reachable sets if certain algorithm parameters are poorly tuned, such as the time step size or the accuracy of the set representation. The tuning is especially difficult in the context of nonlinear systems where over-approximation errors accumulate over time due to the so-called wrapping effect, often requiring expert knowledge. In order to widen the applicability of reachability analysis for practitioners, we propose the first adaptive parameter tuning approach for reachability analysis of nonlinear continuous systems tuning all algorithm parameters. Our modular approach can be applied to different reachability algorithms as well as various set representations. Finally, an evaluation on numerous benchmark systems shows that the adaptive parameter tuning approach efficiently computes very tight enclosures of reachable sets.
@inproceedings{wetzlinger2021, author = {Wetzlinger, Mark and Kulmburg, Adrian and Althoff, Matthias}, title = {Adaptive parameter tuning for reachability analysis of nonlinear systems}, year = {2021}, publisher = {Association for Computing Machinery}, doi = {10.1145/3447928.3456643}, booktitle = {Proceedings of the 24th International Conference on Hybrid Systems: Computation and Control}, articleno = {16}, } - On the co-NP-completeness of the zonotope containment problemAdrian Kulmburg, and Matthias Althoff
We introduce a new type of norm for non-degenerate zonotopes to solve the point containment problem, i.e., whether a point lies in a zonotope. With this norm we prove the co-NP-completeness of the zonotope containment problem, i.e., whether a zonotope is contained within another one. We propose novel algorithms to solve the zonotope containment problem exactly in polynomial time when fixing the dimension or the number of generators of either of the two zonotopes. In addition, we propose an optimisation-based algorithm, that is particularly suitable for disproving containment for zonotopes.
@article{kulmburg2021, title = {On the {co-NP-completeness} of the zonotope containment problem}, journal = {European Journal of Control}, volume = {62}, pages = {84-91}, year = {2021}, doi = {10.1016/j.ejcon.2021.06.028}, author = {Kulmburg, Adrian and Althoff, Matthias}, }