Systèmes multi-agents, la méthode "Eco Problem Solving"

Les Systèmes Multi Agents (SMA) ont été inspirés par l'observation des comportements sociaux des colonies d'insectes. Les colonies de fourmis et d'abeilles exhibent de l'intelligence collective et intelligence distribuée.

Reproduire ou étendre ces comportements observés est possible en les simulant avec un ordinateur, on se retrouve alors à créer un Système Multi Agent, défini par l'environnement et les agents qui évoluent dedans.

On trouve plein d'applications qui bénéficient de ces systèmes, l'agent prend une forme différente selon le domaine d'application : une cellule en biologie, un robot en robotique, un humain en sociologie, une node en réseau, un personnage dans un jeu vidéo, un véhicule dans un réseau de transport…

Les SMA excellent en simulation de phénomènes réels et résolution de problèmes dans des systèmes complexes

Par exemple la simulation de foule est faite dans un système multi agent:

Vadere Crowd Simulation

Un agent

Qu'est-ce qui défini un agent ? Il doit être :

Autonome : Capable d'agir sans intervention humaine

Réactif : Capable de réagir à son environnement

Proactif : Poursuit activement un but

Sociable : Capable de communiquer, coopérer avec d'autres agents

Pour ça, on définit :

Sa perception de son environnement

Son système de décision (machine état transition, algorithme, réseau de neurone…)

Les actions qu'il peut appliquer à son environnement

Son but

Un exemple d'agent : un rover martien

Son environnement est physique, c'est Mars

Sa perception est l'ensemble des informations enregistrées par ses capteurs (caméra, température, humidité…)

Ses actions sont de se déplacer, récolter des échantillons, transmettre un message à la Terre

Son but est de récolter le plus d'échantillons, les plus divers possibles et maintenir son intégrité

Quels avantages à cette modélisation ?

Pourquoi s'embêter à rajouter cette couche d'abstraction lorsque l'on veut résoudre un problème ?

La modélisation d'agents prend tout son sens lorsque l'on considère des environnements comportant plusieurs agents, on a alors un Système Multi Agent, capable de:

Distribution : partager des responsabilités, charges de calculs, décisions entre plusieurs agents

Décentralisation : la responsabilité et le contrôle n'appartiennent plus à un unique système

Résilience : Si un agent rencontre une erreur, tous les autres s'adaptent et le système est toujours fonctionnel

Émergence : Les règles d'interaction entre les agents fait émerger des comportements plus complexe que ce qui a été initialement défini.

Comportement sociaux : Un comportement difficile à répliquer par une intelligence monolithique (par définition)

C'est un champ en plein développement dans la communauté scientifique, et peu démocratisé dans l'industrie. Il reste encore pleins d'avantages à découvrir.

Les systèmes multi-agents réactifs

La capacité réflexive d'un agent peut se placer sur un spectre dont la première extrémité est constituée des agents cognitifs, capable de raisonnements complexes, anticipation, apprentissage et prédiction (on les aborderas dans un article futur). L'autre extrémité est constituée des agents réactifs, qui décident de leurs actions en suivant des règles simples de type stimulus-réponse.

Craig Reynolds : Boids (Simulated flocking)

Par exemples, dans la simulation du comportement de nuée (les fameux boids), chaque agent suit 3 règles prédéfinies : séparation, alignement et cohésion. Ces 3 règles font émerger un comportement social complexe, la nuée.

Dans un SMA réactif, les agents ont une représentation limitée de leur environnement et des autres agents. Ils réagissent simplement aux changements qu'ils perçoivent. C'est de leurs interactions qu'émerge un comportement collectif intelligent permettant la résolution du problème.

L'avantage des agents réactifs est leur simplicité et leur robustesse. Ils sont peu coûteux en ressources et s'adaptent facilement aux changements de l'environnement. Leur inconvénient est le manque de capacités cognitives évoluées comme l'apprentissage ou l'anticipation.

La méthode "eco problem solving"

Pour appliquer la méthode eco solving, il faut redéfinir un problème pour que sa solution soit l'état de stabilité d'un système multi agent. Les agents du système sont réactifs et définis avec les 4 états suivants :

