För att ta reda på hur väl en Multi-Agent-Systems-bot kan stå sig mot andra, icke-MAS-bottar, så har vi implementerat en bot till brädspelet Arimaa. Botten är implementerad i C++ och den kan spela mot andra bottar, eller människor, genom Arimaas officiella hemsida. Syftet har varit att skapa en fullfjädrad bot som både klarar av att spela korrekt, och att spela bra. För att ta reda på om MAS är en bra designfilosofi för Arimaa så har vi utmanat ett antal av de bottar som andra människor skapat och lagt upp på hemsidan. Alla bottarna har under tiden de legat uppe blivit rankade genom tävlingar och utmaningar och flera av dessa har tävlat om stora pengar, vilket betyder att människor har lagt mycket tid på dem. Efter ett stort antal matcher mot andra bottar så har vi kommit fram till att Arimaa är ett väldigt svårt spel att koda bottar till. Vi lyckades bara slå några av de sämsta bottarna på hemsidan men MAS visar stor potential och vi tror att man kan göra väldigt avancerade bottar med det. Jämfört med de bästa bottarna så är vår väldigt snabb och minneseffektiv. Man borde absolut experimentera mer.

With the help of rapidly advancing communication technology, control systems are increasingly integrated via communication networks. Networked control systems (NCSs) bring significant advantages such as flexible and scalable structures, easy implementation and maintenance, and efficient resources distribution and allocation. NCSs empowers to finish some complicated tasks using some relatively simple systems in a collaborated manner. However, there are also some challenges and constraints subject to the imperfection of communication channels. In this thesis, the stabilization problems and the performance limitation problems of control systems subject to networked-induced constraints are studied. Overall, the thesis mainly includes two parts: 1) Consensus and consensusability of multi-agent systems (MASs); 2) Delay margins of NCSs. Chapter 2 and Chapter 3 deal with the consensus problems of MASs, which aim to properly design the control protocols to ensure the state convergence of all the agents. Chapter 4 and Chapter 5 focus on the consensusability analysis, exploring how the dynamics of the agents and the networked induced constraints impact the overall systems for achieving consensus. Chapter 6 pays attention to the delay margins of discrete-time linear time-invariant (LTI) systems, studying how the dynamics of the plants limit the time delays that can be tolerated by LTI controllers. In Chapter 2, the leader-following consensus problem of MASs with general linear dynamics and arbitrary switching topologies is considered. The MAS with arbitrary switching topologies is formulated as a switched system. Then the leaderfollowing consensus problem is transformed to the stability problem of the corresponding switched system. A necessary and sufficient consensus condition is derived. The condition is also extended to MASs with time-varying delays. In Chapter 3, the consensus problem of MASs with general linear dynamics is studied. Motivated by the multiple-input multiple-output (MIMO) communication technique, a general framework is considered in which different state variables are exchanged in different independent communication topologies. This novel framework could improve the control system design flexibility and potentially improve the system performance. Fully distributed consensus protocols are proposed and analyzed for the settings of fixed and switching multiple topologies. The protocols can be applied using only local information. And the control gains can be designed depending on the dynamics of the individual agent. By transforming the overall MASs into cascade systems, necessary and sufficient conditions are provided to guarantee the consensus under fixed and switching state-variables-dependent topologies, respectively. Chapter 4 investigates the consensusability problem for MASs with time-varying delays. The bounded delays can be arbitrarily fast time-varying. The communication topology is assumed to be undirected and fixed. Considering general linear dynamics under average state protocols, the consensus problem is then transformed into a robust control problem. Sufficient frequency domain criteria are established in terms of small-gain theorem by analyzing the delay dependent gains for both continuoustime and discrete-time systems. The controller synthesis problems can be solved by applying the frequency domain design methods. The consensusablity problem of general linear MASs considering directed topologies are explored from a frequency domain perspective in Chapter 5. By investigating the properties of Laplacian spectra, a consensus criterion is established based on the stability of several complex weighted closed-loop systems. Furthermore, for singleinput MASs, frequency domain consensusability criteria are proposed on the basis of the stability margins, which depend on the H∞ norm of the complementary sensitivity function determined by the agents’ unstable poles. The corresponding design procedure is also developed. Chapter 6 studies the delay margin problem of discrete-time LTI systems. For general LTI plants with multiple unstable poles and nonminimum phase zeros, we employ analytic function interpolation and rational approximation techniques to derive bounds on delay margins. Readily computable and explicit lower bounds are found by computing the real eigenvalues of a constant matrix, and LTI controllers can be synthesized based on the H∞ control theory to achieve the bounds. The results can be also consistently extended to the case of systems with time-varying delays. For first-order unstable plants, we also obtain bounds achievable by proportionalintergral- derivative (PID) controllers, which are of interest to PID control design and implementation. It is worth noting that unlike its continuous-time counterpart, the discrete-time delay margin problem being considered herein constitutes a simultaneous stabilization problem, which is known to be rather difficult. While previous work on the discrete-time delay margin led to negative results, the bounds developed in this chapter provide instead a guaranteed range of delays within which the delayed plants can be robustly stabilized, and in turn solve the special class of simultaneous stabilization problems in question. Finally, in Chapter 7, the thesis is summarized and some future research topics are also presented. / Graduate

In order to succeed, it is imperative that all e-commerce systems include an effective and reliable trust and reputation modeling system. This is particularly true of decentralized e-commerce systems in which autonomous software engage in commercial transactions. Many researchers have sought to overcome the complexities of modeling a subjective, human concept like trust, resulting in several trust and reputation models. While these models each present a unique offering and solution to the problem, several issues persist. Most of the models require direct experience in the e-commerce system in order to make effective trust decisions. This leaves new agents and agents who only casually use the e-commerce system vulnerable. Additionally, the reputation ratings of agents who are relatively new to the system are often indistinguishable from scores for poorly performing agents. Finally, more tactics to defend against agents who exploit the characteristics of the open, distributed system for their own malicious needs are required. To address these issues, a new metric is devised and presented: seniority. Based on agent age and activity level within the e-commerce system, seniority provides a means of judging the credibility of other agents with little or no prior experience in the system. As the results of experimental analysis reveals, employing a reputation model that uses seniority provides considerable value to agents who are new agents, casual buyer agents and all other purchasing agents in the e-commerce system. This new metric therefore offers a significant contribution toward the development of enhanced and new trust and reputation models for deployment in real-world distributed e-commerce environments.

No description available.

Multi-Agent Systems (MASs) and Partial and Ordinary Differential Equations (PDEs and ODEs respectively) have often been employed by researchers to effectively model and simulate Complex Adaptive Systems (CASs). PDEs and ODEs are reduction based approaches which view the system globally and ignore any local interactions and processes. MASs are considered by many to be a better tool to model CASs, but have issues as well. Case in point, there is concern that present day MASs fail to capture the true essence of inter-cellular communication in a CAS. In this work we present a realistic and utilizable communication framework for inter-agent communication for a CAS simulation. We model the dynamic properties of the communication signals and show that our model is a realistic model for inter-cellular communication. We validate our system by modeling and simulating pattern formation in Dictyostelium discoideum, a unicellular organism. / Master of Science

Cette thèse porte sur le problème du transport à la demande (TAD). Nous proposons trois approches décentralisées basées sur les systèmes multi-agents pour résoudre ce problème. La première approche multi-agent utilise l'algorithme A* afin de trouver une solution optimale dans un réseau routier caractérisé par des vitesses de voyage constantes. Des expérimentations sont effectuées sur le réseau routier d'une ville libanaise appelée Tripoli et de bons résultats sont obtenus. Cependant, dans une ville comme Tripoli, les vitesses de voyage dépendent fortement de la situation dynamique du trafic routier. Pour cette raison, la deuxième approche multi-agent massif vient remédier à la première en tenant compte de l'évolution du trafic. Le réseau routier est considéré comme dynamique déterministe. Il se caractérise par des vitesses de voyages dépendantes de la situation habituelle du trafic. Ces vitesses sont pré-calculées en se basant sur des connaissances historiques du trafic routier. Les résultats expérimentaux montrent que le nombre de clients insatisfaits est supérieur à 50 % si les vitesses sont considérées comme constantes. Or, les connaissances historiques ne suffisent pas pour refléter la situation réelle du trafic surtout en cas d'apparition d'un événement imprévu tel qu'un accident sur le réseau. Pour cela, une troisième approche multi-agent massif auto-organisé est proposée. Le réseau routier est considéré comme dynamique stochastique caractérisé par des vitesses de voyage dépendantes de la situation réelle du trafic. Cette approche représente l'organisation dynamique du trafic à son échelle en se basant sur des connaissances historiques du trafic et sur des informations du trafic en temps réel. Les trajectoires des véhicules et leurs durées sont calculées et recalculées en ligne à chaque fois qu'un événement imprévu perturbe la situation habituelle du trafic. Les résultats expérimentaux montrent que jusqu'à 39 % des clients seront insatisfaits si un accident routier n'est pas considéré durant le traitement de leurs demandes. Autrement, 50 % à 100 % de ces clients sont satisfaits. / This thesis addresses the problem of on-demand transport (ODT). We propose three decentralized approaches based on multi-agent systems to solve this problem. The first multi-agent approach uses the algorithm A* in order to find an optimal solution in a road network characterized by constant travel speeds. Experiments are carried out on the road network of a Lebanese city called Tripoli and good results are obtained. However, in a city like Tripoli, travel speeds depend heavily on the dynamic situation of road traffic. For this reason, the second multi-agent approach massif comes to remedy the first taking into account the evolution of traffic. The road network is considered as dynamic deterministic. It is characterized by travel speeds dependent on the usual traffic situation. These speeds are pre-calculated on the basis of historical knowledge of road traffic. The experimental results show that the number of dissatisfied customers is greater than 50 % if the speeds are considered to be constant. Nevertheless, historical knowledge is not sufficient to reflect the actual traffic situation, especially in case of an unexpected event (such as an accident) occurring on the network. For this, a self-organized massive multi-agent approach is proposed. The road network is considered as a dynamic stochastic characterized by travel speeds dependent on the actual traffic situation. This approach represents the dynamic organization of traffic on its scale based on historical traffic knowledge and real-time traffic information. Vehicle trajectories and their durations are calculated and recalculated online whenever an unexpected event disrupts the usual traffic situation. The experimental results show that up to 39 % of customers will be dissatisfied if a road accident is not considered during the processing of their demands. Otherwise, 50 % to 100 % of these customers are satisfied.

Blockchains address trust through cryptography and consensus. Bitcoin is the first digital currency without trusted agents. Ethereum extends this technology by enabling agents on a blockchain, via smart contracts. However, a systemic trust model for smart contracts in blockchains is missing. This thesis describes the ecosystem of smart contracts as an open multi-agent system. A trust model introduces social control through deposits and review agents. Trust-related attributes are quantified in 2,561 smart contracts from GitHub. Smart contracts employ a mean of three variables and functions and one in ten has a security-related issue. Moreover, blockchains restrict computation tasks. Resolving these restrictions while maintaining trust requires verifiable computation. An algorithm for verifiable computation is developed and implemented in Solidity. It uses an arbiter enforcing the algorithm, computation services providing and verifying solutions, and a judge assessing solutions. Experiments are performed with 1000 iterations for one to six verifiers with a cheater prior probability of 30%, 50%, and 70%. The algorithm shows linear complexity for integer multiplication. The verification depends on cheater prior probability and amount of verifiers. In the experiments, six verifiers are sufficient to detect all cheaters for the three prior probabilities. / Blockchains adresserar tillit genom kryptografi och konsensus. Bitcoin är den första digitala valutan utan betrodda agenter. Ethereum utökar denna teknik genom att möjliggöra agenter i blockchain, via smart contracts. En systemisk förtroende modell för smart contracts i blockchains saknas emellertid. Denna avhandling beskriver ekosystemet för smarta kontrakt som ett öppet multi-agent system. En förtroendemodell introducerar social kontroll genom inlåning och granskningsagenter. Tillitrelaterade attribut kvantifieras i 2,561 smart contracts från GitHub. De använder ett medelvärde av tre variabler och funktioner med en av tio som har en säkerhetsre-laterad fråga. Dessutom blockchains begränsa beräkningsuppgifter. Att lösa dessa begränsningar samtidigt som du behåller förtroendet kräver kontrollerbar beräkning. En algoritm för verifierbar beräkning utvecklas och implementeras i Solidity. Den använder en arbiter som tillämpar algoritmen, computation services som tillhandahåller och verifierar lösningar och en judge som bedömer lösningar. Experiment utförs med 1000 iterationer för en till sex verifierare med en snyggare sannolikhet för 30%, 50% och 70%. Algoritmen visar linjär komplexitet för heltalsmultiplicering. Verifieringen beror på fuskans tidigare sannolikhet och antal verifierare. I experimenten är sex verifierare tillräckliga för att detektera alla cheaters för de tre tidigare sannolikheterna.

