Blog ENI : Toute la veille numérique !
💥 Un livre PAPIER acheté
= La version EN LIGNE offerte pendant 1 an !
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
  1. Livres et vidéos
  2. L'Intelligence Artificielle pour les développeurs
  3. Systèmes multi
Extrait - L'Intelligence Artificielle pour les développeurs Concepts et implémentations en C# (2e édition)
Extraits du livre
L'Intelligence Artificielle pour les développeurs Concepts et implémentations en C# (2e édition) Revenir à la page d'achat du livre

Systèmes multi-agents

Présentation du chapitre

Ce chapitre présente les systèmes multi-agents, qui permettent de répondre à une grande variété de problématiques. Dans ces systèmes, plusieurs agents, aux comportements individuels simples, vont travailler de concert pour résoudre des problèmes beaucoup plus complexes.

Ces algorithmes sont inspirés des observations faites en biologie (et plus particulièrement en éthologie). Des colonies d’insectes arrivent à résoudre des problèmes complexes (comme créer une termitière) alors que chaque insecte n’a individuellement pas de grandes capacités. Ce chapitre commence donc par présenter les principales caractéristiques de ces insectes sociaux.

Les caractéristiques minimales d’un système pour qu’il puisse être considéré comme étant multi-agents sont ensuite présentées, ainsi que les différentes catégories d’agents.

Certains algorithmes sont particuliers et sont un champ d’études à eux seuls. Le chapitre continue donc par la présentation de ceux-ci : algorithmes de meutes, colonies de fourmis, systèmes immunitaires artificiels et automates cellulaires.

Plusieurs exemples d’implémentations en C# sont aussi proposés. Enfin, ce chapitre se termine par une synthèse....

Origine biologique

Les insectes ont intéressé les chercheurs en biologie et éthologie (l’étude des comportements) depuis longtemps. Même si tous leurs comportements sociaux ne sont pas encore connus, les grands principes ont été mis à jour.

La majorité de ceux-ci (environ 90 % des espèces) sont solitaires. Chaque insecte vit de son côté, avec peu voire pas de liens avec ses voisins. C’est le cas par exemple de la majorité des araignées, des moustiques, des mouches… Les contacts se limitent à la recherche de nourriture (par exemple pour les mouches), aux zones de vie (comme les larves de moustiques présentes en grand nombre dans les eaux stagnantes) ou aux périodes de reproduction.

Il existe aussi des insectes sociaux, allant de sociétés très simples à des sociétés très complexes et très organisées. Ceux présentant la plus grande organisation sont dits insectes eusociaux. Ils présentent les caractéristiques suivantes :

  • La population est divisée en castes, chaque caste ayant un rôle précis.

  • La reproduction est limitée à une caste particulière.

  • Les larves et les jeunes sont élevés ensemble au sein de la colonie.

Les insectes eusociaux ne représentent que 2 % des espèces existantes, mais en masse, ils représentent 75 % de l’ensemble des insectes ! Cela prouve que ces sociétés permettent de faire vivre de très nombreux individus.

Les trois espèces eusociales les plus connues sont les abeilles, les termites et les fourmis.

1. Les abeilles et la danse

La majorité des espèces d’abeilles sont solitaires. Cependant, l’espèce Apis Mellifera (l’abeille des ruches qui produit le miel) est une espèce eusociale.

Chaque ruche est une société complète. On y retrouve une reine, chargée de pondre les œufs (elle est fertilisée avant de fonder sa colonie et vit jusqu’à quatre ans), des ouvrières (femelles stériles) et quelques mâles (appelés faux-bourdons) qui ne servent qu’à s’accoupler avec les futures reines. Ils meurent d’ailleurs juste après la reproduction.

Les ouvrières vont avoir différents rôles : le soin au couvain (là où se trouvent les larves), l’entretien de la ruche, la recherche de nourriture, la récolte de celle-ci, la défense de la ruche...

Le phénomène...

Systèmes multi-agents

Toutes les techniques classées comme systèmes multi-agents ont pour but de mettre en œuvre cette intelligence sociale, qui est appelée en informatique intelligence distribuée. Pour cela, on retrouve :

  • un environnement,

  • des objets fixes ou non, étant des obstacles ou des points d’intérêt,

  • des agents, aux comportements simples.

Le but de l’algorithme n’est jamais réellement codé, la solution va émerger de l’interaction de tous ces éléments entre eux.

1. L’environnement

Les objets et les agents se trouvent dans un environnement. Celui-ci peut être plus ou moins complexe : il peut s’agir d’un espace délimité (comme un hangar ou une forêt), d’un graphe, ou même d’un espace purement virtuel.

