We present a motion control framework which allows a group of robots to work together to decide upon their motions by minimizing a collective cost without any central computing component or any one agent performing a large portion of the computation. When developing distributed control algorithms, care must be taken to respect the limited computational capacity of each agent as well as respect the information and communication constraints of the network. To address these issues, we develop a distributed, behavior-based model predictive control (MPC) framework which alleviates the computational difficulties present in many distributed MPC frameworks, while respecting the communication and information constraints of the network. In developing the multi-agent control framework, we make three contributions. First, we develop a distributed optimization technique which respects the dynamic communication restraints of the network, converges to a collective minimum of the cost, and has transients suitable for robot motion control. Second, we develop a behavior-based MPC framework to control the motion of a single-agent and apply the framework to robot navigation. The third contribution is to combine the concepts of distributed optimization and behavior-based MPC to develop the mentioned multi-agent behavior-based MPC algorithm suitable for multi-robot motion control.

Doctor of Philosophy / Department of Computing and Information Sciences / Scott A. DeLoach / Multiagent systems have been proposed as a way to create reliable, adaptable, and efficient systems. As these systems grow in complexity, configuration, tuning, and design of these systems can become as complex as the problems they claim to solve. As researchers in multiagent systems engineering, we must create the next generation of theories and tools to help tame this growing complexity and take some of the burden off the systems engineer. In this thesis, I propose guidance policies as a way to do just that. I also give a framework for multiagent system design, using the concept of guidance policies to automatically generate a set of constraints based on a set of multiagent system models as well as provide an implementation for generating code that will conform to these constraints. Presenting a formal definition for guidance policies, I show how they can be used in a machine learning context to improve performance of a system and avoid failures. I also give a practical demonstration of converting abstract requirements to concrete system requirements (with respect to a given set of design models).

Os smart grids são tidos como a nova geração dos sistemas elétricos de potência, combinando avanços em computação, sistemas distribuídos e inteligência artificial para prover maiores funcionalidades sobre acompanhamento em tempo real da demanda e do consumo de energia elétrica, gerenciamento em larga escala de geradores distribuídos, entre outras, a partir de um sistema de controle distribuído sobre a rede elétrica. Esta abordagem alteraria fundamentalmente a maneira como se dá o planejamento e a operação de sistemas de distribuição, e há grandes possibilidades de pesquisa e desenvolvimento possibilitada pela busca de implementação destas funcionalidades. Com esse cenário em vista, o presente trabalho utiliza uma abordagem a partir do uso de sistemas multiagentes para estudar o gerenciamento de sistemas de distribuição, do ponto de vista da reconfiguração da topologia da rede, simulando as características de um smart grid. Nesta dissertação, foi desenvolvido um sistema multiagente para simulação computacional de um sistema de distribuição elétrico do tipo smart grid, buscando executar a reconfiguração topológica do sistema a partir de dados de carga capturados de forma distribuída pelos agentes dispersos na rede elétrica. Espera-se que o desenrolar da pesquisa conduza à vários estudos sobre algoritmos e técnicas que melhor implementem tais funcionalidades a serem transpostas para um ambiente de produção. / Smart grids are taken as the new generation of electric power systems, combining advances in computing, distributed systems and artificial intelligence to provide more features on real-time monitoring of demand and consumption of electricity, managing large-scale distributed generators, among others, from a distributed control system on the grid. This approach fundamentally alter the way how is the planning and operation of distribution systems, and there are great possibilities for research and development offered in the quest to implement these features. With that environment, this text uses an approach through the use of multi-agent systems to study the management of the distribution system, from the reconfiguration of grid topology, simulating the characteristics of a smart grid. In this text, was developed a multiagent system to computational simulation of a distribution system like smart grid to topological reconfiguration, from datas collected for agents in electrical grid. It is expected that the conduct of research leads to several studies about better algorithms and techniques that would implement such functionality in a production environment.

