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.

Cooperative control of multi-agent systems (MASs) has been intensively investigated in the past decade. The task is always complicated for an individual agent, but can be achieved by collectively operating a group of agents in a reliable, economic and efficient way. Although a lot of efforts are being spent on improving MAS performances, much progress has yet to be developed on different aspects. This thesis aims to solve problems in the consensus control of multiple quadrotors and/or mobile robots considering irregular sampling controls, heterogeneous agent dynamics and the presence of model uncertainties and disturbances. The thesis proceeds with Chapter 1 by providing the literature review of the state-of-the-art development in the consensus control of MASs. Chapter 2 introduces experimental setups of the laboratory involving two-wheeled mobile robots (2WMRs), quadrotors, positioning systems and inter-vehicle communications. All of the developed theoretical results in Chapters 3-6 are experimentally verified on the platform. Then it is followed by two main parts: Irregular sampling consensus control methods (Chapter 3 and 4) and cooperative control of heterogeneous MASs (Chapter 5 and 6). Chapter 3 focuses on the non-uniform sampling consensus control for a group of 2WMRs, and Chapter 4 studies the event-based rendezvous control for a group of asynchronous robots with time-varying communication delays. Chapter 5 concentrates on cooperative control methods for a heterogeneous MAS consisting of quadrotors and 2WMRs. Chapter 6 focuses on the design of a quadrotor flight controller which is robust to various adverse factors such as model uncertainties and external disturbances. The developed controller is further applied to the consensus control of the heterogeneous MAS. Specifically, Chapter 3 studies synchronized and non-periodical sampling consensus control methods for a group of 2WMRs. The directed and switching communication topologies among the network are considered in the controller design. The 2WMR is an underactuated system, which implies that it can not generate independent x and y accelerations in the two-dimensional plane. The rendezvous control methods are proposed for 2WMRs. The algebraic graph theory and stochastic matrix analysis are employed to conduct the convergence analysis. Although the samplings in the work of Chapter 3 are aperiodic, one feature is that local clocks of agents are required to be synchronized. Challenges arise in the practical control of distributed MASs, especially in the scenario that the global clock is lacking. Moreover, frequent samplings can result in redundant information transmissions when the communication bandwidth is limited. To address these problems, Chapter 4 investigates an event-based rendezvous control method for a group of asynchronous MAS with time-varying communication delays. Integral-type triggering conditions for each robot are adopted to be checked periodically. If the triggering condition is satisfied at one checking instant, the agent samples and broadcasts the state to the neighbors with a bounded communication delay. Then an algorithm is provided for driving 2WMRs to asymptotically reach rendezvous. The convergence analysis is conducted through Lyapunov approaches. Most of the theoretical works on cooperative control are focused on controlling agents with identical dynamics. However, in certain realistic scenarios, some complex missions require the cooperation of different types of agent dynamics such as surveillance, search and rescue, etc. Tasks can be carried out with higher efficiency by employing both the autonomous ground vehicles and unmanned aerial vehicles. To achieve better performance for MASs, in Chapter 5, distributed cooperative control methods for a heterogeneous MAS consisting of quadrotors and 2WMRs are developed. Consensus conditions are provided, and the theoretical results are experimentally verified. Many existing quadrotor control methods need exact model parameters of the quadrotor. In reality, when a quadrotor is conducting some tasks with extra payloads or with unexpected damages to the model structure, errors in parameters could result in the failure of the flight. External disturbances also inevitably affect the flight performance. To move a step further towards practical applications, in Chapter 6, a robust quadrotor flight controller using Integral Sliding Mode Control (ISMC) technique is investigated. In experiments, an extra payload with the position and mass unknown, is attached to destroy the accuracy of the model and to add disturbances. The designed controller significantly rejects negative effects caused by the payload during the flight. This controller is also successfully applied to an MAS consisting of a quadrotor and 2WMRs. / Graduate

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.

As more industrial processes, transportation and appliances have been automated or equipped with some level of artificial intelligence, the number and scale of interconnected systems has grown in the recent past. This is a development which can be expected to continue and therefore the research in performance of interconnected systems and networks is growing. Due to increased automation and sheer scale of networks, dynamically scaling networks is an increasing field and research into scalable performance measures is advancing. Recently, the notion gamma-robustness, a scalable network performance measure, was introduced as a measurement of interconnected systems robustness with respect to external disturbances. This thesis aims to investigate how the distribution of control effort and cost, within interconnected system, affects network performance, measured with gamma-robustness. Further, we introduce a notion of fairness and a measurement of unfairness in order to quantify the distribution of network properties and performance. With these in place, we also present distributed algorithms with which the distribution of control effort can be controlled in order to achieve a desired network performance. We close with some examples to show the strengths and weaknesses of the presented algorithms. / I och med att fler och fler system och enheter blir utrustade med olika grader av intelligens så växer både förekomsten och omfattningen av sammankopplade system, även kallat Multi-Agent Systems. Sådana system kan vi se exempel på i traffikledningssystem, styrning av elektriska nätverk och fordonståg, vi kan också hitta fler och fler exempel på så kallade sensornätverk i och med att Internet of Things och Industry 4.0 används och utvecklas mer och mer. Det som särskiljer sammankopplade system från mer traditionella system med flera olika styrsignaler och utsignaler är att dem sammankopplade systemen inte styrs från en central styrenhet. Istället styrs dem sammankopplade systemen på ett distribuerat sätt i och med att varje agent styr sig själv och kan även ha individuella mål som den försöker uppfylla. Det här gör att analysen av sammankopplade system försvåras, men tidigare forskning har hittat olika regler och förhållninssätt för agenterna och deras sammankoppling för att uppfylla olika krav, såsom stabilitet och robusthet. Men även om dem sammankopplade systemen är både robusta och stabila så kan dem ha egenskaper som vi vill kunna kontrollera ytterligare. Specifikt kan ett sådant prestandamått vara systemens motståndskraft mot påverkan av yttre störningar och i vanliga olänkade system finns det en inneboende avvägning mellan kostnad på styrsignaler och resiliens mot yttre störningar. Samma avvägning hittar vi i sammankopplade system, men i dessa system hittar vi också ytterligare en dimension på detta problem. I och med att ett visst mått av en nätverksprestanda inte nödvändigtvis betyder att varje agent i nätverket delar samma mått kan agenterna i ett nätverk ha olika utväxling mellan styrsignalskostnad och resiliens mot yttre störningar. Detta gör att vissa agenter kan ha onödigt höga styrsignalskonstander, i den mening att systemen skulle uppnå samma nätverksprestanda men med lägre styrsignalskostnad om flera av agenterna skulle vikta om sina kontrollinsatser. I det här examensarbetet har vi studerat hur olika val av kontrollinsats påverkar ett sammankopplat systems prestanda. Vi har gjort detta för att undersöka hur autonoma, men sammankopplade, agenter kan ändra sin kontrollinsats, men med bibehållen nätverksprestanda, och på det sättet minska sina kontrollkostnader. Detta har bland annat resulterat i en distruberad algoritm för att manipulera agenternas kontrollinsats så att skillnaderna mellan agenternas resiliens mot yttre störningar minskar och nätverksprestandan ökar. Vi avslutar rapporten med att visa ett par exempel på hur system anpassade med hjälp av den framtagna algoritmen får ökad prestanda. Avslutningsvis följer en diskussion kring hur vissa antaganden kring systemstruktur kan släppas upp, samt kring vilka områden framtida forskning skulle kunna fortsätta med.