Algorithms for leader selection in stochastically forced consensus networks

Fu Lin, Makan Fardad, Mihailo R. Jovanovic

Research output: Contribution to journalArticle

80 Citations (Scopus)

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 (which indicate whether a node is a leader) 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.

Original languageEnglish (US)
Article number6780618
Pages (from-to)1789-1802
Number of pages14
JournalIEEE Transactions on Automatic Control
Volume59
Issue number7
DOIs
StatePublished - 2014

Fingerprint

Sensor networks
Trajectories

Keywords

  • Alternating direction method of multipliers (ADMMs)
  • consensus networks
  • convex optimization
  • convex relaxations
  • greedy algorithm
  • leader selection
  • performance bounds
  • semidefinite programming (SDP)
  • sensor selection
  • variance amplification

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Control and Systems Engineering
  • Computer Science Applications

Cite this

Algorithms for leader selection in stochastically forced consensus networks. / Lin, Fu; Fardad, Makan; Jovanovic, Mihailo R.

In: IEEE Transactions on Automatic Control, Vol. 59, No. 7, 6780618, 2014, p. 1789-1802.

Research output: Contribution to journalArticle

@article{9892d6ddb76b44ac8817e279349273cc,
title = "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 (which indicate whether a node is a leader) 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.",
keywords = "Alternating direction method of multipliers (ADMMs), consensus networks, convex optimization, convex relaxations, greedy algorithm, leader selection, performance bounds, semidefinite programming (SDP), sensor selection, variance amplification",
author = "Fu Lin and Makan Fardad and Jovanovic, {Mihailo R.}",
year = "2014",
doi = "10.1109/TAC.2014.2314223",
language = "English (US)",
volume = "59",
pages = "1789--1802",
journal = "IEEE Transactions on Automatic Control",
issn = "0018-9286",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "7",

}

TY - JOUR

T1 - Algorithms for leader selection in stochastically forced consensus networks

AU - Lin, Fu

AU - Fardad, Makan

AU - Jovanovic, Mihailo R.

PY - 2014

Y1 - 2014

N2 - 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 (which indicate whether a node is a leader) 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.

AB - 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 (which indicate whether a node is a leader) 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.

KW - Alternating direction method of multipliers (ADMMs)

KW - consensus networks

KW - convex optimization

KW - convex relaxations

KW - greedy algorithm

KW - leader selection

KW - performance bounds

KW - semidefinite programming (SDP)

KW - sensor selection

KW - variance amplification

UR - http://www.scopus.com/inward/record.url?scp=84903316917&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84903316917&partnerID=8YFLogxK

U2 - 10.1109/TAC.2014.2314223

DO - 10.1109/TAC.2014.2314223

M3 - Article

VL - 59

SP - 1789

EP - 1802

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

SN - 0018-9286

IS - 7

M1 - 6780618

ER -