(41b) Graph-Based Abstractions and Tools for the Modeling and Simulation of Cyber-Physical Systems

Complex systems are inherently cyber-physical in nature [1]. For instance, a chemical process is a physical system that is driven by decisions made by a control system, which is in turn a cyber system comprised of devices (e.g., sensors, controllers, actuators) that execute diverse computing tasks and that exchange signals and data through a communication network. Modeling and simulating the behavior of cyber-physical systems is becoming increasingly important, but capturing their interdependencies is technically challenging [2]. The behavior of a physical system is expressed mathematically in the form of an algebraic model while the behavior of a cyber system is expressed mathematically in the form of algorithms which may be executed on heterogeneous computing architectures.

This talk presents abstractions to model and simulate the dependencies that arise in cyber-physical systems. We discuss an algebraic graph abstraction that captures physical connectivity in complex optimization models and a computing graph abstraction that captures communication connectivity in computing architectures. We will show how the algebraic graph performs as a general decomposition framework for optimization problems and how it facilitates the implementation and interfacing with distributed algorithms such as ADMM [3], Nested Benders [4], Lagrangian Decomposition [5], and Parallel Interior Point methods [6]. We also show how it enables graph partitioning [7] and community detection capabilities [8] which can be used to apply decomposition algorithms to complex physical systems that consider computational load balancing aspects [9].

Finally, we discuss how the computing graph abstraction facilitates the evaluation of optimization and control algorithms and their simulation in virtual environments that involve distributed,
centralized, and hierarchical computing architectures. We discuss its connections with automata theory and discrete event simulation [10] and how this permits a state-space representation.
We end with an example of simulating a real-time distributed control architecture subject to delays, latency, and communication and controller failures [11]. The proposed abstractions are implemented in a Julia-based software package that we call Plasmo.jl [12].

References:

[1] J. Lee, B. Bagheri, and H.-A. Kao. A cyber-physical systems architecture for industry 4.0-based manufacturing systems. Manufacturing Letters, 3:18–23, 2015.

[2] E. A. Lee. Cyber physical systems: Design challenges. In 11th IEEE Symposium on Object Oriented Real-Time Distributed Computing (ISORC), pages 363–369. IEEE, 2008.

[3] J. S. Rodriguez, B. Nicholson, C. Laird, and V. M. Zavala. Benchmarking admm in nonconvex nlps. Computers & Chemical Engineering, 119:315–325, 2018.

[4] A. Conejo, E. Castillo, R. Minguez, and R. Garci-Bertrand. Decomposition Techniques in Mathemat-ical Programming. 2006.

[5] I. E. Grossmann. Advances in mathematical programming models for enterprise-wide optimization. Computers and Chemical Engineering, 47:2–18, 2012.

[6] N. Chiang, C. G. Petra, and V. M. Zavala. Structured Nonconvex Optimization of Large-Scale Energy Systems Using PIPS-NLP. 2014 Power Systems Computation Conference, pages 1–7.

[7] G. Karypis and V. Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM Journal on Scientific Computing, 20(1):359–392, 1998.

[8] S. Fortunato. Community detection in graphs. Physics Reports, 486(3):75–174, 2010.

[9] W. Tang, A. Allman, D. B. Pourkargar, and P. Daoutidis. Optimal decomposition for distributed optimization in nonlinear model predictive control through community detection. Computers & Chemical Engineering, 111:43–54, 2017.

[10] A. Agarwal and I. E. Grossmann. Linear coupled component automata for milp modeling of hybrid systems. Computers & Chemical Engineering, 33(1):162–175, 2009.

[11] B. T. Stewart, A. N. Venkat, J. B. Rawlings, S. J. Wright, and G. Pannocchia. Cooperative distributed model predictive control. Systems and Control Letters, 59(8):460–469, 2010.

[12] Jalving, J., Cao, Y., & Zavala, V. M. Graph-based modeling and simulation of complex systems, Computers & Chemical Engineering, 125:134–154, 2019