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 :

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.

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 :

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.

Classification des agents

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

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.

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.

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.

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

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

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...