image
Emmanuel Hermellin
Recherche
Emmanuel Hermellin

Travaux de recherche

Intelligence artificielle - Système multi-agent - Simulation multi-agent - Simultanéité - Émergence - Vie artificielle - Simulation - Planification automatique - Calcul Haute Performance - GPGPU - Parallélisme


Simulations multi-agents sur architectures massivement parallèles Ccontexte, recherche et perspectives

Contexte

La grande diversité des objectifs que la simulation multi-agents peut adresser (étude de systèmes complexes, de phénomènes biologiques, conception de systèmes multi-agents pour la robotique, etc.) montre toute la richesse du paradigme multi-agent. L'augmentation des capacités de calcul de nos ordinateurs actuels ainsi que la qualité (et la variété) des outils existants, dédiés à ce paradigme de conception, ont permis une envolée spectaculaire du nombre de simulations multi-agents et témoignent de sa popularité grandissante.

Cependant, nous avons montré, dans mon travail de thèse, que les performances constituent un verrou majeur dans ce domaine. Ainsi, il n'est pas rare de devoir simplifier le modèle ou de faire des compromis sur les caractéristiques de ce dernier pour compenser les limites introduites par ce manque de performances. D'autant plus, à l'heure où il est de plus en plus question de simulations à large échelle (scalable) et/ou multi-niveaux, on peut facilement prédire que le besoin en ressources de calcul va augmenter de manière quasi exponentielle à court et moyen termes.

Ainsi, la motivation première derrière ces travaux de recherche, commencé en thèse, est d'apporter des solutions aux problèmes de performance que l'on peut rencontrer quand on simule des modèles multi-agents. Suivant les orientations prises en direction du calcul haute performance par différents groupes de recherche et industriels, nous nous sommes tournés en particulier vers l'utilisation de la puissance computationnelle des cartes graphiques via le GPGPU. Cette technologie offre en effet un des meilleurs rapports en termes de performance, prix et consommation énergétique tout en permettant à tout un chacun d'utiliser une solution de calcul intensif grâce à la disponibilité de cette dernière dans de nombreux ordinateurs.

Néanmoins, malgré les avantages que peut avoir le GPGPU, nous avons souligné que cette technologie est difficile à mettre en oeuvre. Le GPGPU s'accompagne en effet d'un contexte de programmation particulier du fait qu'il s'appuie sur un parallélisme de type SIMD (Simple Instruction Multiple Data, c.f. Taxonomie de Flynn) qui nécessite notamment de suivre les principes de la programmation par traitement de flux de données (stream processing paradigm). Utiliser le GPGPU de manière efficiente peut donc être très complexe selon le cadre et les objectifs poursuivis.

Problématiques abordées en thèse

Dans le cadre des simulations multi-agents, les spécificités d'implémentation qui accompagnent la programmation sur GPU obligent à repenser la modélisation multi-agents, notamment car il n'est pas possible d'adopter une conception orientée objet classique. De ce fait, les modèles multi-agents usuels ne peuvent être simulés sur GPU sans un effort de traduction conséquent et non trivial.

De plus, considérer l'utilisation des GPU, reposant sur des architectures massivement parallèles, pour accélérer l'exécution des simulations exacerbe les problèmes d'implémentation déjà présents en séquentiel. En effet, les différents outils dédiés à la simulation multi-agent proposent une programmation haut niveau limitant la réutilisabilité des modèles sur d'autres plates-formes. Cela oblige également d'adopter une philosophie et une modélisation propre à chacun des outils ce qui restreint fortement l'accessibilité de ces derniers.

Dans ce contexte, l'état de l’art réalisé [Hermellin et al., 2014, Hermellin et al., 2015] nous a permis d'argumenter qu'une meilleure intégration du GPGPU ne pouvait se faire qu'avec une amélioration de l'accessibilité, de la réutilisabilité et de la généricité des solutions proposées et qu'elle passait nécessairement par l'utilisation d'une approche hybride (on utilise conjointement le processeur et le GPU). La difficulté était donc de trouver une solution répondant à ces critères.

Contributions scientifiques de la thèse

Ainsi, nous avons présenté le principe de délégation GPU. Celui-ci propose d'utiliser de manière directe le GPGPU (et donc de profiter de la puissance des GPU) au travers d'une approche hybride tout en conservant l'accessibilité et la facilité de réutilisation d'une interface de programmation orientée objet.

Ce principe de conception, qui appartient au courant E4MAS [Weyns and Michel, 2015], s'inspire de travaux tels que [Weyns et al., 2007]. Ainsi, de la même manière que pour les artefacts [Ricci et al., 2011], ce principe propose de réifier une partie des calculs du modèle (comme les calculs de perception) dans l'environnement sous la forme de dynamiques environnementales traitées par des modules de calcul GPU.

Le courant E4MAS considère l'environnement comme un élément essentiel des systèmes multi-agents : "The environment is a first-class abstraction [...] that mediates both the interaction among agents and the access to resources." [Weyns et al., 2007]
Les artifacts sont des abstractions de première classe pour façonner et programmer des environnements fonctionnels que les agents exploiteront au moment de l'exécution, comprenant des fonctionnalités qui concernent l'interaction, la coordination, l'organisation et l'interaction avec l'environnement externe. [Ricci et al., 2011]

Les différentes expérimentations de ce principe sur une variété de modèles multi-agents [Hermellin and Michel, 2015,Hermellin and Michel, 2016b, Hermellin and Michel, 2016e, Hermellin and Michel, 2016c] ont souligné le caractère générique de l'approche mais aussi sa capacité à produire des modules GPU indépendants et réutilisables. De plus, grâce à la modularité apportée par l'approche hybride utilisée, les modules GPU créés reposent sur des noyaux de calcul (kernels) très simples (seulement quelques lignes de code) améliorant de ce fait l'accessibilité du GPGPU.

D'ailleurs, il est apparu durant ces applications successives du principe de délégation GPU que nous suivions toujours le même processus d'implémentation [Hermellin and Michel, 2016f]. Nous avons généralisé l'application du principe de délégation GPU sous la forme d'une méthode de conception basée sur ce principe [Hermellin and Michel, 2017b]. Ici, l'objectif était de permettre à un développeur n'ayant aucune expérience dans le domaine de la programmation GPU de l'aborder d'une manière simple, et surtout itérative.

Travaux de recherche post-thèse

Les perspectives de recherche autour des travaux effectués en thèse étaient nombreuses. Deux axes étaient tout particulièrement prometteurs et ont été par la suite explorés :

  • 1. Génie logiciel orienté agent (AOSE).
    Il est clair que l'on a besoin de solutions qui facilitent la modélisation et l'implémentation de simulations multi-agents et cela quelque soit le contexte technologique. En s'inscrivant dans le courant E4MAS, notre méthode de conception poursuit cette quête de simplification au travers d'une décomplexification des comportements agents rendue possible grâce à la place donnée aux environnements (l'environnement est considéré comme essentiel). Bien que l'on ait mis de côté jusqu'ici cet aspect (la diminution de la complexité n'était pas le but premier de mes travaux de thèse), la question de la complexité prend tout son sens avec la méthode que nous proposons car le fait de se baser sur le principe de délégation GPU (qui explicite la séparation entre le modèle agent et l'environnement) et le fait de choisir ce qui va être exécuté par le GPU (grâce à l'approche hybride), permet de fournir à l'agent des percepts et des moyens d'action de haut niveau, afin de simplifier son comportement et d'en garder l'essentiel. En ce sens, nos contributions poursuivent bien les efforts du courant E4MAS et s'inscrivent dans la lignée de travaux tels que [Viroli et al., 2006 , Weyns et al., 2007, Ricci et al., 2011, Michel, 2015, Weyns and Michel, 2015].

    Ainsi, dans une démarche de génie logiciel orienté agent, il est pertinent d'étudier l'impact que peut avoir notre méthode sur la programmation multi-agents en évaluant la capacité de notre méthode à simplifier l'implémentation et la modélisation multi-agent et cela en dehors d'un contexte GPGPU.

    De plus, dans un contexte hardware de plus en plus hétérogène, distribué, connecté, interactif (e.g. IoT), réussir à déléguer une partie d'un système ou modulariser son implémentation va devenir crucial pour assurer son bon fonctionnement. Tout l'enjeu consistera à définir des méthodes de conception efficaces capables de s'adapter au contexte matériel sans en être dépendant. En ce sens, le principe de délégation porté par notre méthode est un bon point de départ, dans le domaine des simulations multi-agents, que je cherche à améliorer et étendre aux systèmes multi-agents (et pas que).

  • 2. Ordonnancement et simultanéité
    L'autre orientation de mes recherches concerne l'ordonnancement des modèles multi-agents. En effet, l'application de notre méthode sur un modèle peut ne pas être neutre (apparition de nouvelles dynamiques suite aux modifications engendrées) mais elle souligne également l'importance que l'on doit donner à l'ordonnancement : l'ordre dans lequel les agents sont activés et produisent leurs perceptions et actions. Il existe d'ailleurs de nombreux de travaux qui traitent de l'ordonnancement dans les systèmes multi-agents et de l'impact qu'il peut avoir sur l'exécution et la dynamique des systèmes. Parmi ces travaux, on peut citer par exemple [Fatès and Chevrier, 2010] qui montre que même avec seulement deux agents aux comportements minimalistes, plongés dans un environnement simple, il est possible d'obtenir des dynamiques très différentes suivant la manière dont le reste du modèle est élaboré (perception, action, temps, interaction, etc.) ou encore IRM4S qui traite de l'utilisation des notions d'influence et de réaction pour la simulation de systèmes multi-agents [Michel, 2007, Chevrier and Fatès, 2008].

    Nous avons d'ailleurs montré que, notre méthode, de par sa conception hybride, impose de séparer les calculs liés aux agents (CPU), des calculs liés à l'environnement (GPU) ce qui introduit un mécanisme en deux phases sur les parties du modèle concernées. Ce mécanisme peut être, à juste titre, relié à une approche de type IRM4S [Hermellin and Michel, 2017a]. Ainsi, un des axes de recherche est de mener une réflexion autour de l'ordonnancement des agents et sur son impact sur la dynamique des systèmes dans un contexte d'utilisation hybride du GPGPU ou plus généralement d'architectures matérielles massivement parallèles. Surtout, considérant que ce genre d'architecture matérielle va se généraliser dans les années à venir.

    Cependant, malgré la possibilité d'intégrer des solutions telle qu'IRM4S dans notre approche (ce travail est en cours et fera l'objet d'une publication future), cette dernière souffrira toujours de biais introduits par l'utilisation du calcul parallèle et par les contraintes inhérentes à ces technologies (comme les problématiques de synchronisation et communication) pouvant d'une part limiter les performances et d'autre part modifier le comportement des agents. De plus, l'activation des agents et l'ordonnancement de leurs actions seraient eux aussi toujours contraints par l'implémentation du modèle et par l'architecture matérielle sur laquelle la simulation est implémentée. Ainsi, il serait pertinent de s'intéresser aux recherches menées dans le domaine des systèmes dynamiques asynchrones dans un cadre discret [Contassot-Vivier, 2006] et tout particulièrement au cas du comportement des réseaux d'automates à états finis. En effet, ces derniers permettent de modéliser de nombreux systèmes complexes et en particulier leurs processus itératifs parallèles. L'activation des agents pouvant être vue comme un processus itératif parallèle, un lien pourrait être fait entre ces deux domaines et doit être exploré.

  • 3. La place du hardware
    Utilisé au départ pour satisfaire un besoin en performance, le hardware (les cartes graphiques dans le contexte du principe de délégation GPU) est devenu plus qu'un simple moyen pour atteindre nos objectifs. Il a permis de répondre également à des problématiques de simultanéité que l'on rencontre dans les simulations et systèmes multi-agents en autorisant une implémentation élégante d'IRM4S. C'est pourquoi les cartes graphiques et plus généralement les architectures matérielles massivement parallèles doivent être considérées comme parties intégrantes des systèmes que l'on étudie. En les considérant comme telle, nous sommes ainsi obligés de revoir notre façon de penser, concevoir et implémenter un système. C'est avec ce prisme que je souhaite aussi étudier ces architectures matérielles dans d'autres domaines de recherche (simulation, apprentissage automatique, etc.).

