Submodularity in Dynamics and Control of Networked Systems

Thesis (Ph.D.)--University of Washington, 2014Controlling a networked dynamical system to reach a desired state is a fundamental challenge in applications including transportation, energy, social, and biological systems. One scalable approach to controlling such systems is to directly control the states of a subset of leader nodes, while relying on local interactions to steer the remaining nodes towards their desired states. The choice of leader nodes is known to affect system metrics including robustness to noise, rate of convergence to a desired state, and controllability of the system. Selecting an optimal subset of leader nodes, however, is inherently a combinatorial problem, making optimal leader node selection intractable in general. This thesis presents a submodular optimization framework to selecting leader nodes for control of networked systems. We investigate the problem of selecting a subset of leader nodes in order to minimize node state errors due to noise in the communication links between nodes. We prove that the error due to link noise is a supermodular function of the set of leader nodes, leading to the first polynomial-time algorithms for minimizing error due to link noise with provable optimality bounds. We develop our approach for networks with static topologies, as well as dynamic topologies due to random link failures, switching between predefined topologies, and arbitrary mobility. We study selecting leader nodes in order to minimize convergence error, defined as the error in the intermediate node states prior to reaching their desired values. We derive upper bounds for a class of convergence error metrics based on the hitting time of random walk on the network, which we prove to be a supermodular function of the set of input nodes. We present polynomial-time algorithms for minimizing convergence error with provable optimality bounds, for static as well as dynamic networks. Efficient algorithms have recently been proposed for selecting leader nodes to satisfy controllability, defined as the ability to drive the non-input nodes from any initial state to any desired state in finite time. These algorithms, however, do not incorporate performance criteria including robustness to noise and convergence rate. We study the problem of leader selection for joint performance and controllability, and prove that controllability can be formulated as a matroid constraint on the set of leader nodes. We propose efficient algorithms with provable optimality gap for selecting leader nodes for joint performance and controllability, and characterize the submodular structure of the largest controllable subgraph of a network. We also investigate selecting input nodes for guaranteeing synchronization in networked systems. Using the widely-studied Kuramoto model of nonlinear phase-coupled oscillators, we develop novel threshold-based conditions for a set of input nodes to ensure synchronization of the remaining nodes from almost any initial state (global practical synchronization). We formulate selection of input nodes to satisfy these conditions as a submodular optimization problem, leading efficient algorithms for selecting the minimum-size input nodes for synchronization. Finally, we study algorithms for distributed online submodular maximization, with leader selection in distributed networks as one motivating application. We present algorithms that achieve provable optimality bounds while minimizing computation, communication, and storage overhead at the nodes. Our approach is developed for unconstrained optimization of non-monotone submodular functions, as well as cardinality-constrained monotone submodular maximization