Em Teoria dos Jogos, o Dilema do Prisioneiro para N Participantes (DPNP) é o problema que representa, em sua forma elementar, o paradoxo que gera as dificuldades existentes na formação da cooperação entre mais de dois agentes. Diversos trabalhos foram e continuam sendo feitos sobre esse tema, no sentido de compreender melhor os fatores que influenciam o surgimento e a evolução da cooperação numa sociedade. Neste trabalho, o objetivo principal é o de analisar o impacto do poder expressivo de um modelo de representação de estratégias neste surgimento e evolução. Para tal, foi desenvolvido um modelo computacional de jogos evolutivos, onde agentes participam repetidamente do DPNP. Nele, as estratégias que definem qual será a jogada de um determinado agente são desenvolvidas e selecionadas através de mecanismos de mutação e reprodução daquelas que obtiveram melhores resultados nas iterações anteriores, e implementadas através de duas representações com diferentes poderes computacionais: autômatos finitos e autômatos adaptativos. Este modelo foi implementado num sistema denominado S2E2 onde foram executados diversos experimentos de simulação. Através da comparação dos resultados obtidos para ambas as representações, verificou-se que em ambos os casos a sociedade consegue atingir, após um período inicial, um nível de cooperação relativamente alto e estável. A análise das estratégias utilizadas pelos agentes, entretanto, mostrou que o uso de autômatos adaptativos resulta em uma pequena vantagem, embora estatisticamente não significativa, pois permite surgir estratégias que visam retornar a uma situação de cooperação. / In Game Theory, the n-Players Prisoner\'s Dilemma (NPPD) is a problem that represents, in its elementary form, the paradox that leads to the existing difficulties in the development of cooperation between two or more agents. Many works were and are still being done about this subject, trying to better understand the factors that influence the development and evolution of cooperation in a society. In this work, the main objective is to analyze the impact of the expressive power of the strategies representation model in this development and evolution. In order to do so, a computational model of evolutionary games was developed, where agents are spatially distributed and participate on the NPPD with five participants, interacting only with their neighbors. In this model, the strategies that define the agent\'s decisions are developed and selected through mutation and reproduction of those strategies that obtained better results in the last iterations, and they are implemented by two representations with different computational power: finite automata and adaptative automata. This model was implemented in a system called S2E2 and several simulation experiments were carried on. Comparing the results obtained in those experiments, it was verified that after an initial period of time in both cases the society achieved a relatively high and stable level of cooperation. On the other hand, the analysis of the strategies used by the agents showed that the use of adaptative automata resulted in a slight advantage, although not statistically significative, because they allow the emergence of strategies that return to a situation of cooperation.

Este trabalho foi elaborado considerando conceitos de quatro áreas de pesquisa: ciência da computação, ciência cognitiva, ciência da informação e comunicação social. A contribuição principal aqui se dá em definir agentes minimamente cognitivos que participam ativamente na dinâmica do fluxo de informações, sofrendo influência das mensagens que recebem e também interferindo no que irá passar adiante. O modelo contempla tanto características relacionadas ao ambiente e sociedade, definidos usando ontologias, quanto à mente, arquitetura e funcionamento dos agentes. Cada personagem possui três módulos de decisão, podendo acessar meios de comunicação em massa, assimilar informações recebidas e também falar com seus amigos. Para o módulo de assimilação, estão apresentadas quatro formas que os agentes podem usar para avaliar as informações que recebem. Primeiramente foi elaborada uma função, depois foram definidas três máquinas de estados finitos, aumentando gradativamente a complexidade e a interdependência entre os parâmetros envolvidos em cada uma. Foi também elaborada uma função adaptativa, a qual a partir de uma regra definida pelo usuário para a troca entre as máquinas de estado que os agentes dispõem, propiciou resultados satisfatórios mesmo nos casos onde alguma das máquinas de estado apresentou deficiências. Visando reproduzir uma situação inspirada na vida real, estão apresentados resultados de uma versão combinada (definida pelo autor) onde foram considerados três grupos e a possibilidade de acesso a meios de comunicação em massa e/ou troca de mensagens entre amigos. Usando o modelo como base, um simulador foi desenvolvido onde é possível ter não só uma visão global da dinâmica que está acontecendo na sociedade, mas também o que alguns agentes ficam sabendo e que podem falar sobre. Os estudos de caso visaram comparar as diferentes formas de assimilação de informações que os agentes podem usar (elaboradas pelo autor), avaliar a influência da variação de alguns parâmetros e reproduzir a dinâmica do fluxo de informações em redes sociais, a comparando com o que acontece quando se tem a divulgação broadcast. / This work was developed considering concepts of four research areas: computer science, cognitive science, information science and social communication. The main contribution here is to define minimally cognitive agents who actively participate in dynamic of information flow interfering on the messages received and are being affected by them. The model consider characteristics related to the environment and the society, defined by using ontologies, and the \"mind\", architecture and functioning of the agents. Each character has three decision modules. They can access means of mass communication, assimilate information received and talk to their friends. To the assimilation module were presented four forms that agents can evaluate received information, a function, and three finite state machines (FSM). They were elaborated increasing the complexity. After, it was developed an adaptive function, in which using a rule the user define how to exchange between the finite state machines that agents have. This function provided satisfactory results even in cases where some of the FSMs presented problems. Aiming to reproduce a situation inspired in real life a combined version was defined by the author, in where were considered three groups that can access means of mass communication and / or talk to their friends. Based on the model, a simulator was developed in which there are not only an overview of the society dynamics, but also what agents learn and what they can talk about. The case studies were performed aiming to compare the different assimilation forms (developed by the author), to evaluate the influence of some parameters variation and to reproduce the dynamics of information flow, comparing the influence of a social network communication and the mass communication activity.

Les réseaux sont présents dans plusieurs domaines scientifiques et d’ingénierie tels que la biologie, la physique, la sociologie ainsi que la robotique ou la théorie de la communication. L’étude de ces réseaux montre qu’ils sont souvent structurés en sous-groupes. Entre eux il n’y a pas ou il y a très peu d’interaction. Par conséquent, un accord local au sein de chaque groupe est naturellement atteint alors que le consensus associé à un tel réseau doit être imposé par une loi de commande spécifique. Nous proposons donc un contrôleur discret quasi-périodique pour échanger des informations entre les groupes. Un agent de chaque groupe est choisi le « leader » et, à certains moments, ces leaders communiquent entre eux à travers un nouveau réseau. Ceci permet d’obtenir le consensus dans tout le réseau mais engendre des réinitialisation/sauts dans l’état de leaders. La première contribution de la thèse est la caractérisation de la valeur de consensus dans le cadre des systèmes linéaires impulsifs. Il est remarquable que la valeur de consensus dépende seulement des conditions initiales et des topologies des réseaux impliqués. Elle n’est donc pas sensible aux instants de réinitialisation des états de leaders. Afin d’étudier la stabilité de la valeur de consensus obtenue, nous proposons une méthode fondée sur la vérification d’une condition LMI. Cela peut être adaptée pour la conception du réseau d’interaction entre les leaders permettant d’atteindre une valeur de consensus a priori choisie. Il est aussi possible d’utiliser la condition LMI afin de garantir une vitesse de convergence désirée vers le consensus. Pour ces derniers objectifs, la topologie du réseau continue à être considérée comme fixe et connue pour chaque groupe. L’ensemble des valeurs de consensus qui peuvent être atteintes est contenu dans l’intervalle défini par le minimum et le maximum des accords locaux initiaux. Ensuite nous présentons l’étude d’un problème pratique. Des robots mobiles non-holonome, séparés dans des groupes, doivent atteindre une formation donnée. L’algorithme de consensus à pour mission de définir les trajectoires de référence pour ces robots en prenant en compte juste les informations locale. Le robot poursuit la trajectoire de référence en utilisant une commande classique pour cela. / Networks appear in several areas of science and engineering such as biology, physics, sociology as well as robotics and communication theory. Studying these networks it is possible to see cluster-like structures, which are disconnected or very weakly connected one to another. The presence of these clusters hampers consensus throughout the overall network. Instead, local agreement is reached within each cluster. To enforce consensus we have to design an appropriate decentralized controller that imposes interactions between clusters. While the interactions inside each cluster are continuous, we propose a quasi-periodic discrete controller to exchange information between clusters. A single agent from each cluster is chosen to be the leader, and at certain moments, the leaders communicate with each other through a new network. This allows consensus in the entire network but generates resets/jumps on the leaders’ state. The first contribution of this manuscript is related to the characterization of the consensus value in the linear impulsive dynamics framework. It is noteworthy that the consensus value depends only on the initial conditions and the topologies of the involved networks. Therefore, the consensus value does not depend on the reset sequence used for the leaders’ states. To study the stability of the consensus value a LMI based condition is proposed. The main advantage of this approach is its flexibility. Indeed with some modifications to the LMI condition it is possible to analyse the convergence speed of the network or to design the leaders’ network. The purpose of leaders’ network design is to reach an a priori specified consensus value with a specified convergence speed. Whatever is the objective, throughout the manuscript we consider that the network topology is fixed and known for each cluster. The set of consensus values that can be reached is restricted to the interval defined by the minimum and maximum initial local agreements. A last contribution is related to the application of the proposed methodology to a practical situation. We consider a fleet of non-holonomic mobile robots separated in clusters. The communication inside each cluster are secured and cheap while between clusters it is expensive and not securely to communicate. Nevertheless the robots have to reach a given formation. In this case our consensus algorithm is in charge of providing reference trajectories to each robot by using only the available local information. The robot follows the reference by using a classical trajectory tracking control.