L’environnement correspond donc principalement au problème que l’on cherche à résoudre.

Cet environnement doit pouvoir évoluer au cours du temps : les agents peuvent s’y déplacer, ou les objets être modifiés.

2. Les objets

L’environnement possède des objets avec lesquels les agents peuvent interagir. Ceux-ci peuvent correspondre à des sources de nourriture, des briques de construction, des villes à visiter, des obstacles…

Rien n’impose que ces objets soient ou non transportables, qu’ils...

Classification des agents

Les agents peuvent être de types très différents, en fonction de certaines caractéristiques.

1. Perception du monde

La première différence se situe sur la perception du monde qu’auront les agents. Ils peuvent avoir une vue d’ensemble de tout le monde (perception totale), ou seulement de ce qui se trouve dans leur voisinage (perception localisée). De plus, ils peuvent avoir une vision symbolique, ou seulement celle issue de la perception.

Par exemple, si on prend des robots qui se déplacent dans un étage d’immeuble, ils peuvent ne connaître que ce qu’ils voient (la pièce qui les entoure, une perception localisée) ou avoir une carte préenregistrée de tout l’étage avec leur position dessus (par exemple via un GPS, une perception totale).

De plus, lorsqu’ils ont une caméra, ils peuvent avoir, dans le cas d’une vision symbolique, des algorithmes de reconnaissance d’images leur permettant de reconnaître certains objets (loquets des portes, boutons, cibles...) ou, dans le cas d’une vision issue de la perception, devoir agir en fonction des images brutes (telles qu’elles sont obtenues par la caméra).

Les chercheurs en systèmes multi-agents ont une préférence pour des perceptions localisées, et ils sont très partagés entre une approche symbolique et une approche purement basée sur les perceptions.

2. Prise des décisions

Les agents doivent choisir quoi faire à tout moment. Ils peuvent avoir un plan déterminé d’avance, ce qui est rarement conseillé, ou agir...

Principaux algorithmes

Il existe quelques algorithmes particuliers plus connus que les autres, et présentant des environnements, objets et agents définis. Quatre sont ici présentés : les algorithmes de meutes, l’optimisation par colonies de fourmis, les systèmes immunitaires artificiels et les automates cellulaires.

Dans le chapitre sur les métaheuristiques, l’algorithme d’optimisation par essaims particulaires alors présenté pouvait déjà être vu comme un système multi-agents dans lequel chaque solution a une vue globale de toutes les autres solutions et une mémoire (la meilleure solution trouvée jusqu’alors). Ils se déplacent dans l’espace de solution qui sert d’environnement. Il n’y a pas d’objets. Cependant, cette technique est éloignée de la notion d’agents réactifs.

1. Algorithmes de meutes

À partir de quelques règles simples, il est possible de simuler des comportements de meutes ou de groupes. Craig Reynolds crée ainsi en 1986 les boids, des créatures artificielles évoluant en groupe.

Pour cela, les créatures ont trois comportements, liés à la présence d’autres individus dans leur proximité :

  • Un individu très proche va provoquer un comportement d’évitement (pour éviter de rentrer dans un autre individu) : c’est le comportement de séparation.

  • Un individu proche modifie la direction de la créature, celle-ci ayant tendance à s’aligner sur la direction de son voisin : c’est le comportement d’alignement.

  • Un individu à distance moyenne va provoquer un rapprochement. En effet, si une créature en voit une autre, elle ira vers elle : c’est le comportement de cohésion.

Il est aussi possible d’ajouter un "angle mort" à l’arrière du boid simulant le fait qu’il ne peut pas voir derrière lui.

images/06DP01.png

En fonction des paramètres, en particulier le choix des distances, on peut observer des individus complètement isolés ou au contraire des individus se déplaçant en meutes et pouvant se retrouver après un obstacle, à la manière des bancs de poissons ou des nuées d’oiseaux ou d’insectes.

On observe donc bien une structure émergente à partir de quelques règles très simples. De plus, les trajectoires semblent aléatoires : en réalité l’ensemble est devenu un système complexe, bien que complètement déterministe, qui fait que la moindre modification de l’espace ou du placement initial amène à des mouvements très différents.

On peut alors se servir de ces boids pour représenter...

Domaines d’application

Les domaines d’application des systèmes multi-agents sont très nombreux, cela grâce à la diversité des algorithmes.

1. Simulation de foules

La première utilisation est la simulation de foules. De nombreux logiciels utilisent des agents pour simuler des personnes se déplaçant dans un lieu, permettant ainsi de comprendre les réactions en cas d’évacuation, et découvrir les zones de bousculades potentielles.

On retrouve aussi cette simulation dans le domaine du trafic routier, pour comprendre et simuler les modifications induites par des changements comme l’ajout de feux, ou la réduction de la vitesse sur certaines portions.

Il est aussi possible de simuler des troupes, que ce soient des guerriers, des joueurs, des animaux... Ces simulations sont très utilisées dans le monde du loisir, car elles permettent d’obtenir des animations à faible coût.

Ainsi, le logiciel MASSIVE, un des leaders du marché, a servi à créer de nombreuses publicités (comme pour Adidas, Coca Cola, Pepsi...) et surtout de nombreux films, pour simuler les grands mouvements de foule (et limiter les coûts en figurants). Le logiciel a ainsi été utilisé dans les films suivants (entre autres) : La planète des singes, l’affrontement (2014), World War Z (2013), Godzilla (2014), Pompei (2014)...

Implémentation

Plusieurs exemples sont ici implémentés. Par leur fonctionnement, ces algorithmes sont principalement graphiques, aussi les codes présentés ici, s’ils sont génériques pour les classes de base, sont des applications WPF pour Windows.

Lors de la création de tels projets avec Visual Studio, des fichiers App.config, App.xaml et App.xaml.cs sont créés. Ceux-ci ne sont pas modifiés. Par contre, les fichiers MainWindows.xaml et MainWindows.xaml.cs sont, eux, modifiés et le code est fourni.

Le modèle MVVM est volontairement non respecté, pour garder le code plus léger, et simplifier sa compréhension.

1. Banc de poissons

La première application est une simulation d’un banc de poissons, inspirée des boids de Reynolds, en deux dimensions.

Nous allons donc voir un ensemble de poissons, représentés sous la forme de traits, se déplacer dans un océan virtuel et éviter des zones dangereuses à l’intérieur de celui-ci (cela peut représenter des obstacles physiques ou des zones présentant des prédateurs).

Le comportement du banc sera donc uniquement obtenu par émergence.

a. Les objets du monde et les zones à éviter

Avant de coder les agents eux-mêmes, nous allons coder une première classe qui peut être utilisée à la fois pour les objets et les agents. Celle-ci, nommée ObjectInWorld, présente deux attributs PosX et PosY indiquant les coordonnées de l’objet. Il s’agit de champs publics pour optimiser les accès à ceux-ci. En effet, il y aura de nombreux accès et l’appel d’une méthode (avec la création de son contexte) serait une perte de temps notable.

La base de notre classe est donc la suivante. On a créé deux constructeurs, un par défaut et un initialisant les deux attributs.


using System; 
  
public class ObjectInWorld 
{ 
    public double PosX; 
  
    public double PosY; 
  
    public ObjectInWorld() {} 
  
    public ObjectInWorld(double _x, double _y) 
    { 
           PosX = _x; 
           PosY = _y; 
    } 
}
 

On ajoute une méthode permettant de calculer la distance entre l’objet et un autre objet de l’environnement.


   public double DistanceTo(ObjectInWorld _object) 
   { 
          return Math.Sqrt((_object.PosX - PosX) * (_object.PosX - 
PosX) + (_object.PosY - PosY) * (_object.PosY - PosY)); 
   }
 

Cette distance est souvent demandée, et elle fait appel à une racine...

Synthèse

Les systèmes multi-agents permettent de résoudre un grand nombre de problèmes, à la fois dans la simulation de foules, dans la planification et la recherche de chemins et dans la simulation de problèmes complexes, pour mieux les comprendre et les étudier.

Ils reposent tous sur les observations faites sur les insectes eusociaux, qui sont capables de résoudre des tâches très complexes à partir de règles très simples. C’est par émergence que la solution apparaît, et non par un plan préprogrammé. Les abeilles trouvent de nouvelles sources de nourriture, les fourmis communiquent par phéromones pour optimiser les accès à la nourriture et les termites construisent d’énormes termitières climatisées.

En informatique, les systèmes multi-agents contiennent donc un environnement dans lequel se trouvent des objets et des agents. Il n’y a que très peu de règles à suivre sur ceux-ci, et chaque problème pourra donc avoir une ou plusieurs modélisations possibles.

Il existe cependant quelques algorithmes plus connus parmi les systèmes multi-agents. On peut citer les algorithmes simulant les comportements de meutes basés sur les boids, l’optimisation par colonies de fourmis et ses phéromones artificielles, les systèmes immunitaires...