Distributed Mobile Robotics (DMR) is a multidisciplinary research area with many open research questions. This is a survey of the state of the art in Distributed Mobile Robotics research. DMR is sometimes referred to as cooperative robotics or multi-robotic systems. DMR is about how multiple robots can cooperate to achieve goals and complete tasks better than single robot systems. It covers architectures, communication, learning, exploration and many other areas presented in this master thesis. / Uppsatsen är en brett spektrum på vilken forskning som pågår rörande distribuerad mobil robotik, dvs hur många robotar kan samverka för att lösa uppgifter. / Adress: Victor Adolfsson Folkparksvägen 12:24 372 38 Ronneby Telefon: 0457-171 42 Mobil: 0709-441389

Cette thèse porte sur le développement d'une approche de modélisation destinée à quantifier la durabilité de systèmes industriels à partir de biomasse (considérés comme des systèmes complexes), et à fournir un outil d’aide à la décision qui permette, en modifiant certaines de leurs caractéristiques, de diminuer leurs impacts environnementaux.Elle s’appuie sur deux études de cas régionales : la première permet de tester l’hypothèse théorique pour évaluer les facteurs qui contribuent à l’adoption par les agriculteurs du « panic érigé » (switchgrass) dans l’Etat du Michigan (USA), et les effets associés en termes d’impacts environnementaux, en utilisant un modèle multi-agents couplé à l’analyse du cycle de vie ; la seconde combine modélisation multi-agents et système d'information géographique par le biais d’une analyse de flux de matières et d’énergie pour révéler les opportunités symbiotiques d’un écosystème agro-industriel en Champagne-Ardenne (France).On montre que ces deux modèles fonctionnels ont une valeur ajoutée significative pour l’analyse de systèmes sociotechniques durables et la simulation de scénarios futurs / This research is about developing a modeling framework in order to quantify the sustainability of industrial systems for biomass energy (conceived of as complex systems), and to provide decisionmakers with an aiding-tool for reducing their environmental impacts by modifying some of their features.It draws upon two regional case-studies. In the first one, an hybrid agent-based/life cycle assessment approach is used to test the theoretical background, understand the main decision-making factors influencing farmers’ adoption of switchgrass ethanol in Michigan (USA) and assess how such patterns affect environmental impacts. In the second case-study, agent-based modeling and geographical information system are used together via material and energy flow analysis to reveal the potential for industrial symbiosis in the bio-economy cluster of Champagne-Ardenne (France). We show that both models have a significant added value for the analysis of sustainable complex systems and the simulation of future scenarios

Cette thèse s’intéresse aux concepts de mobilité et de gestion du spectre dans les réseaux à radio cognitive. Ainsi, nous avons proposé deux approches décentralisées basées sur les systèmes multi-agents (SMA). Nous avons, tout d’abord, intégré des agents au sein des utilisateurs secondaires (n’ayant pas de licence pour l’accès au spectre) et des utilisateurs primaires (disposant d’une licence) et nous avons défini leurs comportements au moment du handover. Notre première solution NESAM propose un mécanisme de négociation entre les agents permettant aux utilisateurs secondaires de se voir allouer une bande de spectre avec un bon rapport prix par durée d’allocation. Nous avons, par ailleurs, proposé une deuxième solution LASMA qui se base sur l’enchère combinée avec de l’apprentissage pour assurer une gestion efficace du spectre ainsi qu’une gestion de la mobilité des utilisateurs à radio cognitive. Nos algorithmes prennent en compte les préférences des utilisateurs, comme la fréquence spectrale, le prix et la durée ainsi que les contraintes de l’environnement spectral telles que les bandes de fréquences disponibles. Nos propositions assurent une exploitation importante des ressources spectrales tout en diminuant le nombre de handovers spectraux. De plus, nos algorithmes offrent un handover spectral transparent et sans interruption lors des déplacements des utilisateurs. Nous avons prouvé également que nos solutions permettent de satisfaire les besoins des utilisateurs et d’améliorer leur utilité / In this thesis, we are interested in mobile cognitive radio networks while ensuring an efficient spectrum sharing and seamless handover at the same time. Hence, we propose two decentralized approaches based on multi-agents systems. We first deployed agents on each primary (licensed) and secondary (unlicensed cognitive radio) users, respectively. Besides, we define agents’ behaviors during the handover process.Our proposal NESAM defines a novel negotiation mechanism between agents to allow secondary users assigning the appropriate spectrum band giving a good price for the use duration. We have also proposed a second solution LASMA using the learning based auctions. Our algorithms take into account users’ requirements such as spectrum frequency, price and duration as well as environment’s constraints such as available resources.Our proposals improve the overall spectrum utilization and minimize the number of spectrum handovers when users move from one network to another one. This proves that our algorithms ensure efficient spectrum allocation and enable seamless handover during user’s mobility. Besides, we proved that our approaches guarantee users’ satisfaction and improve their utility

In this thesis, we examine algorithms for the division of labour in a group of robot. The algorithms make no use of direct communication. Instead, they are based only on the interactions among the robots and between the group and the environment.<p><p>Division of labour is the mechanism that decides how many robots shall be used to perform a task. The efficiency of the group of robots depends in fact on the number of robots involved in a task. If too few robots are used to achieve a task, they might not be successful or might perform poorly. If too many robots are used, it might be a waste of resources. The number of robots to use might be decided a priori by the system designer. More interestingly, the group of robots might autonomously select how many and which robots to use. In this thesis, we study algorithms of the latter type.<p><p>The robotic literature offers already some solutions, but most of them use a form of direct communication between agents. Direct, or explicit, communication between the robots is usually considered a necessary condition for co-ordination. Recent studies have questioned this assumption. The claim is based on observations of animal colonies, e.g. ants and termites. They can effectively co-operate without directly communicating, but using indirect forms of communication like stigmergy. Because they do not rely on communication, such colonies show robust behaviours at group level, a condition that one wishes also for groups of robots. Algorithms for robot co-ordination without direct communication have been proposed in the last few years. They are interesting not only because they are a stimulating intellectual challenge, but also because they address a situation that might likely occur when using robots for real-world out-door applications. Unfortunately, they are still poorly studied.<p><p>This thesis helps the understanding and the development of such algorithms. We start from a specific case to learn its characteristics. Then we improve our understandings through comparisons with other solutions, and finally we port everything into another domain.<p><p>We first study an algorithm for division of labour that was inspired by ants' foraging. We test the algorithm in an application similar to ants' foraging: prey retrieval. We prove that the model used for ants' foraging can be effective also in real conditions. Our analysis allows us to understand the underlying mechanisms of the division of labour and to define some way of measuring it.<p><p>Using this knowledge, we continue by comparing the ant-inspired algorithm with similar solutions that can be found in the literature and by assessing their differences. In performing these comparisons, we take care of using a formal methodology that allows us to spare resources. Namely, we use concepts of experiment design to reduce the number of experiments with real robots, without losing significance in the results.<p><p>Finally, we apply and port what we previously learnt into another application: Sensor/Actor Networks (SANETs). We develop an architecture for division of labour that is based on the same mechanisms as the ants' foraging model. Although the individuals in the SANET can communicate, the communication channel might be overloaded. Therefore, the agents of a SANET shall be able to co-ordinate without accessing the communication channel. / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

Cette thèse s’intéresse à la gestion décentralisée des données récoltées par les réseaux de capteurs dans le contexte des réseaux électriques intelligents (smart grids). Nous proposons une architecture décentralisée basée sur les systèmes multi-agents pour la gestion des données et de l’énergie dans un smart grid. En particulier, nos travaux traitent de la gestion des données des réseaux de capteurs dans le réseau de distribution d’un smart grid et ont pour objectif de lever deux verrous essentiels : (1) l'identification et la détection de défaillances et de changements nécessitant une prise de décision et la mise en œuvre des actions correspondantes ; (2) la gestion des grandes quantités de données qui seront récoltées suite à la prolifération des capteurs et des compteurs communicants. La gestion de ces informations peut faire appel à plusieurs méthodes, dont l'agrégation des paquets de données sur laquelle nous nous focalisons dans cette thèse. Nous proposons d’agréger (PriBaCC) et/ou de corréler (CoDA) le contenu de ces paquets de données de manière décentralisée. Ainsi, le traitement de ces données s'effectuera plus rapidement, ce qui aboutira à une prise de décision rapide et efficace concernant la gestion de l'énergie. La validation par simulation de nos contributions a montré que celles-ci répondent aux enjeux identifiés, notamment en réduisant le volume des données à gérer et le délai de communication des données prioritaires / This thesis focuses on the decentralized management of data collected by wireless sensor networks which are deployed in a smart grid, i.e. the evolved new generation electricity network. It proposes a decentralized architecture based on multi-agent systems for both data and energy management in the smart grid. In particular, our works deal with data management of sensor networks which are deployed in the distribution electric subsystem of a smart grid. They aim at answering two key challenges: (1) detection and identification of failure and disturbances requiring swift reporting and appropriate reactions; (2) efficient management of the growing volume of data caused by the proliferation of sensors and other sensing entities such as smart meters. The management of this data can call upon several methods, including the aggregation of data packets on which we focus in this thesis. To this end, we propose to aggregate (PriBaCC) and/or to correlate (CoDA) the contents of these data packets in a decentralized manner. Data processing will thus be done faster, consequently leading to rapid and efficient decision-making concerning energy management. The validation of our contributions by means of simulation has shown that they meet the identified challenges. It has also put forward their enhancements with respect to other existing approaches, particularly in terms of reducing data volume as well as transmission delay of high priority data

Cette thèse s’intéresse à la gestion décentralisée à l’aide des systèmes multi-agents de l’énergie, notamment de sources renouvelables, dans le contexte des réseaux électriques intelligents (smart grids). Nos travaux de recherche visent à minimiser la facture énergétique des consommateurs en se focalisant sur deux verrous essentiels que nous nous proposons de lever : (1) résoudre le problème de l’intermittence des énergies renouvelables; (2) minimiser les pertes d’énergie. Pour pallier le problème d’intermittence des énergies renouvelables et dans le but de maintenir un coût énergétique peu onéreux même lors des pics d’utilisation, nous avons intégré un système de stockage intelligent. Nous avons, en effet, proposé des algorithmes permettant d’utiliser les systèmes de stockage intelligents et la négociation multi-agents pour réduire la facture énergétique tout en conservant un taux de décharge minimal de la batterie et une perte énergétique minimale. La validation par simulation de nos contributions a montré que celles-ci répondent aux enjeux identifiés, notamment en réduisant le coût de l’énergie pour les consommateurs en comparaison aux travaux de l’état de l’art. / This thesis focuses on the decentralized management using multi-agent systems of energy, including renewable energy sources, in the smart grid context. Our research aims to minimize consumers’ energy bills by answering two key challenges: (1) handle the problem of intermittency of renewable energy sources; (2) reduce energy losses. To overcome the problem of renewable resources intermittency and in order to minimize energy costs even during peak hours, we integrated an intelligent storage system. To this end, we propose many algorithms in order to use intelligent storage systems and multi-agent negotiation algorithm to reduce energy cost while maintaining a minimal discharge rate of the battery and minimal energy loss. The validation of our contributions has shown that our proposals respond to the identified challenges, including reducing the cost of energy for consumers, in comparison to the state of the art.

Decentralized decision-making is an active research topic in artificial intelligence. In a distributed system, a number of individually acting agents coexist. If they strive to accomplish a common goal, the establishment of coordinated cooperation between the agents is of utmost importance. With this in mind, our focus is on multi-agent reinforcement learning (RL) methods which allow for automatically acquiring cooperative policies based solely on a specification of the desired joint behavior of the whole system.The decentralization of the control and observation of the system among independent agents, however, has a significant impact on problem complexity. Therefore, we address the intricacy of learning and acting in multi-agent systems by two complementary approaches.First, we identify a subclass of general decentralized decision-making problems that features regularities in the way the agents interact with one another. We show that the complexity of optimally solving a problem instance from this class is provably lower than solving a general one.Although a lower complexity class may be entered by sticking to certain subclasses of general multi-agent problems, the computational complexitymay be still so high that optimally solving it is infeasible. Hence, our second goal is to develop techniques capable of quickly obtaining approximate solutions in the vicinity of the optimum. To this end, we will develop and utilize various model-free reinforcement learning approaches.Many real-world applications are well-suited to be formulated in terms of spatially or functionally distributed entities. Job-shop scheduling represents one such application. We are going to interpret job-shop scheduling problems as distributed sequential decision-making problems, to employ the multi-agent RL algorithms we propose for solving such problems, and to evaluate the performance of our learning approaches in the scope of various established scheduling benchmark problems.

Les problèmes de satisfaction de contraintes distribués (DisCSP) permettent de formaliser divers problèmes qui se situent dans l'intelligence artificielle distribuée. Ces problèmes consistent à trouver une combinaison cohérente des actions de plusieurs agents. Durant cette thèse nous avons apporté plusieurs contributions dans le cadre des DisCSPs. Premièrement, nous avons proposé le Nogood-Based Asynchronous Forward-Checking (AFC-ng). Dans AFC-ng, les agents utilisent les nogoods pour justifier chaque suppression d'une valeur du domaine de chaque variable. Outre l'utilisation des nogoods, plusieurs backtracks simultanés venant de différents agents vers différentes destinations sont autorisés. En deuxième lieu, nous exploitons les caractéristiques intrinsèques du réseau de contraintes pour exécuter plusieurs processus de recherche AFC-ng d'une manière asynchrone à travers chaque branche du pseudo-arborescence obtenu à partir du graphe de contraintes dans l'algorithme Asynchronous Forward-Checking Tree (AFC-tree). Puis, nous proposons deux nouveaux algorithmes de recherche synchrones basés sur le même mécanisme que notre AFC-ng. Cependant, au lieu de maintenir le forward checking sur les agents non encore instanciés, nous proposons de maintenir la consistance d'arc. Ensuite, nous proposons Agile Asynchronous Backtracking (Agile-ABT), un algorithme de changement d'ordre asynchrone qui s'affranchit des restrictions habituelles des algorithmes de backtracking asynchrone. Puis, nous avons proposé une nouvelle méthode correcte pour comparer les ordres dans ABT_DO-Retro. Cette méthode détermine l'ordre le plus pertinent en comparant les indices des agents dès que les compteurs d'une position donnée dans le timestamp sont égaux. Finalement, nous présentons une nouvelle version entièrement restructurée de la plateforme DisChoco pour résoudre les problèmes de satisfaction et d'optimisation de contraintes distribués. / Distributed Constraint Satisfaction Problems (DisCSP) is a general framework for solving distributed problems. DisCSP have a wide range of applications in multi-agent coordination. In this thesis, we extend the state of the art in solving the DisCSPs by proposing several algorithms. Firstly, we propose the Nogood-Based Asynchronous Forward Checking (AFC-ng), an algorithm based on Asynchronous Forward Checking (AFC). However, instead of using the shortest inconsistent partial assignments, AFC-ng uses nogoods as justifications of value removals. Unlike AFC, AFC-ng allows concurrent backtracks to be performed at the same time coming from different agents having an empty domain to different destinations. Then, we propose the Asynchronous Forward-Checking Tree (AFC- tree). In AFC-tree, agents are prioritized according to a pseudo-tree arrangement of the constraint graph. Using this priority ordering, AFC-tree performs multiple AFC-ng processes on the paths from the root to the leaves of the pseudo-tree. Next, we propose to maintain arc consistency asynchronously on the future agents instead of only maintaining forward checking. Two new synchronous search algorithms that maintain arc consistency asynchronously (MACA) are presented. After that, we developed the Agile Asynchronous Backtracking (Agile-ABT), an asynchronous dynamic ordering algorithm that does not follow the standard restrictions in asynchronous backtracking algorithms. The order of agents appearing before the agent receiving a backtrack message can be changed with a great freedom while ensuring polynomial space complexity. Next, we present a corrigendum of the protocol designed for establishing the priority between orders in the asynchronous backtracking algorithm with dynamic ordering using retroactive heuristics (ABT_DO-Retro). Finally, the new version of the DisChoco open-source platform for solving distributed constraint reasoning problems is described. The new version is a complete redesign of the DisChoco platform. DisChoco 2.0 is an open source Java library which aims at implementing distributed constraint reasoning algorithms.

L'intelligence en essaim constitue désormais un domaine à part entière de l'intelligence artificielle distribuée. Les problématiques qu'elle soulève touchent cependant à de nombreux autres domaines ou questions scientifiques. En particulier le concept d'essaim trouve pleinement sa place au sein de la science dites des ``systèmes complexes''. Cette thèse présente ainsi la conception, les caractéristiques et les applications d'un modèle original, le système multi-agent logistique (SMAL), pour le domaine de l'intelligence en essaim. Le SMAL trouve son origine en modélisation des systèmes complexes : il est en effet issu des réseaux d'itérations logistiques couplées dont nous avons adapté le modèle de calcul au schéma ``influence-réaction'' des systèmes multi-agents. Ce modèle est fondé sur des principes communs à d'autres disciplines, comme la synchronisation et le contrôle paramétrique, que nous plaçons au coeur des mécanismes d'auto-organisation et d'adaptation du système. L'environnement à base de champs est l'autre aspect fondamental du SMAL, en permettant la réalisation des interactions indirectes des agents et en jouant le rôle d'une structure de données pour le système. Les travaux décrits dans cette thèse donnent lieu à des applications principalement en simulation et en optimisation combinatoire.L'intérêt et l'originalité du SMAL pour l'intelligence en essaim résident dans l'aspect générique de son schéma théorique qui permet de traiter avec un même modèle des phénomènes considérés a priori comme distincts dans la littérature : phénomènes de ``flocking'' et phénomènes stigmergiques ``fourmis'' à base de phéromones. Ce modèle répond ainsi à un besoin d'explication des mécanismes mis en jeu autant qu'au besoin d'en synthétiser les algorithmes générateurs. / Swarm Intelligence is from now on a full part of Distributed Artificial Intelligence. Its associated problematics meet many other fields and scientific questions. The concept of swarm in particular belongs to the science called the science of complex systems. This phd thesis shows the design and the characteristics and the applications of a novel type of model called the logistic multi-agent system (LMAS) dedicated to the Swarm Intelligence field. The LMAS has its foundations in complex system modeling: it is inspired from the coupled logistic map lattice model which has been adapted to the ``Influence-Reaction'' modeling of multi-agent systems. This model is based on universal principles such as synchronization and parametric control which are considered as the main mechanisms of self-organization and adaptation in the heart of the system. The field-layered based environment is the other important feature of the LMAS, since it enables indirect interactions and plays the part of a data structure for the whole system. The work of this thesis is put into practice for simulation and optimization.The novelty of the LMAS lies in its generic theoretical framework, which enables to tackle problems considered as distinct in the literature, in particular flocking and ant-like stigmergic behavior. This model meets the need of explaining basic mechanisms and the need of synthesizing generative algorithms for the Swarm Intelligence.

A Inteligência Artificial Distribuída traz uma série de novas perspectivas para a computação quando considera sistemas heterogêneos, adaptativos, evolutivos, continuamente em funcionamento e abertos. Estes sistemas, chamados de sociedades, apresentam tais características por permitirem que seus componentes, chamados de agentes, migrem entre sociedades, isto é, agentes podem sair e entrar em sociedades. Sociedades abertas permitem a migração dos agentes e coloca dois tipos de problemas para o agente que está migrando: problemas de linguagem e interação, que concernem ao uso de expressões usadas e à maneira como as interações são organizadas na nova sociedade; e, problemas de conhecimento e atuação, que se referem à como um agente irá se comportar a fim de realizar justamente aquilo que a sociedade espera dele. Este trabalho se atem aos problemas de conhecimento e atuação. Para que os agentes da sociedade possam cooperar e coordenar suas ações, é necessário que tenham conhecimento das capacidades, habilidades, desejos e planos dos outros agentes. Grande parte do conhecimento a respeito dos outros pode ser extraído dos papéis que estes podem assumir na sociedade. Assim sendo, o problema colocado para este trabalho é como os agentes da sociedade que receberam o agente imigrante e o próprio agente imigrante conhecerão/aprenderão os papéis uns dos outros. São desenvolvidos três mecanismos de identificação de papéis, bem como a comparação entre eles e sua adequação a tipos de migração. Os três mecanismos são os seguintes: i) Identificação de papéis por protocolo de apresentação: é proposta uma linguagem de descrição de protocolos (LDP) e uma especificação de protocolo de apresentação nesta LDP. Os agentes que utilizam este mecanismo conseguem se identificar com rapidez, porém necessitam conhecer várias informações “locais” da sociedade, o que pode ser muito restritivo para um agente migrante. ii) Identificação de papéis por observação e classificação: esta solução procura classificar o agente observado em um papel de um conjunto prédefinido de papéis. Neste conjunto, os papéis são descritos por meio de processos de interação (PI). Para isto, desenvolveu-se a noção de PI. Para isto, desenvolveu-se a noção de PI. Foram desenvolvidas duas formas de proceder a classificação: construir uma especificação do agente a partir da observação das suas ações e verificar se esta pertence ao conjunto pré-definido de papéis; e, verificar se o comportamento do agente confere com as execuções possíveis para algum dos papéis pré-definidos. Este mecanismo é mais adequado para sociedades abertas e tem boa precisão no resultado apresentado, porém, a identificação do papel de um agente pode ser demorada. iii) Identificação de papéis por reconhecimento de intenções em planos: este mecanismo baseia-se na existência de uma relação entre intenções e papéis. A partir das ações observadas para o agente, procura-se saber qual seu plano, sua intenção e, conseqüentemente, seu papel. Para isto foi implementado um procedimento de indução de planos. Este mecanismo também é adequado para sociedades abertas, no entanto, a identificação, embora satisfatória, nem sempre é completamente correta. Estes três mecanismos foram testados em simulações numa implementação da sociedade Produtor - Consumidor, onde puderam ser comprovadas as características de cada um. / Distributed Artificial Intelligence brings a number of new perspectives to Computing Science when heterogeneous, adaptative and evolutive systems, those under functioning and open, are taken into consideration. These systems, named societies, present these characteristics because they allow their components, named agents, to migrate within societies, that is, agents are allowed to enter and to leave societies. Agents' migration brings two kinds of problems to the migrating agent: language and interaction problems both related to the use of used expressions and to the way the interactions are organized in the new society; and, knowledge and performance problems refering to the way the agent will behave in order to accomplish exactly what society expects him to do. This work is limited to knowledge and performance problems. In order to cooperate and coordinate their actions, the society's agents need to learn about the capabilities, abilities wishes and plans of other agents. A great part of knowledge of others can be extracted from the social roles these agents can play. Therefore, the problem posed in this work is how social agents who has received an immigrating agent and the immigrating agent himself will know and learn one another's roles. Three role identification mechanisms, and the comparison between them and their adaptation to migration types as well are developed. The three mechanisms are the following: i) Role Identification by means of presentation protocol:a language of protocol description (LPD) and a specification of presentation protocol in this LPD are proposed. The agents who use this mechanism can rapidly identify each other, however they need know a number of 'local' social information, which can be very restrictive to the migrating agent. ii) Role identification by means of observation and classification: this solution tries to classify the observed agent as a role out of set of definite roles. In this set, the roles are described by means of interactional processes (IP). Therefore, the notion of IP was developed. Two ways to proceed the role classification were developed: to build the agent's especification departing from the observation of their actions and to check whether this especification belongs to a set of pre-defined roles; and to check whether the agent's behavior fits the possible executions to some predefined roles. This mechanism is more adequate to open societies and has good precision in the result presented, but, the agent's role identification can last longer. iii) Role Identification by means of intention and plans recognition: this mechanism is based on the existence of a relationship between intentions and roles. By departing from the agent's observed actions, his plan, intention, consequently, his role is recognized. Therefore an induced plan procedure was implemented. This mechanism is also adequate to open societies, however, the identification, though satisfactory, is not always totally correct. These three mechanisms were tested in simulated situations in a kind of Producer- Consumer Society implementation in which each one's characteristics could be verified.