skip to main content

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, February 13 until 2:00 AM ET on Friday, February 14 due to maintenance. We apologize for the inconvenience.


Title: Scale fragilities in localized consensus dynamics
We consider distributed consensus in networks where the agents have integrator dynamics of order two or higher (n>=2). We assume all feedback to be localized in the sense that each agent has a bounded number of neighbors and consider a scaling of the network through the addition of agents in a modular manner, i.e., without re-tuning controller gains upon addition. We show that standard consensus algorithms, which rely on relative state feedback, are subject to what we term scale fragilities, meaning that stability is lost as the network scales. For high-order agents (n>=3), we prove that no consensus algorithm with fixed gains can achieve consensus in networks of any size. That is, while a given algorithm may allow a small network to converge, it causes instability if the network grows beyond a certain finite size. This holds in families of network graphs whose algebraic connectivity, that is, the smallest non-zero Laplacian eigenvalue, is decreasing towards zero in network size (e.g. all planar graphs). For second-order consensus (n=2) we prove that the same scale fragility applies to directed graphs that have a complex Laplacian eigenvalue approaching the origin (e.g. directed ring graphs). The proofs for both results rely on Routh–Hurwitz criteria for complex-valued polynomials and hold true for general directed network graphs. We survey classes of graphs subject to these scale fragilities, discuss their scaling constants, and finally prove that a sub-linear scaling of nodal neighborhoods can suffice to overcome the issue.  more » « less
Award ID(s):
1932777
PAR ID:
10484640
Author(s) / Creator(s):
; ;
Publisher / Repository:
Elsevier
Date Published:
Journal Name:
Automatica
Volume:
153
Issue:
C
ISSN:
0005-1098
Page Range / eLocation ID:
111046
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We consider the problems of asymptotic stability and robustness in large-scale second-order consensus networks and vehicle platoons in the discrete-time domain. First, we develop a graph-theoretic methodology to design the state feedback law for the second-order consensus networks and vehicle platoons in a discrete-time framework. We analyze the stability of such networks based on algebraic properties of the Laplacian matrices of underlying graphs and each vehicle’s update cycle (also known as the time step). We further provide a necessary and sufficient condition of stability of a linear second-order consensus network in the discrete-time domain. Moreover, we evaluate the robustness of the consensus networks by employing the expected value of the steady-state dispersion of the state of the entire network, also known as squared H2-norm, as a performance measure. We show the connection between performance measures with respect to network size, connectivity, and the update cycle. The main contribution of this work is that we provide a formal framework to quantify the relation between scaling performance measures and restrictions of the vehicles’ update cycles. Specifically, we show that denser networks (i.e., networks with more communications/edges) require faster agents (i.e., smaller update cycles) to outperform or achieve the same level of robustness as sparse networks (i.e., networks with fewer communications/edges). 
    more » « less
  2. This article delves into the challenges of ensuring stability (in some sense) and robustness in large-scale second-order consensus networks (SOCNs) and autonomous vehicle platoons in the discrete-time domain. We propose a graph-theoretic methodology for designing a state feedback law for these systems in a discrete-time framework. By analyzing the behavior of the solutions of the networks based on the algebraic properties of the Laplacian matrices of the underlying graphs and on the value of the update cycle (also known as the time step) of each vehicle, we provide a necessary and sufficient condition for the stability of a linear second-order consensus network in the discrete-time domain. We then perform an $\mathcal {H}_{2}$ -based robustness analysis to demonstrate the relationship between the $\mathcal {H}_{2}$ -norm of the system, network size, connectivity, and update cycles, providing insights into how these factors impact the convergence and robustness of the system. A key contribution of this work is the development of a formal framework for understanding the link between an $\mathcal {H}_{2}$ -based performance measure and the restrictions on the update cycle of the vehicles. Specifically, we show that denser networks (i.e., networks with more communication links) might require faster agents (i.e., smaller update cycles) to outperform or achieve the same level of robustness as sparse networks (i.e., networks with fewer communication links) - see Fig. 1. These findings have important implications for the design and implementation of large-scale consensus networks and autonomous vehicle platoons, highlighting the need for a balance between network density and update cycle speed for optimal performance. We finish the article with results from simulations and experiments that illustrate the effectiveness of the proposed framework in predicting the behavior of vehicle platoons, even for more complex agents with nonlinear dynamics, using Quanser's Qlabs and Qcars. 
    more » « less
  3. null (Ed.)
    Semi-supervised and unsupervised machine learning methods often rely on graphs to model data, prompting research on how theoretical properties of operators on graphs are leveraged in learning problems. While most of the existing literature focuses on undirected graphs, directed graphs are very important in practice, giving models for physical, biological or transportation networks, among many other applications. In this paper, we propose a new framework for rigorously studying continuum limits of learning algorithms on directed graphs. We use the new framework to study the PageRank algorithm and show how it can be interpreted as a numerical scheme on a directed graph involving a type of normalised graph Laplacian . We show that the corresponding continuum limit problem, which is taken as the number of webpages grows to infinity, is a second-order, possibly degenerate, elliptic equation that contains reaction, diffusion and advection terms. We prove that the numerical scheme is consistent and stable and compute explicit rates of convergence of the discrete solution to the solution of the continuum limit partial differential equation. We give applications to proving stability and asymptotic regularity of the PageRank vector. Finally, we illustrate our results with numerical experiments and explore an application to data depth. 
    more » « less
  4. Recent spectral graph sparsificationresearch aims to construct ultra-sparse subgraphs for preserving the original graph spectral (structural) properties, such as the first few Laplacian eigenvalues and eigenvectors, which has led to the development of a variety of nearly linear time numerical and graph algorithms. However, there is very limited progress in the spectral sparsification of directed graphs. In this work, we prove the existence of nearly linear-sized spectral sparsifiers for directed graphs under certain conditions. Furthermore, we introduce a practically efficient spectral algorithm (diGRASS) for sparsifying real-world, large-scale directed graphs leveraging spectral matrix perturbation analysis. The proposed method has been evaluated using a variety of directed graphs obtained from real-world applications, showing promising results for solving directed graph Laplacians, spectral partitioning of directed graphs, and approximately computing (personalized) PageRank vectors.

     
    more » « less
  5. null (Ed.)
    Abstract We introduce a set of novel multiscale basis transforms for signals on graphs that utilize their “dual” domains by incorporating the “natural” distances between graph Laplacian eigenvectors, rather than simply using the eigenvalue ordering. These basis dictionaries can be seen as generalizations of the classical Shannon wavelet packet dictionary to arbitrary graphs, and do not rely on the frequency interpretation of Laplacian eigenvalues. We describe the algorithms (involving either vector rotations or orthogonalizations) to construct these basis dictionaries, use them to efficiently approximate graph signals through the best basis search, and demonstrate the strengths of these basis dictionaries for graph signals measured on sunflower graphs and street networks. 
    more » « less