Coordination of Open Multi-Agent Systems

During the last decade, the problem of consensus in Multi-Agent Systems (MASs) has been studied with special emphasis on graph theoretical methods. Consensus can be regarded as a control objective in which all the agents in a network converge to (or agree “upon”) a common value. This is achieved through a given control strategy usually referred to as consensus algorithm. The consensus problem in MASs becomes more challenging in the presence of agents that can join and leave the network, hence the so-called “open” multi-agent systems. This topic is recent in the scientific literature and quickly gaining attention. Thus, this dissertation is motivated by this topic, focusing on the consensus problem on the median consensus value and the average consensus in open multi-agent systems. Hence, this thesis is first devoted to designing a novel distributed open average consensus protocol for multi-agent systems. The distributed algorithm tracks the average of the agents’ state despite the time-varying size and composition of the network. The research activity consists of the design and formal characterization of the convergence properties of the algorithm. The results have been corroborated by numerical simulations. As for the second part of the research activity, the characterization of the convergence properties of a distributed algorithm to compute and track the median value of a set of numbers in open multi-agent systems has been proposed. A continuous time formulation is considered where the state variables of the agents track with zero error the median value of a set of time-varying reference signals given as input to the agents in a time-varying, undirected network topology. The performance of the proposed protocol is considered in the framework of open multi-agent systems by proposing join and leave mechanisms, i.e., the scenario where agents may join and leave the network during the protocol execution. One notable feature of consensus on the median value is the robustness of the median value, as opposed to the average value, with respect to abnormal or outlier state values. Non-smooth Lyapunov theory is employed to provide convergence guarantees and simple tuning rules to adjust the algorithm parameters. Apart from studying open multi-agent systems, this dissertation also proposes a distributed scheme for transforming any connected interaction graph with a possible no integer average degree into a connected approximately random k-regular graph which is independent of the degree of the initial graph. in more details, we define some local graph transformation rules (consisting of rules for cutting, adding, and moving edges) and provide a distributed implementation. In the resulting process, a random regular graph is obtained while the agents observe and modify only the local structure of the network. As such, the network achieves high expansion ratios and algebraic connectivity, which provide robustness to various structural and functional perturbations.