Algorithms for leader selection in stochastically forced consensus networks

Abstract

We are interested in assigning a pre-specified number of nodes as leaders in order to minimize the mean-square deviation from consensus in stochastically forced networks. This problem arises in several applications including control of vehicular formations and localization in sensor networks. For networks with leaders subject to noise, we show that the Boolean constraints (a node is either a leader or it is not) are the only source of nonconvexity. By relaxing these constraints to their convex hull we obtain a lower bound on the global optimal value. We also use a simple but efficient greedy algorithm to identify leaders and to compute an upper bound. For networks with leaders that perfectly follow their desired trajectories, we identify an additional source of nonconvexity in the form of a rank constraint. Removal of the rank constraint and relaxation of the Boolean constraints yields a semidefinite program for which we develop a customized algorithm well-suited for large networks. Several examples ranging from regular lattices to random graphs are provided to illustrate the effectiveness of the developed algorithms.

Submitted to IEEE Transactions on Automatic Control

References in corpus (4)

• Finding community structure in networks using the eigenvectors of matrices
• Coherence in Large-Scale Networks: Dimension-Dependent Limitations of Local Feedback
• Optimal Control of Vehicular Formations with Nearest Neighbor Interactions
• A Tight Lower Bound on the Controllability of Networks with Multiple Leaders

Cited by in corpus (6)

• Sensor Selection for Estimation with Correlated Measurement Noise
• Graph Distances and Controllability of Networks
• Optimal Network Topology for Effective Collective Response
• Structured decentralized control of positive systems with applications to combination drug therapy and leader selection in directed networks
• Resilient Sensor Placement for Kalman Filtering in Networked Systems: Complexity and Algorithms
• Sensor Selection Cost Optimization for Tracking Structurally Cyclic Systems: a P-Order Solution