Search

In this paper, the question of expected time to convergence is addressed for unbiased quantized consensus on undirected connected graphs, and some strong results are obtained. The paper first provides a tight expression for the expected convergence time of the unbiased quantized consensus over general but fixed networks. It is shown that the maximum expected convergence time lies within a constant factor of the maximum hitting time of an appropriate lazy random walk, using the theory of harmonic functions for reversible Markov chains. Following this, and using electric resistance analogy of the reversible Markov chains, the paper provides an upper bound of $O(nmD\log n)$ for the expected convergence time to consensus, where $n$, $m$ and $D$, denote, respectively, the number of nodes, the number of edges, and the diameter of the network. Moreover, the paper shows that the above upper bound is tight up to a factor of $\log n$ for some simple graphs such as line graph and cycle. Finally, the results are extended to bound the expected convergence time of the underlying dynamics in time-varying networks. Modeling such dynamics as the evolution of a time inhomogeneous Markov chain, the paper derives an upper bound for the expected convergence time of the dynamics using the spectral representation of the networks. This upper bound is significantly better than earlier ones given for different quantized consensus protocols over time-varying graphs. [ABSTRACT FROM PUBLISHER]

Mathematically, the Rayleigh quotient is defined as the quadratic function of a symmetric matrix and a nonzero (usually unconstrained) variable vector. In this paper, we consider the constrained Rayleigh quotient, in which the variable vector has the orthogonality constraint, i.e., it is constrained to be orthogonal to a nonzero vector, this nonzero vector is called the orthogonality-constraint vector (or abbreviated as the OC-vector) for the variable vector. The matrix for the Rayleigh quotient is an eigen-balanced (EB) Laplacian matrix. A tighter lower bound of the constrained Rayleigh quotient has many implications in mathematics as well as in cooperative control problems. The main contributions in this paper are as follows: First, we provide the greatest lower bound (or the infimum) of the constrained Rayleigh quotient with respect to a general OC-vector and the EB Laplacian matrix, whose results are novel and better than the existing results. Then, we interpret the physical meaning of our results in an insightful geometric form and characterize the properties of the results. Finally, as an example to illustrate the merit of the tighter lower bound of the constrained Rayleigh quotient, we consider the scale of the agents driving by a fundamental consensus protocol, and show that the convergence rate of the agents’ scale is characterized by the greatest lower bound of the constrained Rayleigh quotient. [ABSTRACT FROM AUTHOR]

This paper analyzes distributed control protocols for first- and second-order networked dynamical systems. We propose a class of nonlinear consensus controllers where the input of each agent can be written as a product of a nonlinear gain, and a sum of nonlinear interaction functions. By using integral Lyapunov functions, we prove the stability of the proposed control protocols, and explicitly characterize the equilibrium set. We also propose a distributed proportional-integral (PI) controller for networked dynamical systems. The PI controllers successfully attenuate constant disturbances in the network. We prove that agents with single-integrator dynamics are stable for any integral gain, and give an explicit tight upper bound on the integral gain for when the system is stable for agents with double-integrator dynamics. Throughout the paper we highlight some possible applications of the proposed controllers by realistic simulations of autonomous satellites, power systems and building temperature control. [ABSTRACT FROM AUTHOR]

In this paper, we present a generalization of a recent result on the almost sure consensus for networks affected by relative-state-dependent measurement noise. Specifically, we give two sufficient conditions for the synchronization of networks of diffusively coupled nonlinear nodes affected by certain state-dependent noise diffusion processes. We use this condition to study the onset of synchronization in a network of Lorenz systems and collective opinion dynamics. [ABSTRACT FROM AUTHOR]

In this paper, we consider a discrete-time consensus network, and assume that one of the agents acts as a leader and injects an input signal to improve the overall system performance, in particular to increase the speed of convergence to consensus or to achieve finite-time consensus. Two possible control protocols are proposed, and the characteristic polynomials of the resulting closed-loop systems are determined. These results allow us to investigate the consensus and finite-time consensus of the overall systems. Open problems and future research directions conclude this paper. [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]

This paper studies the quantized feedback stabilization problem for nonlinear systems with external disturbance. A dynamic quantizer with a quantization parameter is implemented in this paper. To extract more information, the quantization parameter is updated according to an updating protocol at the discrete-time instants. Three quantization cases are studied in this paper, i.e., state quantization case, input quantization case, and output quantization case. Based on the updating protocol and Lyapunov approach, sufficient conditions are developed for quantized feedback stabilization of the closed-loop system. [ABSTRACT FROM AUTHOR]

This paper develops a measure-theoretic approach for generating the collective behavior of flocking of planar autonomous vehicles under all-to-all communication scheme. To obtain flocking protocol, we formulate the notion of state of styled-velocity flocking for the target state of a design problem instead of considering solution-ansatzes. This notion captures a broader class of flocking behaviors of non-parallel motions, as well as embodies the two important performances of cohesion maintenance and collision avoidance. To pose a control design problem, a measure-valued transition equation is obtained to induce an auxiliary one-body continuum-model from the exact multi-body particle-model of the collective system. The design problem is then formulated on the auxiliary continuum-model, and a systematic design procedure is presented. The state of styled-velocity flocking of the particle-model under the obtained flocking protocol is then verified with an important result on the continuous dependence on initial data of solutions of the measured-valued transition equation. Application to elliptical flocking of mobile robots is presented to illustrate the novelty of the presented theory. [ABSTRACT FROM PUBLISHER]

