Search

A directed acyclic graph (DAG) is a common topology in biological, engineering, and social networks. A network topology is critical in determining a collective behavior of a network dynamic system. For example, the convergence rate of a consensus behavior in a multiagent system relies on the eigenvalues of the Laplacian associated with the network topology. This article aims to analyze the influence of adding a reverse edge into a DAG on convergence rate. It reveals the existence of the so-called interfering reverse edges; adding one single edge in this category can reduce the so-called dominant convergence rate even for a large network. More specifically, a necessary and sufficient condition of an interfering reverse edge is explicitly constructed. According to the condition, a computationally efficient method is proposed to assess an interfering reverse edge. [ABSTRACT FROM AUTHOR]

In this article, we present a Lyapunov framework for establishing stability with respect to a compact set for a nested interconnection of nonlinear dynamical systems ordered from slow to fast according to their convergence rates, where each of the dynamics is influenced only by the slower dynamics and the successive fastest one. The proposed approach explicitly considers more than two time scales, it does not require modeling multiple time scales via scalar time constants, and provides analytic bounds that make ad-hoc time-scale separation arguments rigorous. Motivated by the technical results, we develop a novel control strategy for a grid-forming power converter that consists of an inner cascaded two-degree-of-freedom controller and dispatchable virtual oscillator control as a reference model. The resulting closed-loop converter-based ac power system is in the form of a nested system with multiple time scales. We apply our technical results to obtain explicit bounds on the controller set points, branch powers, and control gains that guarantee almost global asymptotic stability of the multiconverter ac power system with respect to a prespecified solution of the ac power flow equations. Finally, we validate the performance of the proposed control structure in a case study using a high-fidelity simulation with detailed hardware validated converter models. [ABSTRACT FROM AUTHOR]

This article concerns the evolution of multiagent systems on networks over Riemannian manifolds. The motion of each agent is governed by the gradient descent flow of a disagreement function that is a sum of (squared) distances between pairs of communicating agents. Two metrics are considered: geodesic distances and chordal distances for manifolds that are embedded in an ambient Euclidean space. We show that networks that, roughly speaking, are dominated by a large cycle yield multistable systems if the manifold is multiply connected or contains a closed geodesic that is of locally minimum length in a space of closed curves. This result summarizes previous results on the stability of splay or twist state equilibria of the Kuramoto model on S1 and its generalization, the quantum sync model on SO(n). It also extends them to the Lohe model on U(n). [ABSTRACT FROM AUTHOR]

This article addresses the problem of simultaneous distributed state estimation, and control of linear systems with linear state feedback, subjected to process, and measurement noise, under the constraints of quantized, and rate-limited network data transmission. In the set-up adopted, sensors and actuators communicate through a network with a strongly connected topology. Unlike the case of centralized linear systems, for which the separation principle holds, the above practical assumption prevents the separate design of observers, and controller because each of the nodes does not necessarily have access to the control inputs generated at all the other nodes. We derive a linear distributed Luenberger observer, and a set of sufficient conditions that guarantee ultimate boundedness of the estimation error, and system state vectors, with bounds that depend on the $\mathcal {L}_{\infty }$ norm of the noise signals, and the number of bits used in the transmissions. A numerical example illustrates the performance and effectiveness of the proposed algorithm in controlling a network of open-loop unstable systems. [ABSTRACT FROM AUTHOR]

We characterize a class of systems for which the H-infinity optimal control problem can be simplified in a way that enables sparse solutions and efficient computation. For a subclass of the systems, an optimal controller can be explicitly expressed in terms of the matrices of the system's state-space representation. In many applications, the controller given by this formula, which is static, can be implemented in a decentralized or distributed fashion. Examples are temperature dynamics in buildings, water irrigation, and electrical networks. [ABSTRACT FROM AUTHOR]