[Chevrier and Fatès, 2008] Chevrier, V. and Fatès, N. (2008). Multi-agent Systems as Discrete Dynamical Systems : Influences and Reactions as a Modelling Principle. Research report.
[Contassot-Vivier, 2006] Contassot-Vivier, S. (2006). Asynchronism : Continuous and discrete contexts. Habilitation à diriger des recherches, Université de Franche-Comté.
[Fatès and Chevrier, 2010] Fatès, N. and Chevrier, V. (2010). How important are updating schemes in multi-agent systems? an illustration on a multi-turmite model. In van der Hoek, W., Kaminka, G. A., Lespérance, Y., Luck, M., and Sen, S., editors, 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), Toronto, Canada, May 10-14, 2010, Volume 1-3, pages 533–540. IFAAMAS.
[Michel, 2015] Michel, F. (2015). Approches environnement-centrées pour la simulation de systèmes multi-agents. Pour un déplacement de la complexité des agents vers l’environnement. PhD thesis, Université de Montpellier.
[Michel, 2007] Michel, F. (2007). Le modèle irm4s, de l’utilisation des notions d’influence et de réaction pour la simulation de systèmes multi-agents. Revue d’Intelligence Artificielle, 21(5-6) :757–779.
[Hermellin and Michel, 2017a] Hermellin, E. and Michel, F. (2017a).Complex flocking dynamics without global stimulus. In Proceedings of the Fourteenth European Conference Artificial Life, ECAL 2017, Lyon, France, September 4-8, 2017, pages 513--520, MIT Press. [Hermellin and Michel, 2017b] Hermellin, E. and Michel, F. (2017b). Defining a methodology based on GPU delegation for developing MABS using GPGPU. In Nardin, L. G. and Antunes, L., editors, Multi-Agent Based Simulation XVII - InternationalWorkshop, MABS 2016, Singapore, May 10, 2016, Revised Selected Papers, volume 10399 of Lecture Notes in Computer Science, pages 24–41. Springer.
[Hermellin and Michel, 2016a] Hermellin, E. and Michel, F. (2016a). Defining a Methodology Based on GPU Delegation for Developing MABS using GPGPU. In Antunes, L. and Nardin, L. G., editors, Multi-Agent Based Simulation XVII, International Workshop, MABS 2016, Singapore, May 10, Revised Selected Papers, pages 24--41, Lecture Notes in Computer Science (10399), Springer.
[Hermellin and Michel, 2016b] Hermellin, E. and Michel, F. (2016b). Expérimentation du principe de délégation GPU pour la simulation multiagent. les boids de reynolds comme cas d’étude. Revue d’Intelligence Artificielle, 30(1-2) :109–132.
[Hermellin and Michel, 2016c] Hermellin, E. and Michel, F. (2016c). Gpu delegation : Toward a generic approach for developping mabs using gpu programming. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, AAMAS ’16, pages 1249–1258, Richland, SC. International Foundation for Autonomous Agents and Multiagent Systems.
[Hermellin and Michel, 2016d] Hermellin, E. and Michel, F. (2016d). Méthodologie pour la modélisation et l’implémentation de simulations multi-agents utilisant le GPGPU. In Michel, F. and Saunier, J., editors, Systèmes Multi-Agents et simulation - Vingt-quatrièmes journées francophones sur les systèmes multi-agents, JFSMA 16, Saint-Martin-du-Vivier (Rouen), France, Octobre 5-7, 2016., pages 107–116. Cépaduès Éditions.
[Hermellin and Michel, 2016e] Hermellin, E. and Michel, F. (2016e). Multi-Agent Based Simulation XVI : International Workshop, MABS 2015, Istanbul, Turkey, May 5, 2015, Revised Selected Papers, volume 9568, chapter GPU Environmental Delegation of Agent Perceptions : Application to Reynolds’s Boids, pages 71–86. Springer International Publishing.
[Hermellin and Michel, 2016f] Hermellin, E. and Michel, F. (2016f). Overview of case studies on adapting MABS models to GPU programming. In Bajo, J., Escalona, M. J., Giroux, S., Hoffa-Dabrowska, P., Julián, V., Novais, P., Pi, N. S., Unland, R., and Silveira, R. A., editors, Highlights of Practical Applications of Scalable Multi-Agent Systems. The PAAMS Collection - International Workshops of PAAMS 2016, Sevilla, Spain, June 1-3, 2016. Proceedings, volume 616 of Communications in Computer and Information Science, pages 125–136. Springer.
[Hermellin and Michel, 2015] Hermellin, E. and Michel, F. (2015). Délégation GPU des perceptions agents : Application aux boids de reynolds. In Vercouter, L. and Picard, G., editors, Environnements socio-techniques - JFSMA 15 - Vingt-troisièmes Journées Francophones sur les Systèmes Multi-Agents, Rennes, France, June 30th-July 1st, 2015, pages 185–194. Cépaduès Éditions.
[Hermellin et al., 2015] Hermellin, E., Michel, F., and Ferber, J. (2015). État de l’art sur les simulations multi-agents et le GPGPU. Revue d’Intelligence Artificielle, 29(3-4) :425–451.
[Hermellin et al., 2014] Hermellin, E., Michel, F., and Ferber, J. (2014). Systèmes multi-agents et GPGPU : état des lieux et directions pour l’avenir. In Courdier, R. and Jamont, J., editors, Principe de Parcimonie - JFSMA 14 - Vingt-deuxièmes Journées Francophones sur les Systèmes Multi-Agents, Loriol-sur-Drôme, France, Octobre 8-10, 2014, pages 97–106. Cépaduès Éditions.
[Ricci et al., 2011] Ricci, A., Piunti, M., and Viroli, M. (2011). Environment programming in multi-agent systems : an artifact-based perspective. Autonomous Agents and Multi-Agent Systems, 23(2) :158–192.
[Viroli et al., 2006] Viroli, M., Omicini, A., and Ricci, A. (2006). Engineering MAS environment with artifacts. In Weyns, D., Parunak, H. V. D., and Michel, F., editors, Environments for Multi-Agent Systems, volume 3830 of Lecture Notes in Computer Science, pages 62–77. Springer Berlin Heidelberg
[Weyns and Michel, 2015] Weyns, D. and Michel, F. (2015). Agent Environments for Multi-Agent Systems IV, 4th International Workshop, E4MAS 2014 - 10 Years Later, Paris, France, May6, 2014, Revised Selected and Invited Papers, volume 9068 of LNCS. Springer.
[Weyns et al., 2007] Weyns, D., Omicini, A., and Odell, J. (2007). Environment as a first class abstraction in multiagent systems. Autonomous Agents and Multi-Agent Systems, 14(1) :5–30.


Planification automatique Recherche et valorisation

Planification automatique

Durant mon post-doctorat, j'ai fait le choix de changer de thématique de recherche afin de m'ouvrir à d'autres domaines de l'intelligence artificielle. Ainsi, au sein de l'équipe MAGMA (nouvellement MARVIN) du Laboratoire Informatique de Grenoble (LIG), je me suis intéressé à la planification automatique et plus particulièrement à la planification avec réseaux hiérarchisés de tâches (abrégé en planification HTN pour hierarchical task network) qui est une approche à la planification automatique où les actions sont structurés. En planification HTN, un problème est décrit en donnant :

  • Des tâches primitives, qui correspondent à des actions STRIPS [Fikes and Nilsson, 1971] ;

  • des tâches complexes, qui se décomposent en plusieurs sous-tâches ;

  • des tâches buts, qui correspondent aux buts STRIPS, qui sont plus générales.

La planification HTN est indécidable en général, c'est-à-dire qu'il n'existe pas d'algorithme pour planifier un problème HTN dans le cas général [Erol et al., 1996]. Des restrictions syntaxiques décidables ont été mises en place et certains problèmes HTN peuvent maintenant être résolus en les traduisant efficacement en planification classique (en PDDL par exemple) [Behnke et al., 2019].

STRIPS (Stanford Research Institute problem solver) est un algorithme de planification classique conçu par Richard Fikes et Nils Nilsson en 1971. [Fikes and Nilsson, 1971]

