research-article

Public Access

Constructing Control System Abstractions from Modular Components

Authors:

Majid ZamaniAuthors Info & Claims

HSCC '18: Proceedings of the 21st International Conference on Hybrid Systems: Computation and Control (part of CPS Week)

Pages 137 - 146

https://doi.org/10.1145/3178126.3178144

Published: 11 April 2018 Publication History

Abstract

This paper tackles the problem of constructing finite abstractions for formal controller synthesis with high dimensional systems. We develop a theory of abstraction for discrete time nonlinear systems that are equipped with variables acting as interfaces for other systems. Systems interact via an interconnection map which constrains the value of system interface variables. An abstraction of a high dimensional interconnected system is obtained by composing subsystem abstractions with an abstraction of the interconnection. System abstractions are modular in the sense that they can be rearranged, substituted, or reused in configurations that were unknown during the time of abstraction. Constructing the abstraction of the interconnection map can become computationally infeasible when there are many systems. We introduce intermediate variables which break the interconnection and the abstraction procedure apart into smaller problems. Examples showcase the abstraction of a 24-dimensional system through the composition of 24 individual systems, and the synthesis of a controller for a 6-dimensional system with a consensus objective.

References

[1]

M. Arcak, C. Meissen, and A. Packard. 2016. Networks of dissipative systems. Springer International Publishing.

Digital Library

[2]

C. Baier and J. P. Katoen. 2008. Principles of model checking. The MIT Press.

Digital Library

[3]

C. Belta and L.C.G.J.M. Habets. 2006. Controlling a class of nonlinear systems on rectangles. IEEE Trans. Automat. Control 51, 11 (2006), 1749--1759.

[4]

D. Boskos and D. V. Dimarogonas. 2015. Decentralized abstractions for feedback interconnected multi-agent systems. In Proceedings of 54th IEEE Conference on Decision and Control. 282--287.

[5]

R. E. Bryant. 1986. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Trans. Comput. 35, 8 (1986), 677--691.

Digital Library

[6]

S. Coogan and M. Arcak. 2015. Efficient finite abstraction of mixed monotone systems. In Proceedings of 18th International Conference on Hybrid Systems: Computation and Control. 58--67.

Digital Library

[7]

A. Girard, G. Pola, and P. Tabuada. 2010. Approximately bisimilar symbolic models for incrementally stable switched systems. IEEE Trans. Automat. Control 55, 1 (January 2010), 116--126.

[8]

F. Gruber, E. Kim, and M. Arcak. 2017. Sparsity-Aware Finite Abstraction. In 2017 IEEE 56th Conference on Decision and Control (CDC).

[9]

L.C.G.J.M. Habets, P.J. Collins, and J.H. Van Schuppen. 2006. Reachability and control synthesis for piecewise-affine hybrid systems on simplices. IEEE Trans. Automat. Control 51, 6 (2006), 938--948.

[10]

O. Hussein, A. Ames, and P. Tabuada. 2017. Abstracting partially feedback linearizable systems compositionally. IEEE Control Systems Letters 1, 2 (October 2017), 227--232.

[11]

J. Liu and N. Ozay. 2014. Abstraction, discretization, and robustness in temporal logic control of dynamical systems. In Proceedings of the 17th International Conference on Hybrid Systems: Computation and Control. ACM New York, NY, USA, 293--302.

Digital Library

[12]

P.J. Meyer, A. Girard, and E. Witrant. 2017, accepted. Compositional abstraction and safety synthesis using overlapping symbolic models. IEEE Trans. Automat. Control (2017, accepted).

[13]

S. Mouelhi, A. Girard, and G. Gössler. 2013. CoSyMA: A Tool for Controller Synthesis Using Multi-scale Abstractions. In 16th International Conference on Hybrid Systems: Computation and Control. ACM, 83--88.

Digital Library

[14]

G. Pola, A. Girard, and P. Tabuada. 2008. Approximately bisimilar symbolic models for nonlinear control systems. Automatica 44, 10 (October 2008), 2508--2516.

Digital Library

[15]