Doctor of Philosophy / Department of Computing and Information Sciences / Scott A. DeLoach / Coalition formation is a key cooperative behavior of a system of multiple autonomous agents. When the capabilities of individual agents are not su fficient for the improvement of well-being of the individual agents or of the entire system, the agents can bene t by joining forces together in coalitions. Coalition formation is a technique for finding coalitions that are best fi tted to achieve individual or group goals. This is a computationally expensive task because often all combinations of agents have to be considered in order to find the best assignments of agents to coalitions. Previous research has therefore focused mainly on small-scale or otherwise restricted systems. In this thesis we study coalition formation in large-scale multi-agent systems. We propose an approach for coalition formation based on multi-agent simulation. This approach allows us to find coalitions in systems with thousands of agents. It also lets us modify behaviors of individual agents in order to better match a specific coalition formation application. Finally, our approach can consider both social welfare of the multi-agent system and well-being of individual self-interested agents. Power distribution systems are used to deliver electric energy from the transmission system to households. Because of the increased availability of distributed generation using renewable resources, push towards higher use of renewable energy, and increasing use of electric vehicles, the power distribution systems are undergoing signi ficant changes towards active consumers who participate in both supply and demand sides of the electricity market and the underlying power grid. In this thesis we address the ongoing change in power distribution systems by studying how the use of renewable energy can be increased with the help of coalition formation. We propose an approach that lets renewable generators, which face uncertainty in generation prediction, to form coalitions with energy stores, which on the other hand are always able to deliver the committed power. These coalitions help decrease the uncertainty of the power generation of renewable generators, consequently allowing the generators to increase their use of renewable energy while at the same time increasing their pro fits. Energy stores also bene t from participating in coalitions with renewable generators, because they receive payments from the generators for the availability of their power at speci fic time slots. We first study this problem assuming no physical constraints of the underlying power grid. Then we analyze how coalition formation of renewable generators and energy stores in a power grid with physical constraints impacts the state of the grid, and we propose agent behavior that leads to increase in use of renewable energy as well as maintains stability of the grid.

