1,721,045 research outputs found
Multi-stage discrete time and randomized dynamic average consensus
Full text linkIn this paper we propose a novel local interaction protocol which solves the discrete time dynamic average consensus problem, i.e., the consensus problem on the average value of a set of time-varying input signals in an undirected graph. The proposed interaction protocol is based on a multi-stage cascade of dynamic consensus filters which tracks the average value of the inputs with small and bounded error. We characterize its convergence properties for time-varying discrete-time inputs with bounded variations. The main novelty of the proposed algorithm is that, with respect to other dynamic average consensus protocols, we obtain the next unique set of advantages: i) The protocol, inspired by proportional dynamic consensus, does not exploit integral control actions or input derivatives, thus exhibits robustness to re-initialization errors, changes in the network size and noise in the input signals; ii) The proposed design allows to trade-off the quantity of information locally exchanged by the agents, i.e., the number of stages, with steady-state error, tracking error and convergence time; iii) The protocol can be implemented with randomized and asynchronous local state updates and keep in expectation the performance of the discrete-time version. Numerical examples are given to corroborate the theoretical findings, including the case where a new agent joins and leaves the network during the algorithm execution to show robustness to re-initialization errors during runtime
Lyapunov-Free Analysis for Consensus of Nonlinear Discrete- Time Multi-Agent Systems
No full textIn this paper we propose a novel method to establish stability and convergence to a consensus state for a class of nonlinear discrete-time Multi-Agent System (MAS) which is not based on Lyapunov function arguments. In particular, we focus on a class of discrete-time multi-agent systems whose global dynamics can be represented by sub-homogeneous and order-preserving nonlinear maps. The preliminary results of this paper directly generalize results for sub-homogeneous and order-preserving linear maps which are shown to be the counterpart to stochastic matrices thanks to nonlinear Perron-Frobenius theory. We provide sufficient conditions on local interaction rules among agents to establish convergence to a fixed point and study the consensus problem in this generalized framework as a particular case. Examples to show the effectiveness of the method are provided to corroborate the theoretical analysis. In these examples, some nonlinear interaction protocols are proved to converge to the consensus state without the use of Lyapunov functions
Gossip-Based Estimation of Centroid and Common Reference Frame in Open Multi-Agent Systems
No full textDecentralized estimation of centroid and common reference frame in multi-agent systems is a challenging problem, particularly when agents do not have access to global positioning data. This challenge intensifies in Open Multi-Agent Systems (OMAS), where the network composition dynamically changes due to agents joining or leaving, causing fluctuations in the number of participants. This paper presents a novel, decentralized gossip-based algorithm that enables agents in OMAS to collaboratively estimate both the centroid and a common reference frame in a 2-D environment where the number of agents may fluctuate over time. Notably, our approach remains robust despite noisy distance measurements and intermittent participation, as it relies on asynchronous, local pairwise interactions. Designed to accommodate the dynamic nature of network topologies, our algorithm can be employed for real-world applications where agents can join or leave the system due to failures, resource limitations or external environmental factors
Consensus on the average in arbitrary directed network topologies with time-delays
No full textIn this preliminary paper we study the stability property of a consensus on the average algorithm in arbitrary directed graphs with respect to communication/sensing time-delays. The proposed algorithm adds a storage variable to the agents' states so that the information about the average of the states is preserved despite the algorithm iterations are performed in an arbitrary strongly connected directed graph. We prove that for any network topology and choice of design parameters the consensus on the average algorithm is stable for sufficiently small delays. We provide simulations and numerical results to estimate the maximum delay allowed by an arbitrary unbalanced directed network topology
Secure rendezvous and static containment in multi-agent systems with adversarial intruders
Full text linkIn this paper we propose a novel distributed local interaction protocol for networks of multi-agent systems (MASs) in a multi-dimensional space under directed time-varying graph with the objective to achieve secure rendezvous or static containment within the convex hull of a set of leader agents. We consider the scenario where a set of anonymous adversarial agents may intrude the network (or may be hijacked by a cyber-attack) and show that the proposed strategy guarantees the achievement of the global objective despite the continued influence of the adversaries which cannot be detected nor identified by the collaborative agents. We characterize the convergence properties of the proposed protocol in terms of the characteristics of the underlying network topology of the multi-agent system. Numerical simulations and examples corroborate the theoretical results
A duality-based approach for distributed min-max optimization with application to demand side management
Full text linkIn this paper we consider a distributed optimiza- tion scenario in which a set of processors aims at minimizing the maximum of a collection of “separable convex functions” subject to local constraints. This set-up is motivated by peak- demand minimization problems in smart grids. Here, the goal is to minimize the peak value over a finite horizon with: (i) the demand at each time instant being the sum of contributions from different devices, and (ii) the local states at different time instants being coupled through local dynamics. The min-max structure and the double coupling (through the devices and over the time horizon) makes this problem challenging in a distributed set-up (e.g., well-known distributed dual decompo- sition approaches cannot be applied). We propose a distributed algorithm based on the combination of duality methods and properties from min-max optimization. Specifically, we derive a series of equivalent problems by introducing ad-hoc slack variables and by going back and forth from primal and dual formulations. On the resulting problem we apply a dual sub- gradient method, which turns out to be a distributed algorithm. We prove the correctness of the proposed algorithm and show its effectiveness via numerical computation
Discrete-Time Dynamic Consensus on the Max Value
No full textIn this paper, we propose a novel consensus protocol for discrete-time
multi-agent systems (MAS), which solves the dynamic consensus problem on the
max value, the so-called dynamic max-consensus problem. In the dynamic max consensus problem, the objective of each agent is to estimate the time-varying value
of the maximum instantaneous value among the reference signals associated to the
agents in the network, by exploiting only local interactions. The proposed interac tion protocol enables the agents to solve this problem with an a priori bounded error,
without exchange of input information among the agents. Furthermore, the proposed
protocol can be tuned by means of a tuning parameter, enabling a trade-off between
convergence time and steady-state error. We also provide a preliminary characteriza tion of the maximum relative tracking error. Numerical simulations corroborate the
theoretical analysis of the convergence properties of the proposed protocol
A MILP Scheduling Problem for Multi-Robot Logistics Systems in a Precision Farming Application and a Polynomial Time Optimal Algorithm
No full textIn this paper, we present an innovative use of multi-robot systems in a precision farming application proposed in the European project 'CANOPIES'. The considered scenario is then formalized identifying a real-time scheduling problem that needs to be solved for the efficient use of the multi-robot platform. A solution to the proposed real-time scheduling problem is first identified by proposing a mixed integer linear programming (MILP) problem formulation which is iteratively solved within a receding horizon time window. Then, we propose a polynomial time optimal algorithm able to solve a simplified but relevant scenario of the proposed multi-robot scheduling problem. Numerical examples are presented to corroborate the formal analysis of the proposed algorithm
A gossip-based algorithm for discrete consensus over heterogeneous networks
No full textQuantized consensus assumes that the state of each node may only take nonnegative integer values. Reaching consensus under quantization is equivalent to determining a balanced assignment of
identical tasks to nodes. In this paper we generalize this problem in two ways and denote the resulting framework discrete
consensus. First, we consider tasks that are not identical: each one is characterized by its own weight. Secondly, we assume that nodes are not identical as well. As an example, in the case of task
assignment, that we consider as a reference problem in this
framework, nodes may have different speeds and should be assigned a total weight proportional to their speed.
We provide a gossip-based distributed algorithm that aims to minimize the maximum execution time over nodes, whose convergence to
a bounded set is guaranteed. We show that the convergence time of the proposed algorithm relies ultimately on the average meeting time
between two agents performing a random walk on a graph
Dynamic min and max consensus and size estimation of anonymous multiagent networks
Full text linkIn this article, we propose two distributed control protocols for discrete-time multiagent systems, which solve the dynamic consensus problem on the max value. In this problem, each agent is fed an exogenous reference signal and has the objective to estimate and track the instantaneous and time-varying value of the maximum among all the signals fed to the network by exploiting only local and anonymous interactions among the agents. The first protocol achieves bounded steady-state and tracking errors which can be tradedoff for convergence time. The second protocol achieves zero steady-state error and requires knowledge of an upper bound to the diameter of the graph representing the network. Modified versions of both protocols are provided to solve the dual dynamic minconsensus problem. These protocols are then exploited to solve a distributed size estimation problem in a network of anonymous agents in a dynamic setting where the size
of the network is time-varying during the execution of the estimation algorithm. Numerical simulations are provided in order to corroborate the characterization of the proposed protocols
- …
