research-article

Control Synthesis for Large Collections of Systems with Mode-Counting Constraints

Authors:

Petter Nilsson,

Necmiye OzayAuthors Info & Claims

HSCC '16: Proceedings of the 19th International Conference on Hybrid Systems: Computation and Control

Pages 205 - 214

https://doi.org/10.1145/2883817.2883831

Published: 11 April 2016 Publication History

Abstract

Given a large homogeneous collection of switched systems, we consider a novel class of safety constraints, called mode-counting constraints, that impose restrictions on the number of systems that are in a particular mode. We propose an approach for synthesizing correct-by-construction switching protocols to enforce such constraints over time. Our approach starts by constructing an approximately bisimilar abstraction of the individual system model. Then, we show that the aggregate behavior of the collection can be represented by a linear system, whose system matrices are induced by the transition graph of the abstraction. Finally, the control synthesis problem with mode-counting constraints is reduced to a cycle assignment problem on the transition graph. One salient feature of the proposed approach is its scalability; the computational complexity is independent of the number of systems involved. We illustrate this approach on the problem of coordinating a large collection of thermostatically controlled loads while ensuring a bound on the number of loads that are extracting power from the electricity grid at any given time.

References

[1]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows. Prentice Hall, 1993.

[2]

A. Bayen, C. Tomlin, Y. Ye, and J. Zhang. Milp formulation and polynomial time algorithm for an aircraft scheduling problem. In Proc. of IEEE CDC, pages 5003--5010, 2003.

[3]

A. Borri, D. V. Dimarogonas, K. H. Johansson, M. D. Di Benedetto, and G. Pola. Decentralized symbolic control of interconnected systems with application to vehicle platooning. In 4th IFAC Workshop on Distributed Estimation and Control in Networked Systems, pages 285--292, 2013.

[4]

A. Colombo and D. Del Vecchio. Least restrictive supervisors for intersection collision avoidance: A scheduling approach. IEEE Trans. on Automatic Control, 60(6):1515--1527, June 2015.

[5]

S. Coogan and M. Arcak. Efficient finite abstraction of mixed monotone systems. In Proc. of HSCC, pages 58--67, 2015.

Digital Library

[6]

S. Esmaeil Zadeh Soudjani and A. Abate. Aggregation and control of populations of thermostatically controlled loads by formal abstractions. IEEE Trans. on Control Systems Technology, 23(3):975--990, 2015.

[7]

E. Frazzoli, M. Dahleh, and E. Feron. Maneuver-based motion planning for nonlinear systems with symmetries. IEEE Trans. on Robotics, 21(6):1077--1091, 2005.

Digital Library

[8]

A. Girard and G. J. Pappas. Approximation Metrics for Discrete and Continuous Systems. IEEE Trans. on Automatic Control, 52(5):782--798, 2007.

[9]

Gurobi Optimization, Inc. Gurobi optimizer reference manual, 2015.

[10]

T. T. Johnson and S. Mitra. A small model theorem for rectangular hybrid automata networks. In FMOODS/FORTE, pages 18--34. Springer, 2012.

Digital Library

[11]

S. Karaman, R. G. Sanfelice, and E. Frazzoli. Optimal control of mixed logical dynamical systems with linear temporal logic specifications. In Proc. of IEEE CDC, pages 2117--2122, 2008.

[12]

S. Koch, J. L. Mathieu, and D. S. Callaway. Modeling and control of aggregated heterogeneous thermostatically controlled loads for ancillary services. In Proc. of PSCC, pages 1--7, 2011.

[13]

M. Lewin. On exponents of primitive matrices. Numerische Mathematik, 18(2):154--161, 1971.

Digital Library

[14]

J. Liu and N. Ozay. Abstraction, discretization, and robustness in temporal logic control of dynamical systems. In Proc. of HSCC, 2014.

Digital Library

[15]

J. L. Mathieu, S. Koch, and D. S. Callaway. State estimation and control of electric loads to manage real-time energy imbalance. IEEE Trans. on Power Systems, 28(1):430--440, 2013.

[16]

O. Mickelin, N. Ozay, and R. M. Murray. Synthesis of correct-by-construction control protocols for hybrid systems using partial state information. In Proc. of ACC, 2014.

[17]

G. Pola and P. Tabuada. Symbolic Models for Nonlinear Control Systems: Alternating Approximate Bisimulations. SIAM J. Control Optim., 48(2):719--733, 2009.

Digital Library

[18]

P. Pourbeik, P. S. Kundur, and C. W. Taylor. The anatomy of a power grid blackout. IEEE Power and Energy Magazine, 4(5):22--29, 2006.

[19]

V. Raman, A. Donzé, D. Sadigh, R. M. Murray, and S. A. Seshia. Reactive synthesis from signal temporal logic specifications. In Proc. of HSCC, pages 239--248, 2015.

Digital Library

[20]

M. Rungger, M. Mazo Jr, and P. Tabuada. Specification-guided controller synthesis for linear systems and safe linear-time temporal logic. In Proc. of HSCC, pages 333--342, 2013.

Digital Library

[21]

B. M. Sanandaji, H. Hao, and K. Poolla. Fast regulation service provision via aggregation of thermostatically controlled loads. In Proc. of HICSS, pages 2388--2397, 2014.

Digital Library

[22]

E. Seneta. Non-negative matrices and Markov chains. Springer, 2006.

[23]