This article deals with dynamical networks in which the relations between node signals are described by proper transfer functions and external signals can influence each of the node signals. We are interested in graph-theoretic conditions for identifiability of such dynamical networks, where we assume that only a subset of nodes is measured but the underlying graph structure of the network is known. This problem has recently been investigated from a generic viewpoint. Roughly speaking, generic identifiability means that the transfer functions in the network can be identified for “almost all” network matrices associated with the graph. In this article, we investigate the stronger notion of identifiability for all network matrices. To this end, we introduce a new graph-theoretic concept called the graph simplification process. Based on this process, we provide necessary and sufficient topological conditions for identifiability. Notably, we also show that these conditions can be verified by polynomial time algorithms. Finally, we explain how our results generalize existing sufficient conditions for identifiability. [ABSTRACT FROM AUTHOR]

The issue of synchronization in the power grid is receiving renewed attention, as new energy sources with different dynamics enter the picture. Global metrics have been proposed to evaluate performance and calculated under highly simplified assumptions. In this article, we extend this approach to more realistic network scenarios and more closely connect it with metrics used in power engineering practice. In particular, our analysis covers networks with generators of heterogeneous ratings and richer dynamic models of machines. Under a suitable proportionality assumption in the parameters, we show that the step response of bus frequencies can be decomposed in two components. The first component is a system-wide frequency that captures the aggregate grid behavior, and the residual component represents the individual bus frequency deviations from the aggregate. Using this decomposition, we define—and compute in closed form—several metrics that capture dynamic behaviors that are of relevance for power engineers. In particular, using the system frequency, we define industry-style metrics (Nadir, RoCoF) that are evaluated through a representative machine. We further use the norm of the residual component to define a synchronization cost that can appropriately quantify interarea oscillations. Finally, we employ robustness analysis tools to evaluate deviations from our proportionality assumption. We show that the system frequency still captures the grid steady-state deviation, and becomes an accurate reduced-order model of the grid as the network connectivity grows. Simulation studies with practically relevant data are included to validate the theory and further illustrate the impact of network structure and parameters on synchronization. Our analysis gives conclusions of practical interest, sometimes challenging the conventional wisdom in the field. [ABSTRACT FROM AUTHOR]

One of the most important problems in the field of distributed optimization is the problem of minimizing a sum of local convex objective functions over a networked system. Most of the existing work in this area focuses on developing distributed algorithms in a synchronous setting under the presence of a central clock, where the agents need to wait for the slowest one to finish the update, before proceeding to the next iterate. Asynchronous distributed algorithms remove the need for a central coordinator, reduce the synchronization wait, and allow some agents to compute faster and execute more iterations. In the asynchronous setting, the only known algorithms for solving this problem could achieve an either linear or sublinear rate of convergence. In this paper, we build upon the existing literature to develop and analyze an asynchronous Newton-based method to solve a penalized version of the problem. We show that this algorithm guarantees almost sure convergence with a global linear and local quadratic rate in expectation. Numerical studies confirm the superior performance of our algorithm against other asynchronous methods. [ABSTRACT FROM AUTHOR]

Several algorithms in prior literature have been proposed, which guarantee the consensus of normally behaving agents in a network that may contain adversarially behaving agents. These algorithms guarantee that the consensus value lies within the convex hull of initial normal agents’ states, with the exact consensus value possibly being unknown. In leader-follower consensus problems, however, the objective is for normally behaving agents to track a reference state that may take on values outside of this convex hull. In this paper, we present methods for agents in time-varying graphs with discrete-time dynamics to resiliently track a reference state propagated by a set of leaders, despite a bounded subset of the leaders and followers behaving adversarially. Our results are demonstrated through simulations. [ABSTRACT FROM AUTHOR]

In this note, robust consensus for a class of nonlinear second-order multiagent systems with uncertainties is investigated from an event-triggered control approach. An event-triggered distributed control protocol is designed to achieve semiglobal robust leaderless consensus for directed graphs. To guarantee the feasibility of the proposed scheme, the event-based consensus is converted to an event-based stabilization for analysis. Zeno behavior is avoided under the proposed event-triggered mechanism. The effectiveness of the proposed event-triggered scheme is demonstrated by numerical simulations. [ABSTRACT FROM AUTHOR]

