Biomimétisme : algorithme de toile d'araignée

Le biomimétisme est une pratique scientifique consistant à imiter, ou à s'inspirer de systèmes naturels, ou vivants. Parmi les exemples de ce domaine, on retrouve entre autres : formes de poissons pour l'aérodynamisme de voitures, ou autres véhicules, transfert de fluides par capillarité comme dans les végétaux, ou encore l'algorithme de colonies de fourmis pour la recherche du plus court chemin dans un graphe.

Ce que je vous propose aujourd'hui, c'est un petit algorithme maison, implémenté en Ruby, pour simuler la localisation d'une proie dans une toile d'araignée.

La nature :

Les araignées se divisent en de très nombreuses espèces qui ont différentes approches pour la chasse, et notamment l'utilisation de leur toile (certaines n'en tissent d'ailleurs pas...). Pas mal d'espèces utilisent leur toile afin de piéger leurs proies. Certaines sont averties que "quelque chose" est dans leur toile de la manière suivante : une fois la toile tissée, l'araignée tisse un ou plusieurs fils entre la toile et sa cachette, et est avertie par les vibrations de ce(s) fil(s) de "liaison".

Le modèle :

Imaginons qu'une araignée possède une très grande toile. Un seul fil de liaison serait probablement insuffisant car même en étant prévenue de la présence d'une proie, elle devrait ensuite la rechercher, "au hasard", dans sa toile. Bien. Prenons la même araignée, mais ayant créé un fil de liaison avec chacun des fils principaux de sa toile. En prenant la suite des fils touchés par sa proie, elle peut en déduire étape par étape sa localisation. C'est ce que ce propose de faire cet algorithme.

L'algorithme :

L'algorithme proposé peut être qualifié de naïf. On considère que l'espace (plan de fait) est décomposé en différentes zones par les fils de la toile. Un fil touché correspond à un signal.

1. Début
2. "zones précédentes" = toute la toile
3. Pour chaque signal
   

• "zones signalées" = zones voisines du fil touché
• "zones potentiellement occupées" = "zones signalées" accessibles depuis "zones précédentes" via le fil touché
  
• "zones précédentes" = "zones potentiellement occupées"
• Fin

Pour une présentation plus "visuelle", j'ai fait un petit slide disponible ici au format pps (je voulais tester SlideShare, mais le site s'entête à rejeter mes slides... dommage...).

Le code :

Le code Ruby de cet algo est disponible sur Pastie.

zone.rb décrit la classe des zones entre les fils (yarns en anglais), et spiderweb.rb la classe de la toile d'araignée, contenant la méthode run_analysis implémentant l'algorithme proposé ci-dessus.
runtest.rb est un cas test on ne peut plus simple de l'algo : c'est le cas illustré dans mon petit slide.
pentacle.rb est un cas-test de toile en forme de pentacle.

realisticweb.rb permet de construire des toiles de forme "réaliste" : cercles concentriques et rayons (diamètres de fait dans mon code - ajout à la classe Spiderweb).
realweb_test.rb est un cas test associé.

Discussion :

L'efficacité de l'algorithme dépend fortement de la forme de la toile. Ce problème doit très probablement être formulable sous forme de problème de graphe, ou problème entier (cherchons son dual ^^). Selon la forme de la toile, il est possible que l'algo ne puisse pas déterminer une zone unique contenant la proie, même si le nombre de signaux tend vers l'infini.

Utilité ?

Éventuellement pour un système de sécurité (comme dans les films à gros budget... les fils de la toiles deviennent alors des "lasers"...). Plus probablement de la localisation pour une petite intelligence artificielle. Ou même la recherche d'une "localisation abstraite" sur un réseau quelconque (ne me demandez pas pourquoi, je pense à FaceBook là : fils = liens friends, signaux = utilisation du fil par une appli FB, zones = ?).

Remarques / Questions ?

N'hésitez pas : il serait incroyable que j'ai été suffisamment clair ou précis !