Araignées sociales et analyse d'images

==> Page principale Vincent THOMAS

Araignees Sociales

Parmi les 30.000 espèces d'araignées, il existe environ 30 espèces sociales (comme Anolesimus eximius). Les araignées de ces espèces vivent au sein de colonies pouvant réunir jusqu'à 5000 individus. Ensemble, alors qu'elles ne mesurent que quelques millimetres, elles parviennent à produire de gigantesques structures soyeuses pouvant atteindre 100 m3. Afin de comprendre la spécificité des comportements des araignées sociales, un modèle censé rendre compte de l'apparition du travail collaboratif de construction a été proposé suite à une collaboration entre l'équipe MAIA et l'équipe du professur B. Krafft.

une toile d'Anolesimius Eximius photo@B. Krafft

Les résultats de cette collaborations sont présentés dans cette page qui décrit

• le modèle et les hypothèses censés rendre compte de ce phenomène
• l'application de ce modèle pour la résolution distribuée de problèmes posés en informatique.

Modele

Objectif du modèle

L'équipe d'éthologues dirigée par le professeur Krafft souhaitait valider l'hypothèses selon laquelle un mécanisme relativement simple : la stigmergie pouvait expliquer le phénomène collectif.

La notion de stigmergie a été introduite par Grassé en 1959 [grasse] et peut être formulée par l'expression : "le travail guide l'ouvrier". Au cours de leur cycle de vie, les individus déposent des fils de soie au sein de l'environnement et construisent une structure soyeuse. En retour, ces fils modifient les comportements des araignées qui les perçoivent. Les fils disposés dans l'environnement permettent alors aux araignées de s'échanger de manière implicite de l'information sur l'avancement de leur activité collective. Il est alors possible d'observer l'apparition d'un phènomène collectif sans que des communications directes entre individus ne soient necessaires.

L'autre enjeu de la simulation consistait à determiner si la seule tolerance interindividuelle, absente chez les araignées solitaires, permettait de passer d'un comportement solitaire à un comportement social pouvant expliquer la construction des structures soyeuses observées.

Simulation de phenomènes collectifs

Les systèmes multi-agents (SMA) sont particulièrement adaptés à la simulation de phénomènes biologiques collectifs. En effet, un système multi-agents permet de décrire une société à l'aide de lois comportementales locales.

Une simulation basée sur un SMA permet donc de mettre en relation des causes locales (lois comportementales contenues dans l'agent) avec des résultats globaux (observation globale d'un comportement collectif) et de répercuter comment un comportement individuel peut modifier le comportement collectif.

Proposer une telle simulation consiste alors à définir les lois comportementales (de préférence les plus simples possibles) à donner aux agents pour que le comportement collectif apparaissant à l'éxecution parviennent à produire des constructions proches de celles observées experimentalement. Dans cet exemple, il s'agissait donc de définir les lois locales qui régissent le comportement des araignées virtuelles afin de reproduire des toiles complexes resultant du travail de plusieurs individus.

Modèle proposé

Le modèle de simulation est fondé sur un système multi-agents réactif. Plusieurs individus sont déposés dans un environnement virtuel et leur comportement est régi par des régles décisionnelles stochastiques trés simples de type stimulus-reponse.

Le comportement d'une araignée virtuelle est défini par ces trois règles élémentaires.

* Dépot de soie: L'araignée virtuelle dépose des fils de soie dans son environnement en fonction d'une probabilité donnée.

* Attraction vers la soie: Les araignées virtuelles sont attirées par la soie et ont tendance à suivre un fil dèja déposé au sein de l'environnement en fonction d'une probabilité donnée et du nombre de fils de soie visibles par l'agent.

* Retour sur toile: Lorsqu'une araignée virtuelle se situe loin d'une toile, elle a une probabilité non nulle de suivre le fil qu'elle n'a pas attachée dans l'environnement pour retourner au dernier endroit où elle a déposé un fil.

Ces règles élémentaires parviennent à produire un comportement collectif coherent. La structure soyeuse reste de taille finie et d'une structure identique aux structures observées experimentalement in vivo.

Analyse d'images

L'application que nous souhaitions concevoir avait pour objectif d'extraire des régions contigues homogènes dans une image à niveau de gris. L'application prend donc en entrée une image à niveau de gris et donne en sortie un ensemble de régions. L'idée qui a guidé cette démarche était d'utiliser les toiles construites par les araignées en considérant qu'une toile correspond à une region extraite. Ainsi, une image peut être représentée par une matrice de pixels (ou un environnement 3d discrétisé, le niveau de gris correspondant à l'altitude du pixel). Dans cet environnement nous disposons des agents dont le comportement est basé sur celui des araignées de la simulation précédente. Ces araignées évoluent dans l'environnement et générent une toile. Celle-ci est censée représenter une région contigue de niveau de gris homogène.

Le comportement d'une araignée est décrit par les trois items comportementaux stochastiques suivants

• Se déplacer dans l'environnement sur une case adjacente ou en suivant un fil
• Poser un fil entre le piquet d'arrivée et le dernier piquet filé si le piquet d'arrivée correspond aux critères de selection
• Revenir sur sa toile si l'araignée s'en est trop éloignée

Demonstration

L'image présentée ici montre la construction des différentes toiles. L'objectif était d'extraire les pixels correspondants à la chevelure d'Alain. On pose dans l'environnement 5 agents (de couleur jaune, orange, bleue, verte et rouge) chacun ayant pour tache d'extraire les pixels correspondants à la chevelure d'alain. Ces agents construisent progressivement une toile de la couleur qui leur est associée. Au bout d'un certain nombre d'itérations, les toiles recouvrent entièrement la région que l'on souhaitait extraire.

Une applet de démonstration sera prochainement disponible Elle permet de charger une image et de disposer des araignées dans l'environnement.

Liens

Pages personnelles

• Vincent Chevrier et Christine Bourjot à l'origine du modele araignée et qui ont encadré mon DEA et ma thèse.
• Bertrand Krafft ethologue et professeur émerite de l'université Henri Poincaré qui a étudié Anolesimius Eximius

Vulgarisation

• Le site de vulgarisation de l'INRIA, interstice, propose un article La strategie de l'araignee. Il présente en outre une applet java permettant de tester l'importance des parametres du modele sur la construction collective de toile.

Demonstrations

• Une applet de demonstration développée en collaboration avec des etudiants de master M2 sera prochainement disponible. Cette application a été fournie dans le CD supplément du livre "auto-organisation" dont nous avons écrit un chapitre.

Articles scientifiques

Plus d'informations concernant ces travaux sont accessibles dans les articles suivants:

• l'article Mutli-agent simulation in biology : application to social spider case. (V. Chevrier et C. Bourjot., In Proc. Of Agent Based Simulation Workshop II, 2001) présente le modèle araignée et sa validation biologique
• mon mémoire de DEA présente une étude comparative des résultats des algorithmes araignées appliques au traitement d'images
• l'article de WIAS présente une vision globale de la transposition du modèle araignee au traitement d'image

References

• [grasse] La reconstruction du nid et les coordinations inter-individuelles chez Bellicosi- termes natalensis et Cubitermes sp. La theorie de la stigmergie: Essai d’interpretation des termites constructeurs. Cet article de référence presente le concept de stigmergie