[English]
|
Comment les fourmis trouvent de la nourriture
Beaucoup d'espès de fourmis communiquent avec leurs congénères en utilisant des odeurs chimiques comme les phéromones. Les phéromones peuvent être utilisées de bien des manières par les fourmis et les autres animaux (dont les humains), mais nous nous interesserons ici à la façon dont les fourmis les utilisent pour diriger chaque autre dans l'environement---ce problème est proche de celui de diriger un flot d'information dans un réseau.Considérons une colonie de fourmis. L'observation rapide de cette dernière nous apprend que les fourmis marchent généralement en ligne droite entre leur fourmilière et leur source de nourriture. Le concept d'une "armée" de fourmis est entré dans la culture populaire, et la plupart des gens vivant dans des endroits favorables au fourmis (presque tous les endroits favorables aux humains sur la terre) ont pu observer ce phénomène. Marcher en ligne droite, qui est généralement le chemin le plus court, semble une solution évidente au problème de transport de nourriture efficace, et nous pourrions n'y trouver aucun interêt.
Photo by Harold Thimbleby --- used without permission
Bien sûr, nous ferions la même chose. Quand nous regardons une file de fourmis à nos pieds, nous pourrions simplement penser "et alors ?". Mais nous avons des cerveaux énormes en comparaison des fourmis, avec un systême de vision extraordinairement complexe (plus de 25% du cevrveau humain est consacré à la vision), et nous avons une vue du terrain plus élevée. Malgré ces avantages, il n'est pas tout le temps évident pour nous de trouver la route la plus efficace, surtout dans un environnement avec beaucoup d'obstacle. Prenons les fourmis et leur cerveau simple, on ne peut considérer leur découverte de route collective comme triviale... Alors comment font-elles ?
Supposons qu'une colonie n'ait aucune information sur l'emplacement de nourriture dans leur environnement. La stratégie des humains serait d'envoyer une "équipe de secours" pour ratisser les environs---les "scouts" qui trouvent la nourriture peuvent en rapporter au quartier général, et informer les autres du lieu où elle se trouve. Les fourmis cherchent la nourriture en marchant au hasard, ce qui est similaire à notre approche "ratissage", mais deux problêmes les empêchent d'appliquer directement la technique des "équipes de secours". Tout d'abord, comment les "fourmis-scouts", une fois la nourriture découverte, retrouvent la route du nid ? Ensuite, même si la fourmi retrouve le chemin du nid, comment peut-elle informer les autres fourmis de l'emplacement de la nourriture ? Les réponses résident dans un usage intelligent des phéromones.
Pour résoudre le problème de localisation de nid, les fourmis laissent derrière elles un trace de phéromones quand elles recherchent de la nourriture. Dans l'image suivante, les pistes laissées par les fourmis errantes sont matérialisées en rouge.
Quand une fourmi trouve de la nourriture, elle peut suivre sa propre trace de phéromones jusqu'au nid---un peu comme si on avait semé des miettes de pains dans les bois pour retrouver le chemin de la maison. Sur le chemin du retour, la fourmi résoud le deuxième problème, en redéposant des phéromones, créant ainsi une piste avec une odeur plus forte. Sur l'image suivante, la fourmi A atteint en première la nourriture, et revient au nid par son propre chemin, pendant que les deux autres continuent à errer.
Quand les autres fourmis tombent sur une trace de phéromones, elles abandonnent leurs recherches, et se mettent à suivre la piste. Sur l'image suivante, la fourmi D découvre la "double trace" laissée par la fourmi A, et commence à la suivre. La fourmi C rencontre la "trace simple" laissée par D et la suit cette piste, qui mène finalement à la piste A. La fourmi B finit par trouver une route jusqu'à la nourriture, qui est complétement différente de celle tracée par la fourmi A.
Si une fourmi revient bredouille au nid, elle fait demi-tour, et suit la trace dans l'autre direction. Quand une fourmi atteint la nourriture, elle en prend, puis fait demi-tour,et suit le chemin inverse jusqu'au nid. Sur le retour, elle renforce la trace, en laissant une couche supplémentaire de phéromone. Dans l'image suivante, la fourmi C rejoint la trace de A, mais la suit dans la mauvaise direction, revenant au nid bredouille. La fourmi B suit sa propre route jusqu'au nid---elle ne croise jamais la route que les autres utilisent. Les fourmis A et D ramènent de la nourriture le long de la route établie.
Nous avons expliqué comment les fourmis trouvent la nourriture, mais pas encore comment elles trouvent le chemin le plus court qui y mène. Un détail aide à répondre à la question. Le chemin le plus court est parcouru plus rapidement par les fourmis qui l'arpentent. Par exemple, si deux fourmis X et Y parcourent respectivement un chemin de 10 mètres et 20 mètres de long, la fourmi X fera deux fois plus d'allers-retours dans le même temps. La fourmi X déposera donc deux fois plus de phéromones que la fourmi Y. Or, les autres fourmis préférent suivre le chemin le plus odorant, donc le plus court.. L'image suivante le démontre. Quand B depose sa nourriture et veut repartir pour un autre voyage, elle découvre le chemin plus odorant utilisé par les autres fourmis, et abandonne le sien. A partir de ce moment, les quatre fourmis utilisent le chemin découvert par A pour ramener la nourriture au nid.
Au fil du temps, de nombreux chemins sont créés, mais l'odeur du plus court est la plus renforcée, et il devient rapidement le chemin le plus populaire, et assez vite, toutes les fourmis l'utilisent.
Des règles simples
La manière dont les fourmis s'orientent est bien différente de celle des humains. Nous observons l'environnement dans son ensemble, et nous essayons de calculer la meilleure route. Bien entendu, la méthode des fourmis a des avantages sur notre approche "de haut niveau". Par exemple, elle marche parfaitement dans l'obscurité. S'il doit s'orienter sans repère visuel, l'être humain est en grande difficulté.La méthode des fourmis peut être résumée en quelques règles simples, suivies par chaque membre de la colonie :
| Condition: | Action: |
| Ne transporte pas de nourriture pas sur une piste de phéromone | marcher au hasard déposer des phéromones |
| Ne transporte pas de nourriture sur une piste de phéromone | suivre la piste de phéromone déposer des phéromones |
| Revient bredouille au nid sur une piste de phéromone | faire demi-tour suivre le chemin dans l'autre sens |
| Trouve de la nourriture | Prendre de la nourriture Faire demi-tour suivre le chemin dans l'autre sens |
| Transporte de la nourriture | Suivre le chemin déposer de la phéromone |
| Revient au nid avec de la nourriture | déposer la nourriture faire demi-tour suivre le chemin dans l'autre sens |
En savoir plus à propos des fourmis
Comme nous allons maintenant décrire le protocole de routage de MUTE, inspiré des colonies de fourmis, nous allons laisser le monde réel des fourmis derriè nous. Cependant, il existe des mines d'informations à propos des fourmis et de leur comportement (en anglais):Simplifions la nature
Bien que la talbe des "règles simples" ci-dessus est relativement facile à comprendre, elle contient tout de même sept règles, ce qui n'est pas aussi simple que ce que nous aimerions avoir. De plus, le comportement n'est pas optimal : un fourmi sans nourriture peut suivre le chemin dans la mauvaise direction, jusqu'au nid. Bien sûr, quand une fourmi atteint le nid, elle fait demi-tour et suit finalement la route vers la nourriture, mais elle a fait un chemin inutile. Le problème vient de l'absence de direction dans le chemin, et c'est sûr qu'il est difficile de matérialiser une direction avec des traces chimiques.Dans le monde de la programmation, nous ne sommes pas limités par des marqueurs non-directionnels. En ajoutant une direction aux marqueurs, nous obtenons un ensemble de règles plus simple.
Supposons que nous procurions aux fourmis deux types phéromones au lieu d'un seule, et que nous leur donnions une direction. Le premier type de phéromone montrerait la route vers le nid, et nous l'appellerons "phéromone de nid". Le second type de phéromone serait alors le "phéromone de nourriture", indiquant le chemin vers la source de nourriture. Quand les fourmis partent chercher de la nourriture, elles marchent au hasard, en laissant une trace de phéromone de nid. Quand une fourmi trouve de la nourriture, elle en prend un morceau, et suit sa piste de phéromone de nid, en laissant une couche de phéromone de nourriture. Si une fourmi croise une trace de phéromones nourriture, elle la suit jusqu'à la nourriture, délaissant ainsi la trace de phéromone de nid.
Cette simple modification simplifie considérablement notre ensemble de règles :
| Condition: | Trace suivie: | Marquer avec: |
| Ne porte pas de nourriture | phéromone de nourriture, ou au hasard sinon | phéromone de nid |
| Porte de la nourriture | phéromone de nid | phéromone de nourriture |
Des marques de peintures en forêt...
Ce mécanisme est similaire à celui qu'on utiliserait en peignant des flèches sur les arbres pour se repérer dans une forêt. Par exemple, une flèches bleue pourrait signigifier "vers le lac", et une flèches jaune "vers le chalet." Si vous venez du chalet et cherchez le lac, vous pouvez peindre le log du trajet des croix jaune.. En revenant du lac, vous pouvez suivre votre trace jaune, en peignant des flèches bleues aux arbres. Le point clé est que vous savez toujours comment revenir d'où vous venez, mê si vous ne savez pas comment allez où vous voulez. Si vous croisez un tronc déjà marqué, vous ajoutez une flèche, même si elle contredit une flèches déjà présente.Une fois que beaucoup de gens auront parcouru le chemin entre le chalet et le lac, il y aura beaucoup de flèches dans la forêt ---beaucoup d'arbres ayant plusieurs flèches, parfois contradictoires. Quand vous cherchez à revenir au chalet, comment interéter un tronc peint de dix flèches jaunes? Il y a plusiseurs stragégies, mais la plus simple serait de suivre la direction indiquée par la majorité des flèches, car elles indiquent probablement le chemin le plus court (rappelons que le chemin le plus court est aussi le plus fréquenté).
(Cette technique est présentée en exemple, ce c'est pas une suggestion. S'il vous plait, ne peignez pas de flèches sur les troncs en forêt...)
Comment MUTE route les messages
Dans un réseau, nous n'avons pas de fourmis, ou des promeneurs cherchant leur chemin entre un chalet et un lac. Au lieu de ça, nous avons des messages qui doivent aller d'un expéditeur à un bénéficiaire. Puisque les utilisateurs de MUTE sont anonymes, aucun noeud du réseau ne sait exactement oû trouver un bénéficiaire particulier (plus précisément quelle machine un bénéficiaire particulier utilise). Tout comme les fourmis qui n'ont pas une vue d'ensemble de l'environement, les messages MUTE ne sont dirigés dans le réseau qu'à l'aide d'indices locaux.Chaque noeud MUTE maintient des connexions àplusiseurs noeuds voisins, et ces connexions servent à relayer les messages. Suppons qu'un noeud MUTE X reçoive un message d'Alice pour Bob du noeud Y, un de ses voisins. X ne peut deviner où est Bob dans le réseau. Cependant la réception du message apprend quelquechose à X à propos d'Alice: le message venant d'Alice arrive par Y. Dans le futur, si le noeud X reçoit un message pour Alice, il pourra l'envoyer à Y en utilisant cet indice.
Sans tenir compte de ce que X append à propos d'Alice, il n'a toujours pas d'information sur Bob. La meilleure stratégie, en s'inspirant des fourmis, est d'envoyer des fourmis dans toutes les directions, ce qui revient à envoyer une copie du message à tous les voisins de X (ce que nous appelons un message "multi-diffusé"). Un des voisins peut avoir plus d'information sur la direction dans laquelle Bob se trouve. Si aucun des noeuds n'a d'information sur localisation de Bob, ils diffuseront le message à tous leurs voisins. Si Bob est bien dans le réseau, cette technique finira par payer.
Remarquons qu'avec la recherche de Bob, le message a laissé une trace d'indices vers Alice. Quand le message arrive à Bob, et que Bob renvoit sa réponse, cette dernière peut suivre ces indices sur un chemin plutôt direct jusqu'à Alice.
Quand la réponse est routée vers Alice, elle laisse une trace qui pourra être utilisée pour renvoyer des messages d'Alice à Bob. Les autres noeuds peuvent utiliser cette information aussi.. Par exemple, si le propriétaire du noeud X envoie un message é Bob, il passera par une voie plutô directe en utilisant les indices existant.
En observant ses diagrames d'exemples, on peut voir que le mécanisme de routage de MUTE ressemble à la technique des flèches dans la forêt présentée ci dessus. Chaque noeud peut être considéré comme un tronc, et chaque connexion comme un chemin entre deux arbres voisins. Chaque noeud retient un ensemble de flèches, et chaque flèche signifie quelquechose comme "Pour aller vers Bob, par là." Dans cette exemple, nous suivons les flèches bleues pour retourner vers Bob.
Nous devons garder à l'esprit que les messages d'un même noeud laissent une trace unique quand ils parcourent le réseau. Les messages d'Alice laissent la trace d'Alice, et nous pouvons suivre cette trace pour envoyer des messages à Alice. Dans les diagrammes, les flèches sombres représentent le trajet des messages, et les pâles les traces laissées par ces derniers..
Pour plus d'information sur la manière dont MUTE implémente le routage inspiré par les colonies de fourmis, aller voir la page Détails Techniques.