rapid-communication

Hybrid zonotopes: : A new set representation for reachability analysis of mixed logical dynamical systems

Authors:

Trevor J. Bird,

Herschel C. Pangborn,

Justin P. KoelnAuthors Info & Claims

Volume 154, Issue C

https://doi.org/10.1016/j.automatica.2023.111107

Published: 01 August 2023 Publication History

Abstract

This article presents a new set representation named the hybrid zonotope that is equivalent to the union of 2 N constrained zonotopes – convex polytopes – through the addition of N binary zonotope factors. The major contribution of this manuscript is a closed-form solution for exact forward reachable sets of discrete-time, linear hybrid systems modeled as mixed logical dynamical systems. The proposed approach captures the worst-case exponential growth in the number of convex sets required to represent the nonconvex reachable set while exhibiting only linear growth in the complexity of the hybrid zonotope set representation. Redundancy removal techniques are provided that leverage binary trees to store the combinations of binary factors of the hybrid zonotope that map to nonempty convex subsets. Numerical examples show the hybrid zonotope’s ability to compactly represent nonconvex reachable sets with an exponential number of features. Furthermore, the hybrid zonotope is shown to be closed under linear mappings, Minkowski sums, generalized intersections, and halfspace intersections.

References

[1]

Achterberg Tobias, Bixby Robert E., Gu Zonghao, Rothberg Edward, Weninger Dieter, Presolve reductions in mixed integer programming, INFORMS Journal on Computing (2020).

[2]

Althoff Matthias, Frehse Goran, Girard Antoine, Set propagation techniques for reachability analysis, Annual Review of Control, Robotics, and Autonomous Systems (2021).

[3]

Althoff Matthias, Stursberg Olaf, Buss Martin, Computing reachable sets of hybrid systems using a combination of zonotopes and polytopes, Nonlinear Analysis. Hybrid Systems (2010).

[4]

Alur Rajeev, Courcoubetis Costas, Halbwachs Nicolas, Henzinger Thomas A., Ho Pei-Hsin, Nicollin Xavier, et al., The algorithmic analysis of hybrid systems, Theoretical Computer Science (1995).

[5]

Asarin Eugene, Bournez Olivier, Dang Thao, Maler Oded, Approximate reachability analysis of piecewise-linear dynamical systems, in: Hybrid systems: Computation and control, Springer, 2000.

[6]

Bemporad Alberto, Morari Manfred, Control of systems integrating logic, dynamics, and constraints, Automatica (1999).

[7]

Bemporad Alberto, Morari Manfred, Verification of hybrid systems via mathematical programming, in: Vaandrager Frits W., van Schuppen Jan H. (Eds.), Hybrid systems: Computation and control, Springer, Berlin, 1999.

[8]

Bird Trevor J., Jain Neera, Unions and complements of hybrid zonotopes, IEEE Control Systems Letters (2021).

[9]

Bird Trevor J, Pangborn Herschel C, Jain Neera, Koeln Justin P, Hybrid zonotopes: A new set representation for reachability analysis of mixed logical dynamical systems, 2021, arXiv preprint arXiv:2106.14831.

[10]

Blanchini Franco, Miani Stefano, Set-theoretic methods in control, in: Systems & control: Foundations & applications, 2nd ed., Springer, Cham, 2015.

[11]

Blondel Vincent D., Tsitsiklis John N., Complexity of stability and controllability of elementary hybrid systems, Automatica (1999).

[12]

Chen Mo, Tomlin Claire J., Hamilton–Jacobi reachability: Some recent theoretical advances and applications in unmanned airspace management, Annual Review of Control, Robotics, and Autonomous Systems (2018).

[13]

Combastel Christophe, Functional sets with typed symbols: Mixed zonotopes and polynotopes for hybrid nonlinear reachability and filtering, Automatica (2022).

[14]

