intelligence collective

L'algorithme simple que les fourmis utilisent pour construire des ponts

Même sans personne pour les diriger, les fourmis légionnaires travaillent en groupe pour construire des ponts avec leurs corps. De nouvelles recherches révèlent les règles simples qui conduisent à un comportement de groupe aussi complexe.

Les fourmis légionnaires forment des colonies de plusieurs millions d'individus, mais n'ont pas de foyer permanent. Elles traversent la jungle chaque nuit à la recherche de nouveaux lieux de recherche de nourriture. En chemin, elles accomplissent des prouesses logistiques qui feraient la fierté d'un général quatre étoiles, notamment la construction de ponts avec leur propre corps.

Tout comme les essaims de robots bon marché et stupides que j’ai étudiés dans mon récent article, les fourmis légionnaires gèrent cette coordination sans chef et avec des ressources cognitives minimales. Une fourmi légionnaire individuelle est pratiquement aveugle et possède un cerveau minuscule qui ne peut pas même commencer à comprendre leur mouvement collectif élaboré. " Il n’y a pas de chef, pas de fourmi architecte qui dit ‘nous devons construire ici’ ", a déclaré Simon Garnier , directeur du Swarm Lab au New Jersey Institute of Technology et co-auteur d’une nouvelle étude qui prédit quand une colonie de fourmis légionnaires décidera de construire un pont.

L’étude de Garnier permet d’expliquer non seulement comment les fourmis non organisées construisent des ponts, mais aussi comment elles accomplissent la tâche encore plus complexe qui consiste à déterminer quels ponts valent la peine d’être construits.

(vidéo : Alors que l'écart s'élargit lentement, un pont de fourmis armée s'effondre puis se rétablit.)

Pour comprendre comment cela se déroule, prenons le point de vue d’une fourmi en marche. Lorsqu’elle rencontre un obstacle sur son chemin, elle ralentit. Le reste de la colonie, qui avance toujours à 12 centimètres par seconde lui marche dessus. À ce stade, deux règles simples s’appliquent.

La première dicte à la fourmi que lorsqu’elle sent d’autres fourmis marcher sur son dos, elle doit se figer. " Tant que quelqu’un te marche dessus, tu restes immobile ", explique Garnier.

Le même processus se répète chez les autres fourmis : elles enjambent la première fourmi, mais — oh, oh — l’espace est toujours là, donc la fourmi suivante ralentit, se fait piétiner et se fige sur place. De cette façon, les fourmis construisent un pont suffisamment long pour enjamber l’espace qui se trouve devant elles. Les fourmis qui suivent dans la colonie peuvent alors marcher dessus.

Mais ce n’est pas tout. Les ponts impliquent des compromis. Imaginez qu’une colonie de fourmis se retrouve face à un trou en forme de V sur son chemin. La colonie ne veut pas faire le tour complet du trou – cela prendrait trop de temps – mais elle ne construit pas non plus de pont sur la partie la plus large du trou, ce qui minimiserait la distance à parcourir par la colonie. Le fait que les fourmis légionnaires ne construisent pas toujours le pont qui minimise la distance suggère qu’il existe un autre facteur dans leur calcul inconscient.

(Photo : un contour- espace en forme de V offre aux fourmis un compromis : un chemin plus direct nécessitera plus de fourmis pour le construire.)

" En écologie, quand on voit quelque chose de ce genre, cela signifie généralement qu'il y a un rapport coût-bénéfice ", explique Garnier. " On essaie de comprendre : quel est le bénéfice et quel est le coût ? "

Selon les écologistes, le prix à payer est que les fourmis piégées dans les ponts ne sont pas disponibles pour d’autres tâches, comme la recherche de nourriture. À tout moment au cours d’une marche, une colonie peut entretenir entre 40 et 50 ponts - avec une seule fourmi et jusqu’à 50 fourmis par pont. Dans un article de 2015 , Garnier et ses collègues ont calculé que jusqu’à 20 % de la colonie peut être occupée dans des ponts à la fois. À ce stade, un itinéraire plus court ne vaut tout simplement pas les fourmis supplémentaires qu’il faudrait pour créer un pont plus long.

Sauf que, bien sûr, les fourmis individuelles n’ont aucune idée du nombre de leurs congénères qui se maintiennent dans un tel  pont-passage. Et c’est là qu’entre en jeu la deuxième règle. Lorsque les fourmis individuelles exécutent l’algorithme de " pontage ", elles sont sensibles à la bousculade. Lorsque le trafic sur leur dos dépasse un certain niveau, elles restent en place, mais lorsque ce niveau descend en dessous d’un certain seuil – peut-être parce que trop d’autres fourmis sont maintenant occupées à construire elles-mêmes un pont – la fourmi se débloque et rejoint la marche.

Cette nouvelle étude est le résultat d'expériences menées sur des fourmis légionnaires dans la jungle panaméenne en 2014. Sur la base de ces observations, les chercheurs ont créé un modèle qui quantifie la sensibilité des fourmis au passage des piétons et prédit quand une colonie franchira un obstacle et quand elle décidera, en quelque sorte, qu'il vaut mieux faire le tour.

" Nous essayons de déterminer si nous pouvons prédire dans quelle mesure les fourmis prendront des raccourcis en fonction de la géométrie de leur environnement ", a déclaré Garnier.

L'évolution semble avoir doté les fourmis armées de l'algorithme idéal pour construire des ponts à la volée. Les chercheurs qui travaillent à la construction d'essaims de robots simples cherchent encore les instructions qui permettront à leurs machines bon marché d'accomplir des prouesses similaires. L'un des défis auxquels ils doivent faire face est que la nature fabrique des fourmis de manière plus fiable et à moindre coût que les humains ne peuvent fabriquer des robots-essaims, dont les batteries ont tendance à s'épuiser. Le deuxième défi est qu'il est très possible que le comportement des fourmis armées soit régi par d'autres règles que les deux simples exemples décrits ici.

" Nous décrivons les fourmis légionnaires comme des êtres simples, mais nous ne comprenons même pas ce qu'elles font. Oui, elles sont simples, mais peut-être pas aussi simples qu'on le pense ", a déclaré Melvin Gauci , chercheur à l'Université de Harvard qui travaille sur la robotique en essaim. 

Auteur: Internet

Info: Quanta Magazine, Kevin Hartnett, fév. 2028

[ insectes ]

subtile asymétrie

Des physiciens créent le labyrinthe le plus complexe au monde pour dompter un cristal exotique

 En s’inspirant d’une méthode analytique imaginée pour résoudre un vieux problème d’échecs, des chercheurs ont pu produire un labyrinthe incroyablement complexe qui représente la structure d’une famille de matériaux mystérieux.

(photo du Quasicristal Labyrinthe )

En s’appuyant sur les échecs et la géométrie fractale pour mieux comprendre la structure d’un type de cristal particulièrement exotique, des physiciens britanniques et suisses ont conçu un algorithme qui s’est avéré capable de produire un labyrinthe à la complexité absolument diabolique — le plus difficile jamais créé selon eux.

Les objets sur lesquels travaille cette équipe ne sont en fait pas tout à fait des cristaux à proprement parler : il s’agit en fait de quasicristaux. À l’inverse des cristaux normaux qui sont incroyablement abondants, ces quasicristaux sont aussi exceptionnellement rares à l’état naturel. En fait, il n’en existe qu’une poignée de sources naturelles connues — et il s’agit à chaque fois de météorites.

Au-delà de leur rareté, ce qui rend ces matériaux si intéressants, c’est que leur architecture. Les atomes sont arrangés selon une structure hautement organisée et symétrique, comme les cristaux traditionnels. Mais à la différence de ces derniers, les groupes atomes ne se répètent pas périodiquement dans l’espace en suivant un motif simple. À la place, ils présentent des types de symétrie beaucoup plus élaborés.

(Photo  : Quasicrystal1. Une représentation de la structure d’un quasicristal constitué d’aluminium, de palladium et de manganèse)

" Les quasi-cristaux ont toutes ces symétries qui ne pourraient en aucun cas exister dans les cristaux, ce qui est assez fascinant. C’est une très belle branche des mathématiques — mais n’importe qui peut en apprécier la beauté directement, sans avoir besoin d’en comprendre les détails ", explique Felix Flicker, co-auteur de l’étude cité par New Scientist.

Du cristal, des échecs et des maths

Puisque les exemples ne se bousculent pas au portillon, la science a encore beaucoup de choses à apprendre sur les particularités des quasicristaux. Afin de mieux comprendre ces aliens géométriques, l’équipe de Flicker a décidé de créer un algorithme ultraspécialisé pour en décrire la structure. Et pour y parvenir, ils se sont inspirés… des échecs.

La filiation n’est pas évidente, mais la structure des quasi-cristaux présente en effet des particularités avec un vieux problème de logique basé sur les déplacements de la pièce la plus singulière du roi des jeux de plateau.

Ce puzzle dit du Cavalier d’Euler commence avec un cavalier positionné sur n’importe quelle case de l’échiquier. L’objectif, c’est de lui faire visiter toutes les autres cases sans jamais repasser deux fois par la même. Lorsqu’on trace le parcours de ce cavalier, on obtient ce qu’on appelle un circuit hamiltonien, c’est-à-dire qu’il passe une seule fois par tous les points d’un graphe.

Or, il se trouve que la structure des atomes dans les quasicristaux suit aussi cette règle. Et c’est là que ces travaux deviennent croustillants, car cette similitude permet d’appréhender le problème sous l’angle de la théorie de la complexité.

Une incursion dans la théorie de la complexité

En général, trouver un circuit hamiltonien est ce qu’on appelle un problème NP-complet. Ce terme désigne un problème dont la complexité augmente de manière exponentielle avec le nombre d’éléments, à tel point qu’il devient vite impossible de calculer la solution par force brute à notre échelle de temps. En revanche, si l’on se retrouve face à une solution potentielle, il est facile de vérifier rapidement si elle est valide, un peu comme un puzzle où il suffit d’observer l’image finale.

Tout l’enjeu, c’est donc de trouver une façon de résoudre ces problèmes dits NP-complets en un temps raisonnable (ou plus précisément en un temps dit polynomial). Et c’est un problème qui fait tourner les mathématiciens en bourrique depuis des décennies. En fait, cela rentre même dans le giron de P=NP, un des fameux Problèmes du Prix du Millénaire. Il s’agit d’une liste de sept problèmes mathématiques majeurs dont la résolution s’accompagne d’un prix d’un million de dollars. Jusqu’à présent, seul un d’entre eux, la Conjecture de Poincaré, a été résolu (par Grigori Perelman en 2010).

Cette équation matérialise une question quasi existentielle pour les mathématiciens : ces problèmes complexes sont-ils vraiment aussi difficiles à aborder qu’ils en ont l’air, ou existe-t-il une solution générale simple que personne n’a encore trouvée pour chercher une solution rapidement ?

Si cette hypothèse P=NP était confirmée un jour, ce qui est loin d’être acquis, les implications seraient énormes. Cela changerait fondamentalement la nature d’une foule de problèmes très importants pour la science moderne, mais aujourd’hui considérés comme quasiment insolubles.

Le point important, c’est que tous les spécialistes de la théorie de la complexité s’accordent sur un point : ils considèrent que s’il existe un algorithme pour résoudre un seul problème NP-complet en un temps raisonnable (polynomial), alors cela signifie qu’il existe aussi une solution relativement simple à TOUS les autres problèmes NP-complets, dont les circuits hamiltoniens ! Et il se trouve que bon nombre d’entre eux sont exceptionnellement importants pour la science moderne. On peut citer le problème du voyageur du commerce, dont la résolution rapide supprimerait immédiatement un tas de casse-têtes logistiques extrêmement ardus, ou les mécanismes du repli des protéines auquel les équipes de DeepMind se sont attaquées grâce au machine learning.

Or, il se trouve que le cavalier d’Euler est un cas particulier. Même si les circuits hamiltoniens sont généralement des problèmes NP-complets, il y en a quelques-uns qui peuvent être résolus rapidement grâce à quelques tours de passe-passe mathématiques. Le cavalier d’Euler en fait partie : on peut rapidement trouver une solution grâce à une méthode simple, l’algorithme de Warnsdorf. Puisque ce problème est intimement lié à la structure des quasicristaux, les auteurs de ces travaux ont donc cherché une méthode analogue pour l’appliquer à leur propre problème.

(Photo : Et ils en ont trouvé une, ce qui leur a permis de générer ce labyrinthe incroyablement difficile qui illustre l’arrangement des atomes dans ces matériaux. Labyrinthe Quasicristal Complet)

Pas une preuve de P=NP, mais des applications concrètes intéressantes

Selon les chercheurs cités par ScienceAlert, ces travaux pourraient avoir des implications très concrètes dans des domaines comme l’optique ou la capture du carbone.

En revanche, cela ne signifie en aucun cas que le problème des circuits hamiltoniens a été résolu une fois pour toutes ; comme pour le Cavalier d’Euler, il s’agit simplement d’une façon très élégante de simplifier un problème bien précis, et en aucun cas d’une solution générale.

Par extension, ce n’est pas non plus une réponse à l’hypothèse P=NP et à tous les autres problèmes NP-complets… mais il s’agit peut-être d’un pas dans cette direction. Qui sait ; si une solution rigoureuse finit par émerger un jour, on se souviendra peut-être de ces travaux comme l’une des pièces qui ont ouvert la voie à une révolution parmi les plus importantes de l’histoire des mathématiques.

Auteur: Internet

Info: https://www.journaldugeek.com, Antoine Gautherie, juillet 2024

[ apériodique ]

platonisme

On vit constamment dans le faux sans le savoir, on s'accommode d'une illusion qui répond à la perfection à ses fantasmes et qui permet d'éviter de faire face à la réalité.

Auteur: Piersanti Gilda

Info: Illusion tragique

[ subjectivité ] [ réconfort ]

interprétation

Le passé, même le plus trouble, n'était pour lui qu'une variable qu'on pouvait modifier à sa guise : rien de définitif, rien de réel, seulement un récit à déconstruire et reconstruire au gré des circonstances et des objectifs fixés.

Auteur: Piersanti Gilda

Info: Les Somnambules

[ manipulation ]

grégarismes

Eusocialité :  Vie sociale la plus évoluée, marquée par trois caractères fondamentaux :

- L’existence d’une coopération dans les soins aux formes immatures

- Le chevauchement d’au moins deux générations

- La présence de femelles spécialisées dans la reproduction. (reines?)

Les animaux eusociaux sont caractérisés par une vie en groupe avec des générations chevauchantes et, pour les hyménoptères, une asymétrie de la reproduction entre des femelles de deux castes différentes, déterminées phénotypiquement, avec des castes d’individus fertiles et non fertiles

Auteur: Triplet Patrick

Info: In "Dictionnaire encyclopédique de la diversité biologique et de la conservation de la nature"

[ triade ] [ homme-animal ] [ insectes sociaux ] [ clans rôles ] [ classes fonctions ]

exactitude

Utiliser le bon mot, la bonne notion, le bon concept, avec la définition la plus couramment acceptée, ou mieux avec la définition la mieux acceptée et comprise relève parfois de l’exploit,…   

(Après avoir présenté son "Dictionnaire encyclopédique de la diversité biologique et de la conservation de la nature")

Auteur: Triplet Patrick

Info:

[ précision sémantique ] [ justesse terminologique ] [ langage ]

objet

Au nom de quoi peut-il [l'être humain] dire qu’il a un corps ? Au nom de ceci qu’il le traite à la va comme-je-te-pousse, il le traite comme un meuble. Il le met dans des wagons par exemple et là il se laisse trimbaler. C’était quand même vrai aussi, ça commençait à s’amorcer quand il le mettait dans des chariots.

Auteur: Lacan Jacques

Info: Conférences et entretiens dans des universités nord-américaines. Scilicet n° 6/7, 1975, pp. 42-45

[ propriété ] [ usage ]

concept psychanalytique

C’est un cercle vicieux de dire que nous sommes des êtres parlants. Nous sommes des "parlêtres", mot qu’il y a avantage à substituer à l’inconscient, d’équivoquer sur la parlote, d’une part, et sur le fait que c’est du langage que nous tenons cette folie qu’il y a de l’être : parce que c’est sûr que nous y croyons, nous y croyons à cause de tout ce qui paraît faire substance ; mais en quoi est-ce de l’être, en dehors du fait que le langage use du verbe être ?

Auteur: Lacan Jacques

Info: Conférences et entretiens dans des universités nord-américaines. Scilicet n° 6/7, 1975, pp. 42-45

[ définition ] [ symbolique-réel-imaginaire ]

énonciation

Il se produit comme ça dans plusieurs places une sorte de petit tourbillon, une manière de dire qui est ce que j’appelle, moi, le style. Je n’ai pas de "conception du monde", mais j’ai un style, un style qui, naturellement, n’est pas tout à fait facile, mais c’est là tout le problème. Qu’est-ce que c’est qu’un style ? Qu’est-ce que c’est qu’une chose ? Qu’est-ce que c’est que la façon dont un style se situe, se caractérise ? Moi, au temps où je parlais seulement avec des camarades, ce qui était, le plus naturel, c’était de dire "ce n’est pas tout à fait ça" et si ce que j’ai écrit après l’avoir dit, si ce que j’ai écrit, d’élaborer ce que j’ai dit, a un cachet, c’est de marquer que j’essaie de serrer au plus près ce qui est "tout à fait ça".

Auteur: Lacan Jacques

Info: Conférences et entretiens dans des universités nord-américaines. Scilicet n° 6/7, 1975, pp. 42-45

[ autocritique ] [ recherche ] [ désir ]

lalangue

Si j’ai employé le terme : "l’inconscient est structuré comme un langage", c’est bien parce que je veux maintenir qu’un langage, ça n’est pas le langage. Il y a quelque chose dans le langage de déjà trop général, de trop logique.

Auteur: Lacan Jacques

Info: Conférences et entretiens dans des universités nord-américaines. Scilicet n° 6/7, 1975, pp. 42-45

[ singularité ] [ asystématique ] [ précision ]