Control of large groups of robotic agents is driven by applications including military, aeronautics and astronautics, transportation network, and environmental monitoring. Cooperative control of networked multi-agent systems aims at driving the behavior of the group via feedback control inputs that encode the groups’ dynamics based on information sharing, with inter-agent communications that can be time varying and be spatially non-uniform. Notably, local interaction rules can induce coordinated behaviour, provided suitable network topologies. Distributed learning paradigms are often necessary for this class of systems to be able to operate autonomously and robustly, without the need of external units providing centralized information. Compared with model-based protocols that can be computationally prohibitive due to their mathematical complexity and requirements in terms of feedback information, we present an online model-free algorithm for some nonlinear tracking problems with unknown system dynamics. This method prescribes the actuation forces of agents to follow the time-varying trajectory of a moving target. The tracking problem is addressed by an online value iteration process which requires measurements collected along the trajectories. A set of simulations are conducted to illustrate that the presented algorithm is well functioning in various reference-tracking scenarios.

No description available.

<p> Software Architecture is a concept that arose during the last two decades as a consequence of the need for a structured design at an early stage. Software Architecture is defined as a pattern of interconnected components satisfying some structural rule. Software architectures are widely used in many types of systems; Multi-Agent Systems should not be an exception. Multi-Agent Systems have emerged as a design paradigm for large and distributed systems. They are composed of autonomous elements that work together in order to pursue a common goal. They are mostly used in Electronic Commerce, Human-Computer Interfaces, and so on.</p> <p> In this research, we investigate the state of the art of Software Architectures in the Multi-Agent Systems field, showing that, generally Multi-Agent Systems do no use the software architecture concept properly and, when they do, they do not show specific architectures for Multi-Agent Systems. The approach followed is based on the analysis of six case studies, which are implemented applications that have been published in some of the most important conferences in the area. Additionally we show that, based on the initial design of each case and existing architectural patterns, it is possible to impose a software architecture on each case.</p> <p> Furthermore, we analyze the way that the term "software architecture" is used in the Multi-Agent Systems literature, showing that, usually, it refers to abstract architectures proposed in standards and frameworks or to an initial design in a system. In addition we clarify related concepts, such as reference architecture, reference models, architectural patterns and design patterns. Finally, we do an exhaustive comparison of the case studies, which aims to highlight commonalities and differences. The objective of this comparison is to analyze if they share a similar architecture that can be reused in more cases and to show how specific properties of Multi-Agent Systems affect in the design of an architecture.</p> / Thesis / Master of Science (MSc)

The problem of constructing and analyzing systems of intelligent, autonomous agents is becoming more and more important. These agents may include people, physical robots, virtual humans, software programs acting on behalf of human beings, or sensors. In a large class of multi-agent scenarios, agents may have different capabilities, preferences, objectives, and constraints. Therefore, efficient allocation of resources among multiple agents is often difficult to achieve. Automated negotiation (bargaining) is the most widely used approach for multi-agent resource allocation and it has received increasing attention in the recent years. However, information uncertainty, existence of multiple contracting partners and competitors, agents' incentive to maximize individual utilities, and market dynamics make it difficult to calculate agents' rational equilibrium negotiation strategies and develop successful negotiation agents behaving well in practice. To this end, this thesis is concerned with analyzing agents' rational behavior and developing negotiation strategies for a range of complex negotiation contexts. First, we consider the problem of finding agents' rational strategies in bargaining with incomplete information. We focus on the principal alternating-offers finite horizon bargaining protocol with one-sided uncertainty regarding agents' reserve prices. We provide an algorithm based on the combination of game theoretic analysis and search techniques which finds agents' equilibrium in pure strategies when they exist. Our approach is sound, complete and, in principle, can be applied to other uncertainty settings. Simulation results show that there is at least one pure strategy sequential equilibrium in 99.7% of various scenarios. In addition, agents with equilibrium strategies achieved higher utilities than agents with heuristic strategies. Next, we extend the alternating-offers protocol to handle concurrent negotiations in which each agent has multiple trading opportunities and faces market competition. We provide an algorithm based on backward induction to compute the subgame perfect equilibrium of concurrent negotiation. We observe that agents' bargaining power are affected by the proposing ordering and market competition and for a large subset of the space of the parameters, agents' equilibrium strategies depend on the values of a small number of parameters. We also extend our algorithm to find a pure strategy sequential equilibrium in concurrent negotiations where there is one-sided uncertainty regarding the reserve price of one agent. Third, we present the design and implementation of agents that concurrently negotiate with other entities for acquiring multiple resources. Negotiation agents are designed to adjust 1) the number of tentative agreements and 2) the amount of concession they are willing to make in response to changing market conditions and negotiation situations. In our approach, agents utilize a time-dependent negotiation strategy in which the reserve price of each resource is dynamically determined by 1) the likelihood that negotiation will not be successfully completed, 2) the expected agreement price of the resource, and 3) the expected number of final agreements. The negotiation deadline of each resource is determined by its relative scarcity. Since agents are permitted to decommit from agreements, a buyer may make more than one tentative agreement for each resource and the maximum number of tentative agreements is constrained by the market situation. Experimental results show that our negotiation strategy achieved significantly higher utilities than simpler strategies. Finally, we consider the problem of allocating networked resources in dynamic environment, such as cloud computing platforms, where providers strategically price resources to maximize their utility. While numerous auction-based approaches have been proposed in the literature, our work explores an alternative approach where providers and consumers negotiate resource leasing contracts. We propose a distributed negotiation mechanism where agents negotiate over both a contract price and a decommitment penalty, which allows agents to decommit from contracts at a cost. We compare our approach experimentally, using representative scenarios and workloads, to both combinatorial auctions and the fixed-price model, and show that the negotiation model achieves a higher social welfare.

Modern robotics demonstrates the reality of near sci-fi solutions regularly. Swarms of interconnected robotic agents have been proven to have benefits in scalability, robustness, and efficiency. In communication restricted environments, such teams of robots are often required to support their own navigation, planning, and decision making processes, through use of onboard processors and collaboration. Example scenarios that exhibit restriction include unmanned underwater surveys and robots operating in indoor or remote environments without cloud connectivity. We begin this thesis by discussing multi-agent state estimation and it's observability properties, specifically for the case of an agent-to-agent range measurement system. For this case, inspired by navigation requirements underwater, we derive several conditions under which the system's state is guaranteed to be locally weakly observable. Ensuring a state is observable is necessary to maintain an estimate of it via filters, thus observability is required to support higher level navigation and planning. We conclude this section by creating an observability-based planner to control a subset of the agents' inputs. For the next contribution, we discuss scalability for coverage maximizing path planners. Typically planning for many individual robots incurs significant computational complexity which increases exponentially with the number of agents, this is often exacerbated when the objective function is collaborative as in coverage optimization. To maintain feasibility while planning for a large team of robots, we call upon a powerful relation from combinatorics which utilizes the greedy selection algorithm and a matroid condition to create an efficient planner that maintains a fixed performance ratio when compared to the optimal path. We then introduce a motivating example of autonomously assisted search and rescues using multiple aerial agents, and derive planners and models to suit the application. The framework begins by estimating the likely locations of a lost person through a Monte Carlo simulation, yielding a heatmap covering the area of interest. The heatmap is then used in combination with parametrized agent trajectories and a machine learning optimization algorithm to maximize the search efficiency. The search and rescues use case provides an excellent computational testbed for the final portion of the work. We close by discussing a computation architecture to support multi-agent system autonomy. Modern robotic autonomy results, especially computer vision and machine learning algorithms, often require large amounts of processing to yield quality results. With general purpose computing devices reaching a progression barrier, one that is not expected to be solved in the near term, increasingly devices must be designed with their end purposes in mind. To better support autonomy in multi-agent systems, we propose to use a distributed cluster of embedded processors which allows the sharing of computation and storage resources among the component members with minimal communication overhead. Our proposed architecture is composed of mature softwares already well-known in the robotics community, Kubernetes and the robot operating system, allowing ease of use and interoperability with existing algorithms. / Doctor of Philosophy / The traditional approach of robotics typically uses a single large platform capable of accomplishing all tasks assigned to it. However, it has been discovered that deploying multiple smaller platforms, each with their own processor and specific expertise, can have massive performance benefits compared to previous approaches. This development has been driven largely by readily available computing and mobility hardware. Termed as multi-agent systems, they can excel in areas that benefit from multiple perspectives, simultaneous task execution, and redundancy. In addition, planning algorithms developed for previous approaches often can map well onto multi-agent systems, provided there is adequate computational support. In cases where network or cloud connectivity is limited, teams of agents must use their own processors and sensors to make decisions and communicate. However, often an individual agent's computing hardware is limited in mass or size, thus limiting it's processing capabilities. In this work we will first discuss several multi-agent system algorithms, starting with estimation and navigation and ending with area search. We then conclude the work by proposing a novel architecture designed to distribute the computation load across the team in a highly scalable way.

In this work, we are interested in expressing and studying certain formal properties of multi-agent games. In particular, we are interested in the case in which a team of agents with imperfect information is playing against the environment. This is modeled by a non-deterministic game, where the agents can only partially distinguish its states, to varying degrees. We will study these games under the lens of the multi-agent knowledge-based subset construction (MKBSC), which, when applied to a game, reduces the degree of imperfect information the agents have. An appropriate language to express interesting and complex properties in these type of games is the epistemic μ-calculus, an extension of classicepistemic logic with a recursive operator. We define two semantics forthis language, one corresponding to a global view of the game, and onecorresponding to a local one. We state a claim relating these two semantics,while proving an analogous statement for epistemic logic. / I detta arbete är vi intresserade av att uttrycka och studera vissa formellaegenskaper hos spel med flera agenter. Särskilt intresserade är vi av falletdär ett lag av agenter med ofullständig information samarbetar mot miljön.Detta modelleras av ett icke-deterministiskt spel, där agenterna endast delviskan särskilja dess tillstånd, i varierande grad. Vi kommer att studera dessa isammanhanget av den kunskapsbaserade multiagent-konstruktionen (MKBSC),som när den tillämpas på ett spel minskar graden av ofullständig informationagenterna har.Ett lämpligt språk för att uttrycka intressanta och komplexa egenskaper idenna typ av spel är den epistemiska μ-kalkylen, en utvidgning av klassiskepistemisk logik genom en rekursiv operator. Vi definierar två semantikerför detta språk, ett som motsvarar ett globalt perspektiv på spelet, och ettmotsvarande ett lokalt perspektiv. Vi formulerar ett påstående som rör dessatvå semantiker för μ-kalkylen, och bevisar ett analogt påstående för epistemisklogik.

Este trabalho tem por objetivo propor uma abordagem para o problema de alocação dinâmica de recursos em ambiente de produção baseada no paradigma de multiagentes. Para tanto, é especificada uma arquitetura multiagente genérica chamada M-DRAP - Multi-agent Dynamic Resource Allocation Planning, a partir da qual podem ser derivados modelos particulares. As principais contribuições deste trabalho compreendem: (i) a definição de uma estratégia que permita o planejamento dinâmico de cada recurso no atendimento as demandas das atividades de produção de forma descentralizada e distribuída, através de uma abordagem orientada a projeto; (ii) a proposição de uma organização social baseada em uma abordagem multiagente orientada a mercado, capaz de propiciar relações de negociação entre agentes autônomos no sentido de atenderem aos seus interesses individuais, contribuindo de forma efetiva para a satisfação dos objetivos e restrições temporais e de custos globais ao sistema de produção como um todo; (iii) a especificação de uma arquitetura multiagente derivada do CIMOSA, representando de forma consistente a estrutura funcional e organizacional de um sistema de produção; (iv) a definição de estratégias baseadas em negociação entre os agentes capazes de propiciarem o tratamento das perturbações que afetam o sistema de produção em tempo real. Como contribuindo associada, e proposta uma metodologia para a modelagem conceitual de sistemas multiagentes para o domínio das aplicações envolvendo modelagem de empresas. / The objective of this work is to propose an approach to the problem of dynamic resource allocation in production systems. A multi-agent reference architecture called M-DRAP - Multi-agent Dynamic Resource Allocation Planning - is specified and described in this thesis. The main contributions of this work are (i) the definition of a decentralised and distributed strategy for dynamic resource allocation planning, using a project oriented approach, (ii) the proposition of a social organisation based on marketoriented behaviour, which considers the necessity of each agent's local plan to converge to an adequate global plan in terms of production costs to the whole system, (iii) the definition of a multi-agent architecture inspired in the CIMOSA reference architecture representing a functional and organisational structure, (iv) the definition of a strategy based on negotiation which propitiates real-time disturbance treatment. As an associated contribution, we propose a methodology to multi-agent systems conceptual modelling adequate to the enterprise modelling domain.