P. Tabuada. Verification and control of hybrid systems: a symbolic approach. Springer, 2009.

Digital Library

[24]

E. M. Wolff, U. Topcu, and R. M. Murray. Optimization-based trajectory generation with linear temporal logic specifications. In Proc. of ICRA, pages 5319--5325, 2014.

[25]

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

[26]

W. Zhang, K. Kalsi, J. Fuller, M. Elizondo, and D. Chassin. Aggregate model for heterogeneous thermostatically controlled loads with demand response. In Proc. of PES General Meeting, pages 1--8, 2012.

Cited By

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
Huang XLyu ZHong Y(2022)Safety verification of large-scale nonlinear systems: a cyclic-small-gain approach2022 IEEE 17th International Conference on Control & Automation (ICCA)10.1109/ICCA54724.2022.9831960(459-462)Online publication date: 27-Jun-2022
https://doi.org/10.1109/ICCA54724.2022.9831960
Jang SOzay NMathieu J(2021)Large-Scale Invariant Sets for Safe Coordination of Thermostatic Loads2021 American Control Conference (ACC)10.23919/ACC50511.2021.9483385(4163-4170)Online publication date: 25-May-2021
https://doi.org/10.23919/ACC50511.2021.9483385
Show More Cited By

Index Terms

Control Synthesis for Large Collections of Systems with Mode-Counting Constraints

Recommendations

On a Class of Maximal Invariance Inducing Control Strategies for Large Collections of Switched Systems
HSCC '17: Proceedings of the 20th International Conference on Hybrid Systems: Computation and Control

Modern control synthesis methods that are capable of delivering safety guarantees typically rely on finding invariant sets. Computing and/or representing such sets becomes intractable for high-dimensional systems and often constitutes the main ...
High-level scheduling model and control synthesis for a broad range of design applications
ICCAD '97: Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design

This paper presents a versatile scheduling model and an efficient control synthesis methodology which enables architectural (high-level) design/synthesis systems to seamlessly support a broad range of architectural design applications from datapath-...
Synthesis using approximately bisimilar abstractions: state-feedback controllers for safety specifications
HSCC '10: Proceedings of the 13th ACM international conference on Hybrid systems: computation and control

This paper deals with the synthesis of state-feedback controllers using approximately bisimilar abstractions with an emphasis on safety problems.

Such problems consist in synthesizing a controller that restricts the behaviors of a system so that its ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

HSCC '16: Proceedings of the 19th International Conference on Hybrid Systems: Computation and Control

April 2016

324 pages

ISBN:9781450339551

DOI:10.1145/2883817

Program Chairs:
Alessandro Abate
University of Oxford, UK
,
Georgios Fainekos
Arizona State University, USA

Copyright © 2016 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 ACM 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 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF

Conference

HSCC'16

Sponsor:

SIGBED

HSCC'16: 19th International Conference on Hybrid Systems: Computation and Control

April 12 - 14, 2016

Vienna, Austria

Acceptance Rates

HSCC '16 Paper Acceptance Rate 28 of 65 submissions, 43%;

Overall Acceptance Rate 153 of 373 submissions, 41%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
120
Total Downloads

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

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Huang XLyu ZHong Y(2022)Safety verification of large-scale nonlinear systems: a cyclic-small-gain approach2022 IEEE 17th International Conference on Control & Automation (ICCA)10.1109/ICCA54724.2022.9831960(459-462)Online publication date: 27-Jun-2022
https://doi.org/10.1109/ICCA54724.2022.9831960
Jang SOzay NMathieu J(2021)Large-Scale Invariant Sets for Safe Coordination of Thermostatic Loads2021 American Control Conference (ACC)10.23919/ACC50511.2021.9483385(4163-4170)Online publication date: 25-May-2021
https://doi.org/10.23919/ACC50511.2021.9483385
Chen YAnderson JKalsi KAmes ALow S(2021)Safety-Critical Control Synthesis for Network Systems With Control Barrier Functions and Assume-Guarantee ContractsIEEE Transactions on Control of Network Systems10.1109/TCNS.2020.30291838:1(487-499)Online publication date: Mar-2021
https://doi.org/10.1109/TCNS.2020.3029183
Yan RJulius A(2021)A Decentralized B&B Algorithm for Motion Planning of Robot Swarms With Temporal Logic SpecificationsIEEE Robotics and Automation Letters10.1109/LRA.2021.30980596:4(7389-7396)Online publication date: Oct-2021
https://doi.org/10.1109/LRA.2021.3098059
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
Wintenberg AOzay N(2020)Implicit Invariant Sets for High-Dimensional Switched Affine Systems2020 59th IEEE Conference on Decision and Control (CDC)10.1109/CDC42340.2020.9303986(3291-3297)Online publication date: 14-Dec-2020
https://doi.org/10.1109/CDC42340.2020.9303986
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
Tabuada P(2020)Controller Synthesis for CPSEncyclopedia of Systems and Control10.1007/978-1-4471-5102-9_100111-1(1-7)Online publication date: 26-Nov-2020
https://doi.org/10.1007/978-1-4471-5102-9_100111-1
Macoveiciuc EReissig G(2019)Memory efficient symbolic solution of quantitative reach-avoid problems2019 American Control Conference (ACC)10.23919/ACC.2019.8814850(1671-1677)Online publication date: Jul-2019
https://doi.org/10.23919/ACC.2019.8814850
Show More Cited By

View Options

Get Access

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents