Un Modèle Organisationnel pour La Conception des
Systèmes Multi-Agents Temps Réel

 Les Systèmes Multi-Agents

De nos jours, 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 celui des systèmes informatique distribues, que de la robotique et du génie logiciel. C’est une discipline qui s’intéresse aux comportements collectifs produits par les interactions de plusieurs entités autonomes et flexibles appelés agents. Les systèmes multi-agents mettent en œuvre des agents homogènes et hétérogènes ayant des buts communs ou distincts. Un SMA est un système distribué composé d’un ensemble d’agents qui interagissent le plus souvent, selon des modes de coopération, de concurrence ou de coexistence. Selon [Cha99] un SMA est généralement caractérisé par : • Chaque agent à des informations ou des capacités de résolution de problèmes limitées, ainsi chaque agent à un point de vue partiel; • Il n’y aucun contrôle global du système multi-agents; • Les données sont décentralisées; • Le calcul est asynchrone. De plus, Tranier [Tra07] décrie un SMA comme étant un ensemble d’entités actives et autonomes (les agents) qui évoluent dans un environnement. Cette relation générale entre un agent et son environnement est illustrée sur la Figure 1.1. Figure 1.1. Interaction entre un agent et son environnement [Tra07]. Dans cette section nous introduisons d’abord, les notions d’agents et de systèmes multi-agents (SMA), pour détailler par la suite les SMATR. 1.1. Le Concept d’Agents D’après [Woo00a], Un agent est un système informatique encapsulé, situé dans un environnement dans lequel il est capable d’effectuer une action flexible et autonome, compatible aux objectifs de la conception. Les agents sont : • Des entités clairement identifiables de résolution de problèmes avec des bornes et des interfaces bien définies; • Situés dans un environnement particulier; ils reçoivent des entrées liées aux états de cet environnement par des capteurs et agissent sur cet environnement par des émetteurs; • Destinés à atteindre un objectif spécifique; • Autonomes et responsables de leur comportement; Les Systèmes Multi-Agents Temps Réel 12 • Capables d’adopter un comportement flexible pour résoudre des problèmes selon les objectifs de la conception; ils sont réactifs (capables de s’adapter aux changements d’état de leur environnement) et proactifs (capables d’adopter un nouvel objectif); • Capables dans un univers multi-agents, de communiquer, coopérer, se coordonner, négocier les uns avec les autres. Lorsqu’un agent perçoit une situation dans l’environnement, il essaie de la reconnaître. Si la situation lui est familière, il peut enclencher un processus de planification afin de résoudre le problème. Il peut aussi reconnaître la situation en terme d’action et donc, passe à l’exécution de la tâche (Reconnaissance- Exécution). Lorsque l’agent perçoit des situations qu’il connaît très bien, il peut faire intervenir son comportement réactif en passant directement à l’action (PerceptionExécution). S’il ne peut pas résoudre un problème (situation non-familière), il engage un processus de coopération pour demander de l’aide aux autres agents (Reconnaissance- Prise de décisions).

Agent versus objet

Plusieurs chercheurs définissent la notion d’agent par rapport à celle d’objet, leur argumentation se base sur le fait que la maitrise d’une nouvelle technologie ou d’un nouveau concept est facilitée par sa référence à des technologies ou concepts voisins et d’ores et déjà maitrisés [Ode00]. Les objets se définissent comme des entités informatiques qui encapsulent un état et qui sont capables d’accomplir des actions (ou méthodes dans cet état) tout en communicant par échange de messages. Bien qu’il existe plusieurs similitudes entre les agents et les objets, il n’en ait pas moins qu’il existe d’importantes différences [Woo02]: La première concerne le degré d’autonomie : les agents comme les objets peuvent encapsuler leur état interne, et agir sur cet état par le biais de leurs méthodes. Pour les objets, une invocation de méthode est assimilée parfois à un envoi de message mais une telle méthode doit être explicitement invoquée par un autre objet pour agir tandis qu’un agent recevant une information décidera par lui-même de l’action subséquente [Woo02, Jar02]. Quant à la deuxième différence entre les objets et les agents provient de la flexibilité du comportement d’un agent. Bien qu’il soit possible de construire des objets disposant de ces caractéristiques, les auteurs de [Woo02, Jar02] noteront que le modèle standard d’un objet ne dit rien à propos de ces types de comportements. Alors que, la troisième différence entre ces deux concepts vient du fait que les agents sont censés avoir chacun son fil d’exécution (thread) [Woo02, Jar02]. Cependant, dans le modèle objet standard, il existe un fil d’exécution unique pour tout le système, bien que l’on voie apparaître du parallélisme dans la programmation orientée objet (POO) avec des langages comme Java offrant la possibilité de lancer plusieurs fils d’exécution en même temps. Toute fois, il faut noter une évolution dans la communauté des adeptes de la POO vers la notion d’objet actif possédant son propre fil d’exécution. Les objets actifs sont généralement autonomes, c’est-à-dire qu’ils peuvent exhiber un comportement sans avoir été sollicités par un autre objet [Hik03]. Odell et ses collègues [Ode00] présentent les agents comme une extension d’objets actifs possédant une prise d’initiative (la capacité à initier des actions sans intervention externe) et un libre arbitre (la capacité à refuser ou à modifier une requête externe). Ils définissent un agent comme un objet qui peut prendre des initiatives et refuser de répondre à une sollicitation. Les Systèmes Multi-Agents Temps Réel 

Caractéristiques des Agents

Selon l’auteur de [Maz13], il existe de nombreuses caractéristiques relatives aux agents qui procurent la force au paradigme agent et qui les distinguent des autres paradigmes logiciels tels que les systèmes orientés objets, les systèmes distribués et les systèmes experts. Il cite les plus intéressantes afin d’avoir une meilleure vision d’un agent, qui cependant, ne possède pas forcément toutes ces caractéristiques :  L’autonomie : l’agent est capable d’agir sans l’intervention d’un tiers (humain ou agent) et contrôle ses propres actions ainsi que son état interne ;  La capacité représentationnelle ou la perception: l’agent peut avoir une vision très locale de son environnement, mais aussi une représentation plus large de cet environnement et notamment des agents qui l’entourent ;  La réactivité : l’agent reçoit des informations de son environnement, et il doit être capable de réagir en conséquence ;  L’intentionnalité ou pro-activité : un agent ne réagit pas simplement aux changements de l’environnement mais il fait preuve d’un comportement dirigé vers ses buts et prend des initiatives lorsqu’elles lui semblent appropriées ;  La communication avec les autres agents ;  L’anticipation : l’agent possède plus ou moins les capacités d’anticiper les évènements futurs;  La rationalité : les agents rationnels disposent de critères d’évaluation de leurs actions et de choix des meilleures pour atteindre le but ;  L’adaptabilité ou la flexibilité: un agent adaptable est un agent capable de moduler ses aptitudes selon l’état de l’environnement. Il est capable d’apprentissage et sait résoudre un nouveau problème a partir de son expérience ;  La sociabilité : un agent interagit avec les autres agents (logiciels et humains) quand la situation l’exige afin d’accomplir ses tâches et aide les autres à atteindre leurs buts.

Classification des Agents

Des chercheurs issus de l’intelligence artificielle distribuée comme Moulin et Chaib-Draa [Mou96] caractérisent les agents par leur capacité à résoudre les problèmes [Maz13], comme suit :  Un agent réactif réagit aux changements de son environnement ou aux messages provenant des autres agents. Il ne possède pas de représentations de lui-même, de son environnement ou des autres agents ;  Un agent intentionnel est une entité qui perçoit et agit sur son environnement, qui est capable de raisonner à propos de ses intentions et ses croyances, qui possède des buts explicites et qui peut concevoir et exécuter des plans d’actions ;  Un agent social possède en plus des propriétés d’un agent intentionnel, des modèles explicites des autres agents. Cependant, Ferber [Fer95] classe les agents en fonction de leur caractère cognitif ou réactif. Les agents cognitifs, dont la plupart sont intentionnels, disposent chacun d’une base de connaissances comprenant l’ensemble d’informations et de savoir-faire leur permettant de réaliser leur tâche et de gérer les interactions avec les autres agents et avec leur environnement. Ils sont capables Les Systèmes Multi-Agents Temps Réel 14 d’anticipation et peuvent planifier leur comportement. Par contre, les agents réactifs sont incapables d’anticiper ou de planifier leur comportement. Alors que, Nwana [Nwa96] propose sept catégories d’agents : • Les agents réactifs ; • Les agents collaboratifs: sont des agents autonomes et qui coopèrent et négocient avec les autres agents afin d’atteindre des ententes lors de la résolution distribuée de problèmes; • Les agents d’interface: ces agents fournissent une assistance à l’utilisateur. Un agent d’interface est capable de s’adapter aux habitudes de l’utilisateur et à ses préférences ; • Les agents mobiles: ce sont des agents qui peuvent se déplacer d’un site à un autre en cours d’exécution pour se rapprocher des données ou des ressources; • Les agents d’information ou d’Internet : ces agents ont pour rôle d’administrer, manipuler ou collecter les informations à partir de plusieurs sources d’informations distribuées ; • Les agents hybrides: un agent hybride consiste en la combinaison de plusieurs caractéristiques des autres agents au sein d’un même agent tels que la mobilité, la collaboration, l’autonomie, la capacité à apprendre, etc. • Et les agents intelligents : Nwana pense que les agents logiciels intelligents n’existent réellement pas encore mais d’après Jennings et Wooldridge [Jen98a], un agent intelligent se caractérise par son autonomie, sa réactivité, sa capacité à agir ainsi que sa sociabilité. 

Approche Voyelles

Voyelles [Dem95] est un cadre conceptuel et méthodologique pour le développement des systèmes multi-agent caractérisé principalement par sa puissance d’abstraction. Dans cette approche (Figure 1.2), Demazeau [Dem01] distingue quatre dimensions orthogonales qui interviennent dans l’analyse, la conception, l’implémentation et l’exécution d’un système multiagent : l’Agent, l’Environnement, l’Interaction et l’Organisation (AEIO) que nous présentons brièvement ci-dessous. Figure 1.2. L’approche Voyelles [Tra07]. L’idée sous-tendue par cette approche comme le fait savoir Michel dans [Mic04] est que chacune de ces dimensions définit une problématique particulière qui doit être explicitement étudiée dans chaque étape de la conception, de la phase d’analyse à l’implémentation. La plate-forme de développement Volcano est basée sur cette méthodologie [Ric02]. Elle a par exemple été utilisée dans [Das02] où les auteurs appliquent la décomposition Voyelles pour l’étude de la coordination dans le contexte de la RoboCup. L’intérêt principal de l’approche voyelles est de proposer une séparation abstraite mais avec suffisement de généralité pour être utile dans la spécification ; conception ; et développement des SMA.

Agent