Este trabalho encontra-se situado na área de Inteligência Artificial, mais especificamente na modelagem de Sistemas Multiagentes destinados à simulação social. A área de pesquisa de simulação social baseada em agentes é uma área recente e bastante promissora. Por tratar de problemas extremamente complexos, existe a necessidade de criar modelos e abstrações para possibilitar sua realização. Dando continuidade a trabalhos anteriores, esta tese pretende consolidar uma nova versão do modelo MAS-SOC, destinado à definição de simulações sociais baseada em Sistemas Multiagentes Situados, com organizações que funcionam em ambientes determinados (organizações situadas). É proposta uma abordagem integrada, que conecta de maneira forte as entidades agentes, organizações e ambiente, sendo os agentes, o ambiente e as estruturas da organização tratadas como entidades de primeira ordem. A definição do ambiente é feita através da linguagem ELMS, estendida com uma infraestrutura normativa. Esta infraestrutura normativa é composta basicamente por objetos normativos e espaços normativos que permitem a distribuição espacial da informação normativa no ambiente, possibilitando a contextualização das normas que os agentes devem seguir em um escopo espacial determinado. A contextualização das normas facilita a sua operacionalização e a verificação de conformidade, reduzindo também a possibilidade de interpretações errôneas das normas. Com isso, a infraestrutura normativa conecta ambiente físico à estrutura da organização do sistema multiagente. Além disso, o modelo proposto usa um esquema mínimo de definição das organizações para armazenar informações e restrições que o projetista da simulação prefira representar desta forma. Esta maneira integrada de modelar os sistemas multiagentes, associando a organização ao espaço em que a organização deve funcionar, pode facilitar a modelagem de grandes sistemas, pois o conceito de espaço normativo permite que a modelagem seja feita através da partição do ambiente físico em módulos onde as atividades da organização situada são realizadas. Assim, o modelo trata de forma bastante prática o uso das normas organizacionais que podem ser representadas através de objetos normativos. Esta forma de representação possibilita aos agentes decidirem sobre a aderência as normas, já que estas não estão embutidas no mecanismo de raciocínio dos agentes. Além disso, a forma contextualizada das normas facilita raciocínio sobre elas e possibilita a aderência a normas previamente desconhecidas pelos agentes. / This work is situated in the research area of Artificial Intelligence, specifically the modelling of Multi-agent systems for social simulation. The research area of agent based social simulation is a recent and interesting area. In order to handle with its very complex problems, it requires the development of models and abstractions to make possible its realisation. Continuing previous works, this thesis aims to consolidate extensions to the MAS-SOC model, in order to turn it into a suitable model for the social simulation based on situated multi-agent systems with organizations that operate in determined environments (situated organisations). It is proposed an integrated approach in which multiagent entities such as agents, organisations and environments are strongly connected to each other, and the environment and the organisational structures being treated as first order entities. The definition of the environment is made with the use of the ELMS language, which have been extended with a normative infrastructure. The normative infrastructure is composed essentially by normative objects and normative places, which are means for the spatial distribution of the normative information over the environment, allowing the contextualisation of the norms in a bounded spatial scope. The norms being bounded in a specific spatial scope facilitates its operationalisation and conformity checks, also reducing the possibilities of norms misinterpretations. Thus, the normative infrastructure connects the physical environment to the organisational structures of the multiagent system. The thesis proposes that this integrated approach to model multi-agent systems may ease the modelling of large scale systems, since it allows the partition of the environment in a modular way, facilitating the operationalisation and verification of the adequacy of the structure of an organisation to the physical space where it is located, and also reducing the possibility of the misinterpretations of norms by the agents, through the contextualisation of norms. Also, the proposed scheme uses a minimal structure for the definition of the organisations in order to store information that the simulation designer prefers to represent in such way. Further, the proposed approach allows a very practical way to use of norms in a physical environment, by allowing the agents to reason about following a norm abiding behaviour or not, since the norms are not hard-wired in their reasoning mechanisms, and its contextualized form facilitates that agents reason about adhering to norms that were previously unknown to them.

