La planification devient complexe quand il s’agit de gérer des situations incertaines. Prédire de façon précise est une tâche fastidieuse pour les planificateurs humains. L’approche Simulation-Based Planning consiste à associer la planification à la simulation. Chaque plan généré est simulé afin d’être testé et évalué. Le plan le plus approprié est alors retenu. Cependant, le problème est encore plus complexe lorsque viennent s’ajouter des contraintes spatiales. Par exemple, lors d’un feu de forêt, des bulldozers doivent construire une ligne d’arrêt pour arrêter la propagation des feux. Ils doivent alors tenir compte non seulement de l’avancée des feux mais aussi des caractéristiques du terrain afin de pouvoir avancer plus facilement. Nous proposons une approche de géosimulation basée sur les agents et qui a pour but d’assister la planification dans un espace réel, à large échelle géographique et surtout à forte composante spatiale. Un feu de forêt est un problème typique nécessitant une planification dans un monde réel incertain et soumis à de fortes contraintes spatiales. Nous illustrons donc notre approche (nommée ENCASMA) sur le problème des feux de forêts. L’approche consiste à établir un parallélisme entre l’Environnement Réel ER (p.ex. une forêt incendiée) et un Environnement de Simulation ES (p.ex. une reproduction virtuelle de la forêt incendiée). Pour garantir un niveau acceptable de réalisme, les données spatiales utilisées dans l’ES doivent absolument provenir d’un SIG (Système d’information Géographique). Les planificateurs réels comme les pompiers ou les bulldozers sont simulés par des agents logiciels qui raisonnent sur l’espace modélisé par l’ES. Pour une meilleure sensibilité spatiale (pour tenir compte de toutes les contraintes du terrain), les agents logiciels sont dotés de capacités avancées telles que la perception. En utilisant une approche par géosimulation multiagent, nous pouvons générer une simulation réaliste du plan à exécuter. Les décideurs humains peuvent visualiser les conséquences probables de l’exécution de ce plan. Ils peuvent ainsi évaluer le plan et éventuellement l’ajuster avant son exécution effective (sur le terrain). Quand le plan est en cours d’exécution, et afin de garantir la cohérence des données entre l’ER et l’ES, nous gardons trace sur l’ES des positions (sur l’ER) des planificateurs réels (en utilisant les technologies du positionnement géoréférencé). Nous relançons la planification du reste du plan à partir de la position courante de planificateur réel, et ce de façon périodique. Ceci est fait dans le but d’anticiper tout problème qui pourrait survenir à cause de l’aspect dynamique de l’ER. Nous améliorons ainsi le processus classique de l’approche DCP (Distributed Continual Planning). Enfin, les agents de l’ES doivent replanifier aussitôt qu’un événement imprévu est rapporté. Étant donné que les plans générés dans le cas étudié (feux de forêts) sont essentiellement des chemins, nous proposons également une approche basée sur la géosimulation orientée agent pour résoudre des problèmes particuliers de Pathfinding (recherche de chemin). De plus, notre approche souligne les avantages qu’apporte la géosimulation orientée agent à la collaboration entre agents humains et agents logiciels. Plus précisément, elle démontre : • Comment la cognition spatiale des agents logiciels sensibles à l’espace peut être complémentaire avec la cognition spatiale des planificateurs humains. • Comment la géosimulation orientée agent peut complémenter les capacités humaines de planification lors de la résolution de problèmes complexes. Finalement, pour appliquer notre approche au cas des feux de forêts, nous avons utilisé MAGS comme plate-forme de géosimulation et Prometheus comme simulateur du feu. Les principales contributions de cette thèse sont : 1. Une architecture (ENCASMA) originale pour la conception et l’implémentation d’applications (typiquement des applications de lutte contre les désastres naturels) dans un espace géographique réel à grande échelle et dynamique. 2. Une approche basée sur les agents logiciels pour des problèmes de Pathfinding (recherche de chemin) particuliers (dans un environnement réel et à forte composante spatiale, soumis à des contraintes qualitatives). 3. Une amélioration de l’approche de planification DCP (plus particulièrement le processus de continuité) afin de remédier à certaines limites de la DCP classique. 4. Une solution pratique pour un problème réel et complexe : la lutte contre les feux de forêts. Cette nouvelle solution permet aux experts du domaine de mieux planifier d’avance les actions de lutte et aussi de surveiller l’exécution du plan en temps réel. / Planning becomes complex when addressing uncertain situations. Accurate predictions remain a hard task for human planners. The Simulation-Based Planning approach consists in associating planning and simulation. Each generated plan is simulated in order to be tested and evaluated. The most appropriate plan is kept. The problem is even more complex when considering spatial constraints. For example, when fighting a wildfire, dozers build a firebreak to stop fire propagation. They have to take into account not only the fire spread but also the terrain characteristics in order to move easily. We propose an agent-based geosimulation approach to assist such planners with planning under strong spatial constraints in a real large-scale space. Forest fire fighting is a typical problem involving planning within an uncertain real world under strong spatial constraints. We use this case to illustrate our approach (ENCASM). The approach consists in drawing a parallel between the Real Environment RE (i.e. a forest in fire) and the Simulated Environment SE (i.e. a virtual reproduction of the forest). Spatial data within the SE should absolutely come from a GIS (Geographic Information System) for more realism. Real planners such as firefighters or dozers are simulated using software agents which reason about the space of the SE. To achieve a sufficient spatial awareness (taking into account all terrain’s features), agents have advanced capabilities such as perception. Using a multiagent geosimulation approach, we can generate a realistic simulation of the plan so that human decision makers can visualize the probable consequences of its execution. They can thus evaluate the plan and adjust it before it can effectively be executed. When the plan is in progress and in order to maintain coherence between RE and SE, we keep track in the SE of the real planners’ positions in the RE (using georeferencing technologies). We periodically replan the rest of the plan starting from the current position of the real planner. This is done in order to anticipate any problem which could occur due to the dynamism of the RE. We thus enhance the process of the classical Distributed Continual Planning DCP. Finally, the agents must replan as soon as an unexpected event is reported by planners within the RE. Since plans in the studied case (forest fires) are mainly paths, we propose a new approach based on agent geosimulation to solve particular Pathfinding problems. Besides, our approach highlights the benefits of the agent-based geo-simulation to the collaboration of both humans and agents. It thus shows: • How spatial cognitions of both spatially aware agents and human planners can be complementary. • How agent-based geo-simulation can complement human planning skills when addressing complex problems. Finally, when applying our approach on firefighting, we use MAGS as a simulation platform and Prometheus as a fire simulator. The main contributions of this thesis are: 1. An original architecture (ENCASMA) for the design and the implementation of applications (typically, natural disasters applications) in real, dynamic and large-scale geographic spaces. 2. An agent-based approach for particular Pathfinding problems (within real and spatially constrained environments and under qualitative constraints). 3. An enhancement of the DCP (particularly, the continual process) approach in order to overcome some limits of the classical DCP. 4. A practical solution for a real and complex problem: wildfires fighting. This new solution aims to assist experts when planning firefighting actions and monitoring the execution of these plans.

L’apprentissage multiagent est une direction prometteuse de la recherche récente et à venir dans le contexte des systèmes intelligents. Si le cas mono-agent a été beaucoup étudié pendant les deux dernières décennies, le cas multiagent a été peu étudié vu sa complexité. Lorsque plusieurs agents autonomes apprennent et agissent simultanément, l’environnement devient strictement imprévisible et toutes les suppositions qui sont faites dans le cas mono-agent, telles que la stationnarité et la propriété markovienne, s’avèrent souvent inapplicables dans le contexte multiagent. Dans ce travail de maîtrise nous étudions ce qui a été fait dans ce domaine de recherches jusqu’ici, et proposons une approche originale à l’apprentissage multiagent en présence d’agents adaptatifs. Nous expliquons pourquoi une telle approche donne les résultats prometteurs lorsqu’on la compare aux différentes autres approches existantes. Il convient de noter que l’un des problèmes les plus ardus des algorithmes modernes d’apprentissage multiagent réside dans leur complexité computationnelle qui est fort élevée. Ceci est dû au fait que la taille de l’espace d’états du problème multiagent est exponentiel en le nombre d’agents qui agissent dans cet environnement. Dans ce travail, nous proposons une nouvelle approche de la réduction de la complexité de l’apprentissage par renforcement multiagent. Une telle approche permet de réduire de manière significative la partie de l’espace d’états visitée par les agents pour apprendre une solution efficace. Nous évaluons ensuite nos algorithmes sur un ensemble d’essais empiriques et présentons des résultats théoriques préliminaires qui ne sont qu’une première étape pour former une base de la validité de nos approches de l’apprentissage multiagent. / Multiagent learning is a promising direction of the modern and future research in the context of intelligent systems. While the single-agent case has been well studied in the last two decades, the multiagent case has not been broadly studied due to its complex- ity. When several autonomous agents learn and act simultaneously, the environment becomes strictly unpredictable and all assumptions that are made in single-agent case, such as stationarity and the Markovian property, often do not hold in the multiagent context. In this Master’s work we study what has been done in this research field, and propose an original approach to multiagent learning in presence of adaptive agents. We explain why such an approach gives promising results by comparing it with other different existing approaches. It is important to note that one of the most challenging problems of all multiagent learning algorithms is their high computational complexity. This is due to the fact that the state space size of multiagent problem is exponential in the number of agents acting in the environment. In this work we propose a novel approach to the complexity reduction of the multiagent reinforcement learning. Such an approach permits to significantly reduce the part of the state space needed to be visited by the agents to learn an efficient solution. Then we evaluate our algorithms on a set of empirical tests and give a preliminary theoretical result, which is first step in forming the basis of validity of our approaches to multiagent learning.

Pour bien fonctionner, une application répartie nécessite de communiquer<br />et d'échanger des informations entre ces différentes entités. Les agents<br />mobiles apparaissent dans ce contexte comme une solution prometteuse<br />permettant la construction d'applications flexibles, adaptables aux<br />contraintes de l'application et de l'environnement d'exécution. Dans<br />cette thèse, la mobilité est étudiée sous deux angles. D'une part,<br />l'envoi du code sur le serveur permet d'adapter les services distants<br />aux exigences du client ce qui permet la réduction du trafic réseau.<br />D'autre part, une machine surchargée peut déléguer l'exécution de<br />certaines de ces tâches à une autre machine ce qui permet de gagner au<br />niveau du temps d'exécution. Une architecture basée sur la technologie<br />d'agents mobiles est proposée. Elle permet l'équilibrage de charge dans<br />une application répartie. L'architecture proposée est décentralisée et<br />l'équilibrage de charge se fait d'une façon dynamique. Un agent mobile<br />collecteur est utilisé afin de construire une vision globale du système.<br />Pour la réduction du trafic, nous proposons la communication par un<br />agent intelligent hybride. L'agent utilise ainsi deux modes,<br />client/serveur ou migration (échange locale), pour sa communication. Le<br />processus décisionnel de Markov est utilisé pour trouver la politique<br />optimale du déplacement de l'agent. Un travail d'expérimentation sur des<br />problèmes concrets permet de valider les algorithmes proposés.

Les problèmes de prise de décisions séquentielles multiagents sont difficiles à résoudre surtout lorsque les agents n'observent pas parfaitement l'état de Y environnement. Les approches existantes pour résoudre ces problèmes utilisent souvent des approximations de la fonction de valeur ou se basent sur la structure pour simplifier la résolution. Dans cette thèse, nous proposons d'approximer un problème de décisions séquentielles multiagent à observation limitée, modélisé par un processus décisionnel markovien décentralisé (DEC-MDP) en utilisant deux hypothèses sur la structure du problème. La première hypothèse porte sur la structure de comportement optimal et suppose qu'il est possible d'approximer la politique optimale d'un agent en connaissant seulement les actions optimales au niveau d'un petit nombre de situations auxquelles l'agent peut faire face dans son environnement. La seconde hypothèse porte, quant à elle, sur la structure organisationnelle des agents et suppose que plus les agents sont éloignés les uns des autres, moins ils ont besoin de se coordonner. Ces deux hypothèses nous amènent à proposer deux approches d'approximation. La première approche, nommée Supervised Policy Reinforcement Learning, combine l'apprentissage par renforcement et l'apprentissage supervisé pour généraliser la politique optimale d'un agent. La second approche se base, quant à elle, sur la structure organisationnelle des agents pour apprendre une politique multiagent dans des problèmes où l'observation est limitée. Pour cela, nous présentons un modèle, le D O F - D E C - M DP (Distance-Observable Factored Decentralized Markov Décision Process) qui définit une distance d'observation pour les agents. A partir de ce modèle, nous proposons des bornes sur le gain de récompense que permet l'augmentation de la distance d'observation. Les résultats empiriques obtenus sur des problèmes classiques d'apprentissage par renforcement monoagents et multiagents montrent que nos approches d'approximation sont capables d'apprendre des politiques proches de l'optimale. Enfin, nous avons testé nos approches sur un problème de coordination de véhicules en proposant une méthode de synchronisation d'agents via la communication dans un cadre à observation limitée.

Les simulations multi-agents reproduisent un phénomène en modélisant intuitivement son fonctionnement au niveau microscopique. Ce fonctionnement est décrit par le comportement d'entités autonomes qui agissent dans un environnement commun. Toutefois, les approches actuelles restreignent les interactions à des effets de bord ou ne fournissent aucune méthodologie réifiant la notion d'interaction. La conception de simulations contenant un grand nombre d'agents interagissant de manière variée s'en trouve complexifiée. Nous soutenons que pour faciliter la conception des simulations, il est préférable que toute entité soit concrétisée par un agent et tout comportement par une interaction. Le moteur de simulation doit de plus être clairement séparé des agents et interactions, de sorte que tout le système multi-agents soit régi par le même algorithme de simulation. Une telle approche procure de nombreux avantages tels que l'automatisation de l'implémentation, la réutilisabilité des interactions ou la conception graduelle du modèle du phénomène. En nous fondant sur ces principes, nous avons développé une approche centrée sur les interactions (IODA) composée d'une pyramide d'outils : un modèle formel, un ensemble d'algorithmes de simulation et une méthodologie. Nous confirmons la faisabilité de cette approche par une plateforme de simulation paramétrable (JEDI) fidèle au modèle formel et un environnement de développement intégré (JEDI-Builder) qui automatise le passage du modèle IODA au code JEDI. Nous montrons ainsi que la concrétisation logicielle des interactions a conduit à une unification du concept d'agent et à une simplification du processus de conception de simulations.

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.