Le concept d’agent à été étudier en détaille dans les sous sections précédentes. Nous nous contentons de donner la définition voyelle d’agent cité dans [Her04] : « les agents sont des entités concrètes ou virtuelles qui existent dans un environnement dans lequel elles peuvent agir et communiquer entre eux, et qui présentent aussi un certain comportement autonome. » 1.5.2. Environnement Selon [Pes97], l’environnement peut être considéré comme la représentation du monde dans lequel les agents se situent. L’environnement est modifiable par les agents, soit de façon globale, soit en faisant la distinction entre objets passifs (soumis aux actions des agents) et entités actives (les agents) [Fer95]. Dans [Aza07] l’auteur présente l’environnement sous plusieurs angles :  Environnement social (par opposition à l’environnement physique): il correspond aux autres agents avec lesquels un agent est en interaction par envoi de message. Alors que, l’environnement physique est constitué des ressources matérielles que l’agent peut percevoir ou sur lesquels il peut agir. Par exemple, dans une société de fourmis, l’environnement physique est composé de nourriture et d’obstacles.  Environnement accessible (par opposition à « inaccessible »): le système peut obtenir une information complète, exacte et à jour sur l’état de son environnement. Par contre, dans un environnement inaccessible, seule une information partielle est disponible. Par exemple, un environnement tel que l’Internet est inaccessible car il est impossible de tout connaître à propos de lui.  Environnement continu (par opposition à « discret »): dans le quel le nombre d’actions et de perceptions possibles est infini. A l’inverse, si ce nombre est limité, l’environnement est dit discret. Ceci est le cas dans un environnement simulé tel qu’un éco-système.  Environnement déterministe (par opposition à « non déterministe »): une action effectuée dans un tel environnement a un effet unique et certain. De plus, l’état suivant de l’environnement est complètement déterminé par l’état courant. Dans un environnement non déterministe, une action n’a pas un effet unique garanti. Par exemple, le monde physique réel est un environnement non déterministe.  Environnement dynamique (par opposition à « statique »): son état dépend des actions des processus appartenant à cet environnement mais aussi des actions d’autres processus externes. Aussi, les changements ne peuvent pas être prédits par le système. Par exemple, l’Internet est un environnement hautement dynamique, son changement n’est pas simplement lié aux actions d’un seul utilisateur. 1.5.3. Interaction Ferber [Fer95] définit les interactions comme étant la mise en relation dynamique de deux ou plusieurs agents par le biais d’un ensemble d’actions réciproques. L’interaction entre agents s’effectue par la communication, les actes de langages et les protocoles d’interaction. Pour atteindre son objectif ou pour améliorer la coordination des actions, un agent peut demander des services à un autre agent. Les Systèmes Multi-Agents Temps Réel 16 Les interactions définissent un contexte organisationnel qui définit la nature des rapports entre agents et qui influence le comportement individuel des agents. Il est donc important de représenter explicitement ces rapports qui sont sujets à un changement continu. Les rapports existants évoluent dans le temps et de nouvelles relations se créent. Dans le travail de [Aza07] l’auteur distingue différents types d’interaction que les agents peuvent adopter comme : la communication, la coopération, la négociation et la coordination. L’interaction se base sur des protocoles qui permettront aux agents d’échanger des messages structurés. Le fait d’interagir va permettre à l’agent de partager de l’information, d’être au courant de ce qui se passe autour de lui, d’atteindre ses buts et d’éviter autant que possible les conflits [Ghb00]. Dans ce qui suit, nous allons décrire quelques modes d’interaction ainsi que les protocoles sur lesquels ils se basent comme illustré dans [Aza07] : La Communication La communication entre les agents est un élément très important dans les SMA. Elle peut être directe ou indirecte. Celle indirecte est adoptée par les agents réactifs. Elle se fait à travers l’environnement ou bien via un tableau noir. Dans une communication par environnement, les agents laissent des traces ou des signaux que les autres agents peuvent percevoir. Dans ce genre de communication il n’y a pas de destinataire bien défini. Cependant la communication directe, concerne les agents cognitifs. Elle est intentionnelle et se fait par envoi de messages à un ou plusieurs destinataires. Ce type de communication (directe) se base sur les trois éléments suivants :  Le langage de communication qui permet de structurer les messages échangés entre les agents tels que KQML [Fin95] et FIPA ACL [Fip02].  L’ontologie qui fournie un vocabulaire et une terminologie compréhensible par tous les agents. Elle concernera les symboles non logiques du contenu du message.  Les mécanismes de communication quant à eux permettent de stocker, rechercher et adresser les messages aux agents. Ces mécanismes sont présents dans les plates-formes multi-agents comme Jade [Bel99] ou MadKit [Fer00]. La Coopération Les agents coopèrent pour atteindre un but commun ou individuel. Ce besoin vient essentiellement du fait qu’un agent ne peut satisfaire son objectif individuellement mais avec l’aide des autres agents du système. Dans la coopération, une tâche sera décomposée entre plusieurs agents afin d’être réalisé par plusieurs mécanismes comme c’est le cas du Contract Net [Smi88]. La Coordination Elle consiste à synchroniser les activités des agents ou à régler les conflits qui existent entre eux. En effet, la coordination met de l’ordre dans le processus global effectué par des agents pour éviter des problèmes dans le comportement global du système. La Négociation Les agents négocient entre eux en faisant des concessions ou en cherchant des alternatives lorqu’ils se retrouvent dans un conflit : « conflits d’intérêts ou de buts, accès à des ressources ou proposition de plusieurs solutions différentes à un seul problème ».

Les Systèmes Multi-Agents Temps Réel 

Les Protocoles d’Interaction Les protocoles d’interaction permettent de décrire explicitement les échanges de messages entre les agents. Ils représentent un schéma commun de conversation utilisé pour exécuter une tâche ou appliquer une stratégie de haut niveau. Un protocole précise qui peut dire quoi à qui et les réactions possibles à ce qui est dit. Il décrit également les enchaînements de messages qui peuvent être possibles entre les agents. Il existe différents types de protocoles d’interaction: les protocoles de coordination, de coopération et de négociation. Parmi les protocoles de coordination les plus utilisés et les plus connus dans les SMA, il y a le protocole Contract Net [Smi88] qui permet aux agents de coordonner leurs activités en établissant des contrats afin d’atteindre leurs buts. 

Organisation

Étant donné que les SMA peuvent être considérés comme une société d’agents coopérant ensemble pour accomplir collectivement un objectif donné, il est nécessaire de résoudre un problème d’organisation, généralement de façon dynamique. Selon Fox [Fox81], une organisation peut être définie comme une structure décrivant comment les membres de l’organisation sont en relation et interagissent afin d’atteindre un but commun. De plus dans [Que02] l’auteur défini l’organisation comme étant la topologie d’un groupe permettant de spécialiser les agents en fonction de leurs compétences. Elle peut également contenir des liens organisationnels et des règles sociales qui contraignent le comportement des agents. L’étude d’une organisation en SMA est composée de :  La structure organisationnelle qui d´ecrit l’organisation en terme de rôles, tâches, responsabilités, et  L’entité organisationnelle qui instancie cette structure. (c’est-à-dire l’affectation des agents aux rôles décrits dans la structure organisationnelle. Querrec [Que02] ajoute aussi qu’une organisation peut être :  Explicite: les rôles sont définis a priori. Avant la simulation, le concepteur connaît la structure organisationnelle.  Emergente: les rôles sont observés a posteriori. Aucune structure organisationnelle n’est connue du concepteur. C’est en observant les interactions entre les agents qu’il se fait une représentation de l’organisation.  Statique: la structure ou les entités organisationnelles sont fixées a priori et ne peuvent évoluer durant la simulation.  Dynamique: la structure ou les entités organisationnelles peuvent évoluer au cours de l’exécution. L’autonomie et le comportement proactif des agents constituant les SMA suggèrent que la conception de ces applications peut être réalisée en imitant le comportement et la structure des organisations humaines, car l’une des missions principales des SMA est de supporter et/ou de contrôler des organisations du monde réel. Un SMA peut, par exemple, aider à contrôler les activités du commerce électronique. Selon [Zam00], la perspective organisationnelle conduit à une caractérisation générale d’un SMA telle que décrite dans la Figure 1.3.