Nous allons voir ici comment son aptitude à trouver son chemin dans un labyrinthe, mise en évidence en biologie, modélisée via la physique et analysée par les mathématiques, ouvre de nouvelles perspectives en informatique.

Si le texte principal de l’article est en piste bleue, les blocs déroulants sont plutôt en piste rouge.

L’expérience

Cette histoire commence par l’expérience d’une équipe nippo-hongroise de biologistes confrontant notre champignon à des labyrinthes [2].

Il ne s’agit pas de le déposer au milieu d’un labyrinthe et de chronométrer le temps qu’il met à en sortir. L’expérience, plus radicale, consiste à découper le physarum en morceaux (d’environ 1cm x 1cm) et d’en tapisser le sol du labyrinthe. La physiologie du physarum lui permet de « recoller les morceaux » quand ils sont proches, et d’adopter ainsi la forme du labyrinthe. On badigeonne ensuite les murs de vinaigre (qu’il déteste) pour éviter qu’il ne les escalade, puis on présente des flocons d’avoine (dont il raffole) à deux entrées du labyrinthe. Le physarum grandit pour couvrir l’avoine, puis commence à réorganiser le « système de distribution » interne qui irrigue les différentes parties de sa cellule. Après quelques heures, on constate que ce système de distribution se réduit à un simple chemin, sans embranchement, qui relie les deux réserves d’avoine. Plusieurs vidéos permettent de visualiser le déroulement d’une telle expérience (par exemple ici en 20 secondes ou là en 2 minutes).

En répétant cette expérience avec une dizaine de labyrinthes différents, on remarque que le physarum trouve à chaque fois le plus court chemin global joignant les deux entrées du labyrinthe. Ce travail a valu aux professeurs Nakagaki, Yamada et Tóth le prix Ig-Nobel 2008 de sciences cognitives. [3]

Plus courts chemins et graphes

Qu’entend-on par « plus court chemin » ? L’idée sous-jacente est que l’on peut modéliser le labyrinthe par un graphe ayant un sommet à chaque angle ou croisement, et une arête entre chaque paire de sommets voisins dans le labyrinthe.

Dans cette modélisation, on peut associer à chaque arête une longueur, c’est à dire la distance entre ses deux sommets. Déterminer le plus court chemin entre deux sommets revient à trouver la séquence d’arêtes qui mène d’un sommet à l’autre tout en minimisant la somme des longueurs des arêtes empruntées.

La recherche de plus court chemin dans les graphes est un problème classique en informatique, qu’il faut résoudre quotidiennement par exemple dans les systèmes de navigation par GPS. Les algorithmes connus pour résoudre ce problème (par exemple ici ou là) sont relativement simples, mais semblent néanmoins hors de portée d’un organisme unicellulaire.

Le physarum est-il effectivement capable de trouver son chemin dans n’importe quel labyrinthe ? On ne peut a priori exclure que les labyrinthes testés par les biologistes ne soient trop simples ou particuliers. Cependant, si cette capacité est avérée, ce champignon exploite sans doute une idée qui a échappé à des générations d’algorithmiciens...

Réseaux de flots

Le physarum gère sa nourriture via un système de canaux internes, qu’il construit et adapte. On peut comprendre sa structure comme un réseau de tuyaux qui relient ses diverses sources de nourriture. Il peut adapter le « diamètre » d’un tuyau à la quantité de nourriture qui doit y transiter. C’est cette faculté à « adapter des diamètres » que l’on interprète comme une capacité de calcul.

On peut modéliser ce réseau comme un graphe ayant un sommet à chaque jonction entre tuyaux, et une arête entre chaque paire de sommets entre lesquels il y a un tuyau. On peut envisager qu’une fois que le physarum épouse la forme du labyrinthe, le graphe de son réseau interne coïncide avec celui du labyrinthe. Cette modélisation associe aussi à chaque arête une capacité, c’est à dire le diamètre du tuyau entre ces deux sommets. (En première approximation, on considère que le diamètre est constant entre deux sommets.) L’ajout de ces capacités transforme le graphe en réseau de flot.

Lors de chaque expérience, on constate que le physarum fait évoluer son réseau de flot vers un réseau très particulier : la capacité est maximale (disons 1) pour les arêtes du plus court chemin entre les deux sommets correspondant aux entrées proches des tas de flocons d’avoine, et minimale (disons 0) ailleurs. Le physarum semble donc disposer d’une dynamique qui « calcule » le plus court chemin.

Modélisation et simulation de la dynamique

Une équipe de mathématiciens appliqués [4] a proposé de modéliser cette dynamique en associant l’évolution du diamètre des tuyaux à la répartition du flot : les tuyaux s’adaptent au flot, et vice-versa. Mathématiquement, il s’agit de coupler la quantité de flot qui s’accumule en chaque sommet et les capacités des arêtes qui y sont reliées. On fait cela au moyen d’un système d’équations différentielles.

Une fois ce modèle posé, on peut le simuler informatiquement via des techniques d’analyse numérique. S’affranchir de la construction des labyrinthes (sans parler de la découpe des physarum !) permet d’examiner des graphes de bien plus grande taille, voire des graphes qui ne sont pas réalisables dans le plan (car impliquant des croisements). Simulation faite, on constate que ce système converge infailliblement vers le plus court chemin pour des dizaines de milliers de graphes, comptant jusqu’à des dizaines de milliers de sommets et des centaines de milliers d’arêtes.

À ce stade, que le modèle proposé soit fidèle ou non à la biologie, il semble y avoir là un théorème à démontrer. Des informaticiens [5] s’y sont attelés et ont prouvé que ce système converge effectivement vers le plus court chemin et ce, pour tout graphe ! [6]

Algorithmes naturels

Au final, l’étude de cet organisme unicellulaire donne de nouvelles idées pour un problème qui fait sécher les informaticiens depuis quelques décennies : calculer de manière décentralisée le plus court chemin dans un graphe. La décentralisation exige, ici, que chaque noeud effectue une partie du calcul en se basant uniquement sur l’information dont il dispose localement. Cet algorithme d’inspiration biologique est un exemple assez spectaculaire d’algorithme naturel, [7] dont l’étude laisse encore de belles pages à écrire.