In this paper, Nash equilibrium seeking among a network of players is considered. Different from many existing works on Nash equilibrium seeking in noncooperative games, the players considered in this paper cannot directly observe the actions of the players who are not their neighbors. Instead, the players are supposed to be capable of communicating with each other via an undirected and connected communication graph. By a synthesis of a leader-following consensus protocol and the gradient play, a distributed Nash equilibrium seeking strategy is proposed for the noncooperative games. Analytical analysis on the convergence of the players’ actions to the Nash equilibrium is conducted via Lyapunov stability analysis. For games with nonquadratic payoffs, where multiple isolated Nash equilibria may coexist in the game, a local convergence result is derived under certain conditions. Then, a stronger condition is provided to derive a nonlocal convergence result for the nonquadratic games. For quadratic games, it is shown that the proposed seeking strategy enables the players’ actions to converge to the Nash equilibrium globally under the given conditions. Numerical examples are provided to verify the effectiveness of the proposed seeking strategy. [ABSTRACT FROM AUTHOR]

This paper considers an unconstrained collaborative optimization of a sum of convex functions, where agents make decisions using local information in the presence of random interconnection topologies. We recast the problem as minimization of the sum of convex functions over a constraint set defined as the set of fixed-value points of a random operator derived from weighted matrices of random graphs. We show that the derived random operator has nonexpansivity property; therefore, this formulation does not need the distribution of random communication topologies. Hence, it includes random networks with/without asynchronous protocols. As an extension of the problem, we define a novel optimization problem, namely minimization of a convex function over the fixed-value point set of a nonexpansive random operator. We propose a discrete-time algorithm using diminishing step size for converging almost surely and in mean square to the global solution of the optimization problem under suitable assumptions. Consequently, as a special case, it reduces to a totally asynchronous algorithm for the distributed optimization problem. We show that fixed-value point is a bridge from deterministic analysis to random analysis of the algorithm. Finally, a numerical example illustrates the convergence of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, the unscented Kalman filtering (UKF) problem is investigated for a class of general nonlinear systems with stochastic uncertainties under communication protocols. A modified unscented transformation is put forward to account for stochastic uncertainties caused by modeling errors. For preventing data collisions and mitigating communication burden, the round-robin protocol and the weighted try-once-discard protocol are, respectively, introduced to regulate the data transmission order from sensors to the filter. Then, by employing two kinds of data-holding strategies (i.e., zero-order holder and zero input) for those nodes without transmission privilege, two novel protocol-based measurement models are formulated. Subsequently, by resorting to the sigma point approximation method, two resource-saving UKF algorithms are developed, where the impact from the underlying protocols on the filter design is explicitly quantified. Finally, compared with the protocol-based extended Kalman filtering algorithms, a simulation example is presented to demonstrate the effectiveness of the proposed protocol-based UKF algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we study fundamental performance limitations of distributed feedback control in large-scale networked dynamical systems. Specifically, we address the question of whether dynamic feedback controllers perform better than static (memoryless) ones when subject to locality constraints. We consider distributed linear consensus and vehicular formation control problems modeled over toric lattice networks. For the resulting spatially invariant systems, we study the large-scale asymptotics (in network size) of global performance metrics that quantify the level of network coherence. With static feedback from relative state measurements, such metrics are known to scale unfavorably in lattices of low spatial dimensions, preventing, for example, a one-dimensional string of vehicles to move like a rigid object. We show that the same limitations in general apply also to dynamic feedback control that is locally of first order. This means that the addition of one local state to the controller gives a similar asymptotic performance to the memoryless case. This holds unless the controller can access noiseless measurements of its local state with respect to an absolute reference frame, in which case the addition of controller memory may fundamentally improve performance. In simulations of platoons with 20–200 vehicles, we show that the performance limitations we derive manifest as unwanted accordionlike motions. Similar behaviors are to be expected in any network that is embeddable in a low-dimensional toric lattice, and the same fundamental limitations would apply. To derive our results, we present a general technical framework for the analysis of stability and performance of spatially invariant systems in the limit of large networks. [ABSTRACT FROM AUTHOR]

This paper is concerned with the moving horizon estimation problem for a class of discrete time-delay systems under the Round-Robin (RR) protocol. The communication between the sensor nodes and the remote state estimator is implemented via a shared network, where only one sensor node is permitted to transmit data at each time instant for the purpose of preventing data collisions. The RR protocol is utilized to orchestrate the transmission order of sensor nodes, under which the selected node obtaining access to the network could be modeled by a periodic function. A lifting technology is introduced to reformulate the system model into a linear system without delays. The aim of the addressed problem is to develop a moving horizon estimator such that the estimation error is ultimately bounded. A sufficient condition is established to ensure the ultimate boundedness in terms of a matrix inequality. Within the established theoretical framework, two optimization problems are proposed to calculate the corresponding estimator parameters according to two different performance requirements (e.g., the smallest ultimate bound and the fastest decay rate). Finally, simulation examples are given to illustrate the effectiveness of the estimator design scheme. [ABSTRACT FROM AUTHOR]

This paper considers the fully distributed tracking consensus problem for general nonlinear multiagent systems with a leader whose control input is nonzero and bounded. First, a new class of distributed state observer for the leader is proposed without the knowledge of the upper bound of the leader's input. Then, the situations that followers are affected by disturbances with unknown upper bound or disturbances generated by exosystems are investigated. Specifically, two distributed control protocols based on the distributed state observer, neural networks, and adaptive laws are proposed. Finally, simulation examples are provided to illustrate the theoretical results. [ABSTRACT FROM AUTHOR]

