Conseils d’une fourmi : Ne me prenez pas trop au sérieux !

Tout observateur averti des fourmis est familier des déplacements de ces insectes le long de chemins dits de fourragement. Ces pistes chimiques, souvent longues de dizaines de mètres, relient une source de nourriture et le nid et permettent à un grand nombre d’individus de se déplacer rapidement entre ces deux endroits.

Elles sont constituées de phéromones, substance chimique sécrétée par les fourmis pour communiquer entre elles. Bien que ces pistes soient étudiées depuis de nombreuses années, jusqu’à récemment, il n’y avait aucun moyen de visualiser directement les phéromones sur les sentiers naturels des fourmis. À l’aide d’une  caméra haute vitesse et de techniques de vision assistée par ordinateur, un groupe de scientifiques, dirigé par Ofer Feinerman du Weizmann Institute of Science en Israël, a développé une nouvelle méthode permettant de détecter avec précision à quel moment et à quel endroit les fourmis sécrètent des traces odorantes.

 
Ces nouveaux outils, appliqués à la visualisation des sentiers des fourmis Paratrechina longicornis, ont permis une découverte surprenante. Les pistes établies par ces fourmis sont d’un type complètement différent de celui observé précédemment. Alors que les sentiers de fourmis classiques marquent de manière continue le trajet entre la source de nourriture et le nid, la piste nouvellement observée est locale et dynamique : seule est indiquée, sur une courte distance, la prochaine étape du chemin à suivre.

Comment justifier le caractère unique des traînées laissées par les fourmis Paratrechina longicornis ? Dans le but de comprendre les avantages que pourrait présenter ce nouveau type de piste, l’équipe de Feinerman a collaboré avec un groupe de théoriciens en informatique mené par Amos Korman du CNRS. Le choix d’une perspective algorithmique pour aborder ce problème peut surprendre. Mais avant de présenter plus en détail le fruit de cette collaboration inter-disciplinaire, il est nécessaire de présenter les conditions dans lesquelles cette étude a vu le jour.

En entrant dans son nouvel appartement, Ehud Fonio, l’un des chercheurs du Weizmann Institute impliqué dans cette étude, a remarqué que des croquettes s’échappaient mystérieusement du bol de nourriture de son chat. Lors d’une inspection plus approfondie, il est apparu que des équipes de petites fourmis coopéraient pour transporter les morceaux de nourriture vers leur nid.

 
Il est important de noter que le contexte dans lequel s’établit ce transport coopératif diffère sensiblement de celui des pistes classiques, étudiées notamment par Jean-Louis Deneubourg : dans les sentiers classiques, les fourmis portent des morceaux de nourriture entre deux points fixes (une source alimentaire et leur nid). À l’inverse, les fourmis observées par M. Fonio portaient une charge beaucoup plus grande qu’elles-mêmes et sur un chemin dont les extrémités évoluaient dans le temps.

Les chercheurs ont aussi remarqué que le transport coopératif, dans cette espèce, s’accompagne d’un chemin de phéromones particulier. La piste est formée graduellement et à mesure que l’objet avance. Ce sont des fourmis indépendantes, parmi celles ne portant pas la charge, qui déposent de courtes traces de phéromones sur les surfaces environnantes. Cela indique le chemin vers le nid. Autrement dit, les fourmis appliquent des marques de parfum dans le voisinage immédiat de la charge en mouvement pour créer ce qui peut ressembler à une courte « flèche » qui suggère une prochaine étape du mouvement collectif. À leur tour, les fourmis porteuses peuvent suivre les « flèches » afin de déplacer la charge. Cependant, un chemin convenant aux fourmis individuellement n’est pas forcément le bon pour un objet plus volumineux comme un gros insecte ou une croquette pour chat. De fait, les chercheurs ont constaté qu’il arrive que les fourmis se dirigent vers des passages suffisamment larges pour les dimensions de leur propre corps mais qui s’avèrent trop étroits pour la charge portée par le groupe. De telles situations sont monnaie courante lors de la navigation d’un gros objet à travers un territoire rempli d’obstacles.

Pour illustrer cette situation, imaginez-vous conduire une voiture dans une ville inconnue. Pour arriver à votre destination, vous utilisez une outil de guidage par satellite (GPS) et vous basez votre navigation sur ses instructions. Cependant ces instructions ne sont pas toujours bonnes. On peut imaginer par exemple un GPS mal configuré qui produit les itinéraires les plus rapides pour un piéton. La plupart des routes demeurent praticables en voiture, et ainsi la plupart des indications du GPS restent valides. Mais d’autres indications conduisent à des impasses ou à des voies étroites, impropres à la circulation en voiture.

Face à ces instructions peu fiables, que pourriez-vous faire en tant que conducteur ? Accepter systématiquement les conseils du GPS conduit à une impasse. Si, à l’inverse, vous ignorez complètement les instructions données, vous perdez toutes les informations disponibles et le trajet devient très long. Formulé ainsi, le problème auquel les fourmis font face est bien de nature algorithmique. Leur solution est la suivante : l’équipe qui transporte la charge suit le plus souvent les directions encodées dans les « flèches d’odeur » déposées par ses collègues, mais par moments, elle les ignore et s’écarte du chemin suggéré en choisissant une direction au hasard. Quelques instants plus tard, l’objet est de nouveau rattrapé par le flux de fourmis non-porteuses, qui continuent de suggérer un itinéraire au moyen de phéromones. Ce comportement partiellement aléatoire contraste avec la vision habituelle des fourmis parcourant de manière stricte leurs sentiers bien définis.

Le caractère localisé des indications et la manière non déterministe avec laquelle le groupe les suit, permettent d’ajuster le degré de dépendance du mouvement collectif aux directions proposées par les fourmis individuelles. Le groupe bénéficie de l’information utile qui est communiquée par les individus non-porteurs tout en évitant les pièges locaux qui peuvent se produire lorsque ces individus les dirigent à tort vers des impasses. Pour reprendre l’analogie du GPS, ce que le conducteur devrait faire pour atteindre rapidement sa destination est de suivre l’indication avec une probabilité fixe, disons 90%, ou sinon, choisir une direction aléatoire.

Dans le cadre d’un tel procédé, il est inutile de marquer le chemin sur toute la distance jusqu’au nid. En effet, comme le groupe a tendance à quitter rapidement les routes marquées, les fourmis n’ont rien à gagner à les prolonger. Un marquage local apparait bien plus économique et rationnel. Mystère résolu.

Modélisation mathématique

Sur le plan mathématique, l’équipe d’Amos Korman, qui comprend son doctorant Lucas Boczkowski et le chercheur Inria Adrian Kosowski, a proposé une version idéalisée du processus. Un agent, représentant le groupe déplaçant un gros objet, se déplace sur un graphe, sur lequel sont déposés des conseils à chaque nœud. Ces conseils modélisent les indications données par les fourmis sous forme de phéromones. Ils indiquent « le bon chemin » avec une certaine probabilité et une direction incorrecte autrement. Ce modèle fournit un cadre dans lequel la stratégie d’écoute aléatoire des fourmis s’exprime naturellement et peut être analysée.

La validation du modèle s’est faite au moyen d’expériences avec de vraies fourmis en comparant leur comportement aux prédictions analytiques du modèle.

