Ces dernières années ont consacré l’émergence du parallélisme dans la plupart des branches de l’informatique.Au niveau matériel, tout d’abord, du fait de la stagnation des fréquences de fonctionnement des unités decalcul. Au niveau logiciel, ensuite, avec la popularisation de nombreuses plates-formes d’exécution parallèle.Une forme de parallélisme est également présente dans les systèmes multi-agents, qui facilitent la description desystèmes complexes comme ensemble d’entités en interaction. Si l’adéquation entre ce parallélisme d’exécutionlogiciel et conceptuel semble naturelle, la parallélisation reste une démarche difficile, du fait des nombreusesadaptations devant être effectuées et des dépendances présentes explicitement dans de très nombreux systèmesmulti-agents.Dans cette thèse, nous proposons une solution pour faciliter l’implémentation de ces modèles sur une plateformed’exécution parallèle telle que le GPU. Notre bibliothèque MCMAS vient répondre à cette problématiqueau moyen de deux interfaces de programmation, une couche de bas niveau MCM permettant l’accès direct àOpenCL et un ensemble de plugins utilisables sans connaissances GPU. Nous étudions ensuite l’utilisation decette bibliothèque sur trois systèmes multi-agents existants : le modèle proie-prédateur, le modèle MIOR etle modèle Collemboles. Pour montrer l’intérêt de cette approche, nous présentons une étude de performancede chacun de ces modèles et une analyse des facteurs contribuant à une exécution efficace sur GPU. Nousdressons enfin un bilan du travail et des réflexions présentées dans notre mémoire, avant d’évoquer quelquespistes d’amélioration possibles de notre solution. / These last years have seen the emergence of parallelism in many fields of computer science. This is explainedby the stagnation of the frequency of execution units at the hardware level and by the increasing usage ofparallel platforms at the software level. A form of parallelism is present in multi-agent systems, that facilitatethe description of complex systems as a collection of interacting entities. If the similarity between this softwareand this logical parallelism seems obvious, the parallelization process remains difficult in this case because ofthe numerous dependencies encountered in many multi-agent systems.In this thesis, we propose a common solution to facilitate the adaptation of these models on a parallel platformsuch as GPUs. Our library, MCMAS, provides access to two programming interface to facilitate this adaptation:a low-level layer providing direct access to OpenCL, MCM, and a high-level set of plugins not requiring anyGPU-related knowledge.We study the usage of this library on three existing multi-agent models : predator-prey,MIOR and Collembola. To prove the interest of the approach we present a performance study for each modeland an analysis of the various factors contributing to an efficient execution on GPUs. We finally conclude on aoverview of the work and results presented in the report and suggest future directions to enhance our solution.

