Dynamics augmentation for robust structural controllability of bidirected networks

This paper addresses the problem of transforming a structurally controllable system with symmetric dynamics matrix into an r -robust structurally controllable system through strategic modifications to the dynamics matrix (i.e., the problem of dynamics augmentation for robust structural controllability of bidirected networks, r -MARS-B). Unlike existing approaches that focus on input placement design, we investigate the minimal number of zero entries in the system’s dynamics matrix that must be changed to non-zero values to ensure structural controllability is preserved when one input fails. We formulate r -MARS-B as an optimization problem and establish its NP-hardness. For the case r = 1 , we present a greedy algorithm for computing approximate solutions using a path-stitching approach, and show that its approximation ratio is unbounded. We provide numerical examples to illustrate our findings and analyze the performance of our algorithm.