Cette thèse porte sur le problème d'allocation de ressource décentralisée, sans argent, où les agents n'ont qu'une connaissance partielle sur le système. L'approche de la thèse sera d'utiliser des échanges locaux, plus exactement des swaps, c'est-à-dire des échanges bilatéraux où chaque agent donne une ressource en échange d'un autre. Le travail se divise en deux parties. La première se concentre sur les problèmes de house market, avec une approche très simple et les agents travaillent sans les connaissances. Le but sera de montrer qu'elle a quand même une performance honorable. Je mettrais en valeur notamment que l'algorithme s'en sort bien par rapport à ceux de la littérature. Et je montrerais même que dans le domaine unimodal, l'algorithme est Pareto-optimal. La deuxième se présente dans une situation plus générale, et où le mécanisme présenté est divisée en 3 parties : protocole de contact, protocole de négociation, et conditions d'arrêt. chaque partie a plusieurs variantes. Je les décrirais et je les testerais expérimentalement. / This thesis covers distributed resources allocation setting, without money balance, where agents have limited knowledge of the system. This thesis will use local swaps, i.e. bilateral deals, where one resource is exchanged for another. This work is divided in two parts. The first part focus the house market, with a very simple mechanism and agents don't use knowledge. The aim will to show that it has however good performances. For this, I will compare the algorithm with those of literature. I will also prove that in the single-peaked domains, this mechanism is Pareto-optimal. The second part examines a general framework. The mechanism contains three sub-protocols : contact protocol, negotiation protocols, and stop conditions. Each protocol will be described and experimented.

L'évolution des technologies de l'information ainsi que la miniaturisation constante des composants électroniques de ces dernières décennies ont permis de doter les objets de la vie de tous les jours de capacités de calcul et de communication. Ces objets connectés sont disséminés dans l'environnement de l'utilisateur et coopèrent les uns avec les autres afin de fournir à l'utilisateur des services intelligents de manière totalement transparente et non intrusive. Ces environnements sont caractérisés par une grande hétérogénéité ainsi qu'une grande dynamicité. Les intégrations dites verticales (les données des capteurs sont externalisées sur les serveurs d'une entreprise) permettent certes une interopérabilité plus importante, mais engendrent des problèmes de saturation des canaux de communication, ainsi que des questionnements sur la sécurité et la confidentialité de des informations. Pour pallier ces problèmes, les intégrations dites horizontales (les entités matérielles sont mises en relation directement au sein de l'infrastructure) sont encouragées. Dans cette thèse, nous adressons le problème du déploiement et de la configuration automatique d'applications au sein de tels environnements ambiants. Nous proposons des mécanismes permettant, à partir d'une description de l'environnement ambiant, la sélection et la configuration d'entités matérielles qui supporteront l'exécution des applications. Ces mécanismes ont été encapsulé dans un intergiciel basé sur le paradigme Multi-agents dans lequel les différents agents logiciels du système collaborent afin de sélectionner les entités de l'infrastructure respectant les besoins et les contraintes des applications à déployer. / Research domains like Ambient Intelligence or Internet of Things came up in the early 2000’s with the technologic improvement and the ongoing miniaturization of electronic devices. These electronic and information devices are scattered in the user’s environment, can communicate and exchange data more and more easily to provide intelligent and non-intrusive services to the users. However, it is difficult to have generic implementations of these applications. These difficulties are due the the high heterogeneity and dynamicity of the ambient environments. Vertical integrations of connected devices (data exchanges from the devices to external servers) allow more interoperability but generate overloads of the communication channels and privacy concerns. To prevent these problems, horizontal approaches (connected devices communicate directly together through the hardware infrastructure) have to be encouraged. In this thesis work, we address the problem of the automatic deployment and configuration of distributed applications in these ambient environments. We propose mechanisms that allow, from a description of the environment, the selection and the configuraion of the hardware entities that will support the execution of applications. These mechanisms are encapsulated in a middleware based on the multi-agent paradigm. The different agents of the system cooperate in order to select the right hardware entities that respects the requirements and the constraints of the applications we want to deploy.

L’analyse des réseaux sociaux a conduit à la découverte d’une propriété très intéressante : ces réseaux se caractérisent par l’existence de zones de forte densité constituées d’éléments fortement connectés entre eux. Ces zones appelées "communautés", évoluent au cours du temps suivant la dynamique des acteurs sociaux et de leurs interactions. L’identification de ces communautés offre un éclairage intéressant sur la structure du réseau et permet de suivre leur évolution au fil du temps. Bien que ce problème ait donné lieu à de très nombreux travaux ces dernières années, la détection des communautés dynamiques reste encore un problème ouvert et aucune solution entièrement satisfaisante n’est encore proposée. Dans ce travail, nous proposons une approche multi-agents pour la détection des communautés dans les réseaux sociaux dynamiques. Les entités de notre approche observent l’évolution du réseau, et en conséquence, elles adaptent en temps réel le graphe représentant le réseau et elles engendrent les modifications adéquates sur les communautés précédemment détectées. Cette approche permet de modéliser le réseau par un graphe dynamique qui s’adapte en fonction l’évolution observée dans le réseau. Pour cette modélisation, plusieurs aspects du réseau sont intégrés : la structure topologique du graphe, la similarité sémantiques des membres sociaux et la communication entre eux. Cette modélisation se base sur le concept d’homophilie et sur une stigmergie à base des phéromones. Afin d’étudier les performances de l’approche proposée, nous l’avons appliquée sur un ensemble très varié de graphes réels et artificiels. Les résultats ont été suffisamment satisfaisants et montrent la bonne performance de notre modèle. / Analysis of social networks has led to the discovery of a very interesting property : these networks are characterized by the existence of areas with high density composed of highly interconnected elements. These areas called "communities", evolve over time according to the dynamic of social members and their interactions. The identification of these communities offers an interesting light on the network structure and it allows to track their progress over time. Although this problem has been the subject of numerous studies in recent years, the detection of dynamic communities remains an open problem and no fully satisfactory solution has yet been proposed. In this work, we propose a multi-agent approach for the detection of communities in dynamic social networks. The entities of our approach observe the evolution of the network and consequently they adapt in real time the graph representing the network and they generate the appropriate changes on previously identified communities. This approach allows to model the network by a graph that dynamically adapts according to the evolution of the network. For this modeling, several network’s aspects are integrated: the topological structure of the graph, the semantic similarity of social members and the communication between them. This modeling is based on the concept of homophily and a pheromone based stigmergy. In order to study the performances of the proposed approach, we applied it to a divers set of real and artificial graphs. The results were satisfactory enough and show the good performance of our model.

<p>In this thesis, we present algorithms to allow agents to estimate certain properties in a robust, online, and distributed manner. Each agent receives a sequence of observations, and through communication, collectively infers properties of the data gathered by all agents by communicating.</p> <p><br></p> <p>In the first part of the thesis, we provide algorithms to infer the correlations between interacting entities from these large datasets. Gaussian graphical models have been well studied to represent the relationships between the various random variables which generate data, and numerous algorithms have been proposed to learn the dependencies in such models. However, existing algorithms typically process data in a batch at a central location, limiting their applications in scenarios where data arrive in real-time and are gathered by different agents.  </p> <p><br></p> <p>To address these challenges, first, we propose an online sparse inverse covariance algorithm to infer the static network structure (i.e., dependencies between nodes) in real-time from time-series data, in a centralized location. Subsequently, we propose a distributed algorithm to cooperatively learn the network structure in real-time from data collected by distributed agents. We characterize the theoretical convergence properties and provide simulations using synthetic datasets and real-world hurricane Twitter datasets in disaster management applications.    </p> <p><br></p> <p>The second part of this thesis addresses the robustness of online and distributed learning under arbitrary data corruption. We propose online and distributed algorithms for robust mean, covariance, and sparse inverse covariance estimation. These algorithms are capable of operating effectively even in the presence of adversarial data attacks. We provide theoretical bounds on the error and rate of convergence of these methods and evaluate their performance under various settings.</p> <p><br></p> <p>Finally, we consider the problem of classification with a network of heterogeneous and partially informative agents, each receiving local data from an underlying true class, and equipped with a classifier that only distinguishes between a subset of the entire set of classes. We propose an iterative algorithm that uses the posterior probabilities of any classifier and recursively updates each agent's local belief based on its local signals and belief information from its neighbors. We then adopt a novel distributed min-rule to update each agent’s global belief and enable learning of the true class for all agents. We analyze the convergence properties of our proposed algorithm, and subsequently, demonstrate and compare its performance with local averaging and global average consensus through simulations and with a visual image dataset.</p>