Dans ce travail, nous proposons un système auto-organisé composé d'agents-robots contrôlés par une architecture de subsomption et des règles locales probabilistes de prises et de dépôts. Ces agents-robots sont capables, grâce au développement de leurs capacités cognitives de se créer une carte cognitive, d'apprendre plusieurs lieux buts et de planifier le retour vers ces buts. Bien que formellement l'algorithme ne permette pas à chaque agent de "mélanger ni de fusionner ou d'optimiser" plusieurs objectifs, nous montrerons que le système global est capable de réaliser une optimisation multi-objectifs. Particulièrement, la fusion de l'apprentissage local avec l'accumulation de décisions individuelles permet de faire émerger (i) des structures dans l'environnement et (ii) des dynamiques tel que le comportement de spécialisation ou les comportements que nous pouvons considérer comme étant "égoïstes" ou "altruistes". Nous montrons qu'un mécanisme d'imitation simple contribue à l'amélioration des performance de notre SMAC et de notre SMRC, à savoir l'optimisation de la durée pour découvrir des différentes ressources, le temps moyen de planification, le niveau global de satisfaction des agents et enfin le temps moyen de convergence vers une solution stable. Particulièrement, l'ajout d'une capacité d'imitation améliore la construction des cartes cognitives pour chaque agent et stimule le partage implicite des informations dans un environnement a priori inconnu. En effet, les découvertes individuelles peuvent avoir un effet au plan social et donc inclure l'apprentissage de nouveaux comportements au niveau individuel. Pour finir, nous comparons les propriétés émergentes de notre SMAC à un modèle mathématique basé sur la programmation linéaire (PL). Cette évaluation montre les bonnes performances de notre SMAC qui permet d'avoir des solutions proches des solutions de la PL pour un coût de calcul réduit. Dans une dernière série d'expériences, nous étudions notre système d'agrégation dans un environnement réel. Nous mettons en place un SMRC, composé par des robots qui sont capables d'effectuer les opérations de prise, de dépôt et de maintien. Nous montrons via les premiers tests d'agrégation que les résultats sont prometteurs. / In this work, we propose a self-organized system composed by agents-robots, controlled by a subsumption architecture with probabilistic local rules of deposits and taking. These agents-robots are able, thanks to the development of their cognitive abilities to create a cognitive map, to learn various goals' locations and to plan the return to these goals. Although formally the algorithm does not allow each agent to « mix or merge or optimize » several objectives, we show that the overall system is able to perform a multi-objective optimization. Specifically, the fusion of local learning with the accumulation of the individual decisions allows to emerge (i) structures in the environment and (ii) several dynamics such as specialization behavior or those that we can consider as « selfish » or « altruistic ». We show that the imitation strategy contributes to the improvement of the performance of our SMAC and our SMRC, namely the optimization of time to explore the various resources, the average planning time, the overall satisfaction level of agents and finally the the average time of convergence to a stable solution. Specifically, the addition of an imitation ability improves the construction of cognitive maps for each agent and stimulates the implicit sharing of informations in an unknown environment. Indeed, individual discoveries can affect the social level and therefore include learning new behaviors at the individual level. Finally, we compare the emergent properties of our SMAC with a mathematical model based on linear programming (LP). This evaluation shows the good performance of our SMAC which allows to obtain solutions close to the solution of the PL for a low cost of computation. In a final series of experiments, we study our aggregation system in a real environment. We set up a SMRC, composed by robots that are able to perform taking operations, deposits operations and refueling operations. We show through the first tests of aggregation that the results are promising.

La ville de Toliara qui se trouve à l’exutoire du bassin de Fiherenana (Madagascar) est soumise chaque année aux aléas inondations. Les enjeux sont donc d'une importance majeure dans cette région. Cette étude débute par l’analyse de l’aléa avec les données hydro climatiques existantes. On cherche alors à déterminer les tendances en utilisant des modèles statistiques basés sur les séries temporelles. Une méthode de reconstitution des données manquantes est alors proposée. Ensuite, deux approches sont menées afin d’évaluer la vulnérabilité de la ville de Toliara et des villages alentours : une approche statique, à partir de relevés de terrain et de l’utilisation d’un système d’information géographique (SIG) ; et une autre avec l'utilisation d'un modèle multi-agents (SMA). La première étape est la cartographie d’un indicateur de vulnérabilité qui est l’agencement de plusieurs critères statiques propre à chaque maison comme la hauteur d’eau potentielle ou la typologie architecturale. La deuxième partie mettra en scène des agents afin de simuler un évènement catastrophique (montée des eaux et évacuation en simultanée). On cherche à savoir quelles sont les chances pour que les occupants d’une habitation puissent sortir indemne d’une inondation, en comparant divers paramètres et scénarios afin d’évaluer le degré de vulnérabilité de chaque ménage. Certains scénarios prennent en compte l’effet de certaines prises de décisions (Informations, sensibilisations etc.). Les indicateurs et les simulations permettent alors de mieux appréhender les risques inondations afin d’être une aide à la gestion des crises. / Hydrological risks are recurrent on the Fiherenana watershed - Madagascar. The city of Toliara, which is located at the outlet of the river basin, is subject each year to hurricane hazards and floods. The stakes are of major importance in this part of the island. This study begins with the analysis of hazard by collecting all existing hydro-climatic data on the catchment. It then seeks to determine trends, despite the significant lack of data, using statistical models (time series). Then, two approaches are used to assess the vulnerability of the city of Toliara and its surrounding villages. First, a static approach, from surveys of land and the use of GIS are conducted. Then, the second method is based on a multi-agent model. The first step is the mapping of a microscale vulnerability index which is an arrangement of several static criteria. For each House, there are several criteria of vulnerability such as potential water depth or architectural typology. As for the second part, scenes of agents are simulated in order to evaluate the degree of housing vulnerability to flooding. The model aims to estimate the chances of the occupants to escape from a catastrophic flood. For this purpose, we compare various settings and scenarios, some of which are conducted to take into account the effect of various decisions made by the responsible entities (awareness campaign etc.). The simulation consists of two essential parts: the simulation of the rise of water and the simulation of the behaviour of the people facing the occurence of hazard. Indicators and simulations allow to better understand the risks in order to help crisis management. Key Words: Hy

Ce travail de recherche s'inscrit dans le cadre des environnements virtuels pour la formation aux instruments de diagnostic biomédical. La simulation de la situation réelle seule ne suffisant pas, il convient d'incorporer un scénario pédagogique pour construire l'apprentissage. Le scénario s'applique pour tous les apprenants, il est donc important d'intégrer des possibilités d'individualisation. Pour cela, nous proposons de coupler l'environnement virtuel à un Système Tutoriel Intelligent (STI). Notre étude débute par une identification des systèmes existants qui nous semblent les mieux adaptés, sur lesquels baser notre proposition : le STI Pégase, le modèle de scénario pédagogique Poseïdon et le méta-modèle Mascaret. Ceci nous permet également d'identifier les limites de Pégase qui sont : le manque de lien avec le scénario pédagogique, le manque de modularité et le manque d'individualisation. Notre proposition, appelée Chrysaor, vise à combler ces faiblesses. Nous proposons ainsi qu'un scénario pédagogique soit une connaissance explicite et par conséquent exploitable par un STI. Les concepts proposés dans notre modèle permettent également au formateur de facilement modifier les comportements, les rôles et les affectations (humain ou agent autonome) : notre système devient ainsi modulaire. Nous illustrons ensuite l'utilisation de Chrysaor dans une application de formation par la réalité virtuelle à un instrument de diagnostic en hémostase utilisé en milieu hospitalier. Sur cette application, des expérimentations comparant les deux types de formation (traditionnelle et virtuelle) permettent de vérifier la qualité de l'apprentissage obtenu par une formation en réalité virtuelle, et de vérifier que ces connaissances sont transférables en environnement réel. / This research focuses on the virtual environments for training in biomedical diagnostic devices. The simulation of the real situation only is not enough, we needs to incorporate a pedagogical scenario to build the learning. The scenario applies to all learners, so it is important to integrate individualization. For this we propose to couple the virtual environment with an Intelligent Tutoring System (ITS). Our study begins with an identification of existing systems that seem best suited, on which to base our proposal: the ITS Pegase, the pedagogical scenario model Poseidon and the meta-model Mascaret. This also allows us to identify the limits of Pegase : the lack of connection with the pedagogical scenario, the lack of modularity and lack of individualization. Our proposal, called Chrysaor, aims to provide the most complete ITS. Thus we propose that a pedagogical scenario is an explicit knowledge and therefore exploitable by an STI. The concepts proposed in our model also allow the instructor to easily modify the behavior, roles and assignments (human or autonomous agent): our system becomes modular. Then we illustrate the use of Chrysaor in an application of virtual reality training in a biomedical device used in hemostasis in hospital. We lead two experiments in order to compare the two types of training (traditional and virtual) to verify the quality of learning achieved by a virtual reality training, and to ensure that this knowledge are transferable in a real environment.