Depuis 5 à 10 ans, les recherches sont nombreuses sur la réduction de l'énergie en l'informatique (principalement sur la réduction de l'électricité). Plusieurs études ont en effet alerté les intervenants et les organismes environnementaux sur l'urgence du problème de la consommation d'énergie des infrastructures à grande échelle, comme les centres de données, l'informatique en nuage ??ou simplement les sociétés exploitant des serveurs et de nombreux équipements IT. Cette prise de conscience est passée d'un problème peu important à une contrainte majeure sur le fonctionnement de ces infrastructures. Dans certains cas, les coûts d'exploitation surpassent les coûts d'investissement, et de nouvelles méthodologies sont nécessaires pour réduire les coûts et l'impact écologique. De nouveaux matériels sont développés par les fabricants d'équipements pour diminuer ces coûts. Seules quelques techniques de base sont offertes aux niveaux logiciels et intergiciels, par les éditeurs. Mais dans les laboratoires, certaines techniques ont prouvé leur efficacité sur des données synthétiques, des tâches dédiées ou des applications sélectionnées, pour être en mesure d'économiser de l'énergie au cours de la vie d'une infrastructure, dans plusieurs contexte, depuis le Cloud au HPC. Malheureusement, le transfert (ou même la connaissance de l'existence) de ces techniques aux industries est limité à des partenaires de projets, des entreprises innovantes ou de grands centres de recherche privés, capables d'investir du temps (et donc de l'argent) sur ce sujet. Dans ma thèse, je m'intéresse sur les raisons de la faible adoption de plusieurs résultats de la recherche, des plus simples aux plus élaborés et je modélise les liens et les interactions entre les acteurs du transfert technologique. Le champ cible a été limité au Green IT (ou informatique éco-responsable), mais la méthodologie et les modèles développés peuvent être étendus à d'autres domaines. L'idée est d'identifier ce qui manque et comment augmenter la vitesse du transfert des connaissances scientifiques. La méthodologie est basée sur le cheminement suivant: d'abord, identifier les acteurs impliqués dans le processus de transfert technologique, comprendre leurs motivations, leurs moyens d'actions et leurs limites. Après une étude de l'état de l'art dans le domaine de la diffusion de l'innovation et de la gestion de l'innovation, cette phase a consisté à la production et l'analyse d'une enquête dédiée ciblant des chercheurs et des entreprises, de tailles et de chiffre d'affaire différentes, restreinte à ceux qui travaillent dans le Green IT. Identifier chaque acteur ne suffit pas, car ils interagissent, et par conséquent, leurs liens et le potentiel de ces liens pour le transfert technologique ont également été étudiés avec soin dans une deuxième phase afin d'identifier les plus importants, avec la même méthodologie que l'identification des acteurs. A partir de ces deux phases, un système multi-agents (SMA) a été conçu. / Over the past 5 to 10 years, research is numerous on energy reduction in IT (mainly electricity reduction). Several studies indeed alerted the stakeholders and environmental agencies on the urgency of the problem of the energy consumption of large scale infrastructures, like data centres, clouds or simply companies running servers and lots of IT equipment. This awareness moved from a non-so-important issue to major constraints on the operation of these infrastructures. In some cases, the operational costs reach the investment costs, urging new methodologies to appear in order to reduce costs and ecological impact. As of today, new hardware are developed by equipment manufacturers to decrease these costs. Only few and basic techniques are offered at the software and middleware levels out-of-the-box: But in laboratories, some techniques have proven on synthetic data, dedicated workflows or selected applications, to be able to save energy during the lifetime of an infrastructure, in several contexts, from Cloud to HPC in particular. Unfortunately, the transfer (or even the knowledge of the existence) of these techniques to industries is limited to project partners, innovative companies or large private research centres, able to invest time (thus money) on this topic. In my thesis, I investigate the reasons restraining the large adoption of several research results, from the simpler ones to more elaborated ones and I model the ties and interactions between the actors of the technological transfer. The target field has been restricted to Green IT but the methodology and the developed models can be extended to other domains as well. The idea is to identify, on the scale of technical maturity for wider adoption, what is missing and how to increase the speed of the transfer of scientific knowledge. The methodology is based on the following path: First, identifying the actors involved in the process of technology transfer, and understanding their motivations, their means of actions and their limitations. After a study of the state of the art in the domain of innovation diffusion and innovation management, this phase involved the production and the analysis of a dedicated survey targeting researchers and companies, from different size and turnover, restricted to those working in the Green IT field. Identifying each actor is not sufficient since they all interact; therefore their links and the potential of these links for technology transfer have also been studied carefully in a second phase so as to identify the most important ones, with the same methodology with the actors' identification. From these two phases, a multi-agent system (MAS) has been designed.

Este trabalho tem por objetivo propor uma abordagem para o problema de alocação dinâmica de recursos em ambiente de produção baseada no paradigma de multiagentes. Para tanto, é especificada uma arquitetura multiagente genérica chamada M-DRAP - Multi-agent Dynamic Resource Allocation Planning, a partir da qual podem ser derivados modelos particulares. As principais contribuições deste trabalho compreendem: (i) a definição de uma estratégia que permita o planejamento dinâmico de cada recurso no atendimento as demandas das atividades de produção de forma descentralizada e distribuída, através de uma abordagem orientada a projeto; (ii) a proposição de uma organização social baseada em uma abordagem multiagente orientada a mercado, capaz de propiciar relações de negociação entre agentes autônomos no sentido de atenderem aos seus interesses individuais, contribuindo de forma efetiva para a satisfação dos objetivos e restrições temporais e de custos globais ao sistema de produção como um todo; (iii) a especificação de uma arquitetura multiagente derivada do CIMOSA, representando de forma consistente a estrutura funcional e organizacional de um sistema de produção; (iv) a definição de estratégias baseadas em negociação entre os agentes capazes de propiciarem o tratamento das perturbações que afetam o sistema de produção em tempo real. Como contribuindo associada, e proposta uma metodologia para a modelagem conceitual de sistemas multiagentes para o domínio das aplicações envolvendo modelagem de empresas. / The objective of this work is to propose an approach to the problem of dynamic resource allocation in production systems. A multi-agent reference architecture called M-DRAP - Multi-agent Dynamic Resource Allocation Planning - is specified and described in this thesis. The main contributions of this work are (i) the definition of a decentralised and distributed strategy for dynamic resource allocation planning, using a project oriented approach, (ii) the proposition of a social organisation based on marketoriented behaviour, which considers the necessity of each agent's local plan to converge to an adequate global plan in terms of production costs to the whole system, (iii) the definition of a multi-agent architecture inspired in the CIMOSA reference architecture representing a functional and organisational structure, (iv) the definition of a strategy based on negotiation which propitiates real-time disturbance treatment. As an associated contribution, we propose a methodology to multi-agent systems conceptual modelling adequate to the enterprise modelling domain.