2016/04/24 by Patterson, Stacy, McGlohon, Neil, Dyagilev, Kirill · 1 citation
#FOS: Electrical engineering #FOS: Mathematics #Optimization and Control (math.OC) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · doi:10.48550/arxiv.1604.07094
We study the problem of optimal leader selection in consensus networks under two performance measures (1) formation coherence when subject to additive perturbations, as quantified by the steady-state variance of the deviation from the desired trajectory, and (2) convergence rate to a consensus value. The objective is to identify the set of k leaders that optimizes the chosen performance measure. In both cases, an optimal leader set can be found by an exhaustive search over all possible leader sets; however, this approach is not scalable to large networks. In recent years, several works have proposed approximation algorithms to the k-leader selection problem, yet the question of whether there exists an efficient, non-combinatorial method to identify the optimal leader set remains open. This work takes a first step towards answering this question. We show that, in one-dimensional weighted graphs, namely path graphs and ring graphs, the k-leader selection problem can be solved in polynomial time (in both k and the network size n). We give an O(n3) solution for optimal k-leader selection in path graphs and an O(kn3) solution for optimal k-leader selection in ring graphs.