J'ai également été amené à travailler sur la façon de transférer les connaissances acquises par la réalisation d'une tâche (tâche source) par un robot pour la réalisation d'une nouvelle tâche (tâche cible). En faisant appel à de l'apprentissage automatique, l'idée est de capturer les similitudes entre les tâches source et cible, et de les exploiter afin d'apprendre la tâche cible plus rapidement. Le défi consiste donc à développer des méthodes pour transférer le modèle de connaissance que le robot apprend sur une situation interactive avec des humains à de nouvelles tâches/situations, notamment à de nouvelles tâches interactives, afin de permettre un apprentissage rapide et l'adaptation à ces nouvelles tâches [Mohammed et al., 2017]. Cette solution pourrait être généralisé en dehors du contexte robotique et intégrée dans un solveur de planification automatique. Ainsi, à partir des différents plans solutions trouvés pour un problème donné, le solveur apprendrait et serait capable de proposer de meilleurs plans compte tenu des conditions initiales données et de l'expérience acquise.

Maturation de travaux de recherche et transfert technologique

Tous ces travaux de recherche ont été réalisé en parallèle avec la maturation et la valorisation d'un outil de planification automatique (PDDL4J) dans lequel les travaux de recherche de l'équipe MAGMA ont été implémentées. A terme, l'objectif a été de réaliser un transfert technologique de ces travaux de recherche par la création d'une start-up. Les phases de maturation puis d'incubation ont été accompagnées par la SATT Linksium (Grenoble). Plus précisément, j'ai donc été amené à :

  • démarcher et rencontrer des industriels afin de réaliser avec eux des preuves de concepts sur la viabilité et l'intérêt de l'outil proposé. Ceci afin de trouver des collaborateurs et clients à la future start-up.

  • comprendre et imaginer quelles pourraient être les besoins des entreprises (à cours et long termes) et comment ces besoins peuvent influencer les recherches de l'équipe ainsi que le développement de l'outil. Mais également participer aux contributions des chercheurs pour, à terme, implémenter les améliorations et découvertes dans l'outil PDDL4J.

  • achever la maturation de l'outil PDDL4J en le menant au niveau des standards industriels. En fin de processus, l'outil est passé d'un TRL 3 à un TRL de 6. Un dépôt APP [PDDL4J v3.8.3] a également été réalisé.

[Behnke et al., 2019] Behnke, G., Höller, D., Bercher, P., Biundo, S., Pellier, D., Fiorino, H., and Alford, R. (2019). Hierarchical Planning in the IPC. In Workshop on HTN Planning (ICAPS), Berkeley, United States.
[Erol et al., 1996] Erol, K., Hendler, J., and Nau, D. S. (1996). Complexity results for htn planning. Annals of Mathematics and Artificial Intelligence, 18(1) :69–93.
[Fikes and Nilsson, 1971] Fikes, R. E. and Nilsson, N. J. (1971). Strips : A new approach to the application oftheorem proving to problem solving.Artificial intelligence, 2(3-4) :189–208.
[Mohammed et al., 2017] Mohammed, O., Bailly, G., and Pellier, D. (2017). Acquiring human-robot interaction skills with transfer learning techniques. In Proceedings of the Companion of the 2017 ACM/IEEE International Conference on Human-Robot Interaction, HRI ’17, page 359–360, New York, NY, USA. Association for Computing Machinery.
[PDDL4J v3.8.3] dépôt APP, mars 2019.

Thèse de doctorat Modélisation et implémentation de simulations multi-agents sur architectures massivement parallèles

Encadrement
Fabien Michel, Maître de conférences HDR, Université de Montpellier, France
Jacques Ferber, Professeur, Université de Montpellier, France

Financement
Bourse ministérielle

Soutenance
18 novembre 2016

Président du jury
Olivier Simonin, Professeur, INSA Lyon, France

Rapporteurs
Alessandro Ricci, Professeur, Université de Bologne, Italie
Vincent Chevrier, Professeur, Université de Lorraine, France

Examinateurs
Olivier Simonin, Professeur, INSA Lyon, France
Jean-Christophe Soulié, Cadre de recherche, CIRAD Montpellier, France


Résumé

La simulation multi-agent représente une solution pertinente pour l’ingénierie et l’étude des systèmes complexes dans de nombreux domaines (vie artificielle, biologie, économie, etc.). Cependant, elle requiert parfois énormément de ressources de calcul, ce qui représente un verrou technologique majeur qui restreint les possibilités d'étude des modèles envisagés (passage à l’échelle, expressivité des modèles proposés, interaction temps réel, etc.).