Satisfait : Un agent est satisfait lorsqu'il a atteint son but personnel, il ne fait alors rien

Recherche de satisfaction : Lorsqu'il est insatisfait, effectue une action qui l'approche de son but. Si un autre agent bloque cette action, alors on l'attaque

Fuite : L'agent s'est fait récemment attaqué, il ne poursuit plus son but. Il sortira de l'état de fuite après un temps d'attente

Recherche de fuite : L'agent se fait activement attaquer, il effectue l'action qui l'éloigne de son attaquant

À l'état initiale, les agents sont insatisfait et vont tous se diriger vers leur satisfaction. Les agents interagissent en s'attaquant et se fuyant. Le système va converger vers un état de stabilité où tous ses agents sont satisfaits. Si le problème a été correctement formulé, cet état de stabilité sera la solution recherchée.

Cette approche permet de trouver des solutions originales et efficaces à des problèmes complexes. Elle nécessite cependant de bien définir les règles de décision des agents pour les faire converger vers une bonne solution, et éviter les boucles.

Illustration

Dans cette illustration, l'environnement est une série de cellules, un agent occupe une cellule de l'environnement, et il est satisfait lorsqu'il est dans la cellule qui lui est attribuée. Lorsqu'un agent est insatisfait, il se déplacent sur une cellule adjacente à celle qu'il occupe. Lorsqu'un agent est en fuite, il se déplace pour s'éloigner de l'agent qui l'attaque.

Dans cet situation initiale, l'agent bleu est satisfait car il occupe la cellule qui lui est attribuée. L'agent rouge est insatisfait car il n'occupe pas la cellule qui lui est attribuée.

L'agent rouge attaque l'agent bleu, car il bloque l'action qui le rapproche de la satisfaction. L'agent bleu est maintenant en état de fuite, il effectue l'action qui l'éloigne de son attaquant. L'agent bleu ne sortira de son état de fuite qu'après un certain temps.

L'agent bleu a continué à fuir. Ici il a fuit vers le bas, mais il aurait pu fuir vers la droite, dans quel cas, il aurait été bloqué sur la cellule de satisfaction de l'agent rouge. Lorsqu'il serait sorti de son état de fuite, il aurait attaqué l'agent rouge, qui serait devenu à son tour l'agent fuyant.

L'agent rouge, n'a plus besoin d'attaquer l'agent bleu et peut atteindre son état de satisfaction. Lorsque l'agent bleu sortira de son état de fuite, il aura le champ libre pour rejoindre son état de satisfaction. Dans quel cas, tous les agents seront satisfait, le système stabilisé.

Exemple d'application : Agencement 3D

Dans cet exemple, l'objectif est d'organiser des boites dans le plus petit espace possible :

Dans la résolution de ce problème, l'algorithmie se limite à la simulation du comportement des agents. Ceux-ci doivent être défini correctement pour obtenir un système qui converge vers sa stabilité.

Boite

Les boites sont disposées en ligne à l'initialisation du problème

Une boite est tout le temps satisfaite

Une boite fuie quand elle est attaquée

Fuite dans la direction où il y a le plus de place

A une liste d'action taboue qui l'empêche de répéter plusieurs fois la même action

Quand n'a nulle part où fuir, attaque les autres boites autours d'elle

Contenant

Le contenant est créé suffisamment grand pour contenir toutes les boites disposées en ligne.

Il est satisfait lorsqu'il atteint sa taille objectif

Il réduit sa taille lorsqu'il est insatisfait

Il attaque les boites lorsqu'elles l'empêche de réduire sa taille

Dans cet exemple, on observe le comportement du contenant, qui cherche sa satisfaction (atteindre la plus petite taille possible). Les boites se font attaquer lorsqu'elles bloquent la satisfaction du contenant, et se déplacent pour lui laisser place. Finalement, le comportement émergeant de ce système multi agent, est l'auto organisation des paquets dans le plus petit espace possible.

Conclusion

Dans cet article, on a exploré les systèmes multi agents réactifs, qui sont une petite partie du domaine. Dans des articles futurs, nous pourrons explorer l'implémentation des simulations de systèmes multi agents et les agents cognitifs.