This paper develops some basic principles to study autocatalytic networks and exploit their structural properties in order to characterize their inherent fundamental limits and tradeoffs. In a dynamical system with autocatalytic structure, the system's output is necessary to catalyze its own production. Our study has been motivated by a simplified model of a glycolysis pathway. First, the properties of this class of pathways are investigated through a network model, which consists of a chain of enzymatically catalyzed intermediate reactions coupled with an autocatalytic component. We explicitly derive a hard limit on the minimum achievable $\mathcal L_2$ -gain disturbance attenuation and a hard limit on its minimum required output energy. Then, we show how these resulting hard limits lead to some fundamental tradeoffs between transient and steady-state behavior of the network and its net production. [ABSTRACT FROM AUTHOR]

This paper deals with the coordination problems over noisy communication channels. We consider a scenario where the communication between network nodes is corrupted by unknown-but-bounded noise. We introduce a novel coordination scheme which ensures: 1) boundedness of the state trajectories and 2) a linear map from the noise to the nodes disagreement value. The proposed scheme does not require any global information on the network parameters and/or the operating environment (the noise characteristics). Moreover, network nodes can sample at independent rates and in an aperiodic manner. [ABSTRACT FROM AUTHOR]

We analyze performance of a class of time-delay first-order consensus networks from a graph topological perspective and present methods to improve it. Performance is measured by network's square of $\mathcal {H}_2$ norm and it is derived in closed form. Moreover, we prove that performance is a convex function of the coupling weights of the underlying graph. We demonstrate that the effect of time-delay reincarnates itself in the form of non-monotonicity, leading to counter-intuitive behaviors of the performance as a function of graph topology. For the network design problem, we propose a tight but simple approximation of the performance measure in order to achieve lower complexity in our problems by eliminating the computationally expensive need for eigendecomposition. More specifically, we discuss three $\mathcal {H}_2$ -based optimal design methods to enhance performance. The proposed algorithms provide near-optimal solutions with improved computational complexity as opposed to existing methods in the literature. [ABSTRACT FROM AUTHOR]

Much recent research has dealt with the identifiability of a dynamical network in which the node signals are connected by causal linear transfer functions and are excited by known external excitation signals and/or unknown noise signals. A major research question concerns the identifiability of the whole network—topology and all transfer functions—from the measured node signals and external excitation signals. So far all results on the identifiability of the whole network have assumed that all node signals are measured. This paper presents the first results for the situation where not all node signals are measurable, under the assumptions that, first, the topology of the network is known, and, second, each node is excited by a known external excitation. Using graph theoretical properties, we show that the transfer functions that can be identified depend essentially on the topology of the paths linking the corresponding vertices to the measured nodes. A practical outcome is that, under those assumptions, a network can often be identified using only a small subset of node measurements. [ABSTRACT FROM AUTHOR]

We consider a distributed online optimization problem where, at each time, a group of agents choose their individual states, after which an individual cost function is revealed to each of them. The whole network then faces a regret according to the cumulative sum of costs incurred by the agents’ chosen states, and each agent faces an individual regret according to the cumulative sum of costs incurred by the agent's state estimation, perceived as the whole network's chosen state. In order to tackle the minimization of the individual regret using only local information, we assume that the group of agents communicate over a fixed undirected connected graph. We then propose an online version of the alternating direction method of multipliers algorithm, distributed over the communication graph, which allows each agent to drive its individual average regret over time to zero. [ABSTRACT FROM AUTHOR]

The finite-time attitude synchronization problem is considered in this paper, where the rotation of each rigid body is expressed using the axis-angle representation. Two discontinuous and distributed controllers using the vectorized signum function are proposed, which guarantee almost global and local convergence, respectively. Filippov solutions and nonsmooth analysis techniques are adopted to handle the discontinuities. Sufficient conditions are provided to guarantee finite-time convergence and boundedness of the solutions. Simulation examples are provided to verify the performances of the control protocols designed in this paper. [ABSTRACT FROM AUTHOR]