Durant ces dernières années, la congestion du trafic urbain et la pollution de l'air sont devenus d'énormes problèmes dans de nombreuses villes dans le monde. Afin de réduire cette congestion, nous pouvons investir dans l'amélioration des infrastructures de la ville. Toutefois, cette solution reste très coûteuse à entreprendre et de ne permet pas de réduire la pollution de l'air. C'est pourquoi nous travaillons sur la mobilité intelligente afin de disposer d'une meilleure utilisation de la voiture. L'application de nouvelles technologies de l'information, tels que les systèmes multi-agents appliqués au contrôle de l'information de la circulation urbaine, a permis de créer et de déployer une gestion plus intelligente du trafic comme le système DRT (transport à la demande). L'objectif des systèmes multi-agents basés sur le DRT est de gérer les taxis de manière intelligente, afin d'accroître le nombre de passagers dans chaque véhicule, et en même temps à réduire le nombre de véhicules dans les rues. Cela permettra de réduire les émissions de CO2 et la pollution de l'air causée par les véhicules, ainsi que la congestion du trafic et les coûts financiers associés. La simulation multi-agents est considérée comme un outil efficace pour les services dynamiques urbains de la circulation. Toutefois, le principal problème est de savoir comment construire un agent à base de modèle pour cette problématique. Ces travaux de recherche présente une solution basée sur les systèmes multi-agents réactifs pour la problématique du transport à la demande (DRT), qui adopte une approche multi-agent de planification urbaine en utilisant des services de contrôle qui satisfont aux principales contraintes : réduction de la période totale creuse, demandes spéciales du client, augmentation du nombre de places utilisées dans un même taxi, utilisation du nombre minimal de véhicules, etc. Dans cette thèse, nous proposons un modèle multi-agents multicouche hybride distribué pour des problématiques en temps réel. Dans la méthode proposée, un agent pour chaque véhicule trouve un ensemble de routes pour sa recherche locale, et choisit un itinéraire en coopérant avec d'autres agents se trouvant dans son domaine de planification. Nous avons examiné expérimentalement, l'efficacité de la méthode proposée. / In recent years, urban traffic congestion and air pollution have become huge problems in many cities in the world. In order to reduce congestion, we can invest in improving city infrastructures. Infrastructure improvements, however, are very costly to undertake and do not reduce air pollution. Hence we can work on intelligent mobility in order to have a more efficient car use. The application of new information technologies, such as multi-agent technologies to urban traffic information control, has made it possible to create and deploy more intelligent traffic management like DRT (Demand Responsive Transport) system. The objective of multi-agent based DRT system is to manage taxis in an intelligent way, to increase the efficient number of passengers in every vehicle, and at the same time to decrease the number of vehicles on streets. This will reduce the CO2 emissions and air pollution caused by the vehicles, as well as traffic congestion and financial costs. Multi-agent simulation has been looked as an efficient tool for urban dynamic traffic services. However, the main problem is how to build an agent-based model for it. This research presents a multi-agent based demand responsive transport (DRT) services model, which adopts a practical multi-agents planning approach for urban DRT services control that satisfies the main constraints: minimize total slack time, client’s special requests, increases taxis’ seats use ratio, and using minimum number of vehicle etc. In this thesis, we propose a multi-agent based multi-layer distributed hybrid planning model for the real-time problem. In the proposed method, an agent for each vehicle finds a set of routes by its local search, and selects a route by cooperation with other agents in its planning domain. By computational experiments, we examine the effectiveness of the proposed method. This research is supported by project “Gestion Temps Réel du Transport Collectif à la Demande” (CPER) Budgetthe French.

Ce travail de recherche est consacré à la formalisation et à la réalisation d’un processus de diagnostic pluridisplinaire. La particularité d’un tel diagnostic résulte du fait qu’il nécessite de nombreux spécialistes, chacun ayant des connaissances sur leur domaine. Le problème principal réside dans les interconnexions entre les domaines. Ces interconnexions peuvent ou non être connues et influer sur le diagnostic. Dans ce manuscrit, nous proposons de réaliser un diagnostic pluridisciplinaire l’aide d’un système multi-agents. Les agents élaborent un diagnostic local à un domaine puis, fusionnent leurs diagnostics afin d’obtenir le diagnostic pluridisciplinaire. Dans ce but, nous proposons un cadre d’argumentation et une méthode de fusion des diagnostics. Ensemble, ces deux propositions forment le modèle ANDi. / Sharing opinions among different participants is a useful and common way to build a constructive argumentation in order to solve complex problems that require the confrontation of different discipline areas. In such settings, experts build different arguments in relation to their own discipline area, then share and confront them to the other experts’ opinions. In this report we present an argumentative framework ANDi based on a multi-agent approach and Bayesian networks. In this framework, the agents support the elaboration of a global diagnostic from local ones. Local diagnostics are resulting of argumentations between group of experts from the same discipline area. We illustrate the use of this argumentation framework on the domain of fault diagnosis.