G. Pola, P. Pepe, and M. D. Di Benedetto. 2016. Symbolic models for networks of control systems. IEEE Trans. Automat. Control 61, 11 (November 2016), 3663--3668.

[16]

G. Reißig. 2011. Computing abstractions of nonlinear systems. IEEE Transaction on Automatic Control 56, 11 (November 2011), 2583--2598.

[17]

G. Reißig, A. Weber, and M. Rungger. April 2017. Feedback Refinement Relations for the Synthesis of Symbolic Controllers. IEEE Trans. Automat. Control 62, 4 (April 2017), 1781--1796.

[18]

R. T. Rockafellar and R. Wets. 2009. Variational analysis. Vol. 317. Springer.

[19]

M. Rungger and M. Zamani. 2016. SCOTS: A Tool for the Synthesis of Symbolic Controllers. In 19th International Conference on Hybrid Systems: Computation and Control. ACM, 99--104.

Digital Library

[20]

F. Somenzi. 2015. CUDD: CU Decision Diagram Package. http://vlsi.colorado.edu/~fabio/CUDD/. (2015). Version 3.0.0.

[21]

P. Tabuada. 2009. Verification and Control of Hybrid Systems. New York, NY,USA: Springer.

Digital Library

[22]

Y. Tazaki and J. Imura. 2009. Discrete-state abstractions of nonlinear systems using multi-resolution quantizer. In International Conference on Hybrid Systems: Computation and Control (HSCC). Lecture Notes in Computer Science, Vol. 5469. Springer Verlag, Berlin Heidelberg, 351--365.

Digital Library

[23]

Y. Tazaki and J. I. Imura. 2008. Bisimilar finite abstractions of interconnected systems. In 11th International Conference on Hybrid Systems: Computation and Control. Springer Berlin Heidelberg, Berlin, Heidelberg, 514--527.

Digital Library

[24]

M. Zamani, A. Abate, and A. Girard. 2015. Symbolic models for stochastic switchedsystems:Adiscretizationandadiscretization-freeapproach. Automatica 55 (May 2015), 183--196.

Digital Library

[25]

M. Zamani, P. Mohajerin Esfahani, R. Majumdar, A. Abate, and J. Lygeros. 2014. Symbolic control of stochastic systems via approximately bisimilar finite abstractions. IEEETrans. Automat. Control 59, 12 (November 2014), 3135--3150.

[26]

M. Zamani, G. Pola, M. Mazo Jr., and P. Tabuada. 2012. Symbolic models for nonlinear control systems without stability assumptions. IEEE Transaction on Automatic Control 57, 7 (July 2012), 1804--1809.

Cited By

Wei XFu AQiao J(2024)Design of Abstract Controller for Symbolic Abstractions2024 43rd Chinese Control Conference (CCC)10.23919/CCC63176.2024.10661583(146-151)Online publication date: 28-Jul-2024
https://doi.org/10.23919/CCC63176.2024.10661583
Macoveiciuc EReissig G(2023)On-the-Fly Symbolic Synthesis With Memory Reduction GuaranteesIEEE Transactions on Automatic Control10.1109/TAC.2022.318848368:4(2576-2583)Online publication date: Apr-2023
https://doi.org/10.1109/TAC.2022.3188483
Li YSun ZLiu J(2023)A Specification-Guided Framework for Temporal Logic Control of Nonlinear SystemsIEEE Transactions on Automatic Control10.1109/TAC.2022.316848968:4(2002-2017)Online publication date: Apr-2023
https://doi.org/10.1109/TAC.2022.3168489
Show More Cited By

Index Terms

Constructing Control System Abstractions from Modular Components

Recommendations

Compositional construction of approximate abstractions
HSCC '15: Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control

In this paper we propose a compositional construction of approximate abstractions of interconnected control systems. Our notion of approximate abstraction is based on so-called simulation functions. The abstraction acts as substitute in the controller ...
Compositional synthesis of opacity-preserving finite abstractions for interconnected systems
Abstract
In this paper, we propose a compositional approach to construct opacity-preserving finite abstractions (a.k.a symbolic models) for networks of discrete-time nonlinear control systems. Particularly, we introduce new notions of ...
Compositional Abstractions of Hybrid Control Systems

