Découvrir

L’intelligence en essaim ou comment faire complexe avec du simple ?

À ses débuts, l'Intelligence Artificielle a puisé son inspiration dans le comportement individuel de l'être humain, en cherchant à reproduire son raisonnement. Elle s'est donc focalisée sur la manière de représenter les connaissances d'un expert et de modéliser son processus de décision, pour construire des systèmes dont le résultat pouvait être qualifié d'« intelligent ».
Mais dans la nature, on observe bien des formes d'intelligence. Pourquoi ne pas prendre en compte une intelligence qui ne serait plus individuelle, mais collective ? Les chercheurs ont ainsi conçu des systèmes « multi-agents » en s'inspirant du fonctionnement d'un groupe d'experts humains.
Une autre source d'inspiration est celle des sociétés d'insectes. Ainsi est née l'« intelligence en essaim », qui trouve des applications dans le domaine de la simulation et au-delà, par exemple en robotique collective ou pour les réseaux.

Un groupe d'experts humains qui doit résoudre un problème, ou encore une société d'insectes, peuvent devenir des sources d'inspiration pour concevoir un système informatique dont l'« intelligence » provient d'un ensemble d'entités - des « agents » - en interaction.

Dans le premier cas, lorsqu'on emploie la métaphore d'un collectif d'humains, chaque entité est supposée douée d'« intelligence ». Les agents communiquent directement en s'envoyant des messages, ils possèdent des représentations du problème à résoudre et sont capables de raisonnements élaborés. La complexité des modèles utilisés autorise à faire appel à des facultés cognitives avancées : représentation explicite et raisonnement sur les autres, raisonnement sur l'avancement de la résolution, persistance d'intentions, notion d'engagement, etc.

Formation d'un pont vivant chez la fourmi d'Argentine « Linepithema humile ».
Formation d'un pont vivant chez la fourmi d'Argentine « Linepithema humile ».
© CNRS Photothèque - Guy Théraulaz

Dans le second cas, au contraire, la métaphore est d'ordre biologique : les agents sont dotés de capacités restreintes de représentation et de raisonnement ; ils sont situés dans un environnement au travers duquel ils interagissent de manière indirecte en y déposant des marques. Alors que dans le premier cas, l'environnement est souvent absent, ici il joue un rôle primordial puisqu'il sert de support aux interactions entre les individus.


1. Une intelligence collective

On a longtemps cru (à tort) que les insectes sociaux étaient plus intelligents que les insectes solitaires, au vu des tâches complexes qu'ils accomplissaient. En effet, bien que ne pouvant être individuellement qualifiés d'intelligents, les membres de ces sociétés sont collectivement capables de réaliser des constructions sophistiquées en savoir plus, de s'adapter à des environnements changeants, de trouver le plus court chemin à une source de nourriture. Autant d'activités collectives dont la sophistication va bien au delà des simples capacités de chacun des individus : on parle alors d'intelligence collective.

L'intelligence en essaim

En Intelligence Artificielle, l'intelligence en essaim definition fait référence à cette intelligence collective des sociétés d'insectes. Elle a fait l'objet de nombreux travaux de recherche, voir par exemple ce mémoire téléchargeable en PDF en savoir plus.

L'intelligence en essaim consiste à étudier et à construire des sociétés d'individus artificiels simples qui sont capables collectivement de fournir une réponse complexe. Dans un tel système multi-agents, chaque agent n'a qu'une vue limitée du système, mais il décide de manière autonome de ses actions. De ce fait, le système est caractérisé par un fonctionnement décentralisé : aucun agent ne décide ni ne coordonne les actions des autres.

Chaque agent est simple : il ne fait appel à aucune représentation ni mécanisme de raisonnement sophistiqué. Ainsi la résolution est le fait des interactions et de la dynamique du système : l'intelligence naît de façon collective. Le résultat global du système est donc émergent, constitué d'une succession de comportements de type « réflexes ».

Par exemple, imaginons un système multi-agent dont l'objectif serait que chaque agent se dispose de manière équidistante sur un cercle de centre O et de rayon r. Cet objectif peut être atteint en dotant chaque agent de deux comportements élémentaires. Le premier comportement s'énonce ainsi : « se diriger jusqu'à une distance r du point O (perçu comme un stimulus de l'environnement) » et le second : « une fois à distance r de O, s'éloigner au maximum des autres ».

Cette applet a été développée avec NetLogo document externe au site par Aurélien Saint-Dizier pour le site Interstices. Elle montre la capacité qu'ont des agents, placés aléatoirement au départ, à s'organiser seuls pour former un cercle, en se répartissant régulièrement autour de celui-ci.
Les agents, rouges à l'origine, deviendront jaunes quand ils seront dans une situation relativement stable, et verts dans une situation très stable. L'applet montre aussi l'importance du réglage des paramètres : en effet, des paramètres mal adaptés ne permettent pas d'arriver à une situation stable.

Mode d'emploi plus détaillé definition
Si l'applet ne s'affiche pas correctement : Vérifiez votre configuration technique definition - Visionnez une démonstration definition
Cette applet a été développée avec NetLogo document externe au site par Aurélien Saint-Dizier pour le site Interstices. Elle montre la capacité qu'ont des agents, placés aléatoirement au départ, à s'organiser seuls pour former un cercle, en se répartissant régulièrement autour de celui-ci.
Les agents, rouges à l'origine, deviendront jaunes quand ils seront dans une situation relativement stable, et verts dans une situation très stable. L'applet montre aussi l'importance du réglage des paramètres : en effet, des paramètres mal adaptés ne permettent pas d'arriver à une situation stable.

Mode d'emploi plus détaillé definition
Si l'applet ne s'affiche pas correctement : Vérifiez votre configuration technique definition - Visionnez une démonstration definition

Avantage au collectif

De tels systèmes se caractérisent par leur adaptabilité et leur robustesse. En effet, du fait d'un contrôle décentralisé, chaque agent réagit en fonction de ses propres perceptions aux modifications de son contexte et il est capable de s'adapter continuellement aux variations de celui-ci. De plus, le nombre des agents, leur caractère intercheangeable, l'absence d'entité centralisatrice rendent un tel système tolérant à la défaillance d'un de ses membres. Dans le cas de l'exemple du cercle, le nombre d'agents composant le système n'a pas besoin d'être précisé pour que le système fonctionne (on peut même ajouter ou supprimer des agents pendant qu'il fonctionne).

Ces deux propriétés permettent à un tel système de changer de comportement en cours de fonctionnement pour qu'il s'adapte aux évolutions de son environnement et d'avoir une dégradation progressive du fonctionnement collectif plutôt qu'un effondrement brutal.

Pour concevoir de tels systèmes, la difficulté principale qui se pose est de déterminer les comportements individuels, leur environnement et la dynamique qui va régir le fonctionnement du système afin qu'il produise la réponse collective souhaitée.

Cependant, les caractéristiques de ces modèles font qu'il est souvent difficile voire impossible de prédire a priori le comportement collectif à partir des comportements individuels. C'est pourquoi la mise au point de ces systèmes passe généralement par une phase expérimentale où l'on évalue le comportement global en fonction de différentes valeurs des paramètres du modèle.

2. ...pour représenter et simuler des systèmes

Cette approche sert tout d'abord à représenter des comportements naturels observés, en biologie du comportement animal, en agronomie, en sociologie. Voici par exemple une simulation de la recherche de nourriture par les fourmis.

Elle se base sur la première expérience qui a permis de mettre en évidence l'intelligence collective développée par les fourmis en quête de nourriture. C'est cette expérience, menée dans les années 1980 par Jean-Louis Deneubourg, professeur à l'Université Libre de Bruxelles, qui est à l'origine du développement du domaine de recherche de l'intelligence en essaim.

Deux chemins de longueur différentes permettent aux fourmis d'accéder de leur nid à une source de nourriture. Une fourmi seule prendra indifféremment l'un ou l'autre chemin, alors qu'une colonie de fourmis choisira de manière privilégiée le chemin le plus court.

L'explication biologique de ce phénomène est assez simple. En effet, en se déplaçant, chaque fourmi marque son chemin en déposant une certaine quantité de phéromones. Au départ, les fourmis empruntent au hasard l'un des chemins. Mais celles qui ont pris le chemin le plus court retournent plus rapidement au nid, déposant donc plus rapidement une nouvelle quantité de phéromones sur le chemin du retour. Les autres fourmis sont ensuite guidées par les traces de phéromones les plus importantes. On observe donc qu'après un temps de convergence, le plus court chemin est emprunté collectivement par une majorité d'individus.

Cette applet a été développée avec NetLogo document externe au site par Aurélien Saint-Dizier pour le site Interstices. Elle illustre la découverte du plus court chemin entre une fourmilière et une source de nourriture.
Des fourmis sortant à gauche vont essayer d'atteindre la nourriture à droite, en passant par l'un des deux chemins, puis chacune devra rentrer déposer la nourriture acquise. Après un certain nombre de passages des fourmis, l'une des branches deviendra très fréquentée : la plus courte entre la fourmilière et la nourriture.

Mode d'emploi plus détaillé definition
Si l'applet ne s'affiche pas correctement : Vérifiez votre configuration technique definition - Visionnez une démonstration definition
Cette applet a été développée avec NetLogo document externe au site par Aurélien Saint-Dizier pour le site Interstices. Elle illustre la découverte du plus court chemin entre une fourmilière et une source de nourriture.
Des fourmis sortant à gauche vont essayer d'atteindre la nourriture à droite, en passant par l'un des deux chemins, puis chacune devra rentrer déposer la nourriture acquise. Après un certain nombre de passages des fourmis, l'une des branches deviendra très fréquentée : la plus courte entre la fourmilière et la nourriture.

Mode d'emploi plus détaillé definition
Si l'applet ne s'affiche pas correctement : Vérifiez votre configuration technique definition - Visionnez une démonstration definition

Mais ce type d'approche ne se limite pas à la représentation de comportements naturels, l'intelligence en essaim est aussi appliquée à la gestion de trafics routiers urbains, à la simulation du mouvement de foule...
Ainsi, le logiciel MASSIVE document externe au site (Multiple Agent Simulation System In Virtual Environnement) utilise ces principes pour créer des scènes d'animations de foules en 3D, dans le cadre du film « Le seigneur des anneaux ». Chaque agent d'une scène est défini par ses caractéristiques et ses réactions à son environnement. Les interactions entre centaines ou milliers d'agents produisent des mouvements de foule réalistes.

3. ...pour résoudre des problèmes

Par ailleurs, cette approche peut être utilisée pour concevoir des systèmes de résolution collective de problèmes. Il s'agit alors de définir des comportements individuels en interaction pour que collectivement se produise une réponse qui sera interprétée comme solution d'un problème. Dans la construction de tels systèmes, les collectifs naturels servent de sources d'inspiration pour concevoir un algorithme de résolution collective de problème. Parmi tous les modèles qu'offre la biologie, les sociétés d'insectes figurent en bonne place.

 

L'un des tout premiers algorithmes s'inspirant du comportement d'une colonie de fourmis est dû à l'Italien Marco Dorigo, de l'Université Libre de Bruxelles. Cet algorithme, inspiré de la recherche de nourriture par les fourmis, s'applique au fameux problème du voyageur de commerce : quel est le chemin le plus court entre n villes qui passe une seule fois par chaque ville ?

 

Cet algorithme a servi de base pour mettre au point diverses applications, qui concernent par exemple les réseaux de communication, comme le routage d'informations dans un réseau. Les performances de ce type d'algorithmes sont comparables à celles d'approches plus conventionnelles.



Cette applet a été développée avec NetLogo document externe au site par Aurélien Saint-Dizier pour le site Interstices.
Elle illustre la résolution du problème du voyageur de commerce. L'algorithme original ainsi que les paramètres expérimentaux qui ont été utilisés pour développer cette applet sont issus des travaux de Marco Dorigo, de l'Université Libre de Bruxelles.

Un voyageur doit passer par un certain nombre de villes, toutes différentes, et revenir à sa ville de départ. Il doit obligatoirement passer par chaque ville, et ne doit y aller qu'une seule fois durant son voyage. Le but est de trouver le chemin le plus court reliant toutes les villes.
L'applet montre que l'emploi d'un système de résolution basé sur le comportement des fourmis et leur capacité à trouver le plus court chemin entre deux points permet de résoudre un tel problème. Le programme donne le meilleur ordre des villes à visiter trouvé, ainsi que la longueur du trajet.
(Attention, selon la puissance de votre ordinateur, il faudra envisager d'être patient !)

Mode d'emploi plus détaillé definition
Si l'applet ne s'affiche pas correctement : Vérifiez votre configuration technique definition - Visionnez une démonstration definition
Cette applet a été développée avec NetLogo document externe au site par Aurélien Saint-Dizier pour le site Interstices.
Elle illustre la résolution du problème du voyageur de commerce. L'algorithme original ainsi que les paramètres expérimentaux qui ont été utilisés pour développer cette applet sont issus des travaux de Marco Dorigo, de l'Université Libre de Bruxelles.

Un voyageur doit passer par un certain nombre de villes, toutes différentes, et revenir à sa ville de départ. Il doit obligatoirement passer par chaque ville, et ne doit y aller qu'une seule fois durant son voyage. Le but est de trouver le chemin le plus court reliant toutes les villes.
L'applet montre que l'emploi d'un système de résolution basé sur le comportement des fourmis et leur capacité à trouver le plus court chemin entre deux points permet de résoudre un tel problème. Le programme donne le meilleur ordre des villes à visiter trouvé, ainsi que la longueur du trajet.
(Attention, selon la puissance de votre ordinateur, il faudra envisager d'être patient !)

Mode d'emploi plus détaillé definition
Si l'applet ne s'affiche pas correctement : Vérifiez votre configuration technique definition - Visionnez une démonstration definition

Ces divers exemples montrent que l'approche d'intelligence en essaim est adaptée pour la modélisation de systèmes faisant intervenir un grand nombre d'entités différentes, en interaction, situées dans un environnement dynamique et fonctionnant de manière décentralisée.

C'est pourquoi elle s'applique bien à la simulation de phénomènes collectifs dont les propriétés globales ne découlent pas directement des propriétés de ses composants, en y apportant une dimension explicative.

Cependant, un grand nombre d'autres domaines de recherche actuels sont caractérisés par les éléments précédents (distribution, absence de point de vue global, environnement dynamique) et sont donc des champs potentiels d'application de cette approche, ne serait-ce qu'en robotique collective document externe au site ou dans le domaine des réseaux (où la transposition du comportement collectif des fourmis a permis l'élaboration d'un algorithme efficace de routage).

Grâce aux évolutions technologiques, les systèmes informatiques sont de plus en plus omniprésents (on les retrouve dans les objets de la vie quotidienne), de plus en plus interconnectés, et toujours en fonctionnement. Cela préfigure donc des systèmes distribués, décentralisés, plongés dans un environnement dynamique et dont le fonctionnement global sera le résultat d'interactions entre les composants : un futur champ d'application pour l'intelligence en essaim ?

Niveau de lecture

Aidez-nous à évaluer le niveau de lecture de ce document.

Il vous semble :

Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (qui ne sera pas publié).