Auteur : Philippe Mathieu, CRISTAL Lab, SMAC Team, University of Lille, email : philippe.mathieu@univ-lille.fr
Contributeurs : Nicolas Mauhé (CRISTAL/SMAC)
Creation : 18/01/2018
Les Systèmes multi-agents (SMA) sont des systèmes dans lequel des entités dotées de leur propre comportement, intéragissent entre-elles. Cette approche de modélisation répond à quatre grandes familles de problèmes :
Il est possible de représenter des agents dans tous les langages, mais les langages objets sont sans aucun doute les plus proches de la philosophie "Agent". Un SMA s'écrit donc très facilement à partir d'un langage à objets. Parmi ces langages, Python apporte la concision dans le code. l'objectif de cette page Jupyter n'est pas de fournir un SMA sophistiqué, mais de montrer les bases de sa conception en quelques lignes.
Dans sa forme la plus simple, un agent est une entité dotée d'une seule capacité, celle de décider quoi faire. Personne ne lui indique ce qu'il doit faire, c'est lui qui décide ! C'est le principe d'autonomie. Il suffit juste de lui donner la parole pour qu'il agisse. Lors de sa prise de parole, l'agent réalise sémantiquement 3 étapes différentes : la perception de son entourage, la decision en fonction de son propre état et de ce qu'il a perçu, puis l'action effective qu'il réalise in fine. Idéalement chaque agent ne peut faire qu'une seule action lors de sa prise de parole.
class Agent:
def __init__(self,name) :
self.name=name
def decide(self):
print("Hello ! My name is "+self.name)
Il est bien sûr possible de créer plusieurs agents et de les interroger directement.
a1 = Agent("philippe")
a2 = Agent("antoine")
a1.decide()
a2.decide()
Hello ! My name is philippe Hello ! My name is antoine
Bien évidemment, un système multi-agent utilise des dizaines voire des
milliers d'agents. Il est alors necessaire de créer une classe
permettant de les manager. En général la méthode qui lance la
simulation se nomme run
et prend en paramètre le nombre de prises de
paroles.
import random
class SMA:
def __init__(self):
self.agentList = []
def addAgent(self,ag):
self.agentList.append(ag)
def run(self,ticks):
for i in range(ticks):
random.choice(self.agentList).decide()
sma = SMA()
sma.addAgent(Agent("paul"))
sma.addAgent(Agent("kim"))
sma.run(6)
Hello ! My name is kim Hello ! My name is kim Hello ! My name is paul Hello ! My name is paul Hello ! My name is paul Hello ! My name is kim
La méthode précédente, triviale, est discutable. Elle donne au hasard la parole à un agent, et, de ce fait, risque d'en avantager certains. Elle n'est pas équitable. Il est plus judiscieux de s'assurer que chaque agent ait au moins une fois la parole avant qu'un autre agent ne l'ait deux fois. On introduit alors la notion de tour de parole. Chaque tour de parole donne aléatoirement la parole à l'ensemble des agents, avant de recommencer. Un tour de parole constitue sémantiquement une unité de temps, un tick d'horloge. La classe SMA s'écrit alors
import random
class SMA:
def __init__(self):
self.resetTicks()
self.agentList = []
def resetTicks(self):
self.tick=0
def addAgent(self,ag):
self.agentList.append(ag)
def run(self,rounds):
for i in range(0,rounds):
self.runOnce()
def runOnce(self):
self.tick+=1
random.shuffle(self.agentList)
for ag in self.agentList :
ag.decide()
print("tick "+str(self.tick)+" ended")
sma = SMA()
sma.addAgent(Agent("paul"))
sma.addAgent(Agent("kim"))
sma.addAgent(Agent("Lisa"))
sma.run(5)
Sur un ordinateur, il n'est jamais possible d'accélérer un processus. Le processus tourne à la vitesse optimale. Néanmoins il est possible de le ralentir. Si on souhaite qu'un agent prenne la parole deux fois moins souvent qu'un autre, il lui suffit alors qu'il la refuse une fois sur deux ce qui se réalise avec un simple modulo dans la procédure de décision. Il est alors possible de paramétrer très finement la vitesse de prise de parole de chaque agent et d'obtenir les rapports de vitesses que l'on souhaite entre les agents.
class Agent:
def __init__(self,name,slowdown) :
self.name=name
self.slowdown=slowdown
self.talk=0
def decide(self) :
if (sma.tick % self.slowdown != 0):
return
self.talk+=1
print("Hello. My name is "+self.name+", and this is my "+str(self.talk)+" talk")
sma = SMA()
sma.addAgent(Agent("paul",1))
sma.addAgent(Agent("kim",2))
sma.addAgent(Agent("lisa",3))
sma.run(6)
Comme tout outil informatique, le Système Multi Agent (SMA) doit permettre à l'utisateur d'étudier différentes propriétés. Ces propriétés à étudier peuvent être placées au niveau microscopique (c'est dire au niveau d'un agent, par exemple l'évolution de son bien-être, de sa richesse, de son age ou de sa santé), et/ou au niveau macroscopique (c'est à dire au niveau du SMA comme le nombre d'agents vivants, le chiffre d'affaire d'un magasin, ou le nombre global de messages échangés). Bien sûr, cette observation peut se faire in fine, auquel cas une valeur est renvoyée en fin d'expérience, ou tout au long de l'expérience, amenant alors à des courbes temporelles.
Prenons l'exemple d'agents placés dans un reseau social. Chaque agent possède une liste d'accointances (entre 1 et le nombre total d'agents), formant ainsi un graphe social. A des fins d'expériences, une information (ball
) est passée d'agent en agent (has_it
), chacun passant l'information à l'une de ses accointances.
SMA(10,matrix)
. lors de cette construction le SMA crée les n agents souhaités en leur passant à tous leur identifiant, ainsi que la liste de leurs accointances
for i in range(nb_agents):
self.agentList.append(Agent(i, np.nonzero(adjacency_matrix[i])[0]))agent(3,[1,5,7])
Cette matrice sera créée en externe par l'une des méthodes du package numpy bien adapté à cela. Numpy offre notamment de très nombreuses fonctions de manipulation de matrices. [http://www.numpy.org/] click tutorial to have a brief intro.
Dans sa méthode de décision, l'agent regarde s'il a l'information, et si oui, choisit aléatoirement l'un de ses amis dans sa liste pour lui passer. A des fins d'analyse, chaque agent gère aussi son historique des récupérations de la balle : une simple map qui contient à chaque tick le nombre de fois où il a obtenu la balle : {0:0, 1:0, 2:0, 3:1, 4:1, 5:2, 6:2}
import numpy as np
class SMA:
def __init__(self, nb_agents, adjacency_matrix):
self.tick = 0
self.agentList = []
# Initialize accointances based on the matrix
for i in range(nb_agents):
self.agentList.append(Agent(i, np.nonzero(adjacency_matrix[i])[0]))
def run(self, rounds):
for i in range(0,rounds):
self.runOnce()
def runOnce(self):
self.tick += 1
for agent in self.agentList:
agent.decide(self.tick)
print("tick " + str(self.tick) + " ended")
class Agent:
def __init__(self, id_number, accointances) :
self.id_number = id_number
self.accointances = accointances
self.has_it = False
self.history = {0: 0}
def decide(self, tick) :
# print("agent "+str(self.id_number)+" has the talk")
if tick not in self.history:
self.history[tick] = self.history[tick-1]
if self.has_it:
chosen = np.random.choice(self.accointances, 1)
self.has_it = False
sma.agentList[chosen[0]].has_it = ball
sma.agentList[chosen[0]].history[tick] = sma.agentList[chosen[0]].history[tick-1] + 1
print(str(self.id_number) + " gives it to " + str(chosen[0]))
On initialise le système en créant tout d'abord un graphe. Le package networkx regorge de méthodes de création de graphes (on s'assure qu'il soit connexe pour que chaque agent ait au moins une accointance). Il suffit ensuite de les convertir en matrices numpy pour les passer au SMA. Voir [https://networkx.github.io/] click doc to have many examples
import networkx as nx
nb_agents = 16
graph = nx.barabasi_albert_graph(nb_agents, 2)
#graph = nx.complete_graph(nb_agents)
#graph = nx.erdos_renyi_graph(nb_agents,0.1)
#graph = nx.cycle_graph(nb_agents)
#graph = nx.random_regular_graph(3,nb_agents)
matrix = nx.to_numpy_array(graph, nodelist=range(nb_agents))
sma = SMA(nb_agents, matrix)
La librairie matplotlib
facilite grandement les représentations graphiques 2D avec sa fonctionplot
.
Plus plus de détails, voir [https://matplotlib.org/users/history.html]
import matplotlib.pyplot as plt
plt.figure(figsize=(10,5)) # pour définir la taille de la figure
nx.draw_networkx(graph)
plt.axis('off')
plt.show()
plt.hist(dict(graph.degree()).values())
plt.show()
On donne la balle à un agent au hasard et on lance un certain nombre de tours.
# On donne la balle
ball = "Could be anything."
an_agent = np.random.choice(sma.agentList)
an_agent.has_it = ball
print("Initially, agent "+str(an_agent.id_number)+" has the ball.")
an_agent.history[0] = 1
# On lance le jeu
nb_rounds = 40
sma.run(nb_rounds)
# On reprend la balle, pour une éventuelle réexécution.
for agent in sma.agentList:
if agent.has_it:
agent.has_it = False
Prenons l'exemple de l'agent 8. On trace l'évolution du nombre de fois où cet agent a reçu la balle tout au long de l'expérience
import matplotlib.pyplot as plt
plt.plot(sorted(list(sma.agentList[8].history.values())))
plt.show()
Il est d'ailleurs possible d'afficher l'évolution de tous les agents sur le meme graphe (même si avec beaucoup d'agents cela devient vite illisible) :
plt.figure(figsize=(12,10))
for agent in sma.agentList:
plt.plot(sorted(list(agent.history.values())), label=agent.id_number)
plt.legend()
plt.show()
On peut également placer des poids sur les noeuds du graphe, liés par exemple au nombre de fois qu'ils ont eu la balle, puis afficher le graphe avec des intensité de bleus différentes selon ces poids. Cela permet par exemple de vérifier l'hypothèse selon laquelle les agents les plus connectés ont eu plus souvent la balle.
plt.figure(figsize=(10,5))
weights = [agent.history[nb_rounds] for agent in sma.agentList]
nx.draw_networkx(graph, node_color=weights, cmap=plt.cm.Blues)
plt.axis('off')
plt.show()
decide
¶On peut se demander qui contrôle le fait que chaque agent n'effectue qu'une seule action à chaque tick ? Dans cette implémentation : rien ! Un agent peut parfaitement exécuter plusieurs actions durant une prise parole sans que le système n'en sache rien. En pratique, lors de la conception d'un SMA, deux possibilités s'offrent au développeur pour la gestion de la méthode decide :
decide
exécute les actions et ne renvoie alors rien. De ce fait les agents peuvent éventuellement faire plusieurs actions, mais en contrepartie on respecte strictement le principe d'autonomieControle des agents ou autonomie des agents, il faut choisir !
En s'appuyant sur l'exercice 1, créez une méthode permettant pour un type de réseau de réaliser n
expériences consécutives. Les valeurs de n
et du réseau seront passés en paramètre. La méthode renverra le nombre d'étapes moyen qu'il a fallu réaliser pour arriver à l'arrêt (un agent avec 2 balles).
Testez cette méthode avec 4 types de réseaux différents (nx.complete_graph(nb_agents)
, nx.erdos_renyi_graph(nb_agents,0.1)
,nx.cycle_graph(nb_agents)
,nx.random_regular_graph(3,nb_agents)
) et montrez l'influence du réseau sur le nombre d'étapes nécessaires.
Sur le même principe que précédemment, on souhaite réaliser un système dans lequel tous les agents se connaissent, et chaque agent possède un certain nombre d'unités de richesse (wealth
). Initalement, tous sont parfaitement égaux et ont tous une richesse de 5. Chaque fois qu'un agent a la parole (donnée de manière équitable), l'agent choisit au hasard un autre agent et lui donne 1 richesse (s'il n'est pas à 0 bien sûr). Réalisez n
tours de parole et tracez ensuite un diagramme de type bar
indiquant la richesse par agent, ainsi que l'histogramme de distribution des richesses.
On souhaite maintenant que les agents aient une préférence pour leur classe sociale, donc ici pour les agents qui ont grosso-modo la même richesse qu'eux. Cette fois la richesse est tirée uniformément entre 1 et 10. Faites en sorte que les dons soient toujours faits avec un agent pris aléatoirement, mais cette fois ci, avec une probabilité proportionnelle à l'inverse de l'écart à son propre wealth. Dans le cas où l'écart est nul (ce qui impliquerait une division par zéro), on pourra fixer la probabilité à 2 (ils ont alors plus de chances d'être pris quand ils sont égaux, que quand ils ont 1 de différence). Retestez ensuite l'évolution de l'histogramme des richesses.
Aide: Il s'agit ici de programmer une sorte de "roue de la fortune" (pour info la methode Choice
de numpy
permet d'indiquer des distributions de probas) dans le processus de décision de l'agent : au moment de sa décision, l'agent calcule une map avec comme clé l'un des agents et comme valeur l'inverse de l'écart à son propre wealth. Il fait ensuite la somme totale des valeurs obtenues et tire un nombre aléatoire entre 0 et ce total. Il reparcourt son tableau en cumulant les valeurs à concurrence du nombre tiré. L'agent sur lequel il tombe correspond à celui à qui il fait un don.
Philippe Mathieu, Yann Secq. Environment Updating and Agent Scheduling Policies in Agent-based Simulators. ICAART Conference, 2012, pp 170-175
Philippe Mathieu, Sébastien Picault, Yann Secq. Design Patterns for Environments in Multi-agent Simulations. PRIMA Conference, 2015, pp 678-686
Philippe Mathieu, Gildas Morvan, Sébastien Picault. Multi-level agent-based simulations: Four design patterns. Journal of Simulation Modelling Practice and Theory, Janv 2018