Publications
2025
- Approximability of the Containment Problem for Zonotopes and EllipsotopesAdrian Kulmburg, Lukas Schäfer, and Matthias Althoff
The zonotope containment problem, i.e., whether one zonotope is contained in another, is a central problem in control theory. Applications include detecting faults and robustifying controllers by computing invariant sets, and obtaining fixed points in reachability analysis. Despite the inherent coNP-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 practice. 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. We also explore the computational complexity of the ellipsotope containment problem with a focus on approximability. Finally, we present new methods to compute safe sets for linear dynamical systems, demonstrating the practical relevance of approximating the ellipsotope containment problem.
@article{kulmburg2025approximability, title = {{Approximability of the Containment Problem for Zonotopes and Ellipsotopes}}, author = {Kulmburg, Adrian and Schäfer, Lukas and Althoff, Matthias}, journal = {IEEE Transactions on Automatic Control}, year = {2025}, volume = {70}, number = {12}, pages = {8104-8119}, doi = {10.1109/TAC.2025.3583624}, } - The Generalized Matrix Norm ProblemAdrian Kulmburg
We study the computability of the operator norm of a matrix with respect to norms induced by linear operators. Our findings reveal that this problem can be solved in polynomial time in certain situations, and we discuss how it can be approximated in other cases. Along the way, we investigate the concept of push-forward and pull-back of seminorms, which leads us to uncover novel duality principles that come into play when optimizing over the unit ball of norms.
@article{kulmburg2025generalized, title = {{The Generalized Matrix Norm Problem}}, author = {Kulmburg, Adrian}, journal = {SIAM Journal on Matrix Analysis and Applications}, volume = {46}, number = {4}, pages = {2226-2252}, year = {2025}, doi = {10.1137/23M1605545}, }
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 applications in many areas of research, including convex geometry, reachability analysis, and invariant set computation. Their popularity stems from a tight relation to linear programming. 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 compare 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}, } - 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}, title = {Search-based and Stochastic Solutions to the Zonotope and Ellipsotope Containment Problems}, year = {2024}, pages = {1057-1064}, doi = {10.23919/ECC64448.2024.10590884}, }
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}, }