Avec les problèmes présents dans le secteur de transport, qu'ils soient financiers ou environnementaux, la mobilité avancée peut y remédier avec la mise à profit de la complémentarité entre les différents modes de transport. Dans ce contexte, nous nous focalisons dans cette thèse à la mise en œuvre d'un système d’information de transport avec la recherche et la composition des itinéraires comodaux pour les clients. L'enjeu est d'être capable de répondre aux attentes des usagers avec des solutions satisfaisantes permettant de proposer des itinéraires optimaux pour gérer efficacement l’intermodalité. Dans un souci pratique, nous fournirons des itinéraires attractifs respectant les contraintes imposées même pour les requêtes simultanées. Nous utilisons des techniques d'accélération permettant de réduire l'espace de recherche pour la planification d’itinéraire. Les itinéraires attractifs sont décomposés en sections de route sur lesquelles les différentes demandes et les offres disponibles sont mises en relation. Les combinaisons des sections de route permettent d'aboutir à un ensemble de solutions intéressantes. L’aspect distribué et dynamique du problème nous a permis d'employer une modélisation basée sur le paradigme agent. Ainsi, l’alliance entre les systèmes multi-agents et les algorithmes génétiques que nous avons mis en place s'avère très utile pour gérer l’articulation de l’intermodalité entre ces différents modes de transport. Les résultats de simulation présentés montrent l’efficacité des méthodes proposées. / Nowadays, the environment impact of transport is significant. In an attempt to address these problems, in this work, we are interested in the implementation of a transport information system, which integrates the existing means of transport to respond users' requests, including public transport and the shared transport like carpooling and car-sharing. In this context of application, we elaborate algorithms to provide attractive paths with respect to the imposed constraints, even for simultaneous requests. Different acceleration techniques for path planning are used to reduce the search space for a better performance. The attractive paths are divided into route sections on which the available offers are allocated to different requests, which is treated as one resource allocation problem using metaheuristics algorithms. With consideration of the distributed and dynamic aspects of the problem, the solving strategy makes use of several concepts like multi-agents system and different optimization methods. The proposed methods are tested with realistic scenarios with instances extracted from real world transport networks. The obtained results indicate that our proposed approaches can efficiently solve the itinerary planning problems by providing good and complete solutions.

Le Problème de Transport à la Demande (PTD), consiste à prendre en charge le transport des personnes d'un lieu de départ vers un lieu d'arrivée. Il est caractérisé par un ensemble de demandes de transport et d'un nombre de véhicules disponible. L'ultime objectif dans ce travail de thèse est d'offrir une alternative optimisée au déplacement individuel et collectif. Le PTD est classé parmi les problèmes NP-difficile, la majorité des travaux de recherche ont été concentrés sur l'utilisation des méthodes approchées pour le résoudre.Ce problème est également multicritère, la solution proposée dans ce travail permet à la fois une réduction du temps de voyage et également de la distance parcourue. Dans cette thèse, nous proposons notre contribution à l'étude et à la résolution du problème de transport à la demande multicritère et dynamique en appliquant l'algorithme de recuit simulé multi-objectif. Une grande partie de notre travail concerne la conception, le développement et la validation des approches qui permettent de donner des solutions optimales ou quasi optimales, pour un PTD. Ces approches utilisent une méthode multicritère qui s’appuie sur l’algorithme de recuit simulé. La modélisation du PTD est représentée par une architecture multi-acteurs. Cette architecture met en évidence l’aspect distribué du système ainsi que les interactions et les relations qui peuvent avoir lieu entre les différents acteurs. Nous présentons dans ce travail un Système Multi-Agents pour la planification des itinéraires des véhicules affectés au transport des voyageurs. Les agents de ce système utilisent le module d’optimisation développé dans la première partie / The Dial a Ride Problem (DRP) is to take passengers from a place of departures to places of arrivals. Different versions of the dynamic Dial a Ride Problem are found in every day practice; transportation of people in low-density areas, transportation of the handicapped and elderly persons and parcel pick-up and delivery service in urban areas. In the DRP, customers send transportation requests to an operator. A request consists of a specified pickup location and destination location along with a desired departure or arrival time. The ultimate aim is to offer an alternative to displacement optimized individually and collectively. The DRP is classified as NP-hard problem that’s why most research has been concentrated on the use of approximate methods to solve it. Indeed the DRP is a multi-criteria problem, the proposed solution of which aims to reduce both route duration in response to a certain quality of service provided. In this thesis, we offer our contribution to the study and solving the DRP in the application using a multi agent system based on the Multi-Objective Simulated Annealing Algorithm

