Combining zonotopes and support functions for efficient reachability analysis of linear systems

Matthias Althoff; Goran Frehse

doi:10.1109/CDC.2016.7799418

Combining zonotopes and support functions for efficient reachability analysis of linear systems

Matthias Althoff, Goran Frehse

Informatics 6 - Associate Professorship of Cyber Physical Systems

University of Grenoble Alpes

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

37 Scopus citations

Abstract

Reachability analysis is an important technique for formally verifying continuous systems, as well as for guaranteed state estimation, stability analysis, and controller synthesis. We present a detailed assessment of the computational efficiency for the reachability analysis of linear systems with respect to the two most scalable set representations: zonotopes and support functions. As a result, we propose representing reachable sets as a combination of support functions and zonotopes. This mix of representations can be converted to polyhedra of desired (directional) precision, at a higher precision compared to exclusively using support functions or zonotopes. The benefits are shown by an in-depth analysis of computational complexity and by numerical experiments.

Original language	English
Title of host publication	2016 IEEE 55th Conference on Decision and Control, CDC 2016
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	7439-7446
Number of pages	8
ISBN (Electronic)	9781509018376
DOIs	https://doi.org/10.1109/CDC.2016.7799418
State	Published - 27 Dec 2016
Event	55th IEEE Conference on Decision and Control, CDC 2016 - Las Vegas, United States Duration: 12 Dec 2016 → 14 Dec 2016

Publication series

Name	2016 IEEE 55th Conference on Decision and Control, CDC 2016

Conference

Conference	55th IEEE Conference on Decision and Control, CDC 2016
Country/Territory	United States
City	Las Vegas
Period	12/12/16 → 14/12/16

Access to Document

10.1109/CDC.2016.7799418

Cite this

Althoff, M., & Frehse, G. (2016). Combining zonotopes and support functions for efficient reachability analysis of linear systems. In 2016 IEEE 55th Conference on Decision and Control, CDC 2016 (pp. 7439-7446). Article 7799418 (2016 IEEE 55th Conference on Decision and Control, CDC 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2016.7799418

@inproceedings{3ce1d03d6d024c26aaa8c88693c22d7c,

title = "Combining zonotopes and support functions for efficient reachability analysis of linear systems",

abstract = "Reachability analysis is an important technique for formally verifying continuous systems, as well as for guaranteed state estimation, stability analysis, and controller synthesis. We present a detailed assessment of the computational efficiency for the reachability analysis of linear systems with respect to the two most scalable set representations: zonotopes and support functions. As a result, we propose representing reachable sets as a combination of support functions and zonotopes. This mix of representations can be converted to polyhedra of desired (directional) precision, at a higher precision compared to exclusively using support functions or zonotopes. The benefits are shown by an in-depth analysis of computational complexity and by numerical experiments.",

author = "Matthias Althoff and Goran Frehse",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 55th IEEE Conference on Decision and Control, CDC 2016 ; Conference date: 12-12-2016 Through 14-12-2016",

year = "2016",

month = dec,

day = "27",

doi = "10.1109/CDC.2016.7799418",

language = "English",

series = "2016 IEEE 55th Conference on Decision and Control, CDC 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "7439--7446",

booktitle = "2016 IEEE 55th Conference on Decision and Control, CDC 2016",

}

Althoff, M & Frehse, G 2016, Combining zonotopes and support functions for efficient reachability analysis of linear systems. in 2016 IEEE 55th Conference on Decision and Control, CDC 2016., 7799418, 2016 IEEE 55th Conference on Decision and Control, CDC 2016, Institute of Electrical and Electronics Engineers Inc., pp. 7439-7446, 55th IEEE Conference on Decision and Control, CDC 2016, Las Vegas, United States, 12/12/16. https://doi.org/10.1109/CDC.2016.7799418

Combining zonotopes and support functions for efficient reachability analysis of linear systems. / Althoff, Matthias; Frehse, Goran.
2016 IEEE 55th Conference on Decision and Control, CDC 2016. Institute of Electrical and Electronics Engineers Inc., 2016. p. 7439-7446 7799418 (2016 IEEE 55th Conference on Decision and Control, CDC 2016).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Combining zonotopes and support functions for efficient reachability analysis of linear systems

AU - Althoff, Matthias

AU - Frehse, Goran

PY - 2016/12/27

Y1 - 2016/12/27

N2 - Reachability analysis is an important technique for formally verifying continuous systems, as well as for guaranteed state estimation, stability analysis, and controller synthesis. We present a detailed assessment of the computational efficiency for the reachability analysis of linear systems with respect to the two most scalable set representations: zonotopes and support functions. As a result, we propose representing reachable sets as a combination of support functions and zonotopes. This mix of representations can be converted to polyhedra of desired (directional) precision, at a higher precision compared to exclusively using support functions or zonotopes. The benefits are shown by an in-depth analysis of computational complexity and by numerical experiments.

AB - Reachability analysis is an important technique for formally verifying continuous systems, as well as for guaranteed state estimation, stability analysis, and controller synthesis. We present a detailed assessment of the computational efficiency for the reachability analysis of linear systems with respect to the two most scalable set representations: zonotopes and support functions. As a result, we propose representing reachable sets as a combination of support functions and zonotopes. This mix of representations can be converted to polyhedra of desired (directional) precision, at a higher precision compared to exclusively using support functions or zonotopes. The benefits are shown by an in-depth analysis of computational complexity and by numerical experiments.

UR - http://www.scopus.com/inward/record.url?scp=85010766621&partnerID=8YFLogxK

U2 - 10.1109/CDC.2016.7799418

DO - 10.1109/CDC.2016.7799418

M3 - Conference contribution

AN - SCOPUS:85010766621

T3 - 2016 IEEE 55th Conference on Decision and Control, CDC 2016

SP - 7439

EP - 7446

BT - 2016 IEEE 55th Conference on Decision and Control, CDC 2016

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 55th IEEE Conference on Decision and Control, CDC 2016

Y2 - 12 December 2016 through 14 December 2016

ER -

Combining zonotopes and support functions for efficient reachability analysis of linear systems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this