Tri du couvain avec Kedama
From OFSET Wiki
Exemple réalisé par Renaud Delcoigne et Frédérick Zann dans le cadre d'un projet d'étude en Intelligence Artificielle Distribuée en 1ère année de Master Informatique à l'Université de Caen.
Contents |
[edit] Introduction
Il a été observé par expérience que les fourmis trient spontanément les oeufs selon leur stade de développement. Ce projet vise à simuler le comportement d'un ensemble de fourmis ouvrières suite à un désordre du couvain d'une fourmilière.
Sur cette image on peut voir la formation de 2 tas distincts d'oeufs triés selon leur maturité.
[edit] Modélisation
Le KedamaWorld représente la fourmilière où sont dispersés les oeufs et où les fourmis se baladent. La simulation est donc constituée de 2 ensembles d'agents les fourmis et les oeufs (de 2 types, rouges et bleus, correspondant à 2 maturités d'oeuf différentes) Les oeufs sont des agents immobiles, qui diffusent des phéromones sur un patch (propre à leur couleur) et attendent d'être portés et déposés par les fourmis. Les fourmis sont les agents réactifs du problème, elle se déplacent aléatoirement sur la fourmilière (le KedamaWorld) et réagit à 2 règles simples:
- Si une fourmi rencontre un oeuf, qu'elle n'en porte pas et que le nombre d'oeufs est localement faible (et donc le taux de phéromones aussi), la fourmi aura tendance à le ramasser, sinon elle continue son chemin.
- Si une fourmi transporte un oeuf et que le nombre d'oeufs est localement élevé (et donc le taux de phéromones aussi), la fourmi aura tendance à poser l'oeuf, sinon elle continue son chemin.
Ces 2 règles simples permettent à un ensemble de fourmis de regrouper facilement et rapidement des ensembles d'oeufs, sans qu'il y ai de communications entre ces fourmis.
[edit] Conception
[edit] Les oeufs
On a définit 2 catégories d'oeufs, représentés dans Kedama par des points rouges et bleus. Les oeufs sont des agents inertes, leur seule fonction étant de diffuser des phéromones sur un patch spécifique à leur type, et de signaler leur présence sur un second patch pour que les fourmis puissent les détecter et signaler la prise d'un oeuf par l'écriture d'une valeur spécifique sur l'emplacement de l'oeuf. Les oeufs ne possèdent qu'un seul script.
- Si l'oeuf est dans l'état pris (transporté par une fourmi)
- Si la fourmi a trouvé un emplacement adéquat
- l'oeuf se déplace aux positions de la fourmi
- Si la fourmi a trouvé un emplacement adéquat
- Sinon
- l'oeuf libère des phéromones
- Si l'oeuf vient d'être pris par une fourmi
- l'oeuf s'efface de son patch
- l'oeuf devient invisible
- l'oeuf passe dans un état pris
- Sinon
- l'oeuf se signale sur son patch
On peut remarquer qu'à aucun moment l'oeuf "suit" une fourmi, lorsqu'un oeuf est embarqué par une fourmi il devient invisible et attends que la fourmi qui le transporte ai trouvé un endroit pour le poser, c'est alors que l'oeuf se téléporte à l'emplacement de la fourmi et redevient visible.
[edit] Les fourmis
Les fourmis sont les agents principaux de ce projet Kedama, dans lequel on reproduit un comportement complexe à partir d'agents peu évolués qui agissent à partir de réflexes élémentaires.
La première fonction d'une fourmi est de parcourir aléatoirement le monde torique à la recherche des oeufs n'appartenant pas à un tas. Une fois un oeuf trouvé, celle ci décide ou non de le ramasser dans le but de le déposer dans un groupe d'oeufs plus important.
Le choix de ramasser ou non et déposer ou non un oeuf se fait sur 2 critères:
- La concentration locale en phéromone
- Le libre arbitre d'une fourmi ( tirage d'un nombre aléatoire )
Les tortues "fourmi" on 2 variables principales:
- L'entier fourmi.oeuf qui détermine si la fourmi est en train de porter un oeuf ( valeur 0 si aucun, 1 si l'oeuf est bleu, 2 si l'oeuf est rouge )
- Le booléen fourmi.deposOeuf qui a pour valeur "vrai" quand la fourmi à trouvé un emplacement où poser l'oeuf. La fourmi passe alors dans un état d'attente que l'oeuf se dépose.
[edit] Script principal de la fourmi
- Si la fourmi a trouvé un emplacement pour l'oeuf qu'elle transporte
- déposer l'oeuf
- Sinon
- la fourmi se déplace
- Si la fourmi a un oeuf
- cherche un emplacement pour cet oeuf
- Sinon
- Vérifier l'existence d'un oeuf sur la case courante
[edit] Script de la prise d'oeuf
- Si la fourmi ne transporte pas d'oeuf
- création d'un nombre aléatoire
- Si la fourmi détecte un oeuf bleu à sa position
- Si la fourmi décide de prendre l'oeuf
- Incrémentation du nombre d'oeufs bleus transportés
- Prendre la couleur de l'oeuf
- Signaler l'oeuf qu'il est pris par l'intermédiaire du patch
- Faire demi tour
- Si la fourmi décide de prendre l'oeuf
- Si la fourmi détecte un oeuf rouge à sa position
- Idem
[edit] Script de recherche d'un emplacement pour l'oeuf
- Si la fourmi possède un oeuf
- création d'un nombre aléatoire
- Si cet oeuf est bleu
- Si la fourmi décide de déposer l'oeuf
- Si la fourmi n'est pas sur une case déjà occupée par un oeuf
- La fourmi a trouvé un emplacement pour l'oeuf, passer en état de dépôt d'oeuf
- Si la fourmi n'est pas sur une case déjà occupée par un oeuf
- Si la fourmi décide de déposer l'oeuf
- Sinon ( l'oeuf est rouge )
- idem
[edit] Script du dépot d'oeuf
- Si la fourmi transporte un oeuf bleu
- Si un oeuf bleu se trouve sur l'emplacement de la fourmi ( l'oeuf bleu a bien été posé )
- Reprendre une couleur noire
- Se retourner
- Avancer
- Sinon
- Signaler à l'oeuf de se poser à l'emplacement de la fourmi
- Si un oeuf bleu se trouve sur l'emplacement de la fourmi ( l'oeuf bleu a bien été posé )
- Sinon ( l'oeuf est rouge)
- Idem
[edit] Variable de seuil
La variable de seuil permet de modifier le taux de phéromones par rapport au taux max, indiquant si une zone est dans un tas ou non. Les oeufs se trouvant dans un emplacement dont le taux de phéromone par rapport au taux max relevé est supérieur à ce seuil sont donc dans un tas et la probabilité qu'ils soient pris par une fourmi est (linéairement) plus faible. Ceci conduit à régler la densité en phéromone (et donc en oeuf) des tas, un taux faible va permettre d'aboutir à des tas à densité faible, un taux élevé à des tas denses.
[edit] Analyse et conclusion
On observe que chaque fourmi se déplace bien avec un oeuf sur le dos, et les regroupent par tas de plus en plus gros, certains tas fusionnent, d'autres disparaissent. Finalement et rapidement, alors qu'un agent n'obéit qu'à des règles très simples, un seul tas par type d'oeuf apparaît, les oeufs sont triés, ce qui conduit à un état stable.
Même si la simulation de l'espèce animale fourmi n'est pas totalement exacte car simplifiée ( aléatoire de déplacement, nombre de types d'oeuf, monde torique, ... ) elle reproduit bien ce qui se produit lorsqu'on éparpille les oeufs de fourmis d'un couvain. C'est donc une réussite et un bon exemple de ce que le parallélisme peut apporter.
[edit] Téléchargement et infos
Ce projet a été réalisé à l'aide de l'article de Michel Casabianca http://www.sdv.fr/pages/casa/html/couvain.html