This paper studies the distributed event-triggered tracking control problem of general linear multiagent systems with a dynamic leader, whose control input might be nonzero and unknown. The existence of the leader's unknown input renders the network heterogeneous and largely increases the difficulty of designing distributed event-based protocols. To solve this problem, we establish a novel asynchronous edge-based event-triggered mechanism, under which communication is not required from the leader to its out-neighbors (informed followers) or by the edge, unless the embedded triggering functions are triggered. Using this mechanism, we design a static asynchronous edge-based event-triggered protocol and an adaptive one, both of which guarantee the achievement of the leader–follower consensus and the exclusion of the Zeno behavior. Note that the adaptive event-based protocol is fully distributed, requiring no global information of the network topology, such as the network's scale, the smallest nonzero eigenvalue of the Laplacian matrix, and the upper bound of the leader's control input. [ABSTRACT FROM AUTHOR]

This paper studies the time-varying output formation (TVOF) tracking problems for heterogeneous linear multiagent systems with a nonautonomous leader on directed topologies, where the dynamics of the agents can be different in the aspects of both parameters and dimensions, and the leader can have unknown control input. A TVOF tracking protocol and a design algorithm are presented using the neighboring interaction. In the proposed protocol, a distributed observer with adaptive updating mechanism is constructed for each follower to asymptotically estimate the state of the leader under the influences of the leader's unknown input first. Then, a local formation controller is presented by utilizing the distributed observer, the local state observer, and the desired formation vector. Based on the Lyapunov stability theory, it is proved that the expected TVOF tracking can be accomplished by the heterogeneous multiagent systems in the presence of the leader's unknown input. Furthermore, a continuous TVOF tracking protocol with $\sigma$ -modification adaptive law is proposed to avoid the large chattering phenomenon. [ABSTRACT FROM AUTHOR]

Consensus is fundamental for distributed systems since it underpins key functionalities of such systems ranging from distributed information fusion, decision making, to decentralized control. In order to reach an agreement, existing consensus algorithms require each agent to exchange explicit state information with its neighbors. This leads to the disclosure of private state information, which is undesirable in cases where privacy is of concern. In this paper, we propose a novel approach for undirected networks, which can enable secure and privacy-preserving average consensus in a decentralized architecture in the absence of an aggregator or third party. By leveraging partial homomorphic cryptography to embed secrecy in pairwise interaction dynamics, our approach can guarantee convergence to the consensus value (subject to a quantization error) in a deterministic manner without disclosing a node's state to its neighbors. We provide a new privacy definition for dynamical systems, and give a new framework to rigorously prove that a node's privacy can be protected as long as it has at least one legitimate neighbor, which follows the consensus protocol faithfully without attempts to infer other nodes’ states. In addition to enabling resilience to passive attackers aiming to steal state information, the approach also allows easy incorporation of defending mechanisms against active attackers who try to alter the content of exchanged messages. Furthermore, in contrast to existing noise-injection-based privacy-preserving mechanisms that have to reconfigure the entire network when the topology or number of nodes varies, our approach is applicable to dynamic environments with time-varying coupling topologies. This secure and privacy-preserving approach is also applicable to weighted average consensus as well as maximum/minimum consensus under a new update rule. Numerical simulations and comparison with existing approaches confirm the theoretical results. Experimental results on a Raspberry-Pi board based microcontroller network are also presented to verify the effectiveness and efficiency of the approach. [ABSTRACT FROM AUTHOR]

In this paper a distributed algorithm for clock synchronization is proposed. This algorithm is based on an extension of the linear consensus algorithm which is able to synchronize a family of identical double integrators. Since in reality the various clocks may have different drifts, the algorithm needs to be designed in such a way that it works correctly also in case of heterogeneous double integrators. We start by reviewing an unrealistic synchronous implementation of the clock synchronization algorithm, that has been recently proposed in the context of noisy double integrators. The main contribution of this paper is to propose a realistic pseudo-synchronous implementation of this algorithm. This pseudo-synchronous algorithm is shown to be a perturbation of the synchronous one and so, through arguments related to the center manifold theorem, it is proved to be locally convergent under the assumption of absence of process noise, measurement noise and propagation delays. However, through numerical simulations, the performance of this algorithm is evaluated also in the case the communication delays are not negligible, the clock drifts are time-varying and the communication channels are unreliable. Moreover, again through numerical simulations, the strategy we propose in this paper is compared with other fully distributed strategies recently proposed in the literature. While being slightly slower to reach the asymptotic synchronization, our strategy seems to significantly outperform the other strategies in terms of robustness to process and measurement noises and time-varying clock drifts. [ABSTRACT FROM AUTHOR]

In the recent paper by Hamadeh et al. (2012) an elegant analytic criterion for incremental output feedback passivity (iOFP) of cyclic feedback systems (CFS) has been reported, assuming that the constituent subsystems are incrementally output strictly passive (iOSP). This criterion was used to prove that a network of identical CFS can be synchronized under sufficiently strong linear diffusive coupling. A very important class of CFS consists of biological oscillators, named after Brian Goodwin and describing self-regulated chains of enzymatic reactions, where the product of each reaction catalyzes the next reaction, while the last product inhibits the first reaction in the chain. Goodwin's oscillators are used, in particular, to model the dynamics of genetic circadian pacemakers, hormonal cycles and some metabolic pathways. In this technical note we point out that for Goodwin's oscillators, where the individual reactions have nonlinear (e.g., Mikhaelis-Menten) kinetics, the synchronization criterion, obtained by Hamadeh et al., cannot be directly applied. This criterion relies on the implicit assumption of the solution boundedness, dictated also by the chemical feasibility (the state variables stand for the concentrations of chemicals). Furthermore, to test the synchronization condition one needs to know an explicit bound for a solution, which generally cannot be guaranteed under linear coupling. At the same time, we show that these restrictions can be avoided for a nonlinear synchronization protocol, where the control inputs are “saturated” by a special nonlinear function (belonging to a wide class), which guarantees nonnegativity of the solutions and allows to get explicit ultimate bounds for them. We prove that oscillators synchronize under such a protocol, provided that the couplings are sufficiently strong. [ABSTRACT FROM AUTHOR]

This paper deals with output-feedback-based state consensus of homogeneous linear multiagent systems. A novel reduced-order dynamic output-feedback protocol is proposed, which does not need the absolute output information of neighboring agents. Necessary and sufficient conditions for the solvability of the consensus problem under the proposed protocol are derived, and it is shown that the protocol state is convergent if consensus is reached. A design algorithm is then constructed for computing the protocol gains. Furthermore, the protocol specialized for leader–follower consensus is addressed. In addition, the solvability of a truncated version of the proposed protocol without controller interaction is discussed from a low-gain perspective. A numerical example is finally presented to demonstrate the effectiveness of the proposed protocol and design method. [ABSTRACT FROM AUTHOR]

This paper considers the distributed event-triggered consensus problem for general linear multiagent networks. Both the leaderless and leader–follower consensus problems are considered. Based on the local sampled state information, distributed adaptive event-triggered protocols are designed, which can ensure that the consensus of the agents is achieved, and the Zeno behavior is excluded by showing that the interval between any two triggering events is lower-bounded by a strictly positive value. Compared with the previous related works, our main contribution is that the proposed adaptive event-based protocols are fully distributed and scalable, which do not rely on any global information of the network graph and are independent of the network's scale. In these event-based protocols, continuous communications are not required for either control laws updation or triggering functions monitoring. [ABSTRACT FROM AUTHOR]

This paper investigates the positive edge-consensus problem via output feedback protocols for undirected networks and directed networks whose edge dynamics are defined on nonnegative spaces. First, the definition and topology of the line graph are presented based on a given nodal graph with positive edge dynamics. Two observer-type positive edge-consensus protocols are introduced, and sufficient conditions of positive consensus for uncertain positive systems are proposed without utilizing the information of algebraic connectivity. Furthermore, necessary and/or sufficient conditions of positive consensus for the nominal systems are derived. The analysis illustrates that the error variables defined in this paper are nonnegative in both protocols. Finally, the illustrative simulation examples are presented to verify the effectiveness of the proposed observer-type positive edge-consensus protocols. [ABSTRACT FROM AUTHOR]

The cooperative output regulation (COR) problem of heterogeneous linear multi-agent networks [multi-agent systems (MASs)] is studied in the paper. Agents are allowed to be inherently heterogeneous linear time-invariant systems and the communication graph is not restricted to be acyclic. Both state- and output-feedback control protocols that make use of neighbors’ output information are considered. In light of robust control theory and robust output regulation theory, small-gain solvability conditions with closed-loop pole specifications are first derived. Then, an ${H_{\infty }}$ performance allocation approach is proposed for protocol design, where algorithms for optimizing graph weights and designing protocol gains are constructed, respectively. Both continuous-time (CT) and discrete-time MASs are investigated in a unified framework. In addition, solvability of the COR problem is further discussed from the graph, agent, and exosystem aspects, respectively. It is proved that the proposed approach pre-explicitly ensures the solvability of the COR problem for either of the three cases: the graph is acyclic; for CT MASs, agents are minimum-phase and right-invertible; and for CT MASs, the poles of the exosystem have zero real part and agents are right-invertible. [ABSTRACT FROM AUTHOR]

This paper is concerned with the ultimate boundedness control problem for a class of networked nonlinear systems subject to the try-once-discard (TOD) protocol scheduling and uniform quantization effects. To prevent the transmission data from collisions, the communication between sensor nodes and the controller is implemented via a constrained communication channel, where only one sensor node is permitted to transmit data at each time instant. The TOD protocol is utilized to regulate the signal transmission over the communication network under which the scheduling behavior is described by a special switching function. On the other hand, the uniform quantization effects of the network are characterized by a round function (i.e., the nearest integer function). The purpose of the addressed problem is to design an observer-based controller for the networked nonlinear systems such that, in the presence of TOD protocol and uniform quantization effects, the closed-loop system is ultimately bounded and the controlled output is locally minimized. Sufficient conditions are established to guarantee the ultimate boundedness of the dynamics of the closed-loop system in mean square by applying the stochastic analysis approach. Furthermore, the desired controller gains are derived by solving a convex optimization problem. Finally, a numerical example is given to illustrate the effectiveness of the proposed controller design scheme. [ABSTRACT FROM PUBLISHER]

Consensus conditions and convergence speeds are crucial for distributed consensus algorithms of networked systems. Based on a basic first-order average-consensus protocol with time-varying topologies and additive noises, this paper first investigates its critical consensus condition on network topology by stochastic approximation frameworks. A new joint-connectivity condition called extensible joint-connectivity that contains a parameter $\delta$ (termed the extensible exponent) is proposed. With this and a balanced topology condition, we show that a critical value of \delta$ for consensus is 1/2$ . Optimization on convergence rate of this protocol is further investigated. It is proved that the fastest convergence rate, which is the theoretic optimal rate among all controls, is of the order 1/t for the worst topologies, which are balanced and satisfy the extensible joint-connectivity condition. For practical implementation, certain open-loop control strategies are introduced to achieve consensus with a convergence rate of the same order as the fastest convergence rate. Furthermore, a consensus condition is derived for nonstationary and strongly correlated random topologies. The algorithms and consensus conditions are applied to distributed consensus computation of mobile ad-hoc networks; and their related critical exponents are derived from relative velocities of mobile agents for guaranteeing consensus. [ABSTRACT FROM PUBLISHER]

This paper is concerned with the \mathcal H\infty filtering problem for a class of time-varying nonlinear delayed system under high-rate communication network and stochastic protocol (SP). The communication between the sensors and the state estimator is implemented via a shared high-rate communication network in which multiple transmissions are generated between two adjacent sampling instants of sensors. At each transmission instant, only one sensor is allowed to get access to the communication network in order to avoid data collisions and the SP is employed to determine which sensor obtains access to the network at a certain instant. The mapping technology is applied to characterize the randomly switching behavior of the data transmission resulting from the utilization of the SP. The aim of the problem addressed is to design an estimator such that the \mathcal H\infty disturbance attenuation level is guaranteed for the estimation error dynamics over a given finite horizon. Sufficient conditions are derived for the existence of the finite-horizon filter satisfying the prescribed \mathcal H\infty performance requirement, and the explicit expression of the time-varying filter gains is characterized by resorting to a set of recursive matrix inequalities. Simulation results demonstrate the effectiveness of the proposed filter design scheme. [ABSTRACT FROM AUTHOR]

In this paper, we study the robust consensus problem for a group of linear discrete-time or continuous-time agents to coordinate over an uncertain communication network, which is to achieve consensus against transmission errors and noises. We model the network by communication links subject to deterministic uncertainties, which can be additive perturbations described by either some unknown transfer functions or norm bounded matrices. We show that the robust consensus problem can generally be solved by solving a simultaneous $H_\infty$ control problem for a set of low-dimensional subsystems. We also derive necessary conditions for the existence of a protocol achieving robust consensus. The results show that for discrete-time agents the uncertainty size must not exceed the inverse of the Mahler measure of the agents, while for continuous-time agents it must be less than the unity. Sufficient conditions in terms of linear matrix inequalities are further presented to design the robust consensus protocols. [ABSTRACT FROM AUTHOR]

In this paper we consider distributed optimization problems in which the cost function is separable, i.e., a sum of possibly non-smooth functions all sharing a common variable, and can be split into a strongly convex term and a convex one. The second term is typically used to encode constraints or to regularize the solution. We propose a class of distributed optimization algorithms based on proximal gradient methods applied to the dual problem. We show that, by choosing suitable primal variable copies, the dual problem is itself separable when written in terms of conjugate functions, and the dual variables can be stacked into non-overlapping blocks associated to the computing nodes. We first show that a weighted proximal gradient on the dual function leads to a synchronous distributed algorithm with local dual proximal gradient updates at each node. Then, as main paper contribution, we develop asynchronous versions of the algorithm in which the node updates are triggered by local timers without any global iteration counter. The algorithms are shown to be proper randomized block-coordinate proximal gradient updates on the dual function. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a novel continuous-time protocol that solves the consensus problem on the median value, i.e., it provides distributed agreement in networked multi-agent systems where the quantity of interest is the median value of the agents' initial values. In contrast to the average value, the median value is a statistical measure inherently robust to the presence of outliers, which is a significant robustness issue in large-scale sensor and multi-agent networks. The proposed protocol requires only binary information regarding the relative state differences among the neighboring agents and achieves consensus on the median value in finite time by exploiting a suitable ad-hoc discontinuous local interaction rule. In addition, we characterize certain resiliency properties of the proposed protocol against the presence of uncooperative agents which do not implement the underlying local interaction rule whereas they interact with their neighbors thus influencing the network. In particular, we prove that despite the persistent influence of (at most) a certain number of uncooperative agents, the cooperative agents achieve finite time consensus on a value lying inside the convex hull of the cooperative agents' initial conditions, provided that the special class of so-called “$k$-safe” network topology is considered. Capabilities of the proposed consensus protocol and its effectiveness are supported by numerical studies. [ABSTRACT FROM AUTHOR]

This paper presents a novel feedback method for the motion planning and coordination of multiple agents that belong to two classes, namely class-A and class-B. All agents are modeled via unicycle kinematics. Agents of class-B do not share information with agents of class-A and do not participate in ensuring safety, modeling thus agents with failed sensing/communication systems, agents of higher priority, or moving obstacles with known upper bounded velocity. The method is built upon a family of 2-D analytic vector fields, which under mild assumptions are proved to be safe feedback motion plans with a unique stable singular point. The conditions which ensure collision free and almost global convergence for a single agent and the analytical form of the vector fields are then utilized in the design the proposed distributed, semi-cooperative multi-agent coordination protocol. Semi-cooperative coordination has been defined in prior work as the ad hoc prioritization and conflict resolution among agents of the same class; more specifically, participation in conflict resolution and collision avoidance for each agent is determined on-the-fly based on whether the agent's motion results in decreasing its distance with respect to its neighbor agents; based on this condition, the agent decides to either ignore its neighbors, or adjust its velocity and avoid the neighbor agent with respect to which the rate of decrease of the pairwise inter agent distance is maximal. The proposed coordination protocol builds upon this logic and addresses the case of multiple agents of distinct classes (class-A and class-B) in conflict. Guarantees on the safety of the multi-agent system and the almost global convergence of the agents to their destinations are proved. The efficacy of the proposed methodology is demonstrated via simulation results in static and dynamic environments. [ABSTRACT FROM AUTHOR]

In this paper, we consider the synchronization control problem for uncertain high-order nonlinear multi-agent systems in a leader-follower scheme, under a directed communication protocol. A robust decentralized control law of minimal complexity is proposed that achieves prescribed, arbitrarily fast and accurate synchronization of the following agents with the leader. The control protocol is decentralized in the sense that the control signal of each agent is calculated based solely on local relative state information from its neighborhood set. Additionally, no information regarding the agents' dynamic model is employed in the design procedure. Moreover, provided that the communication graph is connected and contrary to the related works on multi-agent systems, the controller-imposed transient and steady state performance bounds are fully decoupled from: 1) the underlying graph topology, 2) the control gains selection, and 3) the agents' model uncertainties, and are solely prescribed by certain designer-specified performance functions. Extensive simulation results clarify and verify the approach. [ABSTRACT FROM PUBLISHER]

This paper solves consensus problems for networked agents whose interactions with each other are described by signed digraphs. The Laplacian matrix of a signed digraph is studied by introducing rooted cycles, and the relationship between it and the spanning tree condition is addressed. In particular, the Laplacian matrix of a signed digraph with spanning trees is positive stable if and only if there is at least one negative rooted cycle; otherwise, it has exactly one zero eigenvalue if and only if either there exist no rooted cycles or all existing rooted cycles are positive. It is shown that all agents reach interval bipartite consensus if their associated signed digraph has a spanning tree. Further, the consensus values of all agents depend only on the initial states of those agents which are associated with root vertices. The developed consensus results are applicable for multi-agent systems with both continuous-time and discrete-time dynamics. Illustrative examples are provided to demonstrate interval bipartite consensus performances for multi-agent systems associated with different signed digraphs which all contain spanning trees but are not strongly connected. [ABSTRACT FROM AUTHOR]

We consider a sequence of transferable utility (TU) games where, at each time, the characteristic function is a random vector with realizations restricted to some set of values. The first part of the paper contributes to the definition of a robust (coalitional) TU game and the development of a distributed bargaining protocol. We prove the convergence with probability 1 of the bargaining process to a random allocation that lies in the core of the robust game under some mild conditions on the underlying communication graphs. The second part of the paper addresses the more general case where the robust game may have empty core. In this case, with the dynamic game we associate a dynamic average game by averaging over time the sequence of characteristic functions. Then, we consider an accordingly modified bargaining protocol. Assuming that the sequence of characteristic functions is ergodic and the core of the average game has a nonempty relative interior, we show that the modified bargaining protocol converges with probability 1 to a random allocation that lies in the core of the average game. [ABSTRACT FROM AUTHOR]

Recent papers have treated control communication complexity in the context of information-based, multiple agent control systems including nonlinear systems of the type that have been studied in connection with quantum information processing. The present paper continues this line of investigation into a class of two-agent distributed control systems in which the agents cooperate in order to realize common goals that are determined via independent actions undertaken individually by the agents. A basic assumption is that the actions taken are unknown in advance to the other agent. These goals can be conveniently summarized in the form of a target matrix, whose entries are computed by the control system responding to the choices of inputs made by the two agents. We show how to realize such target matrices for a broad class of systems that possess an input-output mapping that is bilinear. One can classify control-communication strategies, known as control protocols, according to the amount of information sharing occurring between the two agents. Protocols that assume no information sharing on the inputs that each agent selects and protocols that allow sufficient information sharing for identifying the common goals are the two extreme cases. Control protocols will also be evaluated and compared in terms of cost functionals given by integrated quadratic functions of the control inputs. The minimal control cost of the two classes of control protocols are analyzed and compared. The difference in the control costs between the two classes reflects an inherent trade-off between communication complexity and control cost. [ABSTRACT FROM AUTHOR]

The PageRank algorithm employed at Google assigns a measure of importance to each web page for rankings in search results. In our recent papers, we have proposed a distributed randomized approach for this algorithm, where web pages are treated as agents computing their own PageRank by communicating with linked pages. This paper builds upon this approach to reduce the computation and communication loads for the algorithms. In particular, we develop a method to systematically aggregate the web pages into groups by exploiting the sparsity inherent in the web. For each group, an aggregated PageRank value is computed, which can then be distributed among the group members. We provide a distributed update scheme for the aggregated PageRank along with an analysis on its convergence properties. The method is especially motivated by results on singular perturbation techniques for large-scale Markov chains and multi-agent consensus. A numerical example is provided to illustrate the level of reduction in computation while keeping the error in rankings small. [ABSTRACT FROM AUTHOR]

In this paper, we study the stability of networked control systems (NCSs) that are subject to time-varying transmission intervals, time-varying transmission delays, and communication constraints. Communication constraints impose that, per transmission, only one node can access the network and send its information. The order in which nodes send their information is orchestrated by a network protocol, such as, the Round-Robin (RR) and the Try-Once-Discard (TOD) protocol. In this paper, we generalize the mentioned protocols to novel classes of so-called “periodic” and “quadratic” protocols. By focusing on linear plants and controllers, we present a modeling framework for NCSs based on discrete-time switched linear uncertain systems. This framework allows the controller to be given in discrete time as well as in continuous time. To analyze stability of such systems for a range of possible transmission intervals and delays, with a possible nonzero lower bound, we propose a new procedure to obtain a convex overapproximation in the form of a polytopic system with norm-bounded additive uncertainty. We show that this approximation can be made arbitrarily tight in an appropriate sense. Based on this overapproximation, we derive stability results in terms of linear matrix inequalities (LMIs). We illustrate our stability analysis on the benchmark example of a batch reactor and show how this leads to tradeoffs between different protocols, allowable ranges of transmission intervals and delays. In addition, we show that the exploitation of the linearity of the system and controller leads to a significant reduction in conservatism with respect to existing approaches in the literature. [ABSTRACT FROM AUTHOR]