Abstraction is a natural way to hierarchically decompose the analysis and design of hybrid systems. Given a hybrid control system and some desired properties, one extracts an abstracted system while preserving the properties of interest. Abstractions of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

HSCC '18: Proceedings of the 21st International Conference on Hybrid Systems: Computation and Control (part of CPS Week)

April 2018

296 pages

ISBN:9781450356428

DOI:10.1145/3178126

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 April 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

NSF
DFG

Conference

HSCC '18

Sponsor:

SIGBED

HSCC '18: 21st International Conference on Hybrid Systems: Computation and Control

April 11 - 13, 2018

Porto, Portugal

Acceptance Rates

Overall Acceptance Rate 153 of 373 submissions, 41%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
413
Total Downloads

Downloads (Last 12 months)85
Downloads (Last 6 weeks)10

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wei XFu AQiao J(2024)Design of Abstract Controller for Symbolic Abstractions2024 43rd Chinese Control Conference (CCC)10.23919/CCC63176.2024.10661583(146-151)Online publication date: 28-Jul-2024
https://doi.org/10.23919/CCC63176.2024.10661583
Macoveiciuc EReissig G(2023)On-the-Fly Symbolic Synthesis With Memory Reduction GuaranteesIEEE Transactions on Automatic Control10.1109/TAC.2022.318848368:4(2576-2583)Online publication date: Apr-2023
https://doi.org/10.1109/TAC.2022.3188483
Li YSun ZLiu J(2023)A Specification-Guided Framework for Temporal Logic Control of Nonlinear SystemsIEEE Transactions on Automatic Control10.1109/TAC.2022.316848968:4(2002-2017)Online publication date: Apr-2023
https://doi.org/10.1109/TAC.2022.3168489
Tousi Jal Khatib MBajcinca N(2022)Model predictive control of demand response for large scale production lines and networks2022 XXVIII International Conference on Information, Communication and Automation Technologies (ICAT)10.1109/ICAT54566.2022.9811138(1-6)Online publication date: 16-Jun-2022
https://doi.org/10.1109/ICAT54566.2022.9811138
Liu SNoroozi NZamani M(2021)Symbolic models for infinite networks of control systems: A compositional approachNonlinear Analysis: Hybrid Systems10.1016/j.nahs.2021.10109743(101097)Online publication date: Dec-2021
https://doi.org/10.1016/j.nahs.2021.101097
Al Khatib MZamani M(2020)Controller synthesis for interconnected systems using parametric assume-guarantee contracts2020 American Control Conference (ACC)10.23919/ACC45564.2020.9147757(5419-5424)Online publication date: Jul-2020
https://doi.org/10.23919/ACC45564.2020.9147757
Nilsson POzay N(2020)Control Synthesis for Permutation-Symmetric High-Dimensional Systems With Counting ConstraintsIEEE Transactions on Automatic Control10.1109/TAC.2019.291094965:2(461-476)Online publication date: Feb-2020
https://doi.org/10.1109/TAC.2019.2910949
Macoveiciuc EReissig G(2020)Guaranteed memory reduction in synthesis of correct-by-design invariance controllersIFAC-PapersOnLine10.1016/j.ifacol.2020.12.156753:2(5561-5566)Online publication date: 2020
https://doi.org/10.1016/j.ifacol.2020.12.1567
Swikir AZamani M(2019)Compositional Abstractions of Interconnected Discrete-Time Switched Systems2019 18th European Control Conference (ECC)10.23919/ECC.2019.8796176(1251-1256)Online publication date: Jun-2019
https://doi.org/10.23919/ECC.2019.8796176
Liu SZamani M(2019)Compositional synthesis of almost maximally permissible safety controllers2019 American Control Conference (ACC)10.23919/ACC.2019.8815361(1678-1683)Online publication date: Jul-2019
https://doi.org/10.23919/ACC.2019.8815361
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten