This dissertation aims at solving the consensus control problem of multi-agent systems with Lipschitz nonlinearity. This depends on the design of the controller that enables each agent or subsystem in multi-agent systems with Lipschitz nonlinearity to reach consensus; using the understanding of the agents' connection network from the knowledge of graph theory as well as the control system design strategy. The objective is achieved by designing a type of distributed control, namely the consensus control, which manipulates the relative information of each agent in a multi-agent systems in order to arrive at a single solution. In addition, containment control is also developed to solve containment problem. It is an extension of consensus control via leader-follower configuration, aimed at having each agent contained by multiple leaders in a multi-agent systems with Lipschitz nonlinearity. Four types of controllers are proposed - state-feedback consensus controller, observer-based consensus controller, state-feedback containment controller and observer-based containment controller; each provides the stability conditions based on Lyapunov stability analysis in time domain which enabled each agent or subsystem to reach consensus. The observer-based controllers are designed based on the consensus observer that is related to Luenberger observer. Linear Matrix Inequality (LMI) and Algebraic Riccati Equation (ARE) are utilized to obtain the solutions for the stability conditions. The simulation results of the proposed controllers and observers have been carried out to prove their theoretical validity. Several practical examples of flexible robot arm simulations are included to further validate the theoretical aspects of the thesis.

Multi-agent multi-team systems are commonly seen in environments where hierarchical layers of goals are at play. For example, theater-wide combat scenarios where multiple levels of command and control are required for proper execution of goals from the general to the foot soldier. Similar structures can be seen in game environments, where agents work together as teams to compete with other teams. The different agents within the same team must, while maintaining their own ‘personality’, work together and coordinate with each other to achieve a common team goal. This research develops strategy-based multi-agent multi-team systems, where strategy is framed as an instrument at the team level to coordinate the multiple agents of a team in a cohesive way. A formal specification of strategy and strategy-based multi-agent multi-team systems is provided. A framework is developed called SiMAMT (strategy- based multi-agent multi-team systems). The different components of the framework, including strategy simulation, strategy inference, strategy evaluation, and strategy selection are described. A graph-matching approximation algorithm is also developed to support effective and efficient strategy inference. Examples and experimental results are given throughout to illustrate the proposed framework, including each of its composite elements, and its overall efficacy. This research make several contributions to the field of multi-agent multi-team systems: a specification for strategy and strategy-based systems, and a framework for implementing them in real-world, interactive-time scenarios; a robust simulation space for such complex and intricate interaction; an approximation algorithm that allows for strategy inference within these systems in interactive-time; experimental results that verify the various sub-elements along with a full-scale integration experiment showing the efficacy of the proposed framework.

Orientador: Edmundo Roberto Mauro Madeira / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-22T03:57:24Z (GMT). No. of bitstreams: 1 SoaresJunior_MiltonAparecido_M.pdf: 2099044 bytes, checksum: 9429a525b941834e987d70cb3b26c2fc (MD5) Previous issue date: 2013 / Resumo: Apesar do seu sucesso, a arquitetura atual da Internet _e uma fonte de vários problemas para as aplicações atuais e as demandas futuras. A virtualização da infraestrutura da rede é proposta como alternativa para solucionar esses problemas sem a necessidade de alterar o núcleo da Internet, pois ela habilita o pluralismo de arquiteturas de rede. Neste trabalho, foi desenvolvida uma arquitetura de gerência autonômica de redes virtuais baseada em sistemas multiagentes. Um protótipo que realiza a função de autocura de redes virtuais foi implementado a partir dessa arquitetura. Novos algoritmos e mecanismos foram desenvolvidos para melhorar a eficiência do protótipo. Foi realizado, também, um estudo de caso sobre a gerência de redes virtuais que leva em consideração os requisitos das aplicações que estão sendo executadas em uma nuvem. Uma plataforma de experimentação baseada em máquinas virtuais e no OpenFlow foi criada para a execução dos experimentos. Tanto o protótipo quanto a plataforma de experimentação integram ferramentas atuais criando uma única solução para a gerência de redes virtuais. Os resultados apresentados contribuem para aproximar a virtualização de redes e a gerência autonômica da realidade / Abstract: Despite its success, the current architecture of the Internet is a source of many problems for current applications and future demands. The virtualization of network infrastructure is proposed as an alternative to solve these problems without the need to change the core of the Internet, as it enables the network architecture pluralism. We have developed architecture for autonomic management of virtual networks based on multi-agent systems. Based on this architecture, we implemented a prototype that performs the function of self-healing virtual networks. New algorithms and mechanisms have been developed to improve the efficiency of the prototype. A case study on the management of virtual networks that takes into consideration the requirements of the applications that are running on a cloud is also presented. For the execution of the experiments was created an experimentation platform based on virtual machines and on OpenFlow. The prototype and the platform integrate current tools creating a single solution for management of virtual networks. The results contributed to bring network virtualization and autonomic management closer to reality / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

abstract: The problem of modeling and controlling the distribution of a multi-agent system has recently evolved into an interdisciplinary effort. When the agent population is very large, i.e., at least on the order of hundreds of agents, it is important that techniques for analyzing and controlling the system scale well with the number of agents. One scalable approach to characterizing the behavior of a multi-agent system is possible when the agents' states evolve over time according to a Markov process. In this case, the density of agents over space and time is governed by a set of difference or differential equations known as a {\it mean-field model}, whose parameters determine the stochastic control policies of the individual agents. These models often have the advantage of being easier to analyze than the individual agent dynamics. Mean-field models have been used to describe the behavior of chemical reaction networks, biological collectives such as social insect colonies, and more recently, swarms of robots that, like natural swarms, consist of hundreds or thousands of agents that are individually limited in capability but can coordinate to achieve a particular collective goal. This dissertation presents a control-theoretic analysis of mean-field models for which the agent dynamics are governed by either a continuous-time Markov chain on an arbitrary state space, or a discrete-time Markov chain on a continuous state space. Three main problems are investigated. First, the problem of stabilization is addressed, that is, the design of transition probabilities/rates of the Markov process (the agent control parameters) that make a target distribution, satisfying certain conditions, invariant. Such a control approach could be used to achieve desired multi-agent distributions for spatial coverage and task allocation. However, the convergence of the multi-agent distribution to the designed equilibrium does not imply the convergence of the individual agents to fixed states. To prevent the agents from continuing to transition between states once the target distribution is reached, and thus potentially waste energy, the second problem addressed within this dissertation is the construction of feedback control laws that prevent agents from transitioning once the equilibrium distribution is reached. The third problem addressed is the computation of optimized transition probabilities/rates that maximize the speed at which the system converges to the target distribution. / Dissertation/Thesis / Doctoral Dissertation Mechanical Engineering 2020

[pt] Sistemas multiagentes abertos são sociedades em que os agentes autônomos e heterogêneos podem trabalhar para fins semelhantes ou diferentes. A fim de lidar com a heterogeneidade, autonomia e diversidade de interesses entre os diferentes membros, os sistemas estabelecem um conjunto de normas que é usado como um mecanismo de controle social para garantir uma ordem social desejável, em que os agentes trabalhem em conjunto. Tais normas regulam o comportamento dos agentes, definindo obrigações, permissões e proibições. Além disso, as normas podem dar estímulo para a sua realização através da definição de recompensas e pode desencorajar a sua violação, através de punições. Embora as normas sejam promissores mecanismos que regulam o comportamento dos agentes, deve-se levar em conta que os agentes são entidades autônomas, de modo que devem ser livres para decidir cumprir ou violar cada norma. Portanto, os agentes podem utilizar diferentes estratégias para alcançar seus objetivos e cumprir com as normas dirigidas a eles. De um lado, os agentes podem escolher atingir seus objetivos sem se preocupar com suas normas, ou seja, sem se preocupar com as recompensas que poderiam receber se cumprissem as normas ou as punições que receberão por violá-las. Por outro lado, alguns agentes escolherão cumprir com todas as normas embora alguns dos seus objetivos não possam ser alcançados. Neste contexto, este trabalho propõe um framework para simulação de agentes normativos que provê os mecanismos necessários para compreender os impactos das normas sobre os agentes que adotam algumas dessas estratégias para lidar com as normas. A aplicabilidade do framework será avaliada em dois cenários de uso: o primeiro no contexto de prevenções de crimes e o segundo está relacionado a missões de resgate de civis que estão em áreas de risco. / [en] Open multi-agent systems are societies in which autonomous and heterogeneous agents can work towards similar or different ends. In order to cope with the heterogeneity, autonomy and diversity of interests among the different members, those systems establish a set of norms that is used as a mechanism of social control to ensure a desirable social order in which agents work together. Such norms regulate the behaviour of the agents by defining obligations, permissions and prohibitions. Moreover, norms may give stimulus to their fulfillment by defining rewards and may discourage their violation by stating punishments. Although norms are promising mechanisms to regulate agents’ behavior, we should take into account that agents are autonomous entity, so they must be free to decide to fulfill or violate each norm. In this way, agents can use different strategies when deciding to achieve their goals and comply with the norms addressed to themselves. On one hand, agents might choose to achieve their goals without concerning with their norms, i.e., without concerting with the rewards they could receive if they fulfill the norms and the punishments they will receive for violating them. On the other hand, some agents will choose to comply with all the norms although some of their goals may not be achieved. In this context, this work proposes a framework for simulating normative agents that provides the necessary mechanisms to understand the impacts of norms on agents that adopt some of those strategies to deal with norms. The applicability of the framework will be evaluated in two scenarios: the first in the context of prevention of crimes and the second is related to the mission of rescuing civilians who are at risk areas.

Cette thèse traite du problème où une équipe d'agents coopératifs et autonomes, évoluant dans un environnement stochastique partiellement observable, et œuvrant à la résolution d'une tâche complexe, doit modifier dynamiquement sa composition durant l'exécution de la tâche afin de s'adapter à l'évolution de celle-ci. Il s'agit d'un problème qui n'a été que peu étudié dans le domaine de la planification multi-agents. Pourtant, il existe de nombreuses situations où l'équipe d'agent mobilisée est amenée à changer au fil de l'exécution de la tâche.Nous nous intéressons plus particulièrement au cas où les agents peuvent décider d'eux-même de quitter ou de rejoindre l'équipe opérationnelle. Certaines fois, utiliser peu d'agents peut être bénéfique si les coûts induits par l'utilisation des agents sont trop prohibitifs. Inversement, il peut parfois être utile de faire appel à plus d'agents si la situation empire et que les compétences de certains agents se révèlent être de précieux atouts.Afin de proposer un modèle de décision qui permette de représenter ces situations, nous nous basons sur les processus décisionnels de Markov décentralisés et partiellement observables, un modèle standard utilisé dans le cadre de la planification multi-agents sous incertitude. Nous étendons ce modèle afin de permettre aux agents d'entrer et sortir du système. On parle alors de système ouvert. Nous présentons également deux algorithmes de résolution basés sur les populaires méthodes de recherche arborescente Monte-Carlo. Le premier de ces algorithmes nous permet de construire des politiques jointes séparables via des calculs de meilleures réponses successives, tandis que le second construit des politiques jointes non séparables en évaluant les équipes dans chaque situation via un système de classement Elo. Nous évaluons nos méthodes sur de nouveaux jeux de tests qui permettent de mettre en lumière les caractéristiques des systèmes ouverts. / This thesis addresses the problem where a team of cooperative and autonomous agents, working in a stochastic and partially observable environment towards solving a complex task, needs toe dynamically modify its structure during the process execution, so as to adapt to the evolution of the task. It is a problem that has been seldom studied in the field of multi-agent planning. However, there are many situations where the team of agents is likely to evolve over time.We are particularly interested in the case where the agents can decide for themselves to leave or join the operational team. Sometimes, using few agents can be for the greater good. Conversely, it can sometimes be useful to call on more agents if the situation gets worse and the skills of some agents turn out to be valuable assets.In order to propose a decision model that can represent those situations, we base upon the decentralized and partially observable Markov decision processes, the standard model for planning under uncertainty in decentralized multi-agent settings. We extend this model to allow agents to enter and exit the system. This is what is called agent openness. We then present two planning algorithms based on the popular Monte-Carlo Tree Search methods. The first algorithm builds separable joint policies by computing series of best responses individual policies, while the second algorithm builds non-separable joint policies by ranking the teams in each situation via an Elo rating system. We evaluate our methods on new benchmarks that allow to highlight some interesting features of open systems.