We consider damped stochastic systems in a controlled (time varying) potential and study their transition between specified Gibbs-equilibria states in finite time. By the second law of thermodynamics, the minimum amount of work needed for the transition from one equilibrium state to another is the difference between the Helmholtz free energy of the two states and can only be achieved by a reversible (infinitely slow) process. The minimal gap between the work needed in a finite-time transition and the work during a reversible one, turns out to equal the square of the optimal mass transport (Wasserstein-2) distance between the two end-point distributions times the inverse of the duration needed for the transition. This result, in fact, relates nonequilibrium optimal control strategies (protocols) to gradient flows of entropy functionals via the Jordan–Kinderlehrer–Otto scheme. The purpose of this paper is to introduce ideas and results from the emerging field of stochastic thermodynamics in the setting of the classical regulator theory, and to draw connections and derive such fundamental relations from a control perspective in a multivariable setting. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of achieving average consensus over a random time-varying sequence of directed graphs by extending the class of so-called push-sum algorithms to such random scenarios. Provided that an ergodicity notion, which we term the directed infinite flow property, holds and the auxiliary states of agents are uniformly bounded away from zero infinitely often, we prove the almost sure convergence of the evolutions of this class of algorithms to the average of initial states. Moreover, for a random sequence of graphs generated using a so-called time-varying $B$ -irreducible probability matrix, we establish convergence rates for the proposed push-sum algorithm. [ABSTRACT FROM AUTHOR]

This paper revisits the problem of multiagent consensus from a graph signal processing perspective. Describing a consensus protocol as a graph spectrum filter, we present an effective new approach to the analysis and design of consensus protocols in the graph spectrum domain for the uncertain networks, which are difficult to handle by the existing time-domain methods. This novel approach has led to the following new results: 1) explicit connection between the time-varying consensus protocol and the graph filter; 2) new necessary and sufficient conditions for both finite-time and asymptotic average consensus of multiagent systems (MASs); 3) direct link between the consensus convergence rate and periodic consensus protocols, and conversion of fast consensus problem to the polynomial design of the graph filter; 4) two explicit design methods of the periodic consensus protocols with a predictable convergence rate for MASs on uncertain graphs; and 5) explicit formulas for the convergence rate of designed protocols. Several numerical examples are given to demonstrate the validity, effectiveness, and advantages of these results. [ABSTRACT FROM AUTHOR]

In this paper, we investigate a distributed estimation problem for multiagent systems with state equality constraints (SEC). First, under a time-based consensus communication protocol, applying a modified projection operator and the covariance intersection fusion method, we propose a distributed Kalman filter with guaranteed consistency and satisfied SEC. Furthermore, we establish the relationship between consensus step, SEC, and estimation error covariance in dynamic and steady processes, respectively. Employing a space decomposition method, we show that the error covariance in the constraint set can be arbitrarily small by setting a sufficiently large consensus step. Besides, we propose an extended collective observability (ECO) condition based on SEC, which is milder than existing observability conditions. Under the ECO condition, through utilizing a technique of matrix approximation, we prove the boundedness of error covariance and the exponentially asymptotic unbiasedness of state estimate, respectively. Moreover, under the ECO condition for linear time-invariant systems with SEC, we provide a novel event-triggered communication protocol by employing the consistency, and give an offline design principle of triggering thresholds with guaranteed boundedness of error covariance. More importantly, we quantify and analyze the communication rate for the proposed event-triggered distributed Kalman filter, and provide optimization based methods to obtain the minimal (maximal) successive nontriggering (triggering) times. Two simulations are provided to demonstrate the developed theoretical results and the effectiveness of the filters. [ABSTRACT FROM AUTHOR]

Cooperative control of multiagent systems (MAS) on communication networks has received a great deal of attention, mostly for the case of homogeneous agents, which all have the same dynamics. An advantage of cooperative synchronization mechanisms is their local distributed nature, which makes them scalable to large networks. However, most existing design mechanisms require some global information, such as the leader's dynamics or global graph information, so that the control protocols are technically not fully distributed. Moreover, the distributed nature of the control protocols makes them susceptible to faults or uncertainties. In this paper, we study heterogeneous MAS, where all agents may have different dynamics. We provide adaptive resilience mechanisms for rejecting actuator faults, and guarantee exponential convergence of synchronization errors, whereas most existing results on actuator faults guarantee only boundedness of errors. Finally, we provide algorithms that are fully distributed, requiring no knowledge of either the leader's dynamics or of graph properties. [ABSTRACT FROM AUTHOR]

Most of the distributed protocols for multi-agent consensus assume that the agents are mutually cooperative and “trustful,” and so the couplings among the agents bring the values of their states closer. Opinion dynamics in social groups, however, require beyond these conventional models due to ubiquitous competition and distrust between some pairs of agents, which are usually characterized by repulsive couplings and may lead to clustering of the opinions. A simple yet insightful model of opinion dynamics with both attractive and repulsive couplings was proposed recently by C. Altafini, who examined first-order consensus algorithms over static signed graphs. This protocol establishes modulus consensus, where the opinions become the same in modulus but may differ in signs. In this paper, we extend the modulus consensus model to the case where the network topology is an arbitrary time-varying signed graph and prove reaching modulus consensus under mild sufficient conditions of uniform connectivity of the graph. For cut-balanced graphs, not only sufficient, but also necessary conditions for modulus consensus are given. [ABSTRACT FROM PUBLISHER]

Distributed estimation has proven to be suitable for many multiagent system (MAS) applications, yet it relies heavily on information exchange via a costly and vulnerable communication network. This paper proposes a sensing-based distributed estimation algorithm that enables a local monitoring agent to expand its estimation capabilities beyond its sensing range without needing communication overhead. The key to expanding the limited sensing range is to incorporate the MAS's cooperative control protocol, allowing the monitoring agent to infer the state of out-of-range agents from the behavior of in-range agents that may interact with them. Then, the state estimation for out-of-range agents is performed through a Bayesian approach that considers the correlation of state estimates between in-range and out-of-range agents. This approach of only taking sensor measurements of local monitoring agents without interagent communications can successfully compensate for the existing communication-based distributed estimation methods. The performance of the proposed sensing-based distributed estimation algorithm is theoretically verified and demonstrated with numerical simulations of a multivehicle formation flight example. [ABSTRACT FROM AUTHOR]

