Foundations of a CPS Resilience - January 2023

PI: Xenofon Koutsoukos

HARD PROBLEM(S) ADDRESSED

The goals of this project are to develop the principles and methods for designing and analyzing resilient CPS architectures that deliver required service in the face of compromised components. A fundamental challenge is to understand the basic tenets of CPS resilience and how they can be used in developing resilient architectures. The primary hard problem addressed is resilient architectures. In addition, the work addresses scalability and composability as well as metrics and evaluation. 

PUBLICATIONS

[1]    Yasin Yazicioglu, Mudassir Shabbir, Waseem Abbas, Xenofon Koutsoukos. “Strong Structural Controllability of Networks: Comparison of Bounds Using Distances and Zero Forcing”, Automatica. 146, 110562, 2022.
[2]    Mudassir Shabbir, Waseem Abbas, Yasin Yazicioglu and Xenofon Koutsoukos. “Computation of the Distance-based Bound on Strong Structural Controllability in Networks”, IEEE Transactions on Automatic Control, 2022.
[3]    Jiani Li, Waseem Abbas, Mudassir Shabbir, and Xenofon Koutsoukos. “Byzantine Resilient Distributed Learning in Multi-Robot Systems”, IEEE Transactions on Robotics. 38(6), December 2022.
[4]    Feiyang Cai, Zhenkai Zhang, Jie Liu, and Xenofon Koutsoukos. “A Vision Transformer for Open Set Recognition”, IEEE 2022 International Conference on Machine Learning Applications (ICMLA 2022), December 12-14, 2022.

KEY HIGHLIGHTS

This quarterly report presents two key highlights that demonstrate new analysis methods for network controllability. 

Highlight 1: Strong Structural Controllability of Networks: Comparison of Bounds Using Distances and Zero Forcing

Network controllability has been an important research topic in network science, control and decision making with many applications in control and resilience of modern critical infrastructures. We study the strong structural controllability (SSC) of networks, where the external control inputs are injected to only some nodes, namely the leaders. For such systems, one measure of controllability is the dimension of strong structurally controllable subspace (SSCS), which is equal to the smallest possible rank of controllability matrix under admissible coupling weights among the nodes. We compare two tight lower bounds on the dimension of SSCS: one based on the distances of followers to leaders, and the other based on the graph coloring process known as zero forcing. We first show that each of these two bounds can be arbitrarily better than the other in some special cases. We then show that the distance-based lower bound is usually better than the zero-forcing-based bound when the value of the latter is less than the dimensionality of the overall network state, n. On the other hand, we also show that any set of leaders that makes the distance-based bound equal to n necessarily makes the zero-forcing-based bound equal to n (the converse is not true). These results indicate that while the zero-forcing-based approach may be preferable when the focus is only on verifying complete SSC (dimension of SSCS is equal to n), the distance-based approach usually yields a closer bound on the dimension of SSCS when the bounds are both smaller than n. Furthermore, we also present a novel bound based on combining these two approaches, which is always at least as good as, and in some cases strictly greater than, the maximum of the two original bounds. Finally, we support our analysis with numerical results on various graphs. Our results are presented in [1]. 

[1]    Yasin Yazicioglu, Mudassir Shabbir, Waseem Abbas, Xenofon Koutsoukos. “Strong Structural Controllability of Networks: Comparison of Bounds Using Distances and Zero Forcing”, Automatica. 146, 110562, 2022.

Highlight 2: Computation of the Distance-based Bound on Strong Structural Controllability in Networks

We study the problem of computing a tight lower bound on the dimension of the strong structurally controllable subspace (SSCS) in networks with Laplacian dynamics. The bound is based on a sequence of vectors containing the distances between leaders (nodes with external inputs) and followers (remaining nodes) in the underlying network graph. Such vectors are referred to as the distance-to-leaders vectors. We give exact and approximate algorithms to compute the longest sequences of distance-to-leaders vectors, which directly provide distance-based bounds on the dimension of SSCS. The distance-based bound is known to outperform the other known bounds (for instance, based on zero-forcing sets), especially when the network is partially strong structurally controllable. Using these results, we discuss an application of the distance-based bound in solving the leader selection problem for strong structural controllability. Further, we characterize strong structural controllability in path and cycle graphs with a given set of leader nodes using sequences of distance-to-leaders vectors. Finally, we numerically evaluate our results on various graphs. Our results are presented in [2]. 

[2]    Mudassir Shabbir, Waseem Abbas, Yasin Yazicioglu and X. Koutsoukos. “Computation of the Distance-based Bound on Strong Structural Controllability in Networks”, IEEE Transactions on Automatic Control, 2022.

COMMUNITY ENGAGEMENTS

N/A