A proper abstraction of a large-scale linear consensus network with a dense coupling graph is one whose number of coupling links is proportional to its number of subsystems and its performance is comparable to the original network. Optimal design problems for an abstracted network are more amenable to efficient optimization algorithms. From the implementation point of view, maintaining such networks are usually more favorable and cost-effective due to their reduced communication requirements across a network. Therefore, approximating a given dense linear consensus network by a suitable abstract network is an important analysis and synthesis problem. In this paper, we develop a framework to compute an abstraction of a given large-scale linear consensus network with guaranteed performance bounds using a nearly linear time algorithm. First, the existence of abstractions of a given network is proven. Then, we present an efficient and fast algorithm for computing a proper abstraction of a given network. Finally, we illustrate the effectiveness of our theoretical findings via several numerical simulations. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the performance analysis and synthesis of distributed system throttlers (DST). A throttler is a mechanism that limits the flow rate of incoming metrics, e.g., byte per second, network bandwidth usage, capacity, traffic, etc. This can be used to protect a service's backend/clients from getting overloaded, or to reduce the effects of uncertainties in demand for shared services. We study performance deterioration of DSTs subject to demand uncertainty. We then consider network synthesis problems that aim to improve the performance of noisy DSTs via communication link modifications as well as server update cycle modifications. [ABSTRACT FROM PUBLISHER]

We study formation control problems. Our approach is to let a group of systems maximize their pairwise distances while bringing them all to a given submanifold, determining the shape of the formation. The algorithm we propose allows us to initialize the positions of the individual systems in the ambient space of the given submanifold but brings them to the desired formation asymptotically in a stable fashion. Our control inherently consists of a distributed component, maximizing the pairwise distances, and a decentralized component, asymptotically stabilizing the submanifold. We establish a graph-theoretical interpretation of the equilibria that our control enforces and extends our approach to systems living on the special Euclidean group. Throughout this paper, we illustrate our approach on different examples. [ABSTRACT FROM AUTHOR]

In this work, we study Static and Dynamic Games on Large Networks of interacting agents, assuming that the players have some statistical description of the interaction graph, as well as some local information. Inspired by Statistical Physics, we consider statistical ensembles of games and define a Probabilistic Approximate equilibrium notion for such ensembles. A Necessary Information Complexity notion is introduced to quantify the minimum amount of information needed for the existence of a Probabilistic Approximate equilibrium. We then focus on some special classes of games for which it is possible to derive upper and/or lower bounds for the complexity. At first, static and dynamic games on random graphs are studied and their complexity is determined as a function of the graph connectivity. In the low complexity case, we compute Probabilistic Approximate equilibrium strategies. We then consider static games on lattices and derive upper and lower bounds for the complexity, using contraction mapping ideas. A LQ game on a large ring is also studied numerically. Using a reduction technique, approximate equilibrium strategies are computed and it turns out that the complexity is relatively low. [ABSTRACT FROM PUBLISHER]

We investigate performance deterioration in linear consensus networks subject to external stochastic disturbances. The expected value of the steady state dispersion of the states of the network is adopted as a performance measure. We develop a graph-theoretic methodology to relate structural specifications of the coupling graph of a linear consensus network to its performance measure. We explicitly quantify several inherent fundamental limits on the best achievable levels of performance and show that these limits of performance are emerged only due to the specific interconnection topology of the coupling graphs. Furthermore, we discover some of the inherent fundamental tradeoffs between notions of sparsity and performance in linear consensus networks. [ABSTRACT FROM AUTHOR]

While the vast majority of work on consensus and synchronization considers only collaborative interactions among the agents, antagonistic interactions may play important roles in coordination of social systems. In this work, we define a composite model over a stochastically-switching network capturing both collaborative and antagonistic interactions. We consider a general class of agents, so-called conspecifics, defined in terms of a common distribution for their interaction capacity and the weights they ascribe to interactions. We find closed form expressions for necessary and sufficient conditions for consensus, the rate of convergence to consensus, and conditions for stochastic synchronization. This model is further extended to composite topologies capable of capturing any number of independent interaction modes. Results demonstrate the presence of antagonistic interactions may help the system to achieve consensus and synchronization which is not possible in presence of only collaborative interactions and, at times, enables convergence at a faster rate. [ABSTRACT FROM AUTHOR]