Autonomous robots interacting with humans in a social setting must consider the social-cultural environment when pursuing their objectives. Thus the social robot must perceive and understand the social cultural environment in order to be able to explain and predict the actions of its human interaction partners. This dissertation contributes to the emerging field of human-robot interaction for social robots in the following ways: 1. We used the social calculus technique based on culture sanctioned social metrics (CSSMs) to quantify, analyze and predict the behavior of the robot, human soldiers and the public perception in the Market Patrol peacekeeping scenario. 2. We validated the results of the Market Patrol scenario by comparing the predicted values with the judgment of a large group of human observers cognizant of the modeled culture. 3. We modeled the movement of a socially aware mobile robot in a dense crowds, using the concept of a micro-conflict to represent the challenge of giving or not giving way to pedestrians. 4. We developed an approach for the robot behavior in micro-conflicts based on the psychological observation that human opponents will use a consistent strategy. For this, the mobile robot classifies the opponent strategy reflected by the personality and social status of the person and chooses an appropriate counter-strategy that takes into account the urgency of the robots' mission. 5. We developed an alternative approach for the resolution of micro-conflicts based on the imitation of the behavior of the human agent. This approach aims to make the behavior of an autonomous robot closely resemble that of a remotely operated one.

The numerous previous attempts to simulate financial markets tended to be based on strong assumptions about markets or their participants. This thesis describes a more general kind of model - one in which deep reinforcement learning is used to train agents to make a profit while trading with each other on a virtual exchange. Such a model carries less inductive bias than most others - in theory, a neural network is capable of learning arbitrary decision rules. The model itself led to very simple results, but the conclusions from its construction will hopefully be of guidance to anyone implementing such a model in the future. / De många tidigare försöken att simulera finansmarknader har ofta byggt på starka antaganden om marknaderna eller deras deltagare. I den här avhandlingen beskrivs en mer allmän typ av modell - en modell där djup förstärkningsinlärning används för att träna agenter att göra vinst när de handlar med varandra på en virtuell börs. En sådan modell har mindre induktiva fördomar än de flesta andra - i teorin kan ett neuralt nätverk lära sig godtyckliga beslutsregler. Själva modellen ledde till mycket enkla resultat, men slutsatserna från dess konstruktion kommer förhoppningsvis att vara vägledande för alla som tillämpar en sådan modell i framtiden.

This thesis presents an approach to solve an optimal path planning problem for a swarm of drones. We optimize and improve information retrieval in area exploration within applications such a ‘Search and Rescue’-missions or reconnaissance missions. For this, dynamic programming has been used as a solving approach for a optimization problem. Different scenarios have been examined for two types of system, a single-agent system and a multi-agent system. First, there have been restrictions on the agents movement in a grid map and for that, optimal paths have been computed for both systems. Thereafter, two different solving approaches within dynamic programming have been tested and compared. The greedy approach which is a standard use where each agent computes the most optimal path from its own perspective and a simultaneous solving approach where the agents compute the most optimal paths according to all agents perspective. The simultaneous solving approach performed better than the greedy approach, which was expected since it is a more swarm optimal approach. However, it has a higher computational complexity which grows exponentially unlike to the greedy approach. Lastly, we discuss the case when the agents are allowed to move in all directions to optimize the information retrieval for the swarm. Here, dynamic programming turns out to have limitations for our use and purpose. For future work, a suggestion is to model the problem with multiple objective functions instead of one as has been done in this thesis. Also, it would be interesting trying another solving method for the problem. To this, I give example of two methods that would be interesting to compare, using model predictive control or a machine learning-based solution such as reinforcement learning. / Denna avhandling presenterar ett tillvägagångssätt för att lösa ett optimalt ruttplanerings problem för en drönarsvärm. Vi optimerar och förbättrar informationsinhämtningen i områdesutforskning inom applikationer som ’Search and Rescue’-uppdrag eller spaningsuppdrag. För detta har dynamisk programmering använts som en lösningsmetod till optimeringsproblem. Olika scenarier har undersökts för två typer av system, ett en-agent system och ett fler-agent system. Först har agenterna varit begränsade hur de har fått röra sig i en rutnätskarta och för det fallet har optimala vägar beräknats för båda systemen. Därefter har två olika lösningssätt inom dynamisk programmering testats och jämförts. Det giriga tillvägagångssättet som är en standardanvändning där varje agent beräknar den mest optimala vägen ur sitt eget perspektiv och en simultan lösningsmetod där agenterna beräknar de mest optimala vägarna enligt alla agenters perspektiv. Den simultana lösningsstrategin presterade bättre än den giriga, vilket var väntat eftersom det är ett mer svärmoptimalt tillvägagångssätt. Den har dock en högre beräkningskomplexitet som växer exponentiellt jämfört med den giriga metoden. Till sist diskuterar vi fallet då agenterna får röra sig i alla riktningar för att optimera informationssökningen för svärmen. Här visar sig dynamisk programmering ha begränsningar för våran användning och syfte. För framtida arbete är ett förslag att modellera problemet med flera mål funktioner istället för en som har gjorts i denna avhandling. Det skulle också vara intressant att prova ett annat lösningssätt för problemet. Till detta ger jag exempel på två metoder som skulle vara intressanta att jämföra, genom att använda modell prediktiv styrning eller en maskininlärningsbaserad lösning såsom förstärkande inlärning.

Recent years have witnessed a surge in demand for infrastructure and services to cover high demands on processing big chunks of data and applications resulting in a mega Cloud Datacenter. A datacenter is of high complexity with increasing difficulties to identify, allocate efficiently and fast an appropriate host for the requested virtual machine (VM). Establishing a good awareness of all datacenter’s resources enables the allocation “placement” policies to make the best decision in reducing the time that is needed to allocate and create the VM(s) at the appropriate host(s). However, current algorithms and policies of placement “allocation” do not focus efficiently on awareness of the resources of the datacenter, and moreover, they are based on conventional static techniques. Which are adversely impacting on the allocation progress of the policies. This thesis proposes a new Agent-based allocation/placement policy that employs some of the Multi-Agent system features to get a good awareness of Cloud Datacenter resources and also provide an efficient allocation decision for the requested VMs. Specifically, (a) The Multi-Agent concept is used as a part of the placement policy (b) A Contract Net Protocol is devised to establish good awareness and (c) A verification process is developed to fully dimensional VM specifications during allocation. These new results show a reduction in response time of VM allocation and the usage improvement of occupied resources. The proposed Agent-based policy was implemented using the CloudSim toolkit and consequently was compared, based on a series of typical numerical experiments, with the toolkit’s default policy. The comparative study was carried out in terms of the time duration of VM allocation and other aspects such as the number of available VM types and the amount of occupied resources. Moreover, a two-stage comparative study was introduced through this thesis. Firstly, the proposed policy is compared with four state of the art algorithms, namely the Random algorithm and three one-dimensional Bin-Packing algorithms. Secondly, the three Bin-Packing algorithms were enhanced to have a two-dimensional verification structure and were compared against the proposed new algorithm of the Agent-based policy. Following a rigorous comparative study, it was shown that, through the typical numerical experiments of all stages, the proposed new Agent-based policy had superior performance in terms of the allocation times. Finally, avenues arising from this thesis are included. / Al al-Bayt University in Jordan.

