Submodularity in Input Node Selection for Networked Linear Systems EFFICIENT ALGORITHMS FOR PERFORMANCE AND CONTROLLABILITY

Networked systems are systems of interconnected components in which the dynamics of each component are influenced by the behavior of neighboring ones. Examples of networked systems include biological networks; critical physical infrastructures, such as power grids and transportation systems; and critical cyber infrastructures, such as the Internet and social networks. A widely studied method for controlling networked systems is to directly control a subset of components, or input nodes, that then steer the remaining nodes to their desired states. This article presents computationally efficient techniques for selecting input nodes to drive the system to a desired state in the presence of time constraints, - disturbances, and changes in network topology. The proposed methods are applicable to problems including selecting generators to damp unstable oscillations in power systems, identifying genes and proteins that regulate biological networks, and executing formation maneuvers in unmanned vehicles. The article also gives an overview of discrete optimization methods and their applications in sensing and control.