Os smart grids são tidos como a nova geração dos sistemas elétricos de potência, combinando avanços em computação, sistemas distribuídos e inteligência artificial para prover maiores funcionalidades sobre acompanhamento em tempo real da demanda e do consumo de energia elétrica, gerenciamento em larga escala de geradores distribuídos, entre outras, a partir de um sistema de controle distribuído sobre a rede elétrica. Esta abordagem alteraria fundamentalmente a maneira como se dá o planejamento e a operação de sistemas de distribuição, e há grandes possibilidades de pesquisa e desenvolvimento possibilitada pela busca de implementação destas funcionalidades. Com esse cenário em vista, o presente trabalho utiliza uma abordagem a partir do uso de sistemas multiagentes para estudar o gerenciamento de sistemas de distribuição, do ponto de vista da reconfiguração da topologia da rede, simulando as características de um smart grid. Nesta dissertação, foi desenvolvido um sistema multiagente para simulação computacional de um sistema de distribuição elétrico do tipo smart grid, buscando executar a reconfiguração topológica do sistema a partir de dados de carga capturados de forma distribuída pelos agentes dispersos na rede elétrica. Espera-se que o desenrolar da pesquisa conduza à vários estudos sobre algoritmos e técnicas que melhor implementem tais funcionalidades a serem transpostas para um ambiente de produção. / Smart grids are taken as the new generation of electric power systems, combining advances in computing, distributed systems and artificial intelligence to provide more features on real-time monitoring of demand and consumption of electricity, managing large-scale distributed generators, among others, from a distributed control system on the grid. This approach fundamentally alter the way how is the planning and operation of distribution systems, and there are great possibilities for research and development offered in the quest to implement these features. With that environment, this text uses an approach through the use of multi-agent systems to study the management of the distribution system, from the reconfiguration of grid topology, simulating the characteristics of a smart grid. In this text, was developed a multiagent system to computational simulation of a distribution system like smart grid to topological reconfiguration, from datas collected for agents in electrical grid. It is expected that the conduct of research leads to several studies about better algorithms and techniques that would implement such functionality in a production environment.

Em sistemas multiagentes (SMA), a impossibilidade de controle do comportamento interno dos agentes propicia a emergência de dilemas sociais. Uma das possíveis abordagens para resolver tais dilemas é a abordagem social, que tem no conceito de reputação seu principal mecanismo de controle. Para agilizar a obtenção da reputação, torna-se essencial que os agentes cooperem, trocando informações a respeito de reputação. Assim, a partir de diversas observações, avaliações e troca de informações sobre reputação pode-se observar o surgimento da ordem social no sistema global. Entretanto, a heterogeneidade semântica entre os diferentes modelos de reputação torna a interação de agentes um problema, principalmente em SMA abertos. Este trabalho propõe uma arquitetura baseada em serviços, denominada SOARI, para o tratamento deste problema. Esta arquitetura apóia o mapeamento e tradução de conceitos entre ontologias de modelos de reputação distintos através do uso de uma ontologia comum no domínio da reputação. Para ilustrar o uso da arquitetura, foram realizados diversos experimentos nos domínios de comércio eletrônico e de avaliação de obras de arte. Neste último caso, analisou-se os impactos causados nos agentes como conseqüência da habilitação de uma maior expressividade e heterogeneidade na comunicação sobre reputação. / In Multiagent Systems (MAS), controlling the internal agent\'s behavior is impossible and therefore social dilemma may emerge. One possible approach to solve the problem is the social approach, which considers reputation as its main control mechanism. In order to accelerate the reputation evaluation, it is essential that the cooperating agents could exchange information about reputation. Thus, by using observations, evaluations and information exchange about reputation the social order in the global system may occur. However, the semantic heterogeneity of different reputation models makes agent interaction a problem, especially in open MAS. This work proposes a service oriented architecture, named SOARI, to deal with this problem. This architecture supports concept mapping and translation among different reputation model ontologies by using a common ontology. In order to illustrate its deployment, several experiments in the electronic commerce and art appraisal domains were performed. In the latter it was analyzed the effects caused on the agents as a consequence of a more expressive and heterogeneous communication about reputation.

