Abstract
This paper provides a framework to evaluate the performance of single and double integrator networks over arbitrary directed graphs. Adopting vehicular network terminology, we consider quadratic performance metrics defined by the L2-norm of position and velocity based response functions given impulsive inputs to each vehicle. We exploit the spectral properties of weighted graph Laplacians and output performance matrices to derive a novel method of computing the closed-form solutions for this general class of performance metrics, which include H2-norm based quantities as special cases. We then explore the effect of the interplay between network properties (e.g. edge directionality and connectivity) and the control strategy on the overall network performance. More precisely, for systems whose interconnection is described by graphs with normal Laplacian L, we characterize the role of directionality by comparing their performance with that of their undirected counterparts, represented by the Hermitian part of L. We show that, for single-integrator networks, directed and undirected graphs perform identically. However, for double-integrator networks, graph directionality -- expressed by the eigenvalues of L with nonzero imaginary part -- can significantly degrade performance. Interestingly in many cases, well-designed feedback can also exploit directionality to mitigate degradation or even improve the performance to exceed that of the undirected case. Finally we focus on a system coherence metric -- aggregate deviation from the state average -- to investigate the relationship between performance and degree of connectivity, leading to somewhat surprising findings. For example increasing the number of neighbors on a ω-nearest neighbor directed graph does not necessarily improve performance. Similarly, we demonstrate equivalence in performance between all-to-one and all-to-all communication graphs.
Introduction
In the study of networked dynamical systems, achieving consensus—where a group of autonomous agents like drones or power generators synchronizes to a common state—is a fundamental objective. However, these networks are frequently subjected to external disturbances. A critical engineering challenge lies in quantifying the "performance" of such networks, specifically how effectively they restore synchrony following impulsive perturbations.
While performance metrics are well-understood for undirected graphs characterized by symmetric communication, many real-world applications involve directed graphs. These directed topologies introduce mathematical complexities because their representative Laplacian matrices are non-symmetric and often possess complex eigenvalues. This paper addresses this gap by providing a general framework to evaluate performance across arbitrary directed graph topologies.
Methodology
The researchers model the networked system as a Multiple-Input Multiple-Output (MIMO) system. Performance is quantified using the $L_2$-norm of the system's response to impulse disturbances, which encompasses $H_2$-norm metrics as special cases.
To handle the complexity of directed graphs, the authors employ spectral decomposition, specifically utilizing the Jordan Canonical Form of the graph Laplacian matrix $L$. This transformation allows the high-dimensional, coupled network dynamics to be decomposed into a set of independent, lower-dimensional subsystems.
This decomposition enables the derivation of exact closed-form analytical solutions for performance metrics. By focusing on "normal" Laplacians, the authors can isolate the specific effects of edge directionality by comparing a directed graph to its undirected Hermitian counterpart. The framework was validated using various synthetic topologies, including $\omega$-nearest neighbor graphs, imploding star (all-to-one) configurations, and complete (all-to-all) graphs.
Key Insights and Results
The analysis reveals a fundamental distinction between single and double-integrator networks, formalized in Theorems 1 and 2 which provide the first general closed-form solutions for quadratic performance metrics over arbitrary directed graphs:
- Integrator Dynamics: For single-integrator systems on normal graphs, directionality does not impact performance. Conversely, in double-integrator systems—which account for physical properties like mass and inertia—directionality (manifested as imaginary eigenvalues) typically degrades performance.
- Control Strategy: Interestingly, the degradation caused by directionality is not inevitable. The authors demonstrate that by optimizing position and velocity feedback gains, a directed network can be tuned to outperform its undirected equivalent.
- Connectivity Paradox: The study challenges the intuition that increased connectivity always benefits performance. In directed $\omega$-nearest neighbor networks, adding more neighbors can paradoxically lead to worse performance.
- Structural Equivalence: A significant result is the proof that an "all-to-one" leader-follower structure with only $n-1$ edges can achieve the same coherence performance as an "all-to-all" network with $n(n-1)$ edges.
Conclusion
This work provides a robust mathematical framework for evaluating quadratic performance metrics in directed networks. It highlights that while information "flow" in directed graphs can introduce performance penalties in higher-order systems, strategic control design can mitigate these effects or even leverage directionality for superior performance. Future research will focus on extending these linear frameworks to non-linear dynamics and further exploring the concept of "effective resistance" in the context of directed graph performance.
Summary updated