Pour établir la comparaison, l’analyse théorique a été menée dans deux cas extrémaux correspondants à deux scénarios opposés d’expériences ou plus précisément à deux types d’environnement. Le premier type consiste en un terrain ouvert, le second en un terrain sur lequel ont été déposés des obstacles artificiels. Ces obstacles de forme longiligne possèdent une fente étroite par laquelle une fourmi isolée peut passer mais pas l’objet transporté. Pour passer avec l’objet, il est donc nécessaire de contourner l’obstacle. Près de la fente, toutes les indications données par les fourmis sont mauvaises (elles indiquent la direction de la fente). Dans ce cas, le temps mis pour contourner l’obstacle augmente de façon exponentielle avec la taille de celui-ci, comme prédit par le modèle théorique. À l’inverse, en terrain découvert, la plupart des conseils sont corrects et le transport se fait en temps linéaire en la distance à parcourir.

Plus précisément, dans la validation théorique, cet environnement ouvert est modélisé sous forme discrète, comme une grille 2D. Imaginons un agent désirant se déplacer dans une direction donnée, par exemple vers l’Est. Chaque point de la grille comporte une indication directionnelle pointant vers l’Est avec une certaine probabilité p et dans une direction arbitraire sinon. L’agent se déplace sur la grille, en lisant les indications à chaque noeud qu’il visite, mais sans jamais savoir lesquelles sont correctes. S’appuyant sur des résultats de la théorie des probabilités, les auteurs ont prouvé mathématiquement que la stratégie d’écoute aléatoire, pour un paramètre d’écoute bien choisi, garantit une trajectoire approximativement linéaire dans la direction souhaitée, ici, vers l’Est. La preuve repose sur l’hypothèse que le paramètre p est assez petit. Le fait que le modèle possède deux sources d’aléa rend l’analyse ardue. D’abord, l’environnement dans lequel évolue l’agent est aléatoire, car chaque indication est correcte avec une certaine probabilité. Mais en plus de cela, le mouvement de l’agent est lui-même probabiliste.

En un sens, ce résultat confirme l’enseignement empirique du recuit simulé qui montre que l’aléa peut servir à échapper à des pièges locaux. Plus précisément, la technique de recuit simulé repose sur l’ajustement d’un paramètre de température. Ce paramètre contrôle à quel point l’algorithme cherche la meilleure direction locale  à chaque pas. Dans notre contexte, la température correspond à la probabilité d’écoute.

Le cas des graphes quelconques reste très intrigant malgré la simplicité du modèle. Les auteurs conjecturent en fait que si p est inférieur à l’inverse du degré maximal dans le graphe (plus grand nombre de voisins qu’un nœud peut posséder), la stratégie d’écoute aléatoire permet un temps de parcours optimal, c’est-à-dire linéaire en la distance à la cible. Ces découvertes ont récemment été publiées dans la revue eLife.

La stratégie d’écoute aléatoire est un algorithme simple en rapport avec les fourmis. On peut cependant penser à d’autres solutions pour aborder le problème de la navigation dans un environnement aléatoire. Trouver le meilleur algorithme dans une classe de graphes donnée est un défi d’informatique fondamentale. Cela se rapproche du cadre de l’optimisation par colonie de fourmis où des algorithmes intéressants sont obtenus à partir de l’observation empirique sur le comportement des fourmis. Dans un article plus récent, écrit avec Yoav Rodeh et non encore publié, le cas des arbres est étudié. Un algorithme quasi-optimal pour ces topologies y est décrit et analysé.

Avant ce travail, le problème de la navigation dans un environnement avec des conseils aléatoires n’avait pas été approché sous un angle algorithmique. Le fait que le conseil à chaque nœud est permanent (il n’y a pas de possibilité de le ré-échantillonner) distingue ce modèle des autres modèles de navigation avec du bruit.

Mais la leçon des fourmis peut-elle aussi s’appliquer au domaine technologique ? En effet, il semble qu’une telle stratégie simple d’écoute aléatoire, qui consiste à suivre les indications directionnelles avec une probabilité fixe, peut être implémentée dans d’autres contextes. Il n’est pas exclu qu’elle soit utile dans le routage sur internet ou les réseaux de transport.

Merci à Lucas Boczkowski et Philippe Langlois pour la traduction et l’édition.