Les performances des algorithmes multi-agents révèlent une avancée surprenante dans la couverture d’environnements inconnus par des robots autonomes. Cette recherche innovante, inspirée des comportements naturels, promet de transformer notre compréhension des systèmes distribués et de l’intelligence artificielle.
Chapitre 1 : Etat de l’art
Introduction
Depuis quelques années, les systèmes multi-agents ont pris une place de plus en plus importante en informatique, que ce soit dans le domaine de l’intelligence artificielle, dans ceux des systèmes distribués, de la robotique, ou même dans la “vie artificielle”. Les recherches dans le domaine des systèmes multi-agents poursuivent deux objectifs majeurs: le premier concerne l’analyse théorique et expérimentale des mécanismes d’auto-organisation qui ont lieu lorsque plusieurs entités autonomes interagissent; le second s’intéresse à la réalisation d’artefacts distribués capables d’accomplir des tâches complexes par coopération et interaction.
Le problème de recherche d’une cible dont sa position est inconnue à l’avance est très important dans plusieurs applications du monde réel et des recherches académiques. Dans ce problème, la couverture de région est une tâche correspondante parce que la recherche jusqu’à cette cible va engendrer une couverture d’une certaine région avant d’arriver à cette cible. C’est pour cela que le problème est considéré comme un problème de couverture partielle d’une région.
Ce chapitre se trouve divisé en deux parties d’états de l’art. La première partie concerne tout ce qui est en relation avec les notions théoriques des SMA, à savoir l’IAD, les agents, l’interaction, coordination, coopération et simulation. La deuxième partie se concentre plutôt sur le problème de couverture où on cite les travaux réalisés dans la littérature et se divise en deux : couverture mono-robot et couverture multi-robots.
Systèmes multi-agents: définition et principes
Les systèmes multi-agents font partie d’Intelligence Artificielle Distribuée, qui, à la différence d’IA classique, s’intéresse aux comportements intelligents, résultant de l’activité coopérative de plusieurs agents. Le système multi-agents est considéré comme un système distribué composé d’un certain nombre d’entités autonomes (les agents), qui travaillent selon les modes complexes d’interaction, pour réaliser leurs propres buts et par-là même atteindre l’objectif global désiré. Les agents peuvent interagir en communiquant directement entre eux ou par l’intermédiaire d’un autre agent ou en agissant sur leur environnement. [Gouasmi ,05]
l’intelligence artificielle distribuée:
L’intelligence artificielle est reconnue comme étant une discipline informatique qui a pour objectif de modéliser ou de simuler des comportements humains dits intelligents tels que la perception, la prise de décision, l’apprentissage, etc. mais l’IA a vite rencontré un certain nombre de difficultés, dues pour la plupart à la nécessité d’intégrer, au sein d’une même base de connaissances, l’expertise, les compétences et les connaissances d’individus différents qui, dans la réalité, communiquent et collaborent à la réalisation d’un but commun.
A la différence de l’Intelligence Artificielle classique qui modélise le comportement intelligent d’un seul agent, l’intelligence artificielle distribuée s’intéresse à des comportements intelligents qui sont le produit de l’activité coopérative de plusieurs agents.
Le passage du comportement individuel aux comportements collectifs est considéré non seulement comme une extension mais aussi comme un enrichissement de l’IA, d’où émergent de nouvelles propriétés et de nouveaux comportements. [Labidi et al, 93]
Agents : concepts fondamentaux
Le terme « agent » n’est pas aisée du fait du caractère interdisciplinaire des agents qui, d’un côté, sont sujets aux effets des différentes directions de recherches scientifiques et, de l’autre, reflètent les besoins d’applications pratiques. Ainsi, il est difficile de faire accepter par tous une définition précise de cette notion. Car le terme agent étant un terme actuellement porteur, il est utilisé de manière assez vague.
Définition
Définition 1 : Agent [Ferber, 95]
Un agent est une entité :
- qui est capable de percevoir (de manière limitée) son environnement,
- qui ne dispose que d’une représentation partielle de son environnement,
- qui est capable d’agir dans son environnement,
- qui peut communiquer directement avec d’autres agents,
- qui possède des ressources propres,
- qui possède des compétences et peut offrir des services,
- qui est mue par un ensemble de tendances (sous forme d’objectifs individuels),
- dont le comportement tend à satisfaire ses objectifs, en tenant compte des ressources et des compétences dont elle dispose, et en fonction de sa perception et de ses représentations.
A titre d’exemple, on peut dire que l’homme et la fourmi sont des agents physiques. En ce qui concerne l’aspect logiciel, une définition synthétique peut être donnée.
Définition 2 : [Wooldridge, 97]
« Un agent est une entité qui exhibe les caractéristiques suivantes : autonomie, réactivité, pro- active flexible et qui possède une certaine habilité sociale. » [Gouasmi, 05]
Ou :
- Autonome : Son comportement est fonction de ses perceptions qui agissent sur son état, et de sa représentation de l’environnement dans lequel il évolue.
- Réactivité : un agent réactif maintient un lien constant avec son environnement et répond aux changements qui y surviennent.
- Proactif: Il peut prendre des initiatives afin de satisfaire ses buts. Pour ce faire, il n’est pas soumis à l’invocation d’une autre entité pour agir mais peut agir sur sa propre initiative.
- Flexible: Il adapte son comportement à sa perception de son environnement et peut participer à des organisations afin de mieux satisfaire son but.
- Social: Il a la capacité d’interagir pour atteindre ses buts ou pour aider d’autres agents dans leurs activités.
Classification d’agent :
A partir de ces définitions, différents modèles d’agents peuvent être envisagés suivant deux axes : la vision fonctionnelle et la vision décisionnelle :
- La vision fonctionnelle s’appuie sur le degré d’intégration des facettes autonomie, environnement, interaction et organisation dans l’agent. Un agent est autonome, interagissant ou social.
- La vision décisionnelle s’appuie sur le degré de couplage à l’environnement. Un agent est réactif, hybride ou cognitif.
Ces deux visions sont orthogonales et, par conséquent, complémentaires et, les propriétés et caractéristiques des agents sont fortement liées à la représentation de l’environnement. Ainsi, plus un agent possède une représentation élaborée de son environnement, plus il lui est possible d’avoir une activité cognitive [Champion ,03]
[2_performances-des-algorithmes-multi-agents-resultats-cles_1]
Figure 1.1 : Axe pratique d’évaluation de la capacité d’un agent à accomplir individuellement des tâches complexes et à planifier ses actions [Champion ,03]
Agent cognitif :
Les agents cognitifs disposent d’une base de connaissances comprenant les diverses informations liées à leurs domaines d’expertise et à la gestion des interactions avec les autres agents et leur environnement. Les agents sont généralement intentionnels, c’est-à-dire qu’ils possèdent des buts et des plans explicites leur permettant d’accomplir leurs buts. [Courdier, 07]
Agent Réactif :
Les agents réactifs sont souvent qualifiés de ne pas être “intelligents” par eux-mêmes. Ils sont des composantes très simples qui perçoivent l’environnement et sont capables d’agir sur celui-ci. Ils n’ont pas une représentation symbolique de l’environnement ou des connaissances et ils ne possèdent pas de croyances, pas de mécanismes d’envoi de messages. Leurs capacités répondent uniquement au mode stimulus/action qui peut être considéré comme une forme de communication. Un SMA constitué d’agents réactifs possède généralement un grand nombre d’agents et présente un comportement global intelligent. [Haddad et Hamidi, 09]
Agent hybride :
Les agents hybrides sont conçus pour combiner des capacités réactives à des capacités cognitives, ce qui leur permet d’adapter leur comportement en temps réel à l’évolution de l’environnement.
Un agent hybride consiste en la combinaison de plusieurs caractéristiques au sein d’un même agent ; ces caractéristiques concernent la collaboration, l’autonomie et la capacité à apprendre, etc. De façon habituelle, un agent n’est pas complètement de type réactif ni de type délibératif. C’est plutôt une combinaison de ces deux approches. Dans certaines circonstances, un agent doit agir très rapidement alors que dans d’autres, il aura la possibilité de prendre plus de temps pour avoir un processus délibératif de meilleure qualité. Raison pour laquelle, ils sont dits hybrides [Haddad et Hamidi, 09].
Les architectures hybrides entre les deux approches, verticales et horizontales, il existe tout un éventail d’architectures hybrides qui fait intervenir un modèle modulaire avec une approche centralisée ou décentralisée de la gestion des composants d’un agent. L’agent est alors conçu comme une association de modules plus ou moins spécialisés qui fonctionnent en parallèle et qui interagissent. Les interactions entre ces modules permettent d’obtenir un comportement global cohérent. Cette approche permet de combiner des composantes réactives avec des composantes cognitives [Haddad et Hamidi, 09].
Figure 1.2 : Classification d’agents [Courdier ,07]
Architecture d’agent
Un agent se caractérise essentiellement par la façon dont il est conçu et par ses actions, en d’autres termes par son architecture et son comportement. L’architecture correspond à un point de vue de concepteur, qui peut se résumer ainsi : comment assembler les différentes parties d’un agent de manière qu’il accomplisse les actions que l’on attend de lui ? L’architecture d’un agent caractérise ainsi sa structure interne, c’est-à-dire le principe d’organisation qui sous-tend l’agencement de ses différents composants. L’architecture d’un agent est donc une organisation interne modulaire manipulant des flux de données (diffusion, traduction) et gérée par une structure de contrôle (par inhibition, hiérarchique…). [Champion, 03]
Architecture BDI pour un agent cognitif :
Une architecture BDI est conçue en partant du modèle « Croyance-Désir-Intention », en anglais « Belief-Desire-Intention », de la rationalité d’un agent intelligent. [Adina, 02]
Le B = Belief = Croyance : Les croyances d’un agent sont les informations que l’agent possède sur l’environnement et sur d’autres agents qui existent dans le même environnement.
Le D = Desire = Désir : Les désirs d’un agent représentent les états de l’environnement, et parfois de lui-même, que l’agent aimerait voir réalisés.
Le I = Intention = Intention : Les intentions d’un agent sont les désirs que l’agent a décidé d’accomplir ou les actions qu’il a décidé de faire pour accomplir ses désirs.
La figure suivante présente les composantes principales d’une architecture BDI.
[2_performances-des-algorithmes-multi-agents-resultats-cles_2]
Figure 1.3: Architecture BDI. [Adina, 02]
- Architecture de subsomption pour les agents réactifs [Brooks 1990]:
Les architectures verticales sont des architectures adaptées aux agents réactifs. Elles caractérisent des agents modélisés en termes de fonctions de transition entre les données perçues et les actions exécutées. Un principe de décomposition verticale revient à associer à chaque action une fonction simple, elle offre l’avantage d’une conception simple, car ne faisant intervenir que trois composantes : perception-sélection-action [Haddad et Hamidi, 09].
Les architectures réactives représentent le fonctionnement de l’agent au moyen de composantes avec une structure de contrôle simple, et sans représentation évoluée des connaissances de l’agent. L’intelligence de l’agent est vue comme étant le résultat des interactions entre ces composantes et l’environnement. Cela veut dire qu’une telle architecture peut résoudre des problèmes complexes, qui normalement demandent un comportement intelligent, sans traiter l’intelligence du point de vue classique de l’intelligence artificielle. [Adina, 02]
L’architecture subsumption [Brooks, 91] est l’une des architectures verticales les plus connues et utilisées dans le domaine de la robotique. Cette architecture intercale entre la perception et l’action des couches de comportement de complexité croissante : sur la couche basse, les comportements de base tels que le mouvement aléatoire ; sur les couches les plus hautes ceux devant permettre, théoriquement, de satisfaire des comportements spécifiques.
Les couches fonctionnent en parallèle et accèdent à un sous-ensemble des informations captées. L’accès ou système d’action est contrôlé via une hiérarchie de contrôle : les comportements présents sur une couche peuvent supplanter les comportements présents sur les couches inférieures en substituant leurs propres entrées aux entrées des couches inférieures en inhibant toute sortie de ces mêmes couches pour des périodes de temps préprogrammées.
A part ces signaux descendants de suppression et d’inhibition, aucun autre type de communication n’a lieu entre les couches [Briot et Demazeau, 01].
L’architecture réactive la plus connue et la plus influente est celle proposée par Rodney Brooks ; elle s’appelle architecture de subsomption, en anglais « subsumption architecture ».
[2_performances-des-algorithmes-multi-agents-resultats-cles_3]
Figure 1.4 : Architecture subsumption. [Adina, 02]
Un système avec un seul agent est de l’intelligence artificielle classique ; un système avec les agents multiples est une société artificielle. Donc, les thèmes principaux et les fondations de l’intelligence artificielle distribuée sont l’organisation, la coordination et la coopération [Sahki, 08]
________________________
2 Définition donnée par l’article 62 de la loi sur les nouvelles régulations économiques (NRE) du 15 mai 2001. ↑
3 Auchan Les 4 Temps, La Défense. ↑
Questions Fréquemment Posées
Quelles sont les performances des algorithmes multi-agents pour explorer des environnements inconnus ?
Les résultats expérimentaux montrent une amélioration des performances par rapport à l’algorithme MRSAM original.
Comment les systèmes multi-agents fonctionnent-ils dans l’intelligence artificielle distribuée ?
Les systèmes multi-agents sont considérés comme un système distribué composé d’un certain nombre d’entités autonomes qui interagissent pour réaliser leurs propres buts et atteindre l’objectif global désiré.
Pourquoi est-il important de couvrir des régions inconnues avec des robots autonomes ?
Le problème de recherche d’une cible dont sa position est inconnue est très important dans plusieurs applications du monde réel et des recherches académiques, car il engendre une couverture d’une certaine région avant d’arriver à cette cible.