Frehse, Goran, Kateja, Rajat, & Le Guernic, Colas (2013). Flowpipe approximation and clustering in space-time. In Proceedings of the 16th international conference on hybrid systems: Computation and control. ISBN: 978-1-4503-1567-8.

[15]

Heemels W. P. Maurice H., De Schutter Bart, Bemporad Alberto, Equivalence of hybrid dynamical models, Automatica (2001).

[16]

Herceg, Martin, Kvasnica, Michal, Jones, Colin N., & Morari, Manfred (2013). Multi-parametric toolbox 3.0. In 2013 European control conference.

[17]

Knuth Donald Ervin, The art of computer programming, Pearson Education, 1997.

Digital Library

[18]

Kochdumper Niklas, Althoff Matthias, Sparse polynomial zonotopes: A novel set representation for reachability analysis, IEEE Transactions on Automatic Control (2021).

[19]

Le Guernic Colas, Girard Antoine, Reachability analysis of hybrid systems using support functions, in: Lecture notes in computer science, in: Computer aided verification, Springer, Berlin, Heidelberg, 2009, pp. 540–554.

[20]

Liberzon Daniel, Switching in systems and control, in: Systems & control: Foundations & applications, Birkhäuser Basel, 2003.

[21]

LLC Gurobi Optimization, Gurobi optimizer reference manual, 2021.

[22]

Lodi Andrea, Mixed integer programming computation, in: 50 years of integer programming 1958-2008: From the early years to the state-of-the-art, Springer, Berlin, 2010.

[23]

Lofberg, J. (2004). YALMIP : A toolbox for modeling and optimization in MATLAB. In 2004 IEEE international conference on robotics and automation.

[24]

McMullen P., On zonotopes, Transactions of the American Mathematical Society (1971).

[25]

Raghuraman Vignesh, Koeln Justin P., Set operations and order reductions for constrained zonotopes, Automatica (2022).

[26]

Scott Joseph K., Raimondo Davide M., Marseglia Giuseppe Roberto, Braatz Richard D., Constrained zonotopes: A new tool for set-based estimation and fault detection, Automatica (2016).

[27]

Silvestre Daniel, Constrained convex generators: A tool suitable for set-based estimation with range and bearing measurements, IEEE Control Systems Letters (2022).

[28]

Torrisi Fabio D., Bemporad Alberto, HYSDEL-a tool for generating computational hybrid models for analysis and synthesis problems, IEEE Transactions on Control Systems Technology (2004).

Cited By

Casagrande APiazza C(2023)Adaptive Directions for Bernstein-Based Polynomial Set EvolutionReachability Problems10.1007/978-3-031-45286-4_9(113-126)Online publication date: 11-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-45286-4_9

Recommendations

Constrained zonotopes

This article introduces a new class of sets, called constrained zonotopes, that can be used to enclose sets of interest for estimation and control. The numerical representation of these sets is sufficient to describe arbitrary convex polytopes when the ...
Set operations and order reductions for constrained zonotopes
Abstract
This paper presents methods for using zonotopes and constrained zonotopes to improve the practicality of a wide variety of set-based operations commonly used in control theory. The proposed methods extend the use of constrained ...
Classification of Vertex-Transitive Zonotopes
Abstract
We give a full classification of vertex-transitive zonotopes. We prove that a vertex-transitive zonotope is a $Γ$ -permutahedron for some finite reflection group $Γ \subset O (R^{d})$ . The same holds true for zonotopes in which all vertices are on a common sphere, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Automatica (Journal of IFAC)

Automatica (Journal of IFAC) Volume 154, Issue C

Aug 2023

319 pages

ISSN:0005-1098

Issue’s Table of Contents

Elsevier Ltd.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 August 2023

Author Tags

Qualifiers

Rapid-communication

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Casagrande APiazza C(2023)Adaptive Directions for Bernstein-Based Polynomial Set EvolutionReachability Problems10.1007/978-3-031-45286-4_9(113-126)Online publication date: 11-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-45286-4_9

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents