Résolution collective de tâches

L'intelligence collective

Comment une population d’agents très simples accomplit-elle une tâche qui dépasse chacun de ses membres ? C’est la question centrale de l’intelligence collective ou intelligence en essaim, largement observable dans la nature — fourmis, abeilles, bancs de poissons, communautés microbiennes — et dont s’inspirent la robotique en essaim et l’optimisation.

Les stratégies décrites jusqu’ici reposent presque toujours sur l’un des trois ingrédients suivants, ou sur leur combinaison : une mémoire individuelle, sous forme de trajet ou de carte ; une communication explicite de ce qui a été appris ; ou de la stigmergie, c’est-à-dire une coordination indirecte par l’environnement, comme les pistes de phéromones. Au laboratoire, nous cherchons à démontrer qu'aucun de ces ingrédients n'est vraiment necessaire pour accomplir des taches complexes, et qu'ils peuvent tous être remplacés par un grand nombre d'individus ; c'est la force du collectif, dans son état le plus brut.

Nous developpons des simulations avec des agents d'un type nouveau pour résoudre des tâches complexes avec pour seule force leur grand nombre: labyrinthes, recherche et rappatriement de ressources ou encore optimisation de chemins.

Résoudre des labyrinthes

Résoudre un labyrinthe — tâche ultra-classique en robotique — est l'archétype d'une tâche de navigation dans un environnement ultra-contraint. Nos agents ne perçoivent que la densité locale de leurs voisins et l’orientation de ceux-ci, à courte portée. Tout leur comportement se ramène à deux questions posées à chaque instant — est-ce que je bouge ? et, si oui, dans quelle direction ? — auxquelles répondent deux règles cinétiques :

1. la vitesse est modulée par la densité locale : un agent isolé piétine, un groupe dense se déplace vite ;
2. chaque agent s’oriente le long du flux sortant maximal de ses voisins.

Dans un couloir, ces règles suffisent à faire condenser la population en un soliton de densité en forme de comète : une tête dense et rapide, une queue lente qui s’étire. La conservation du nombre d’agents avec un flux non linéaire donne une équation de Burgers non visqueuse, un modèle classique de formation d’ondes de choc dont ces solitons sont les solutions. Un cul-de-sac ne les détruit pas : le soliton rebondit, sa tête absorbe sa queue, et il repart régénéré.

Dans un labyrinthe à deux dimensions, où les culs-de-sac abondent, le même mécanisme produit deux dynamiques collectives successives, à partir de règles inchangées et dans un environnement inchangé. D’abord une persistance à court terme aux intersections, qui interdit aux essaims de revenir immédiatement sur leurs pas et les force donc à explorer systématiquement les branches. Puis, lorsqu’un essaim rejoint sa propre queue — signe qu’il circule le long de la solution — une persistance à long terme qui le verrouille sur elle et l’y maintient durablement, un processus que nous appelons fixing.

Le résultat est spectaculaire:

2 000 agents dans un labyrinthe. La couleur code l’a position initiale ; le taux de résolution ζ est la proportion d’agents sur la solution.

Nos essaims trouvent et figent la solution de labyrinthes de n’importe quelle type et taille — testés jusqu’à un million de cases — que la population recircule dans le labyrinthe ou que les agents soient injectés à une entrée (source) et évacués à une autre (puits). Nous avons montré qu'il existe un régime de résolution rapide, où le temps de résolution croît linéairement avec la taille du labyrinthe ; une efficacité comparable à celle d’algorithmes classiques, mais sans mémoire explicite ni complexité spatiale supplémentaire ! Il existe de plus un point Pareto-optimal où le nombre d’agents nécessaires, le temps de résolution, l’énergie dépensée et le nombre d’agents isolés sont simultanément minimisés.

Ce travail définit une classe de systèmes actifs où la complexité émergente contraste fortement avec la simplicité des règles individuelles : la redondance collective y prend la place de la complexité individuelle. Ces stratégies sont peu probables chez les organismes naturels, qui n’atteignent guère les densités d’agents requises en utilisant d'autres stratégies évolutives, mais elles sont prometteuses pour la robotique en essaim et pour la conception de microparticules actives, où les individus sont généralement peu coûteux.

Pour aller plus loin

1. Maze-solving with density-driven swarms, E. M. Zamora Sánchez, H. Allemand, S. Billès, P.-H. Glinel, N. Bredeche et R. Candelier — arXiv:2509.18359