Systèmes multi-agents CM°1. Système complexe PDF

Systèmes multi-agents CM°1. Système complexe Maxime Morge Département Informatique Université Claude Bernard Lyon 1 2024-2025  Introduction Modéliser Modèle MBA Conc. Déroulement Organisation Prérequis : I « Al...

Systèmes multi-agents CM°1. Système complexe Maxime Morge Département Informatique Université Claude Bernard Lyon 1 2024-2025  Introduction Modéliser Modèle MBA Conc. Déroulement Organisation Prérequis : I « Algorithmique programmation objet » (APO) Évaluation : QCM(s) Supports disponibles via https://moodle.univ-lyon1.fr/course/view.php?id=9245 clé : SMA Morge SMA - CM 1 Page 2  Introduction Modéliser Modèle MBA Conc. Syllabus Objectif : modélisation multi-agents 1 CM1 : Système complexe 2 TD1 : Simulation centrée individus 3 TP1 : Modélisation multi-agents (3h00) 4 TP2 : Programmation multi-agents (3h00) 5 TP3 : Méthode multi-agents pour la résolution du problème 6 CM2 : Théorie du choix social 7 TD2 : Théorie du choix social 8 TP4 : Modèle multi-agents de diffusion de l’information 9 TT1 : Problème de la patrouille multi-agents (1h30) Morge SMA - CM 1 Page 3  Introduction Modéliser Modèle MBA Conc. Simulation centrée individus Modéliser Modéliser consiste à construire une représentation simplifiée du monde. À quoi ça sert ? comprendre et expliquer un processus confirmer des hypothèses sur les causes d’un phénomène prévoir une dynamique future Simulation centrée individus Modélisation informatique des processus complexes simulant une dynamique collective qui est le résultat des comportements des individus et de leurs interactions. En quoi c’est dur ? pouvoir tester différentes actions (What if ?) avoir un modèle crédible, i.e. descriptif calibrer le modèle sur des données réelles Morge SMA - CM 1 Page 4  Introduction Modéliser Modèle MBA Conc. Plan 1 Modéliser 2 Qu’est-ce qu’un modèle Le modèle comme outil de communication et support du raisonnement Systèmes complexes et modèles computationnels 3 Modélisation basée agents Simulation sociale Systèmes multi-agents Simulation multi-agents 4 Conclusion Morge SMA - CM 1 Page 5  Introduction Modéliser Modèle MBA Conc. Outil Sys. comp. Qu’est-ce qu’un modèle ? Model [Minsky, 1965] To an observer B, an object A∗ is a model of an object A to the extent that B can use A∗ to answer questions that interest him about A. A∗ = un ps. (diffusion de l’innovation), un système (e.g. social) ou un phénomène (e.g. ségrégation) Le modèle est : descriptif, en reproduisant le phénomène (e.g. une courbe en “S” pour la diffusion d’une innovation) explicatif en dégageant des facteurs explicatifs prescriptif en prédisant le comportement dans un cas donné (”What if ?”) normatif, en donnant des indications sur la meilleure façon d’agir (« Comment faire pour que … ? »). Morge SMA - CM 1 Page 6  Introduction Modéliser Modèle MBA Conc. Outil Sys. comp. Le modèle Outil de communication et support du raisonnement Un modèle est une abstraction d’un phénomène réel décrit dans un formalisme. Un modèle discursif est décrit en langue naturelle (SHS) Pro : expressif Cons : difficilement transmissibles (langue d’origine), ambigu ⇒ un outil de communication Un modèle mathématique Cons : moins expressif Pro : formel, permet d’inférer de nouvelles connaissances ⇒ un support du raisonnement Un modèle informatique décrit sous la forme de programme informatique des processus qui manipulent des données, i.e. des algorithmiques. Pro : formel et génératif, i.e. produit des données que l’on peut comparer avec des données réelles Morge SMA - CM 1 Page 7  Introduction Modéliser Modèle MBA Conc. Outil Sys. comp. Système complexe Système complexe Un système complexe est un ensemble d’entités en interaction locale dont le comportement global ne peut pas être modélisé par des équations prédictives et solvables. Par exemple, une colonie de fourmis, un marché économique ou une foule Pourquoi complexe ? 1 les boucles de rétroaction (feedback) positives (amplification) ou négatives (régulation), i.e. l’action en retour d’un effet sur sa propre origine 2 la structure d’interaction qui n’est pas nécessairement complète, i.e. toutes les entités n’interagissent avec toutes les autres le monde Morge SMA - CM 1 Page 8  Introduction Modéliser Modèle MBA Conc. Outil Sys. comp. Système complexe Émergence Le comportement global d’un système complexe est émergent, car il découle des règles d’interaction et il est irréductible du tout vers ses parties. Des phénomènes d’auto-organisation émergent des interactions locales, e.g. agrégation d’insectes, banc de poissons ou nuée d’oiseaux [Reynolds, 1987] L’intelligence collective distribuée est un phénomène d’auto-organisation permettant la coopération, e.g. termites, abeilles ou fourmis Morge SMA - CM 1 Page 9  Introduction Modéliser Modèle MBA Conc. Outil Sys. comp. Application à grand succès Morge SMA - CM 1 Page 10  Introduction Modéliser Modèle MBA Conc. Outil Sys. comp. Une seule solution : la simulation Pour connaître l’évolution d’un système complexe Automates cellulaires Modèle informatique pour l’étude des systèmes complexes state(cell, t) cell0 ∈neighbors(cell) state(cell0 , t) → state(cell, t + 1) V Dans un grille unidimensionnelle, il y 256 automates. John Von Neumann Par exemple la règle 30. 1903-1957 t 111 110 101 100 011 010 001 000 t+1 0 0 0 1 1 1 1 0 Morge SMA - CM 1 Page 11  Introduction Modéliser Modèle MBA Conc. Outil Sys. comp. Une seule solution : la simulation Pour connaître l’évolution d’un système complexe Automates cellulaires Modèle informatique pour l’étude des systèmes complexes state(cell, t) cell0 ∈neighbors(cell) state(cell0 , t) → state(cell, t + 1) V Dans un grille unidimensionnelle, il y 256 automates. John Von Neumann Par exemple la règle 30. 1903-1957 t 111 110 101 100 011 010 001 000 t+1 0 0 0 1 1 1 1 0 Morge SMA - CM 1 Page 11  Introduction Modéliser Modèle MBA Conc. Outil Sys. comp. Une seule solution : la simulation Pour connaître l’évolution d’un système complexe Automates cellulaires Modèle informatique pour l’étude des systèmes complexes state(cell, t) cell0 ∈neighbors(cell) state(cell0 , t) → state(cell, t + 1) V Dans un grille unidimensionnelle, il y 256 automates. John Von Neumann Par exemple la règle 30. 1903-1957 t 111 110 101 100 011 010 001 000 t+1 0 0 0 1 1 1 1 0 Morge SMA - CM 1 Page 11  Introduction Modéliser Modèle MBA Conc. Outil Sys. comp. Une seule solution : la simulation Pour connaître l’évolution d’un système complexe Automates cellulaires Modèle informatique pour l’étude des systèmes complexes state(cell, t) cell0 ∈neighbors(cell) state(cell0 , t) → state(cell, t + 1) V Dans un grille unidimensionnelle, il y 256 automates. John Von Neumann Par exemple la règle 30. 1903-1957 t 111 110 101 100 011 010 001 000 t+1 0 0 0 1 1 1 1 0 Morge SMA - CM 1 Page 11  Introduction Modéliser Modèle MBA Conc. Outil Sys. comp. Une seule solution : la simulation Pour connaître l’évolution d’un système complexe Automates cellulaires Modèle informatique pour l’étude des systèmes complexes state(cell, t) cell0 ∈neighbors(cell) state(cell0 , t) → state(cell, t + 1) V Dans un grille unidimensionnelle, il y 256 automates. John Von Neumann Par exemple la règle 30. 1903-1957 t 111 110 101 100 011 010 001 000 t+1 0 0 0 1 1 1 1 0 Morge SMA - CM 1 Page 11  Introduction Modéliser Modèle MBA Conc. Outil Sys. comp. Une seule solution : la simulation Une règle simple produit un motif complexe 4 classes de comportements : 1 conduit à un état homogène 2 mène à des structures stables ou périodiques émergent 3 comportement chaotique avec des motifs apériodiques Stephen Wolfram. 1959- 4 émergence des structures complexes capables d’osciller, de se mouvoir, de persévérer Morge SMA - CM 1 Page 12  Introduction Modéliser Modèle MBA Conc. Outil Sys. comp. Émergence des structures complexes Exemple du jeu de la vie Jeu de la vie Le jeu de la vie est un automate cellulaire bidimensionnel où chaque cellule a 2 états possibles : vivante (1) ou morte (0). Si vivante et 2/3 voisines vivantes alors vivante. Sinon meurt John Horton Conway 1937-2020 Si morte et 3 voisines vivantes, alors vivante Configuration à t Configuration à t + 1 Morge SMA - CM 1 Page 13  Introduction Modéliser Modèle MBA Conc. Outil Sys. comp. Émergence des structures complexes Exemple du jeu de la vie Jeu de la vie Le jeu de la vie est un automate cellulaire bidimensionnel où chaque cellule a 2 états possibles : vivante (1) ou morte (0). Si vivante et 2/3 voisines vivantes alors vivante. Sinon meurt John Horton Conway 1937-2020 Si morte et 3 voisines vivantes, alors vivante Configuration à t Configuration à t + 1 Morge SMA - CM 1 Page 13  Introduction Modéliser Modèle MBA Conc. Outil Sys. comp. Le jeu de la vie est Turing complet Glisseurs, canons, recouvreurs de plan et jardins d’Éden Morge SMA - CM 1 Page 14  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Simulation sociale Simulation sociale La simulation sociale est un domaine de recherche qui utilise les méthodes informatiques pour étudier les sciences sociales. Exemple du modèle de ségrégation de Schelling Une cellule de la grille est un logement Un logement est libre ou occupé par un individu avec une ethnie Un individu a un seuil de tolérance à la différence si son voisinage est sous ce seuil, l’individu garde son logement sinon l’individu déménage vers une cellule vide choisie aléatoirement La grille est initialisée aléatoirement Fait stylisé Une population tolérante (qui accepte même d’être en minorité jusqu’à un certain point) évolue vers une structure ségrégative. Morge SMA - CM 1 Page 15  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Simulation sociale NetLogo est un langage de programmation et un IDE pour la simulations multi-agents Morge SMA - CM 1 Page 16  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Sugarscape Modèle multi-agents de société artificielle Une ressource (le sucre) produit de façon continue et spontanée selon une répartition spatiale hétérogène Les agents sont répartis aléatoirement, explorent l’environnement, ramassent le sucre et font des réserves Une population hétérogène d’agents ayant une espérance de vie, une portée de la vision et un métabolisme À chaque itération, un agent 1 scrute son voisinage (porté de la vision) et se déplacent (ou pas) vers la cellule inoccupée la plus proche qui contient le plus de sucre 2 collecte et consomme (métabolisme) le sucre produit 3 éventuellement meurt de faim ou de vieillesse (espérance de vie) Faits stylisés La répartition inégale des richesses résulte de l’inégalité de la répartition initiale des ressources et de l’inégalité des dispositions des agents Les riches deviennent encore plus riches et les pauvres encore plus pauvres Morge SMA - CM 1 Page 17  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Sugarscape Modèle explicatif des inégalités Morge SMA - CM 1 Page 18  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA CovidSim [Ferguson et al., 2020] Modèle épidémiologique à base d’agents Paramètres : âge, sexe, état de santé, emploi, nb contacts des individus transports, interactions offres de soins R0 etc. Morge SMA - CM 1 Page 19  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Système complexe KISS -Keep It Simple, Stupid [Simon, 2019] Stylisé (concept-driven) Sugarscape KISS KIDS (simple) (détaillé) CovidSim Particulier (data-driven) Morge SMA - CM 1 Page 20  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Systèmes multi-agents Systèmes Multi-Agents (SMA) Un SMA est composé de multiples entités autonomes, appelées agents, en interaction, situés dans un environnement qui prennent part à une organisation. Organisation Niveau macroscopique Niveau mésoscopique Interaction perçoit Environnement Agent Niveau microscopique agit Morge SMA - CM 1 Page 21  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Agent 6= Objet Agent Un agent est une entité de calcul capable de percevoir et d’agir sur son environnement dont le comportement est le résultat de règles ou algorithmes qui lient ses perceptions et son état interne à ses actions. Un agent a un état interne (mémoire) et des opérations, comme un objet (encapsulation) Mais il est autonome, il agit de manière à atteindre les objectifs qui lui ont été fixés lors de la conception Réactif s’il agit par réflexe ou Cognitif (délibératif) s’il raisonne en manipulant une représentation explicite de ses buts, numérique (fonction d’utilité) ou symbolique (langage logique) perçoit Environnement Agent agit Morge SMA - CM 1 Page 22  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Environnement [Russel et Norvig, 2016] Le lieu des actions individuelles ou collectives Environnement L’environnement est l’espace commun partagé par les agents, constitué d’objets, actifs ou passifs, qui peuvent être perçus, voire manipulés (e.g consommés) par les agents. Il est muni d’une topologie qui structure les relations entre agents (accointances) voire leur déplacement et l’accès aux ressources lorsque les agents et les objets sont situés. Un environnement est : accessible si un agent a accès (6= partiellement) à l’état de l’environnement déterministe si l’état du monde à l’instant suivant est complètement déterminé par l’état courant et par les actions effectuées par les agents (6= stochastique) épisodique si à chaque étape, le prise de décision de l’agent dépend uniquement de l’étape elle-même et non pas des décisions prises au cours des étapes précédentes (6= séquentiel) dynamique si l’environnement évolue pendant que l’agent décide quelle action accomplir (6= statique) avec le temps (semi) Morge SMA - CM 1 Page 23  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Interaction Interaction Une interaction est une influence mutuelle entre agents. On distingue les interactions : indirectes (stigmergie), via des signaux, marqueurs chimiques, forces d’attraction/répulsion, etc. directes, via des échanges de message d’un expéditeur à un ou plusieurs destinataires La communication : est associé à un langage muni d’une sémantique afin d’énoncer et d’interpréter ces messages est scénarisée par des protocoles permet de prendre une décision collective en votant, enchérissant, marchandant, argumentant permet aux agents de coopérer, i.e. en collaboration ou en compétition Morge SMA - CM 1 Page 24  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Organisation Organisation Une organisation est une structure sociale explicite ou le schéma stable émergeant de l’activité conjointe des agents. Une organisation peut : Agent joue 1..n 1..n contraindre les comportements individuels pour en réduire la complexité réduire l’étendue des interactions 1..n 1..n définit formuler des buts collectifs et des contraintes globales Groupe 1..n 1..n Rôle Morge SMA - CM 1 Page 25  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Simulation multi-agents EBM-Equation-Based Model Un modèle à base d’équations (statistique, équation différentielle) formalise des relations entre grandeurs macroscopiques observables ABM-Agent-Based Model Un modèle à base d’agents réifient les comportements individuels, l’environnement et les interactions du niveau microscopique. Approche bottom-up qui permet : d’étudier les liens entre les niveaux microscopique, macroscopique et mésoscopique d’intégrer les facteurs explicatifs présents au niveau individuel de représenter l’hétérogénéité des entités, de leurs caractéristiques permanentes (préférences, motivations, etc.) et de leurs expériences (connaissances, expériences) Morge SMA - CM 1 Page 26  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Modèle à base d’équations Exemple du modèle de prédation [Lotka, 1920 ; Volterra, 1928] Modèle de prédation Modèle de la dynamique de systèmes biologiques dans lesquels des prédateurs et des proies interagissent :  dx(t) = x(t) α − βy(t)     σ(s, i) = dt  dy(t) = y(t) δx(t) − γ    dt où x(t) (resp. y(t)) représente l’effectif des proies (resp. prédateurs) en fonction du temps. Les paramètres du modèle sont : α, le taux de reproduction des proies β, i.e. le taux de mortalité des proies δ, i.e. le taux de reproduction des prédateurs γ, i.e. le taux de mortalité des prédateurs Morge SMA - CM 1 Page 27  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Modèle à base d’agents Exemple du modèle de prédation [Wilensky, 2005] Modèle de prédation Modèle centré individus de la dynamique de systèmes biologiques dans lesquels des loups et des moutons interagissent : des moutons errent au hasard dans un paysage en mangeant de l’herbe pour récupérer de l’énergie des loups essayent d’attraper des moutons pour récupérer de l’énergie Les paramètres du modèle sont : la quantité d’énergie pour chaque parcelle d’herbe mangée par un mouton la quantité d’énergie pour chaque mouton mangé par un loup le taux de reproduction des moutons/loups Fait stylisé de l’EBM/ABM Un mouvement harmonique dans l’évolution des populations L’ABM est plus réaliste : des paramètres hétérogènes/spatiaux (déplacement, vision) Morge SMA - CM 1 Page 28  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Modèle à base d’agents Démonstation du modèle de prédation [Wilensky, 2005] Morge SMA - CM 1 Page 29  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Modèle à base d’agents Initialisation du modèle de prédation [Wilensky, 2005] breed [ sheep a-sheep ] ; Les tortues sont de 2 espèces breed [ wolves wolf ] turtles-own [ energy ] ; Chacune ayant un niveau d'énergie to setup ; Configuration clear-all ; réinitialiser ask patches [ set pcolor green ] ; de l'herbe partout create-sheep initial-number-sheep ; créer des moutons [ set shape "sheep" ; facilement visualisable set color white set size 1.5 set label-color blue - 2 set energy random (2 * sheep-gain-from-food) ; en forme setxy random-xcor random-ycor ; dispersés ] create-wolves initial-number-wolves ; créer des moutons [ set shape "wolf" ; facilement visualisable set color black set size 2 ; easier to see set energy random (2 * wolf-gain-from-food) ; en forme setxy random-xcor random-ycor ; dispersé ] reset-ticks ; démarrer l'horologe end Morge SMA - CM 1 Page 30  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Modèle à base d’agents Simulation du modèle de prédation [Wilensky, 2005] to go ; Simulation du modèle if not any? turtles [ stop ] ; arreter si aucune tortue ask sheep [ ; demander à chaque mouton de move ; se déplacer reproduce-sheep ; se reproduire aléatoirement ] ask wolves [ ; demander à chaque loup de move ; se déplacer set energy energy - 1 ; se fatiguer eat-sheep ; manger death ; éventuellement mourir reproduce-wolves ; ou se reproduire ] tick ; incrémenter l'horloge end Morge SMA - CM 1 Page 31  Introduction Modéliser Modèle MBA Conc. Sim. soc. SMA Modèle SMA Modèle à base d’agents Procédures du modèle de prédation [Wilensky, 2005] to move ; Se déplacer rt random 50 ; tourner à droite lt random 50 ; tourner à gauche fd 1 ; avancer d'un pas end to eat-grass ; Manger de l'herbe set pcolor brown set energy energy + sheep-gain-from-food ; ça revigore end to eat-sheep ; Manger un mouton let prey one-of sheep-here ; attraper un mouton if prey != nobody [ ; si possible ask prey [ die ] ; le tuer set energy energy + wolf-gain-from-food ; ça revigore ] end to reproduce-sheep ; ; Se reproduire comme un mouton if random-float 100 < sheep-reproduce [ ; aléatoirement set energy (energy / 2) ; partager l'énergie hatch 1 [ rt random-float 360 fd 1 ] ; éclore et bouger ] end... Morge SMA - CM 1 Page 32  Introduction Modéliser Modèle MBA Conc. À emporter Simulation centrée individus Modélisation informatique des processus complexes simulant une dynamique collective qui est le résultat des comportements des individus et de leurs interactions. Système complexe Un système complexe est un ensemble d’entités en interaction locale dont le comportement global ne peut pas être modélisé par des équations prédictives et solvables. Systèmes Multi-Agents (SMA) Un SMA est composé de multiples entités autonomes, appelées agents, en interaction, situés dans un environnement qui prennent part à une organisation. À venir : Analyse et construire une simulation multi-agents avec Netlogo (TP) Résolution centrée individus (CM) Morge SMA - CM 1 Page 33 Bibliographie I Ferguson, N., Laydon, D., Nedjati Gilani, G., Imai, N., Ainslie, K., Baguelin, M., Bhatia, S., Boonyasiri, A., Cucunuba Perez, Z., Cuomo-Dannenburg, G., et al. (2020).Report 9 : Impact of non-pharmaceutical interventions (NPIs) to reduce COVID19 mortality and healthcare demand. Lotka, A. J. (1920).Analytical note on certain rhythmic relations in organic systems. Proceedings of the National Academy of Sciences, 6(7), 410-415. Minsky, M. (1965).Matter, mind and models. IFIP Congress, 45-49. Reynolds, C. W. (1987).Flocks, herds and schools : A distributed behavioral model. Proceedings of SIGGRAPH, 21(4), 25-34. Russel, S., & Norvig, P. (2016). Artificial Intelligence : A Modern Approach Global Edition. Schelling, T. C. (1971).Dynamic models of segregation. Journal of mathematical sociology, 1(2), 143-186. Simon, H. A. (2019). The sciences of the artificial. MIT press. Volterra, V. (1928).Variations and fluctuations of the number of individuals in animal species living together. ICES Journal of Marine Science, 3(1), 3-51. Morge SMA - CM 1 Page 34 Bibliographie II Wilensky, U. (2005). NetLogo Wolf Sheep Predation model. [http://ccl.northwestern.edu/netlogo/models/WolfSheepPredation]. Morge SMA - CM 1 Page 35