Decentralized multi-agent optimization has emerged as a powerful paradigm that finds broad applications in engineering design including federated machine learning and control of networked systems. In these setups, a group of agents are connected via a network with general topology. Under the communication constraint, they aim to solving a global optimization problem that is characterized collectively by their individual interests. Of particular importance are the computation and communication efficiency of decentralized optimization algorithms. Due to the heterogeneity of local objective functions, fostering cooperation across the agents over a possibly time-varying network is challenging yet necessary to achieve fast convergence to the global optimum. Furthermore, real-world communication networks are subject to congestion and bandwidth limit. To relieve the difficulty, it is highly desirable to design communication-efficient algorithms that proactively reduce the utilization of network resources. This dissertation tackles four concrete settings in decentralized optimization, and develops four provably efficient algorithms for solving them, respectively. Chapter 1 presents an overview of decentralized optimization, where some preliminaries, problem settings, and the state-of-the-art algorithms are introduced. Chapter 2 introduces the notation and reviews some key concepts that are useful throughout this dissertation. In Chapter 3, we investigate the non-smooth cost-coupled decentralized optimization and a special instance, that is, the dual form of constraint-coupled decentralized optimization. We develop a decentralized subgradient method with double averaging that guarantees the last iterate convergence, which is crucial to solving decentralized dual Lagrangian problems with convergence rate guarantee. Chapter 4 studies the composite cost-coupled decentralized optimization in stochastic networks, for which existing algorithms do not guarantee linear convergence. We propose a new decentralized dual averaging (DDA) algorithm to solve this problem. Under a rather mild condition on stochastic networks, we show that the proposed DDA attains an $\mathcal{O}(1/t)$ rate of convergence in the general case and a global linear rate of convergence if each local objective function is strongly convex. Chapter 5 tackles the smooth cost-coupled decentralized constrained optimization problem. We leverage the extrapolation technique and the average consensus protocol to develop an accelerated DDA algorithm. The rate of convergence is proved to be $\mathcal{O}\left( \frac{1}{t^2}+ \frac{1}{t(1-\beta)^2} \right)$, where $\beta$ denotes the second largest singular value of the mixing matrix. To proactively reduce the utilization of network resources, a communication-efficient decentralized primal-dual algorithm is developed based on the event-triggered broadcasting strategy in Chapter 6. In this algorithm, each agent locally determines whether to generate network transmissions by comparing a pre-defined threshold with the deviation between the iterates at present and lastly broadcast. Provided that the threshold sequence is summable over time, we prove an $\mathcal{O}(1/t)$ rate of convergence for convex composite objectives. For strongly convex and smooth problems, linear convergence is guaranteed if the threshold sequence is diminishing geometrically. Finally, Chapter 7 provides some concluding remarks and research directions for future study. / Graduate

Different types of decentralized clustering problems have been studied so far for networks and multi-agent systems. In this paper we introduce a new type of a decentralized clustering problem for networks. The so called Decentralized Packet Clustering (DPC) problem is to find for packets that are sent around in a network a clustering. This clustering has to be done by the routers using only few computational power and only a small amount of memory. No direct information transfer between the routers is allowed. We investigate the behavior of new a type of decentralized k-means algorithm — called DPClust — for solving the DPC problem. DPClust has some similarities with ant based clustering algorithms. We investigate the behavior of DPClust for different clustering problems and for networks that consist of several subnetworks. The amount of packet exchange between these subnetworks is limited. Networks with different connection topologies for the subnetworks are considered. A dynamic situation where the packet exchange rates between the subnetworks varies over time is also investigated. The proposed DPC problem leads to interesting research problems for network clustering.

Deep Reinforcement Learning has achieved a plenty of breakthroughs in the past decade. Motivated by these successes, many publications extend the most prosperous algorithms to multi-agent systems. In this work, we firstly build solid theoretical foundations of Multi-Agent Reinforcement Learning (MARL), along with unified notations. Thereafter, we give a brief review of the most influential algorithms for Single-Agent and Multi-Agent RL. Our attention is focused mainly on Actor-Critic architectures with centralized training and decentralized execution. We propose a new model architec- ture called MATD3-FORK, which is a combination of MATD3 and TD3-FORK. Finally, we provide thorough comparative experiments of these algorithms on various tasks with unified implementation.

No description available.