Multi-agent information gathering (MA-IG) enables autonomous robots to cooperatively collect information in an unfamiliar area. In some scenarios, the focus is on gathering the true mapping of a physical quantity such as temperature or magnetic field. This thesis proposes a computationally efficient algorithm known as multi-agent RRT-clustered Stackelberg game (MA-RRTc-SG) to solve MA-IG. During exploration, measurements are taken along robot paths to update the belief of a Gaussian process (GP), which gives a continuous estimation of the physical process. To seek informative paths, agents first resort to self-planning: one individually generates a number of choices using sampling-based algorithms and preserves informative ones. Then, paths from different robots are combined and investigated based on a multi-player Stackelberg game. The Stackelberg game ensures robots select the combination of paths that yield maximum system reward. The reward function plays an important role in the aforementioned two steps. In our work, robots are awarded for selecting informative paths and punished for hazardous movements and large control inputs. In experiments, we first conduct variation studies to investigate the influence of key parameters in the proposed algorithm. Then, the algorithm is tested in a simulation case to map the radiation intensity in a nuclear plant. Results show that using our algorithm, robots are able to collect information in an efficient and cooperative way compared to random exploration. / Multi-agent informationsinsamling gör det möjligt för autonoma robotar att samarbeta samla in information i ett okänt område. I vissa scenarier ligger fokus på att samla in den verkliga kartläggningen av en fysisk storhet som temperatur eller magnetfält. Den här avhandlingen föreslår en beräkningseffektiv algoritm som kallas multi-agent RRT-clustered Stackelberg game (MA-RRTc-SG) för att lösa multi-agent informationsinsamling. Under prospektering görs mätningar längs robotbanor för att uppdatera tron på en Gaussisk process, vilket ger en kontinuerlig uppskattning av den fysiska processen. För att söka informativa vägar tillgriper agenter först självplanering: man genererar individuellt ett antal val med hjälp av samplingsbaserade algoritmer och bevarar informativa. Sedan kombineras och undersöks vägar från olika robotar utifrån en Stackelberg spel för flera spelare. Stackelberg spelet säkerställer att robotar väljer kombinationen av vägar som ger maximal systembelöning. Belöningsfunktionen spelar en viktig roll i de ovan nämnda två stegen. I vårt arbete belönas robotar för att välja informativa vägar och straffas för osäkra rörelser och stora kontrollingångar. I experiment genomför vi först variationsstudier för att undersöka inverkan av nyckelparametrar i den föreslagna algoritmen. Därefter testas algoritmen i ett simuleringsfall för att kartlägga strålningsintensiteten i ett kärnkraftverk. Resultaten visar att med vår algoritm kan robotar samla in information på ett effektivt och samarbetssätt jämfört med slumpmässig utforskning.

This project concerns optimizing the behavior ofmultiple dispatching robots in a virtual warehouse environment.Q-learning and deep Q-learning algorithms, two establishedmethods in reinforcement learning, were used for this purpose.Simulations were run during the project, implementing andcomparing different algorithms on environments with up to fourrobots. The efficiency of a given algorithm was assessed primarilyby the number of packages it enabled the robots to deliver andhow fast the solution converged. The simulation results revealedthat a Q-learning algorithm could solve problems in environmentswith up to two active robots efficiently. To solve more complexproblems in environments with more than two robots, deep Qlearninghad to be implemented to avoid prolonged computationsand excessive memory usage. / Detta projekt handlar om att optimera rörelserna för ett flertal robotar i en virtuell miljö. Q-learning och deep Q-learning-algoritmer, två väletablerade metoder inom maskininlärning, användes för detta. Under projektet utfördes simuleringar där de olika algoritmerna jämfördes i miljöer med upp till fyra robotar. En given algoritms prestanda bedömdes med avseende på hur många paket robotarna kunde leverera i miljön samt hur snabbt en lösning konvergerade. Resultaten visade att Q-learning kunde lösa problem i miljöer med upp 2 robotar effektivt. För större problem användes deep Q-learning för att undvika långvariga beräkningar och stor minnesåtgång. / Kandidatexjobb i elektroteknik 2021, KTH, Stockholm