This paper is concerned with the sliding mode control (SMC) problem for a class of uncertain discrete-time systems subject to unmatched external disturbances and communication constraints. In order to reduce the bandwidth usage between the controller and the actuators, the stochastic communication protocol (SCP) is utilized to determine which actuator should be given the access to the network at a certain instant. A key issue of the addressed problem is to design both the sliding surface and the sliding mode controller under the SCP scheduling. An updating rule on actuator input is first introduced and then a token-dependent SMC law is designed. Sufficient conditions are established for the resultant SMC systems such that not only the reachability with a sliding domain around the specified sliding surface is ensured, but also the stochastic stability with a prescribed $H_\infty$ performance level is guaranteed. Based on these conditions, a set of coupled matrix inequalities is given to acquire the token-dependent parameter matrices in the proposed SMC law. Finally, a numerical example is presented to illustrate the effectiveness of the proposed $H_\infty$ SMC scheme under the SCP scheduling. [ABSTRACT FROM AUTHOR]

The distributed convex optimization problem is studied in this paper for any fixed and connected network with general constraints. To solve such an optimization problem, a new type of continuous-time distributed subgradient optimization algorithm is proposed based on the Karuch–Kuhn–Tucker condition. By using tools from nonsmooth analysis and set-valued function theory, it is proved that the distributed convex optimization problem is solved on a network of agents equipped with the designed algorithm. For the case that the objective function is convex but not strictly convex, it is proved that the states of the agents associated with optimal variables could converge to an optimal solution of the optimization problem. For the case that the objective function is strictly convex, it is further shown that the states of agents associated with optimal variables could converge to the unique optimal solution. Finally, some simulations are performed to illustrate the theoretical analysis. [ABSTRACT FROM AUTHOR]

This paper deals with the consensus tracking problem for a multiagent system with nonholonomic chained-form dynamics. A new distributed observer is first proposed for each follower to estimate the leader state and the leader input in a prescribed finite-time under both undirected and directed communication graphs. Then based on the observer and by adding a power integrator, a novel nonlinear protocol is designed such that the estimated leader state is tracked in a prescribed finite-time. Different from some existing finite-time consensus tracking approaches, an explicit bound without dependence on initial states is derived for the settling time. Therefore, in an unknown environment where initial conditions are unavailable, the proposed strategy is able to meet specific system requirements, e.g., a military target is tracked by a group of field robots in a prescribed time. Finally, numerical examples are provided to demonstrate the effectiveness of the proposed protocol. [ABSTRACT FROM AUTHOR]

This paper studies the consensus of multiagent systems with binary-valued communication. We consider a group of agents on an undirected graph with a fixed topology, differing from most existing work, the information each agent gets from its neighbors are binary-valued measurements with stochastic noises. A two-time-scale protocol that alternates estimation and control is constructed: Each agent in the system estimates the states of its neighbors’ based on the binary-valued measurements for a dwelt time, during which every agent's state will keep constant; Based on the estimations of its neighbors’ states and its own state, each agent designs its own control, by which the state will be updated and then repeats the process of estimation alternating with control. For the state estimation, we propose an identification algorithm without truncation, which is analyzed to be convergent and the convergence rate is given. By the two-time-scale protocol, the system is shown to achieve weak consensus and mean square consensus by using a stochastic Lyapunov analysis and the consensus speed is given. Simulations are given with different holding time, which are consistent with the theoretical results. [ABSTRACT FROM AUTHOR]

In this note, we consider the synchronization problem for discrete-time linear multi-agent systems with time-varying network topology. To describe a new joint connectivity condition for synchronization, the concept of synchronization reachable topology is introduced. Under the conditions that agent dynamics is neutrally stable and network topology is synchronization reachable, a synchronization and an exponential synchronization result are obtained using paracontraction theory. The two results generalize in a natural way the classical results for the consensus of first-order discrete-time multi-agent systems. Finally, the effectiveness of the results is illustrated by a simulation example. [ABSTRACT FROM AUTHOR]

We consider distributed optimization by a collection of nodes, each having access to its own convex function, whose collective goal is to minimize the sum of the functions. The communications between nodes are described by a time-varying sequence of directed graphs, which is uniformly strongly connected. For such communications, assuming that every node knows its out-degree, we develop a broadcast-based algorithm, termed the subgradient-push, which steers every node to an optimal value under a standard assumption of subgradient boundedness. The subgradient-push requires no knowledge of either the number of agents or the graph sequence to implement. Our analysis shows that the subgradient-push algorithm converges at a rate of O(\ln t/\sqrtt ) . The proportionality constant in the convergence rate depends on the initial values at the nodes, the subgradient norms and, more interestingly, on both the speed of the network information diffusion and the imbalances of influence among the nodes. [ABSTRACT FROM PUBLISHER]

The paper presents new results on asymptotic consensus for continuous time nonautonomous nonlinear networks under almost-periodic interactions. We introduce such consensus algorithms in order to estimate the average of a measured field, despite the presence of limited agents’ interaction (herein represented by almost periodic connectivity). To this end, a suitable notion of integral connectivity is exploited, frozen in state variables, and of simple verification, thanks to ergodicity of the underlying agents’ spatial dynamics. In the considered setup, consensus variables are different than those affecting network's connectivity unlike most of the existing literature on asymptotic agreement. The application of the proposed results is illustrated considering two representative examples in the scenario of autonomous sampling by mobile sensor agents. [ABSTRACT FROM AUTHOR]