Submodularity in Systems with Higher Order Consensus with Absolute Information
For researchers in multi-agent systems and network control, this work provides a theoretical foundation and efficient algorithm for leader selection in higher-order consensus, though the results are incremental extensions of known submodular optimization techniques.
This paper studies m-th order consensus systems with stochastic perturbations and absolute information from leader nodes, deriving stability conditions and coherence expressions for second, third, and fourth order systems. It proves that coherence-based set functions are submodular, enabling a greedy algorithm that selects leader sets with near-optimal coherence, and empirically demonstrates its performance.
We investigate the performance of m-th order consensus systems with stochastic external perturbations, where a subset of leader nodes incorporates absolute information into their control laws. The system performance is measured by its coherence, an $H_2$ norm that quantifies the total steady-state variance of the deviation from the desired trajectory. We first give conditions under which such systems are stable, and we derive expressions for coherence in stable second, third, and fourth order systems. We next study the problem of how to identify a set of leaders that optimizes coherence. To address this problem, we define set functions that quantify each system's coherence and prove that these functions are submodular. This allows the use of an efficient greedy algorithm that to find a leader set with which coherence is within a constant bound of optimal. We demonstrate the performance of the greedy algorithm empirically, and further, we show that the optimal leader sets for the different orders of consensus dynamics do not necessarily coincide.