This paper investigates the joint effect of agent dynamic, network topology and communication data rate on consensusability of linear discrete-time multi-agent systems. Neglecting the finite ...communication data rate constraint and under undirected graphs, a necessary and sufficient condition for consensusability under a common control protocol is given, which explicitly reveals how the intrinsic entropy rate of the agent dynamic and the communication graph jointly affect consensusability. The result is established by solving a discrete-time simultaneous stabilization problem. A lower bound of the optimal convergence rate to consensus, which is shown to be tight for some special cases, is provided as well. Moreover, a necessary and sufficient condition for formationability of multi-agent systems is obtained. As a special case, the discrete-time second-order consensus is discussed where an optimal control gain is designed to achieve the fastest convergence. The effects of undirected graphs on consensability/formationability and optimal convergence rate are exactly quantified by the ratio of the second smallest to the largest eigenvalues of the graph Laplacian matrix. An extension to directed graphs is also made. The consensus problem under a finite communication data rate is finally investigated.
This paper proposes a distributed dual gradient tracking algorithm (DDGT) to solve resource allocation problems over an unbalanced network, where each node in the network holds a private cost ...function and computes the optimal resource by interacting only with its neighboring nodes. Our key idea is the novel use of the distributed push-pull gradient algorithm (PPG) to solve the dual problem of the resource allocation problem. To study the convergence of the DDGT, we first establish the sublinear convergence rate of PPG for non-convex objective functions, which advances the existing results on PPG as they require the strong-convexity of objective functions. Then we show that the DDGT converges linearly for strongly convex and Lipschitz smooth cost functions, and sublinearly without the Lipschitz smoothness. Finally, experimental results suggest that DDGT outperforms existing algorithms.
This paper studies both continuous and discrete time consensus problems for multi-agent systems with linear time-invariant agent dynamics over randomly switching topologies. The switching is governed ...by a time-homogeneous Markov process, whose state corresponds to a possible interaction topology among agents. Necessary and sufficient conditions are derived for achieving consensus under a common control protocol, respectively. It is shown that the effect of switching topologies on consensus is determined by the union of topologies associated with the positive recurrent states of the Markov process. Moreover, the effect of random link failures on discrete time consensus is investigated. The implications and relationships with the existing results are discussed. Finally, the theoretical results are validated via simulations.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
This paper investigates the minimum data rate for mean square stabilizability of linear systems over a lossy digital channel. The packet dropout process of the channel is modeled as a ...time-homogeneous Markov process. To overcome the difficulties induced by the temporal correlations of the packet dropout process and stochastically time-varying data rate due to packet dropouts, a randomly sampled system approach is developed to study the minimum data rate for mean square stabilizability. It is shown that the minimum data rate for scalar systems can be explicitly given in terms of the magnitude of the unstable mode and the transition probabilities of the Markov chain. The number of additional bits required to counter the effect of Markovian packet losses on stabilizability is exactly quantified. Our result contains existing results on data rate and packet dropout rate for stabilizability of linear scalar systems as special cases and provides a means for better bandwidth utilization by jointly considering bits per sample and an effective sampling. Necessary and sufficient conditions on the minimum data rate problem for mean square stabilizability of vector systems are provided respectively and shown to be optimal under some special cases.
This paper is concerned with distributed computation of several commonly used centrality measures in complex networks. In particular, we propose deterministic algorithms, which converge in finite ...time, for the distributed computation of the degree, closeness and betweenness centrality measures in directed graphs. Regarding eigenvector centrality, we consider the PageRank problem as its typical variant, and design distributed randomized algorithms to compute PageRank for both fixed and time-varying graphs. A key feature of the proposed algorithms is that they do not require to know the network size, which can be simultaneously estimated at every node, and that they are clock-free. To address the PageRank problem of time-varying graphs, we introduce the concept of persistent graph, which eliminates the effect of spamming nodes. Moreover, we prove that these algorithms converge almost surely and in the sense of L^p. Finally, the effectiveness of the proposed algorithms is illustrated via extensive simulations using a classical benchmark.
This paper studies the stability of Kalman filtering over a network subject to random packet losses, which are modeled by a time-homogeneous ergodic Markov process. For second-order systems, ...necessary and sufficient conditions for stability of the mean estimation error covariance matrices are derived by taking into account the system structure. While for certain classes of higher-order systems, necessary and sufficient conditions are also provided to ensure stability of the mean estimation error covariance matrices. All stability criteria are expressed by simple inequalities in terms of the largest eigenvalue of the open loop matrix and transition probabilities of the Markov process. Their implications and relationships with related results in the literature are discussed.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
In this paper design methods are given for synchronization control of discrete-time multi-agent systems on directed communication graphs. The graph properties complicate the design of synchronization ...controllers due to the interplay between the eigenvalues of the graph Laplacian matrix and the required stabilizing gains. Two methods are given herein that decouple the design of the synchronizing gains from the detailed graph properties. Both are based on computation of the local control gains using Riccati design; the first is based on an H∞ type Riccati inequality and the second on an H2 type Riccati equation. Conditions are given for synchronization based on the relation of the graph eigenvalues to a bounded circular region in the complex plane that depends on the agent dynamics and the Riccati solution. The notion of ‘synchronizing region’ is used. An example shows the effectiveness of these design methods for guaranteeing synchronization in cooperative discrete-time systems.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
This note investigates the minimum data rate for mean square stabilization of discrete linear time-invariant systems over a lossy channel. The packet dropout process of the channel is modeled as an ...independent and identically distributed process. For general single input systems, the minimum data rate is explicitly given in terms of unstable eigenvalues of the open loop matrix and the packet dropout rate, which clearly reveals the amount of the additional bit rate required to counter the effect of packet dropouts on stabilization. Sufficient data rate conditions for the mean square stabilization of multiple input systems are derived as well.
This paper is concerned with the design of transmission scheduler and estimator for linear discrete-time stochastic systems to reduce the number of measurements to be transmitted from sensor to ...estimator. To this purpose, both controllable and uncontrollable scheduling schemes are considered, respectively. A controllable scheduler is designed as a deterministic function of system measurements, and sequentially decides the transmission of each element of a measurement vector to the estimator. We derive an approximate minimum mean square error (MMSE) estimator. On the other hand, an uncontrollable scheduler means that the transmission of the measurement vector is driven by a random process which is independent of system evolution. The MMSE estimator under this scheduler is cast as the Kalman filtering with intermittent observations. Some stability conditions are established for both the estimators. Finally, illustrative examples are included to validate the theoretical results.
This paper studies system identification of ARMA models whose outputs are subject to finite-level quantization and random packet dropouts. Using the maximum likelihood criterion, we propose a ...recursive identification algorithm, which we show to be strongly consistent and asymptotically normal. We also propose a simple adaptive quantization scheme, which asymptotically achieves the minimum parameter estimation error covariance. The joint effect of finite-level quantization and random packet dropouts on identification accuracy are exactly quantified. The theoretical results are verified by simulations.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
PDF