En quelques années, les domaines des jeux vidéo et des systèmes multi-agents (SMA) ont pris de plus en plus de places dans la vie de chacun. Malgré des similitudes assez fortes (présences d’entité dans les vidéo pouvant être assimilées à des agents), les SMA ne sont presque jamais utilisés dans le développement de jeux. Ce mémoire présente Shine Agent Modeling Platform (SAMP), une plateforme visant intégrer le paradigme multi-agents au sein du développement de jeux vidéo. Cette fusion permet l’utilisation de la puissance des multi-agents au sein des jeux vidéo.SAMP propose une approche au niveau des interactions permettant de réduire le coût de traitement de ces interactions en optimisant le nombre de recherches effectuées dans l’environnement.En plus d’intégrer le paradigme multi-agents, SAMP vise à être accessible à un maximum d’utilisateurs en proposant une interface de modélisation entièrement graphique. Un système d’importation de modèles comportementaux permet de créer deuxniveaux de modélisation : un niveau proche de la logique développement informatique et un niveau proche de la logique métier de l’utilisateur.SAMP est intégré à un moteur de jeux vidéo, Shine Engine, permettant de générer les environnements graphiques dans lesquels les agents évolueront. / In recent years, video games domains and multiagents systems (MAS) domains took more and more place into the life of many pepole. Despite of strong similarities (video games entities wich can be assimilated to agents), MAS are very rarely used during the development of video games. This submission presents the Shine Agent ModelingPlatform (SAMP), a framework trying to integrate the multi-agents paradigm within the development of video games. The purpose is to integrate the efficiency of the MAS within the video games.SAMP provides an approach to enhance the interactions between agents. This approach reduces the number of searches within the environment. In addition to integrate the multi-agents paradigm within the video games, SAMP aims to be userfriendly by proposing a full graphical interface to MAS. An import/export system of these modelsallows users to create two modeling levels: one close to the computer sciences logic and the second close the business logic of the user.SAMP is integrated in a video games engine: Shine Engine. This integration allows to generate the graphic environment in which agents will live.

La conception d’un système de transport en commun doit prendre en compte différentes dimensions pour résoudre deux problèmes importants d’optimisation : l’ordonnancement des véhicules (le graphicage) et l’affectation des conducteurs (l’habillage). Dans nos travaux, nous nous sommes focalisés sur le problème de l'habillage. L’objectif est de minimiser le nombre de conducteurs en respectant toutes les contraintes sociales et économiques. Par sa nature combinatoire, l’habillage est considéré comme une tâche complexe du processus de conception de réseaux de transport en commun. Nous avons proposé une approche fondée sur les hyper-heuristiques dont le principal avantage réside dans leur faculté d’adaptation à différents problèmes. Nous nous sommes intéressés plus particulièrement à une approche coopérative, capable de prendre en compte les changements au cours du processus de résolution. Nous avons étendu les fonctionnalités et amélioré les performances du framework traditionnel des hyper-heuristiques. L’algorithme proposé comporte une combinaison de plusieurs phases et plusieurs niveaux. La métaphore de la coalition est utilisée pour permettre la coopération entre hyper-heuristiques. Elle est destinée à favoriser la diversification des solutions et amplifier la capacité de recherche selon un contrôle décentralisé où chaque hyper-heuristique possède une certaine autonomie. Il est ainsi possible d’envisager différents modes de coopération entre les hyper-heuristiques : partage de solutions, apprentissage par mimétisme ou encore mise en concurrence de différentes stratégies de recherche. L’expérimentation a été réalisée aussi bien sur des instances réelles que sur des benchmarks. Elle a donné de bons résultats tant sur la déviation que sur le temps d’exécution. / The design of public transport system must take into account different dimensions to solve two main problems of optimization: the vehicles scheduling and driver scheduling. In our work, we focused on bus driver scheduling. Its objective is to minimize the number of drivers in accordance with social and environmental constraints. By its combinatorial nature, bus driver scheduling is considered a complex task in the design process of network transport. We have proposed an approach based on hyper-heuristics whose main advantage lies in their ability to adapt to different problems. We are particularly interested in a cooperative approach, which is able to take into account changes in the resolution process. We have extended the functionality and improved performance of the traditional framework of hyper- heuristics by proposing a pattern based on an organizational model. The proposed algorithm consists of a combination of several phases and several levels. The metaphor of the coalition is used to make cooperate several hyper-heuristics. The coalition is intended to favor diversified solutions and expand search capacity with decentralized control where each hyper-heuristic has certain autonomy. It is thus possible to consider different ways of cooperation between the hyper-heuristics: sharing solutions, learning by mimetism or carrying out different competitive search strategies. The experiment was carried out both on real-world instances and benchmarks. It gave good results on both quality of solution and execution time