O objetivo deste trabalho é o desenvolvimento de uma ferramenta de simulação baseada em multiagentes para calcular a emergência de parcerias entre múltiplos agentes. A metodologia adotada foi tomar como base o sistema PART-NET [CONTE’98], que efetua o cálculo da emergência de parcerias entre uma dupla de agentes, e alterá-lo de acordo com o objetivo proposto. Dessa maneira, dividiu-se o trabalho em duas etapas. Na primeira, o sistema original foi reescrito na linguagem Java, promovendo benefícios operacionais, como a melhora da interface e a apresentação dos resultados de forma gráfica. Esse sistema intermediário foi denominado PartNET+. A segunda etapa constituiu-se em expandir a funcionalidade do sistema intermediário, tornando sua arquitetura de agentes mais completa pela adição de planos, o que permite novos tipos de parcerias. Para processar essas parcerias, criou-se um novo algoritmo para cálculo de parcerias entre múltiplos agentes, com base em hipergrafos. O sistema resultante, que compreende estas extensões funcionais, foi denominado PartNET++. / The purpose of this work is the development of a multiagent based simulation tool to account partnership formation among multiple agents. In order to achieve that, the PART-NET [CONTE’98] system was adopted as a base. This system calculates the partnership formation of pairs of agents, and was altered according to the proposed objective. In this manner, the work was divided in two stages. In the first, the original system was redesigned using the Java language, bringing operational improvements to the predecessor, such as user interface enhancement and graphical display of the results. This intermediary system was named PartNET+. The second stage promotes new functionality to this intermediary system, adding plans to its agent architecture to allow new kinds of partnerships. A new algorithm for multiple agents partnership formation was developed based on hipergraphs, and the final system that handles this enhanced partnership formation was called PartNET++

Este trabalho foi elaborado considerando conceitos de quatro áreas de pesquisa: ciência da computação, ciência cognitiva, ciência da informação e comunicação social. A contribuição principal aqui se dá em definir agentes minimamente cognitivos que participam ativamente na dinâmica do fluxo de informações, sofrendo influência das mensagens que recebem e também interferindo no que irá passar adiante. O modelo contempla tanto características relacionadas ao ambiente e sociedade, definidos usando ontologias, quanto à mente, arquitetura e funcionamento dos agentes. Cada personagem possui três módulos de decisão, podendo acessar meios de comunicação em massa, assimilar informações recebidas e também falar com seus amigos. Para o módulo de assimilação, estão apresentadas quatro formas que os agentes podem usar para avaliar as informações que recebem. Primeiramente foi elaborada uma função, depois foram definidas três máquinas de estados finitos, aumentando gradativamente a complexidade e a interdependência entre os parâmetros envolvidos em cada uma. Foi também elaborada uma função adaptativa, a qual a partir de uma regra definida pelo usuário para a troca entre as máquinas de estado que os agentes dispõem, propiciou resultados satisfatórios mesmo nos casos onde alguma das máquinas de estado apresentou deficiências. Visando reproduzir uma situação inspirada na vida real, estão apresentados resultados de uma versão combinada (definida pelo autor) onde foram considerados três grupos e a possibilidade de acesso a meios de comunicação em massa e/ou troca de mensagens entre amigos. Usando o modelo como base, um simulador foi desenvolvido onde é possível ter não só uma visão global da dinâmica que está acontecendo na sociedade, mas também o que alguns agentes ficam sabendo e que podem falar sobre. Os estudos de caso visaram comparar as diferentes formas de assimilação de informações que os agentes podem usar (elaboradas pelo autor), avaliar a influência da variação de alguns parâmetros e reproduzir a dinâmica do fluxo de informações em redes sociais, a comparando com o que acontece quando se tem a divulgação broadcast. / This work was developed considering concepts of four research areas: computer science, cognitive science, information science and social communication. The main contribution here is to define minimally cognitive agents who actively participate in dynamic of information flow interfering on the messages received and are being affected by them. The model consider characteristics related to the environment and the society, defined by using ontologies, and the \"mind\", architecture and functioning of the agents. Each character has three decision modules. They can access means of mass communication, assimilate information received and talk to their friends. To the assimilation module were presented four forms that agents can evaluate received information, a function, and three finite state machines (FSM). They were elaborated increasing the complexity. After, it was developed an adaptive function, in which using a rule the user define how to exchange between the finite state machines that agents have. This function provided satisfactory results even in cases where some of the FSMs presented problems. Aiming to reproduce a situation inspired in real life a combined version was defined by the author, in where were considered three groups that can access means of mass communication and / or talk to their friends. Based on the model, a simulator was developed in which there are not only an overview of the society dynamics, but also what agents learn and what they can talk about. The case studies were performed aiming to compare the different assimilation forms (developed by the author), to evaluate the influence of some parameters variation and to reproduce the dynamics of information flow, comparing the influence of a social network communication and the mass communication activity.