Parmi les technologies disponibles pour faire du calcul intensif (High Performance Computing, HPC), le GPGPU (General-Purpose computing on Graphics Processing Units) consiste à utiliser les architectures massivement parallèles des cartes graphiques (GPU) comme accélérateur de calcul. Cependant, alors que de nombreux domaines bénéficient des performances du GPGPU (météorologie, calculs d’aérodynamique, modélisation moléculaire, finance, etc.), celui-ci est peu utilisé dans le cadre de la simulation multi-agent. En fait, le GPGPU s'accompagne d’un contexte de développement très spécifique qui nécessite une transformation profonde et non triviale des modèles multi-agents. Ainsi, malgré l'existence de travaux pionniers qui démontrent l'intérêt du GPGPU, cette difficulté explique le faible engouement de la communauté multi-agent pour le GPGPU.

Dans cette thèse, nous montrons que, parmi les travaux qui visent à faciliter l'usage du GPGPU dans un contexte agent, la plupart le font au travers d’une utilisation transparente de cette technologie. Cependant, cette approche nécessite d’abstraire un certain nombre de parties du modèle, ce qui limite fortement le champ d’application des solutions proposées. Pour pallier ce problème, et au contraire des solutions existantes, nous proposons d'utiliser une approche hybride (l'exécution de la simulation est partagée entre le processeur et la carte graphique) qui met l'accent sur l'accessibilité et la réutilisabilité grâce à une modélisation qui permet une utilisation directe et facilitée de la programmation GPU. Plus précisément, cette approche se base sur un principe de conception, appelé délégation GPU des perceptions agents, qui consiste à réifier une partie des calculs effectués dans le comportement des agents dans de nouvelles structures (e.g. dans l’environnement). Ceci afin de répartir la complexité du code et de modulariser son implémentation. L'étude de ce principe ainsi que les différentes expérimentations réalisées montre l'intérêt de cette approche tant du point de vue conceptuel que du point de vue des performances. C'est pourquoi nous proposons de généraliser cette approche sous la forme d'une méthode de modélisation et d'implémentation de simulations multi-agents spécifiquement adaptée à l'utilisation des architectures massivement parallèles.

Publications

Articles, Proceedings, Conférences, ...

Complex flocking dynamics without global stimulus

Emmanuel Hermellin, Fabien Michel Inproceedings 2017
(conférence internationale rang B, acceptation papier long environ 30 %)

Proceedings of the 14th European Conference on Artificial Life 2017 (France, Lyon), pages 513--520

Murmuration, i.e. starlings gathering and swirling with extraordinary spatial coherence, is one of the most impressive kind of bird flocking. It is now well accepted that this collective behavior emerges from individual ones and that no global control is involved. In other words, every starling has an equivalent status in the flock and there is no leader deciding how the murmuration evolves. Considering this phenomenon, Reynolds' individual-based rules have been investigated and implemented a number of times to create compelling computer-animated models of the aerial movement of swarm-like flocks of starlings. Reynolds' model is considered as a classic Agent Based Model (ABM) and integrated as a flagship example in many ABM platforms.
Still, it turns out that implementing Reynolds' model is not sufficient per se in the sense that all murmuration simulations use tricks to achieve a convincing animation of this phenomenon. Especially, virtual leaders or points of interest are used to orientate the starlings, which somehow contradicts the no-global-control perspective, and thus suggests that murmuration dynamics is not yet fully grasped. This paper first highlight this aspect of existing murmuration simulations and then show that it is possible to obtain murmuration-like dynamics by only rethinking how Reynolds' are usually implemented. Especially, the proposed model does not require the existence of a virtual leader nor embed any global aspect.
The objective of this article is to show that it is possible to obtain complex coordinated flight dynamics using a very simple ABM and without adding external stimulus nor additional features, that is by only implementing Reynolds's rules thanks to the IRM4S modeling perspective (an Influence Reaction Model for Simulation). So, in this article, we will first focus on the existing implementations of flocking model to list the advantages and limits and then propose our solution based on the IRM4S approach.

Defining a Methodology Based on GPU Delegation for Developing MABS using GPGPU

Emmanuel Hermellin, Fabien Michel Inproceedings 2016
(conférence internationale, acceptation papier long environ 40 %)

Multi-Agent Based Simulation XVII - International Workshop, MABS 2016, Singapore, May 10, 2016, Revised Selected Papers, pages 24--41, Lecture Notes in Computer Science (vol. 10399)

Multi-Agent Based Simulation (MABS) is used to study complex systems in many research domains. As the number of modeled agents is constantly growing, using General-Purpose Computing on Graphics Units (GPGPU) appears to be very promising as it allows to use the massively parallel architecture of the GPU (Graphics Processing Unit) to do High Performance Computing (HPC).
However, this technology relies on a highly specialized architecture, implying a very specific programming approach. So, to benefit from GPU power, a MABS model need to be adapted to the GPU programming paradigm.

GPU Delegation: Toward a Generic Approach for Developping MABS using GPU Programming

Emmanuel Hermellin, Fabien Michel Inproceedings 2016
(conférence internationale ACM rang A*, acceptation papier long environ 20 %)

AAMAS, proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (Singapour, 2016), pages 1249--1258 (ACM acmid.2937106)

Using Multi-Agent Based Simulation (MABS), computing resources requirements often limit the extent to which a model could be experimented. As the number of agents and the size of the environment are constantly growing in these simulations, using General-Purpose Computing on Graphics Units (GPGPU) appears to be very promising as it allows to use the massively parallel architecture of the GPU (Graphics Processing Unit) to do High Performance Computing (HPC). Considering the use of GPGPU for developing MABS, the conclusions of Perumalla and Aaby's work [Perumalla and al., 2008] in 2008 was twofold: (1) data parallel execution capabilities of GPU can be used effectively in MABS and afford excellent speedup on models and (2) effective use of data parallel execution requires resolution of modeling and execution challenges at the cost of a decrease in modularity, ease of programmability and reusability.
In this paper, we propose to study through experiments if the conclusions and issues outlined by Perumalla and Aaby are still true despite the evolution of GPGPU and MABS. To this end, we use the GPU environmental delegation principle on four models in order to compare CPU and GPU implementations. Then, we discuss and analyze the results from both a conceptual and a performance point of view.

Overview of Case Studies on Adapting MABS Models to GPU Programming

Emmanuel Hermellin, Fabien Michel Inproceedings 2016
(workshop international)

Highlights of Practical Applications of Scalable Multi-Agent Systems. The PAAMS Collection: International Workshops of PAAMS 2016, Sevilla, Spain, June 1-3, 2016. Proceedings, pages 125--136, Communications in Computer and Information Science (vol.616)

General-Purpose Computing on Graphics Units (GPGPU) is today recognized as a practical and efficient way of accelerating software procedures that require a lot of computing resources. However, using this technology in the context of Multi-Agent Based Simulation (MABS) appears to be difficult because GPGPU relies on a very specific programming approach for which MABS models are not naturally adapted. This paper discusses practical results from several works we have done on adapting and developing different MABS models using GPU programming. Especially, studying how GPGPU could be used in the scope of MABS, our main motivation is not only to speed up MABS but also to provide the MABS community with a general approach to GPU programming, which could be used on a wide variety of agent-based models. So, this paper first summarizes all the use cases that we have considered so far and then focuses on identifying which parts of the development process could be generalized.

Méthodologie pour la modélisation et l'implémentation de simulations multi-agents utilisant le GPGPU

Emmanuel Hermellin, Fabien Michel Inproceedings 2016
(conférence nationale, acceptation papier long environ 30 %)

JFSMA, vingt-quatrièmes Journées Francophones sur les Systèmes Multi-Agents (Saint Martin du Vivier, France, 2016), pages 107--116

L'utilisation du GPGPU (General-Purpose computing on Graphics Processing Units) dans le cadre de la simulation multi-agent permet de lever, en partie, les contraintes liées au passage à l'échelle. Cependant, à cause de l'architecture massivement parallèle des GPU (Graphics Processing Units) sur laquelle repose le GPGPU, les modèles voulant bénéficier des avantages de cette technologie doivent être adaptés au préalable.
Prenant le parti de ne pas suivre le courant actuel qui vise à rendre transparent l'utilisation du GPGPU dans le but de simplifier son usage, le principe de délégation GPU propose plutôt de transformer un modèle afin qu'il bénéficie des avantages du GPGPU mais sans cacher la technologie utilisée.
Dans cet article, nous présentons une méthodologie basée sur la délégation GPU pour le développement de simulations multi-agents. L'idée est de proposer une généralisation du processus d'application du principe de délégation GPU que nous expérimenterons ensuite sur deux cas d'études afin de définir quels sont les avantages et limites d'une telle approche.

GPU Environmental Delegation of Agent Perceptions : Application to Reynolds’s Boids

Emmanuel Hermellin, Fabien Michel Inproceedings 2015
(conférence internationale, acceptation papier long environ 40 %)

Multi-Agent-Based Simulation XVI - International Workshop, MABS 2015, Istanbul, Turkey, May 5, 2015, Revised Selected Papers, pages 71--86, Lecture Notes in Computer Science (vol.9568)

Using Multi-Agent Based Simulation (MABS), computing resources requirements often limit the extent to which a model could be experimented with. Regarding this issue, some research works propose to use the General-Purpose Computing on Graphics Processing Units (GPGPU) technology. GPGPU allows to use the massively parallel architecture of graphic cards to perform general-purpose computing with huge speedups. Still, GPGPU requires the underlying program to be compliant with the specific architecture of GPU devices, which is very constraining. Especially, it turns out that doing MABS using GPGPU is very challenging because converting Agent Based Models (ABM) accordingly is a very difficult task. In this context, the GPU Environmental Delegation of Agent Perceptions principle has been proposed to ease the use of GPGPU for MABS. This principle consists in making a clear separation between the agent behaviors, managed by the CPU, and environmental dynamics, handled by the GPU. For now, this principle has shown good results, but only on one single case study. In this paper, we further trial this principle by testing its feasibility and genericness on a classic ABM, namely Reynolds's boids. To this end, we first review existing boids implementations to then propose our own benchmark model. The paper then shows that applying GPU delegation not only speeds up boids simulations but also produces an ABM which is easy to understand, thanks to a clear separation of concerns.

Expérimentation du principe de délégation GPU pour la simulation multiagent : les boids de Reynolds comme cas d’étude

Emmanuel Hermellin, Fabien Michel Inproceedings 2015
(revue nationale avec comité de rédaction)

RIA, Revue d'Intelligence Artificielle (2016), pages 109--132 (vol.30 num 1-2)

L'utilisation du GPGPU (General-Purpose Computing on Graphics Processing Units) pour la simulation multiagent permet d'améliorer les performances des modèles et lève ainsi une partie des contraintes liées au passage à l'échelle. Cependant, adapter un modèle pour qu'il utilise le GPU est une tâche complexe car le GPGPU repose sur une programmation extrêmement spécifique et contraignante. C'est dans ce contexte que la délégation GPU des perceptions agents a été proposée. L'idée derrière ce principe est d'identifier dans le modèle des calculs qui peuvent être transformés en dynamiques environnementales afin d'être calculés par des modules GPU. Il a été appliqué sur un cas d'étude et a montré de bons résultats en termes de performances et de conception. Dans cet article, nous proposons de mettre à l'épreuve la faisabilité et la généricité de cette approche en appliquant le principe de délégation GPU sur un modèle agent classique : les boids de Reynolds. Nous montrons que le principe de délégation offre des résultats intéressants au niveau des performances mais aussi d'un point de vue conceptuel (généricité, accessibilité, etc.).

Délégation GPU des perceptions agents : Application aux Boids de Reynolds

Emmanuel Hermellin, Fabien Michel Inproceedings 2015
(conférence nationale, acceptation papier long environ 30 %)

JFSMA, vingt-troisièmes Journées Francophones sur les Systèmes Multi-Agents (Rennes, France, 2015), pages 185--194

L'utilisation du GPGPU (General-Purpose Computing on Graphics Processing Units) pour la simulation multiagent permet d'améliorer les performances des modèles et lève une partie des contraintes liées au passage à l'échelle. Cependant, adapter un modèle pour qu'il utilise le GPU est une tâche complexe car le GPGPU repose sur une programmation extrêmement spécifique et contraignante. C'est dans ce contexte que la délégation GPU des perceptions agents a été proposée. Ce principe consiste à réaliser une séparation claire entre les comportements de l'agent (gérés par le CPU) et les dynamiques environnementales (manipulées par le GPU) dans le but de faciliter l'implémentation de SMA sur GPU. Il a été appliqué sur un cas d'étude et a montré de bons résultats en termes de performances et de conception. Dans cet article, nous proposons de tester la généricité de cette approche en appliquant le principe de délégation GPU sur un modèle agent très classique : les boids de Reynolds. Nous montrons que le principe de délégation offre des résultats intéressants au niveau des performances mais aussi d'un point de vue conceptuel.

État de l’art sur les simulations multi-agents et le GPGPU

Emmanuel Hermellin, Fabien Michel Article 2014
(revue nationale avec comité de rédaction)

RIA, Revue d'Intelligence Artificielle (2015), pages 425--451 (vol.29 num 3-4)

Dans le domaine des systèmes multi-agents, la hausse constante du nombre d'entités implique un besoin en ressource de calcul de plus en plus important. Cependant, les nombreux outils et plates-formes permettant le développement de simulations multi-agents sur CPU ne supportent plus cette demande en perpétuelle augmentation. Une solution est de se tourner vers le calcul haute performance et notamment vers le calcul sur carte graphique : le GPGPU. Apportant un rapport performance/prix imbattable, cette technique souffre cependant d'une programmation très spécifique qui limite son adoption par la communauté. Dans cet article, nous faisons un état des lieux des simulations multi-agents sur GPU et identifions les solutions les plus prometteuses en vue d'une généralisation de l'utilisation de cette technologie dans la communauté multi-agent.

Systèmes multi-agents et GPGPU : état des lieux et directions pour l’avenir

Emmanuel Hermellin, Fabien Michel Inproceedings 2014
(conférence nationale, acceptation papier long environ 30 %)

JFSMA, vingt-deuxièmes Journées Francophones sur les Systèmes Multi-Agents (Loriol, France, 2014), pages 97--106

Dans le domaine des systèmes multi-agents (SMA), la puissance des CPU représente parfois un frein qui limite fortement le cadre dans lequel un modèle peut être conçu et expérimenté. Le Calcul Haute Performance (HPC) et notamment le GPGPU (General-Purpose computing on Graphics Processing Units) est une solution avantageuse en termes de performance et de coût. Cette technologie vise à utiliser les GPU pour réaliser du calcul généraliste mais souffre cependant d'une très grande complexité d'implémentation et d'accessibilité qui ne favorise pas son adoption. Cet article propose un état de l'art des contributions traitant de l'utilisation du GPGPU dans le contexte des SMA et identifie les directions les plus prometteuses en vue d'une généralisation de cette technologie dans la communauté multi-agents.