L'essor d'Internet et du Web a favorisé la mise en ligne de nombreuses informations disponibles, potentiellement utiles pour la veille technologique et scientifique d'une entreprise. Différentes techniques de recherche d¤information sur le Web ont été proposées afin de construire des outils permettant d'affiner la recherche pour obtenir des résultats pertinents. Cependant, dans le contexte du Web actuel, malgré de grandes avancées dans le champ de la recherche d'information, ces outils ont montré leurs limites en termes de précision et de rappel. L'application des technologies du Web Sémantique, en particulier des ontologies, semble donc intéressante pour améliorer les performances de la tâche de veille technologique et scientifique sur le Web. Les travaux de cette thèse se sont déroulés dans le cadre d'une coopération entre le Centre Scientifique et Technique du Bâtiment (CSTB) et l'équipe ACACIA de l'INRIA Sophia Antipolis. L'objectif principal est d'exploiter les technologies du Web Sémantique pour développer un système de veille (OntoWatch), guidé par des ontologies, pour collecter, capturer, filtrer, classer et structurer le contenu du Web en provenance de plusieurs sources d¤information dans un scénario d'aide à la veille technologique et scientifique. Dans une première partie, nous modélisons le processus de veille technologique et scientifique du CSTB reposant sur le modèle général de veille proposé par Lesca. Puis nous identifions les apports potentiels de l¤ontologie dans les différentes étapes et nous construisons une ontologie dédiée au système de veille. Cette ontologie intègre une partie d'une ontologie existante et des vocabulaires offerts dans des thésaurus du domaine du CSTB. Ensuite, nous proposons des algorithmes utilisant une ontologie pour améliorer la recherche des documents sur le Web, puis générer automatiquement les annotations sémantiques (représentées dans le langage RDF) sur ces documents. Ces annotations alimentent dans le système les bases d'annotations, sur lesquelles repose la recherche sémantique d'informations. <br />Enfin, nous proposons une architecture multi-agents pour l'implémentation du système OntoWatch. Nous nous focalisons en particulier sur la conception des sous-sociétés d'agents dédiées à la recherche et à l'annotation automatique des documents sur le Web.

Actuellement, la plupart des simulateurs électromagnétiques se basent sur une résolution des équations aux dérivées partielles. Ces simulateurs ont jusqu'à présent bénéficié d'une augmentation de la puissance informatique compensant les exigences de calcul nécessitées par la croissance de la complexité et de la dimension des objets à modéliser. Cependant la taille des problèmes cruciaux augmente beaucoup plus rapidement que la puissance informatique. Malgré les apports faits pour simplifier les calculs électromagnétiques, la difficulté à tenir compte de tels problèmes complexes nécessite un saut méthodologique important. La méthode dite " énactive ", proposée dans ces travaux, constitue une approche atypique pour la modélisation dynamique d'un environnement naturel et sa simulation en un système de réalité virtuelle. Issue de la modélisation des systèmes multi-agents, elle propose une méthode spécifique pour la modélisation de tels systèmes complexes où de nombreux phénomènes interagissent de nombreuses façons, à des échelles de temps et d'espace pouvant être très différentes. Nous cherchons à suivre l'évolution d'une onde électromagnétique et ses interactions éventuelles avec des objets d'un environnement in virtuo, i.e. à travers un laboratoire virtuel (virtuoscope). Dans ce contexte, cette thèse s'inscrit dans un cadre interdisciplinaire qui allie les outils et les techniques de la réalité virtuelle à la modélisation de phénomènes électromagnétiques. En outre, les phénomènes sont modélisés en tant qu'entités autonomes en interaction. Notre modèle doit donc reposer sur une définition rigoureuse des entités, à savoir les ondes et les milieux, et des interactions qui peuvent avoir lieu afin de reconstituer correctement l'ensemble des phénomènes électromagnétiques " réels " au sein d'un environnement virtuel. Aussi, nous n'avons pas de moyens nous permettant de vérifier ni de valider autrement que par l'expérimentation notre modèle. En ce sens, nous faisons l'enjeu et le pari de parvenir à construire un tel système énactique électromagnétique. Pour cela, nous avons mis au point un ensemble de scénarios d'environnements électromagnétiques, suite au développement de deux modèles de propagation, l'un unidimensionnel et l'autre bidimensionnel. Les résultats seront comparés à des méthodes plus classiques appropriées voire à la théorie lorsque c'est possible.