K Darty

J Saunier
email: julien.saunier@ifsttar.fr

Extraction de comportements pour l'étude de la crédibilité des agents

Keywords: Simulation multi-agents, approche mixte, crédibilité comportementale, extraction/classification de comportements Multi-agent simulation, mixed approach, behavioral credibility, behavior extraction & clustering

Cet article présente une méthode d'évaluation de la crédibilité comportementale en simulation multi-agents. Elle s'appuie sur l'extraction automatique de classes de comportements dans une simulation participative. La méthode que nous proposons combine deux approches. La première, subjective, évalue par des questionnaires les catégories d'utilisateurs dans le dispositif de simulation. La seconde effectue une observation objective des données issues de la simulation pour construire automatiquement des classes de comportements. Nous étudions alors la corrélation entre les catégories d'utilisateurs et les classes de comportement. Nous comparons ensuite les comportements des humains et des agents pour évaluer la crédibilité de ces derniers, en nous appuyant sur les catégories d'utilisateur. Nous illustrons cette méthode dans le cadre d'un simulateur de conduite immersif.

Introduction

La simulation multi-agents de systèmes complexes comprend de nombreuses entités en interaction qui exhibent divers comportements afin d'atteindre leurs buts. Comme le montre Drogoul et al. [START_REF] Drogoul | Manta : New experimental results on the emergence of (artificial) ant societies. Artificial Societies : the computer simulation of social life[END_REF], la validation d'une telle simulation passe nécessairement par une évaluation du système à l'échelle macroscopique. Le concepteur de SMA doit alors disposer d'outils de validation du phénomène collectif. Cependant, la validité au niveau macroscopique ne garantit pas une validité au niveau microscopique, c'està-dire au niveau du comportement de chaque agent du système. Or dans certaines simulation comme les environnements de réalité virtuelle (RV), des humains cohabitent avec les agents simulés. Dans ce cas, le point de vue de l'humain est fortement local et la crédibilité du comportement est jugée au niveau microscopique. En effet, si le comportement individuel est incohérent, l'immersion du sujet dans l'environnement virtuel (EV) -c'est-à-dire le sentiment d'appartenance à l'EV -est rompue [START_REF] Fontaine | The experience of a sense of presence in intercultural and international encounters[END_REF][START_REF] Mcgreevy | The presence of field geologists in mars-like terrain[END_REF].

Cette notion de crédibilité au niveau microscopique est indépendante de la façon dont les comportements sont modélisés. En effet, c'est l'observateur externe qui juge les comportements exhibés et cette perception dépend de nombreux facteurs dont des éléments sensoriels (rendu visuel, haptique, proprioceptif, etc.) [START_REF] Burkhardt | Immersion, réalisme et présence dans la conception et l'évaluation des environnements virtuels[END_REF][START_REF] Stoffregen | On the nature and evaluation of fidelity in virtual environments. Virtual and adaptive environments : Applications, implications, and human performance issues[END_REF]. Le terme consacré dans la littérature pour designer ce sentiment de réalisme est appelé effet de présence [START_REF] Witmer | Measuring presence in virtual environments : A presence questionnaire[END_REF]. Les techniques mises en oeuvre pour améliorer l'effet de présence (appelées techniques d'immersion) sont principalement évaluées sur des données subjectives. En conséquence, l'évaluation de l'effet de présence résultant d'un dispositif de RV est réalisée par des méthodes issues des sciences humaines.

Dans cet article, nous proposons de combiner ces méthodes d'évaluation subjectives avec des méthodes d'analyse de traces de comportements pour évaluer la crédibilité des agents au niveau microscopique. La partie 2 présente les travaux du domaine. La partie 3 explique les objectifs de notre méthodologie ainsi que l'approche utilisée. Nous détaillons les données recueillires et algorithmes utilisés en parties 4 et 5. Enfin, la partie 6 présente son utilisation sur un simulateur de conduite immersif et les résultats obtenus.

Validation comportementale

Dans cette section, nous définissons la notion de comportement au coeur de notre étude et nous présentons les travaux de la littérature autour des approches subjective et objective.

Niveaux de comportements

Les comportements sont un ensemble d'actions d'un individu observables dans l'environnement. Il existe différents niveaux de comportements chez un individu [START_REF] Pavlov | Conditioned reflexes[END_REF] : le niveau le plus bas correspond aux actions simples de type réflexes comme passer en première vitesse dans une voiture. Ces comportements sont identiques aux opérations élémentaires d'un agent. Un type de comportement de niveau intermédiaire met en place une tactique construite d'une suite ordonnée de comportements élémentaires tel le changement de voie d'une voiture sur autoroute. Le comportement de niveau plus élevé est le niveau stratégique sur le long terme. Il est basé sur des choix de tactiques et évolue suivant la dynamique de l'environnement, l'état mental de l'individu et ses émotions [START_REF] Fisher | Handbook of driving simulation for engineering, medicine, and psychology[END_REF] comme doubler une file ralentie de camion. C'est à ces niveaux de comportement, le niveau tactique et stratégique, que nous souhaitons valider la crédibilité comportementale des agents.

Approche subjective

L'approche subjective est issue du domaine de la RV pour la validation du comportement en simulation. Elle consiste à évaluer la qualité d'immersion générale (i.e. sur l'ensemble de la simulation) ou détaillée (i.e. sur des situations spécifiques) via l'effet de présence à l'aide d'un questionnaire [START_REF] Lessiter | A cross-media presence questionnaire : The itc-sense of presence inventory[END_REF]. Dans notre cas pour l'évaluation des comportements stratégiques, la notion de présence est trop large car elle comprend des éléments autres que comportementaux (qualité visuelle, sonore, etc.). Cependant des sousparties de l'effet de présence nous intéressent pour les comportements des agents. Il s'agit de : -la crédibilité comportementale qui évalue dans quelle mesure les utilisateurs interagissant avec l'agent pensent qu'ils observent un être pensant qui a ses propres croyances, des désirs et une véritable personnalité [START_REF] Lester | The persona effect : affective impact of animated pedagogical agents[END_REF], -la fidélité psychologique qui détermine dans quelle proportion la tâche simulée engendre chez l'utilisateur une activité et des processus psychologiques identiques à ceux de la tâche réelle [START_REF] Patrick | Training : Research and practice[END_REF]. C'est-à-dire dans quelle proportion le simulateur produit un comportement semblable à celui exigé dans la situation réelle [START_REF] Leplat | Simulation et simulateur : principes et usages. Regards sur l'activité en situation de travail : contribution à la psychologie ergonomique[END_REF]. Dans cet article, nous nous intéressons à la crédibilité comportementale et surtout à son évaluation quantitative.

Pour cela, nous mettons en place une simulation participative (au sens des systèmes mixtes où les humains remplacent certains agents). Dans ce contexte, l'évaluation est sensible à des phénomènes psychologiques comme l'irrationalité et l'incapacité d'expliquer ses jugements [START_REF] Javeau | L'enquête par questionnaire : manuel à l'usage du praticien[END_REF]. Aussi, cette évaluation n'explicite pas nécessairement les comportements manquants ni les défauts des comportements jugés non crédibles.

C'est pourquoi nous proposons de compléter ces études subjectives par un recueil d'analyse de données objectives.

Approche objective

L'approche objective est utilisée dans le domaine des systèmes multi-agents et se concentre sur la comparaison de données quantitatives [START_REF] Caillou | Description automatique de dynamiques de groupes dans des simulations à base d'agents[END_REF]. Elle a pour but de vérifier que le fonctionnement des agents est identique à celui observé dans la réalité et donc d'évaluer le réalisme de la simulation. L'évaluation objective se fait principalement au niveau macroscopique car les données sont plus aisées à obtenir [START_REF] Champion | Mécanisme de coordination multi-agent fondé sur des jeux : applicationa la simulation comportementale de trafic routier en situation de carrefour[END_REF][START_REF] Maes | Learning interface agents[END_REF] mais certain travaux, comme [START_REF] Caillou | Description automatique de dynamiques de groupes dans des simulations à base d'agents[END_REF], proposent d'utiliser des connaissances pour changer de niveau.

Pour la RV ou la simulation participative, la validation macroscopique est nécessaire, mais elle ne suffit pas pour valider les comportements des agents. En effet, un comportement collectif valide ne signifie pas que les comportement individuels qui le compose le soient. Ainsi, il faut une analyse au niveau microscopique or il existe encore peu de travaux sur l'évaluation objective au niveau microscopique, une des difficultés étant la complexité des données à étudier. L'approche subjective et l'approche objective se complètent en suivant deux moyens différents : expertise humaines et analyse des données brutes. A notre connaissance, il n'existe pas de technique d'analyse des comportements stratégiques en simulation alliant à la fois une validation de la crédibilité comportementale et de la similitude entre humains et agents virtuels.

Objectif et approche

Notre objectif est l'évaluation des agents d'une simulation multi-agents au niveau microscopique de façon pertinente pour la RV. Pour cela, nous utilisons une analyse à base de classe utilisant les deux types de données disponibles, objectives (via des traces) et subjectives (via des questionnaires).

Une analyse à base de classes

Recueil de données de questionnaires. La première approche est exploitée en vue d'une évaluation subjective des catégories de sujet. Elle est basée sur des questionnaires qui fournissent des scores d'échelles à partir des réponses quantitatives. Les questionnaires permettent de recueillir des données sur l'habitude comportementale dans la tâche demandée, sur la perception du dispositif et sur le rapport aux mondes virtuels. Nous obtenons alors des indications sur la typologie des sujets grâce à des scores calculés sur chaque questionnaire ainsi que sur chacune de leurs sous-échelles.

Recueil de données de simulations. Nous exploitons la seconde approche en vue d'une validation objective des comportements. Dans un premier temps, nous recueillons les données brutes (appelées traces) des comportements du sujet humain dans une simulation participative. Nous enregistrons les variables disponibles sur le sujet et son contexte (les agents et l'environnement de la simulation). Dans un second temps, nous répliquons les scénarios en remplaçant les sujets par des agents simulés et recueillons les mêmes traces. Les agents sont générés en faisant varier les paramètres d'entrée du modèle.

Ces deux phases nous fournissent un ensemble de traces de comportement de bas niveau (niveau opérationnel). Les traces, particulièrement dans le cas des sujets humains, sont bruitées et ne représentent qu'une instance d'un comportement au niveau tactique ou stratégique.

Classification. Pour généraliser les analyses de nos traces au niveau des comportements, nous proposons de passer par des catégories de comportements. Ces catégories servent d'abstraction aux traces en regroupant, au sein d'une même classe, les différentes traces représentatives d'un même comportement de haut niveau (niveau tactique/stratégique).

De façon à extraire les catégories, nous proposons d'appliquer des méthodes de classification. Le choix d'algorithmes supervisés nécessitant l'étiquetage par un expert d'un grand nombre de traces, il est préférable d'opter pour une approche non-supervisée. Ainsi nous pouvons traiter un nombre quelconque de traces, et ce indépendamment du domaine.

Démarche générale

Notre méthode commence par la passation des sujets sur le simulateur permettant le recueil des traces ainsi que des réponses aux questionnaires.

La méthode générale est donnée dans la figure 1. L'évaluation du comportement des agents se fait par deux moyens : l'étude de la corrélation entre les catégories de sujets (d'après les questionnaires) et les classes de comportements (issues des traces), et la comparaison des classes de comportements des sujets humaines et des classes de comportement des agents.

Pour l'étude de la corrélation entre les catégories de sujets et leurs comportements observés dans la simulation participative, nous avons besoin d'une part des réponses aux questionnaires relatifs à l'expérience en elle-même en vue de la classification des catégories de sujet, et d'autre part des traces obtenues en simulation pour la classification des comportements humains observés. L'étude de la composition des classes nous permet de rapprocher des catégories de sujets avec des classes de comportements. S'il y a une forte corrélation de la composition des classes de comportement et de catégories de sujet, cela veut alors dire que les classes de comportement ont un sens en terme de typologie du sujet.

Concernant la comparaison des classes de comportement des sujets et de celles des agents,

Cas d'étude

Afin de tester notre méthode, nous souhaitons évaluer le réalisme des comportements des agents du simulateur de trafic routier de l'IFSTTAR (voir la figure 2), en utilisant le simulateur de conduite ARCHISIM [START_REF] Champion | Behavioral road traffic simulation with archisim[END_REF]. Pour cela, nous faisons passer les participants de l'expérience sur un parcours contenant d'autres véhicules simulés.

Méthode de classification des catégories de sujet humain

Dans cette partie, nous détaillons les différents éléments de notre méthode de validation comportementale, ainsi que les outils utilisés.

Les questionnaires

Le comportement des sujets humains en réalité virtuelle est sujet à des biais induits par le dispositif. Nous nous intéressons donc au comportement du sujet dans sa tâche, mais aussi à son rapport au dispositif, de façon à contrôler l'expérience. De façon générale, pour les dispositifs de RV, nous proposons donc d'utiliser trois ensembles de questionnaires :

-un ensemble relatif à l'activité étudiée, permettant la comparaison ultérieure avec les comportements des agents, -un ensemble relatif au type de rapport du sujet avec les dispositifs d'immersion et -un ensemble relatif à l'expérience elle-même, pour évaluer le dispositif et la crédibilité comportementale des agents simulés. Nous utilisons de préférence des questionnaires validés par les chercheurs en sciences humaines, y compris dans leur version traduite en français. Cette validation prend en compte l'ordre des questions, la compréhension des questions par les sujets avec un vocabulaire non ambigu, l'absence d'induction dans les réponses par les questions, la pertinence des modalités de réponses et l'utilité de toutes les questions.

2. Les détails du modèle peuvent être trouvés dans [START_REF] Champion | Behavioral road traffic simulation with archisim[END_REF] Typologie de comportement. En premier lieu il est nécessaire de soumettre un questionnaire de comportement spécifique au domaine, effectué avant l'expérimentation, pour caractériser le comportement général du sujet dans l'activité étudiée. Dans le cadre de notre application au comportement de conduite, nous avons choisi le Driver Behavior Questionnaire (DBQ) [START_REF] Reason | Errors and violations on the roads : a real distinction[END_REF] dans sa version française [START_REF] Gabaude | Self-regulatory driving behaviour in the elderly : relationships with aberrant driving behaviours and perceived abilities[END_REF]. Évaluation du dispositif et de la crédibilité comportementale. Le premier questionnaire évalue l'effet de présence du sujet pendant l'expérience dans toutes ses composantes. Pour cela, nous utilisons le Presence Questionnaire (PQ) 5 , qui permet d'obtenir un score global ainsi que des scores sur les sous-échelles Réalisme, Possibilité d'agir, Qualité de l'interface, Possibilité d'examiner, Auto-évaluation de la performance, Auditif et Haptique [START_REF] Witmer | Measuring presence in virtual environments : A presence questionnaire[END_REF].

Dans le but de d'approfondir l'évaluation de la crédibilité comportementale de la présence, nous avons élaboré deux autres questionnaires : -un premier, général, ayant pour but d'évaluer la qualité ressentie des comportements des agents dans l'ensemble de la simulation. Il contient une affirmation par phase basée sur le modèle suivant : "Un « humain » peut 3. Ce questionnaire a été traduit et validé par le laboratoire de cyberpsychologie de l'Université du Québec en Outaouais [START_REF] Robillard | Validation canadiennefrançaise de deux mesures importantes en réalité virtuelle : l'immersive tendencies questionnaire et le presence questionnaire[END_REF].

4. N'existant pas de traduction à notre connaissance nous avons fait traduire le questionnaire par un expert-traducteur anglophone, puis vérifié la cohérence de la traduction.

5. Il a été traduit par le même laboratoire de cyberpsychologie [START_REF] Robillard | Validation canadiennefrançaise de deux mesures importantes en réalité virtuelle : l'immersive tendencies questionnaire et le presence questionnaire[END_REF].

avoir les comportements « C » effectués par les « agents » dans cette situation « S » ". Par exemple : "Des conducteurs humains peuvent avoir les comportements de conduite effectués par les conducteurs des véhicules simulés aux carrefours". -un second, spécifique, ciblant des éléments particuliers sur des situations précises s'étant présentées lors de la simulation. Il est soumis lors de la diffusion vidéo de la simulation que le sujet vient d'effectuer (appelée phase de rejeu) et contient une ou plusieurs questions par phase. Par exemple : dans une phase de suivi de véhicule, nous donnons la consigne "observer le véhicule devant" et demandons l'accord du sujet avec l'affirmation : "Un conducteur humain peut avoir le comportement de conduite effectué par le conducteur du véhicule roulant à faible vitesse devant vous dans cette situation de ligne droite".

Des données aux catégories

Nous obtenons à partir de ces questionnaires des données quantitatives que nous normalisons par un passage à une échelle numérique linéaire. Les scores des échelles des questionnaires sont ensuite calculés et normalisés entre 0 et 1. Une fois les données traitées, classifions les scores des sujets à l'aide d'un algorithme d'apprentissage. Comme nous l'avons vu auparavant, l'algorithme doit être non supervisé avec un nombre de classes libre, comme par exemple le X-moyennes basé sur le Bayesian Information Criterion [START_REF] Pelleg | X-means : Extending k-means with efficient estimation of the number of clusters[END_REF] ou les cartes auto adaptatives [START_REF] Kohonen | The self-organizing map[END_REF].

Nous avons choisi d'utiliser l'algorithme des K-moyennes en cascade. L'initialisation des classes est faite par Kmeans++ qui permet une meilleur répartition des centres des classes en fonction des données [START_REF] Arthur | k-means++ : The advantages of careful seeding[END_REF]. Le nombre de classes est choisi sur le Variance Ratio Criterion qui prend en compte les distances inter et intra classes [START_REF] Caliński | A dendrite method for cluster analysis[END_REF]. Nous appliquons alors l'algorithme de classification sur les réponses aux questionnaires pour obtenir des catégories de sujet conducteur.

5 Traitement des traces de comportement

Données recueillies

Concernant les données objectives de simulation, nous recueillons au cours de la simulation les traces de l'acteur principal (sujet humain ou agent), des agents du trafic en interaction et de l'environnement. Ces traces sont ensuite utilisées pour la classification des comportements tactiques et stratégiques. De façon à inclure les DTW comme nouvelles variables décrivant les acteurs, nous avons choisi de sommer les proximités pour chaque indicateur. En résulte pour chaque acteur principal un vecteur de similarité avec les autres acteurs principaux.

Classes de comportement

Nous classifions alors l'ensemble des données des acteurs principaux (normalisées entre 0 et 1) par le même algorithme d'apprentissage non supervisé que celui utilisé sur les réponses aux questionnaires. Nous obtenons ainsi les classes de comportement des acteurs principaux. Un premier passage de test sans véhicule simulé est effectué pour que le sujet s'habitue au fonctionnement du simulateur ainsi qu'au circuit. Ensuite, le sujet effectue le scénario dans son intégralité, en interaction avec les véhicules simulés. Les données sont alors enregistrées pour la phase de traitement.

✁✂✄ ☎✆✝✞ ✟✠ ✝✡ ☛ ☞☞☞ ✝✡ ✌ ✝✡ ☛ ✍ ☛☞✎✎ ☛☞✏✑ ☞☞☞ ☛☞✎✎ ✍ ☛☞✒☛ ✝✡ ✌ ☛☞✏✑ ☛☞✒☛ ✍ ✄✟✌✟✓✝✞✟✔✕✄ ☎✆✝✞ ✟✠ ✝✡ ☛ ☞☞☞ ✝✡ ✌ ✝✡ ☛ ✖ ✖ ☛ ☞☞☞ ✖ ✖ ☛ ✝✡ ✌ ☛ ☛ ✖ ✄✟✌✟✓✝✞✟✔✕✄ ✝✡ ☛ ☞☞☞ ✝✡ ✌ ✝✡ ☛ ✗ ✒ ✖ ☞☞☞ ✒ ✗ ✘ ✝✡ ✌ ✖ ✘ ✗
Avant la simulation, le DBQ est soumis. Après la simulation, le sujet rempli le questionnaire général de crédibilité comportementale et le PQ. Ensuite, un rejeu de la simulation est effectué, de façon à évaluer les phases unitairement. Lorsque l'ensemble du rejeu de la simulation est terminé, les autres questionnaires (ITQ, GEQ . . .) sont remplis par le sujet. Elle représente donc des conducteurs respectant le code de la route, mais faisant des erreurs potentiellement risquées. La deuxième catégorie obtient des scores moyens sur toutes les échelles. La troisième catégorie contient les scores minimaux sur chaque échelle exceptée Violation, c'est donc une catégorie de conducteurs prudents malgré un faible respect du code de la route. Enfin, la quatrième catégorie regroupe les scores maximaux de 5 sous-échelles sur 7. Elle regroupe donc une catégorie de conducteur à fort risque d'accidents.

Le même algorithme appliqué sur les indicateurs et les DTW issus des traces de la simulation donne 4 classes identiques (contenant les mêmes sujets) à celles du DBQ. L'analyse visuelle des enregistrements nous permet de connaître les caractéristiques de chaque classe sur le scénario donné. Dans le même ordre que dans le paragraphe précédent : -les conducteurs de la première catégorie ont une vitesse inférieure à la limitation avec des oscillations latérales importantes lors des dépassements, -ceux de la seconde catégorie ont une vitesse stable entre 130 et 140Km/h, -ceux de la troisième catégorie ont une vitesse stable proche de la limitation de vitesse, qui diminue légèrement à l'approche de la zone de trafic congestionné, -et ceux de la quatrième catégorie présentent de fortes accélérations et décélérations, amenant la vitesse à varier entre 75Km/h lors d'un freinage brusque et 150Km/h avant et après la zone de trafic congestionné. Ces résultats montrent que les classes de comportement, produites à l'aide d'un algorithme non supervisé, ont un sens en terme de typologie du conducteur. Ceci tend à valider l'approche retenue d'utilisation de classes pour étudier les comportements tactiques à partir de traces.

Conclusion & perspectives

Cet article présente une méthode d'étude de la crédibilité comportementale des agents grâce à une expérimentation en réalité virtuelle. Cette validation a pour originalité de coupler une analyse subjective de la crédibilité comportementale par des questionnaires issus des sciences humaines et une analyse objective des capacités des agents. Cette analyse s'appuie sur une classification des comportements, qui permet d'obtenir des catégories de comportements de plus haut niveau que les traces. La comparaison de ces classes de traces humaines et agents permettent une évaluation objective de la qualité du modèle à reproduire les comportements humains. En parallèle, les questionnaires permettent de s'assurer que nos classes de traces humaines ont un sens en terme de typologie du sujet dans sa tâche.

Notre méthode de validation a été appliquée à la simulation de trafic routier. Cette expérience a montré que la méthodologie est utilisable pour des EVs mixtes complexes, et qu'il est possible d'extraire des comportements stratégiques à partir des traces via notre abstraction. La taille de l'échantillon va être augmentée pour vérifier la robustesse de la méthode.

Plusieurs pistes restent à explorer. Sur la classification, l'évaluation des résultats de plusieurs algorithmes doit permettre de mieux juger de l'adaptation de ceux-ci. Pour cela, utiliser les résultats de la première comparaison (typologie de comportement par questionnaire et classes de comportement observé) permet de choisir l'algorithme le plus pertinent selon l'application.

Certains travaux ont pour but la génération automatique de modèles d'agent à partir des observations de comportements humains [START_REF] Saffar | Conception de simulations multi-agents : vers une modélisation basée sur les observations des comportements réels[END_REF]. Ils ne répondent pas à notre besoin de validation de la crédibilité comportementale. Cependant, ils proposent des méthodes de clustering de comportement [START_REF] Mathieu | From real purchase to realistic populations of simulated customers[END_REF][START_REF] Lacroix | Formalizing the construction of populations in multi-agent simulations[END_REF] pouvant s'appliquer à nos données et sont donc à étudier.

Par ailleurs, une deuxième expérience est prévue pour confronter des observateurs humains externes aux traces humaines et simulées via la notation des enregistrements. Elle permettra d'évaluer la crédibilité des traces simulés et humaines sur la même situation.

FIGURE 2 -

 2 FIGURE 2 -Dispositif du simulateur de conduite avec 3 écrans, volant, boite de vitesse et pédalier.

FIGURE 3 -

 3 FIGURE 3 -Scénario : phase de trafic ralenti sur autoroute

  Tendance et habitude d'immersion. Pour contrôler si le rapport à l'immersion du sujet a un impact sur son comportement, nous souhaitons évaluer comment le sujet réagit face aux techniques d'immersion mises en oeuvre et donc sa capacité à se plonger dans l'environnement virtuel. Pour cela nous utilisons un questionnaire de propension à l'immersion : l'Immersive Tendencies Questionnaire (ITQ) de Witmer et Singer 3 qui se décompose en sous-échelles focus, implication, émotions et jeu [29]. Nous prenons également en compte l'habitude aux immersions. Pour cela nous approfondissons l'échelle jeu de l'ITQ qui ne contient que deux items par un questionnaire d'implication dans les jeux vidéo pour évaluer plus finement la typologie de l'engagement du joueur. Nous utilisons le Game Engagement Questionnaire (GEQ) 4 qui permet de définir le degré d'engagement du sujet selon plusieurs axes : Absorption, Flow, Presence et Immersion [3].

FIGURE 5 -

 5 FIGURE 5 -Transformation des DTW : 1) calcul des DTW entre chaque acteur principal ap pour chaque variable Var i ; 2) obtention par le maximum d'une matrice de similarités par variable ; 3) addition des matrices de similarités.

FIGURE 4 -

 4 FIGURE 4 -Attributs pour la classification : moyenne et écart type puis données agrégées et enfin indicateurs des experts

FIGURE 6 -

 6 FIGURE 6 -Classification (c) des comportements agents (a) et humains (s). Nous observons 3 types de classes : mixtes, uniquement agents et uniquement humains

6 .

 6 En tenant compte du nombre d'agents et du nombre d'humains appartenant aux classes.

  Méthode d'analyse et d'évaluation de comportements. Les cylindres indiquent les données recueillies puis traitées, les 3 rectangles correspondent aux classifications et les cercles aux classes obtenues.

			Évaluation
	Abstractions de traces de comportements	Classification comportements humains et agents	Classes humain	Classes agent
	Expérience sur simulateur	Classification comportements humains
	Réponses aux questionnaires	Classification catégories sujets humains	Catégories humain
	FIGURE 1 -L'étude des classes ainsi produites et de leur
	recouvrement permet l'analyse des comporte-
	ments simulés. Nous pouvons alors remarquer
	trois catégories de classes :
	-celles contenant à la fois des acteurs princi-
	paux (sujets humains et agents). Cette catégo-
	rie correspond aux comportements de haut ni-
	veau qui sont correctement reproduits par les
	agents,
	-celles composées uniquement d'agents simu-
	lés. Elle correspond aux comportements pro-
	duits uniquement par les agents, et sont donc
	soit des erreurs de simulation (les agents
	produisent des comportement n'existant pas),
	soit dûs à un échantillon de sujets trop faible,
	-celles composées uniquement de sujets hu-
	mains qui correspond aux comportements
	n'ayant pas été répliqués par les agents, et
	sont donc soit des manques dans le mo-
	dèle agent, soit l'expression d'un échantillon
	d'agents trop faible sur l'espace des para-
	mètres.
	Au final, ces deux moyens nous permettent
	de comparer les classes de comportement des
	agents avec celles des sujets, qui sont corrélées
	elles-même à leur catégorie.

nous générons des traces pour les mêmes situations que pour les sujets en les remplaçant par des agents. Les agents sont instanciés en faisant varier les paramètres d'entrée du modèle

1

. Nous pouvons alors utiliser les traces des sujets et des agents pour effectuer une classification des comportements de tous les acteurs principaux (humains et agents).

  Cela nous renseigne sur le taux de comportement humain non reproductible par l'agent, c'est donc le pourcentage de comportements manquant. -Enfin, le rapport entre le nombre de classes contenant uniquement des agents et le nombre de classes contenant un agent est de 0.4 (effectif : 0.54). Il est interprété comme un score d'erreur des agents. De plus, ces premiers résultats doivent être approfondis et vérifiés sur un panel plus important.

	pouvons faire les interprétations suivantes :
	-le taux du nombre de classes mixtes par rap-
	port au nombre de classes contenant un hu-
	main est de 0.75 (et en terme d'effectif 6 de
	0.86). Ces taux donnent des indications sur
	le pourcentage de comportement que l'agent
	peut reproduire, c'est-à-dire la capacité du
	modèle à reproduire l'humain.
	-le taux du nombre de classes contenant uni-
	quement des humains par rapport au nombre
	de classes mixtes est ici de 0.25 (effectif :
	0.4).
	Trois types de classes
	de comportement sont observés :
	-trois classes mixtes contiennent humains et
	agents. La première (c2), composée de 3 su-
	jets et 1 véhicule simulé, correspond à la ca-
	tégorie de conducteur respectant le code de la
	route mais faisant des erreurs. Les deux autres
	correspondent à la catégorie de conducteur
	moyen (c3 : 1 sujet et 3 agents) et à celle de
	conducteur à risque (c5 : 1 sujet et 2 agents),
	-une classe c4 est uniquement composée de
	2 sujets humains. Il s'agit de la catégorie de
	conducteurs prudents minimisant les risques,
	-deux classes sont uniquement composées
	d'agent (c1 et c6) : la première contient 2 vé-
	hicules simulés et la seconde 5. L'observation
	de ces deux classes, nous montre que celles-
	ci contiennent les deux véhicules simulés qui
	ont hésité et ralenti fortement lors du dépas-
	sement des poids lourds, et les 5 véhicules si-
	mulés qui n'ont pas su résoudre rapidement la
	situation de zone congestionnée.
	Interprétation. Sous les hypothèses que notre
	expérimentation présente un panel exhaustif des
	situations de conduite, que les agents générés
	regroupent l'entièreté de leurs capacités et que
	la population de sujets est représentative, nous

Les paramètres sont la normativité de l'agent, sa vitesse cible, son expérience, etc.

Résultats & discussionCatégories de conducteurs et classes de comportements. L'algorithme de classification est appliqué sur les données des sous-échelles du questionnaire de comportement de conduite DBQ.


Shirley Hoet
email: shirley.hoet@lip6.fr

Nicolas Sabouret
email: nicolas.sabouret@limsi.fr

Un modèle de mémoire pour l'apprentissage de communication dans un SMA

Keywords: Mémoire, communication, apprentissage Memory, Communication, Learning

and research institutions in France or abroad, or from public or private research centers.

Introduction

Dans un système multi-agents, il est souvent nécessaire que les agents communiquent pour apprendre à agir [START_REF] Tan | Multi-agent reinforcement learning : Independent vs. cooperative agents[END_REF][START_REF] Xuan | Communication decisions in multi-agent cooperation : Model and experiments[END_REF]. La communication directe (c'est-à-dire l'envoi de message avec intention de communiquer) permet ainsi aux agents de récupérer les informations qui leur manquent ou de se coordonner lorsque cela est nécessaire. Tout particulièrement les messages de type commande (request) qui permettent de déléguer des actions et les messages de type contrôle (query) qui permettent de demander des informations aux autres agents. Nous nous intéressons particulièrement à ces messages qui sont au coeur de la communication SMA [START_REF] Ferber | Les systèmes multi-agents[END_REF].

Dans le cas où les agents sont autonomes, des travaux ont montré que les agents devaient non seulement communiquer pour apprendre à agir mais aussi apprendre à communiquer [START_REF] Melo | Learning of coordination : exploiting sparse interactions in multiagent systems[END_REF][START_REF] Kasai | Learning of communication codes in multi-agent reinforcement learning problem[END_REF]. En effet, les agents doivent apprendre dans quel contexte il est nécessaire de communiquer et surtout quels messages ils peuvent envoyer pour résoudre leurs problèmes. Toutefois, les travaux du domaine font l'hypothèse que les agents ont des connaissances partagées sur le problème à résoudre (système fortement couplé) ou qu'ils s'exécutent de manière synchrone [START_REF] Melo | Learning of coordination : exploiting sparse interactions in multiagent systems[END_REF][START_REF] Kasai | Learning of communication codes in multi-agent reinforcement learning problem[END_REF]. Or dans le cas de systèmes réels tel que [START_REF] Canu | Collective decision-theoretic planning for planet exploration[END_REF], les agents évoluent généralement dans un système asynchrone, faiblement couplé et partiellement observable. De plus ils peuvent être hétérogènes dans le sens où ils ne partagent pas les mêmes fonctionnalités. Dans ce contexte, apprendre à communiquer devient un problème difficile à résoudre.

Premièrement, les agents n'ont pas d'informations sur les capacités et les connaissances des autres agents : ils ne peuvent prévoir les effets des messages qu'ils envoient sur les agents qui les reçoivent. De ce fait, il n'est pas possible d'utiliser des outils de planification pour déterminer les messages à utiliser et quand les envoyer pour résoudre un problème donné. L'agent doit apprendre par essai-erreur, par exemple en utilisant de l'apprentissage par ren-forcement pour découvrir quand et comment utiliser ses messages. Deuxièmement, lors de la délégation de tâche (request), chaque commande peut avoir un temps d'exécution différent qui ne peut pas être anticipé par l'agent demandeur. L'agent doit donc apprendre à déterminer quand une commande est terminée et quand il peut entamer les actions qui dépendent de cette terminaison. Les agents doivent donc apprendre à attendre en plus d'apprendre à communiquer.

Troisièmement, l'environnement étant partiellement observable et les agents n'ayant pas de connaissances sur les autres agents, ils ne peuvent pas prédire quelles sont les informations qui leur manquent.

Enfin, l'envoi de messages entre agents peut être une opération coûteuse, par exemple dans les réseaux mobiles ad-hoc. Les agents doivent donc apprendre à utiliser la communication avec parcimonie.

Pour gérer l'ensemble de ces contraintes, nous avons proposé dans [START_REF] Hoet | Apprentissage par renforcement d'actes de communication dans un contexte multiagent[END_REF] d'utiliser des algorithmes d'apprentissage par renforcement spécifiques pour mettre à jour leurs croyances. Nous avons aussi montré qu'il était nécessaire de mémoriser les communications comme un élément de l'état de l'agent pour l'utiliser dans l'algorithme d'apprentissage.

C'est pourquoi, dans cet article, nous présentons un modèle de mémoire pour l'apprentissage de communication autour des messages de commande (request) et de contrôle (query). La section suivante présente les modèles de mémoire existants et leurs limites. La section 2 présente notre modèle d'agents et notre mécanisme de mémorisation des messages. La section 3 présente une évaluation de notre modèle et montre que nos agents sont capables d'apprendre des politiques plus rapidement que d'autres algorithmes de gestion de la mémoire. Enfin, nous discutons les perspectives de nos travaux dans la section 4.

Travaux existants

Il existe trois types de modèle de mémoire dans la littérature. Ces modèles se différencient par le type d'informations qu'ils mémorisent ainsi que par leur mécanisme de mise-à-jour.

Les mémoires temporelles stockent les N dernières observations et actions de l'agent, avec N la taille maximale de la mémoire. La taille de la mémoire nécessaire pour effectuer l'apprentissage est déterminée en utilisant un algorithme incrémental qui permet d'augmenter de 1 en 1 cette taille durant l'apprentissage. Cette taille pouvant être très grande et donc augmenter de façon conséquente l'espace d'état de l'agent, les travaux de [START_REF] Dutech | Un algorithme d'apprentissage par renforcement pour les processus décisionnels de Markov partiellement observés : apprendre une extension sélective du passé[END_REF][START_REF] Kachites | Reinforcement learning with selective perception and hidden state[END_REF] se sont intéressés à déterminer de manière heuristique la meilleure taille de mémoire pour chaque état initial de l'agent. Cependant, ces modèles requièrent que l'agent mémorise les N dernières informations pour pouvoir prendre en compte une action effectuée il y a N pas de temps, même si seule cette action est pertinente. Cela conduit à un espace d'état à explorer k N -1 fois plus grand, lorsque k est le nombre d'actions possibles pour chacune des N -1 actions non pertinentes.

La mémoire de travail [START_REF] Michael | Learning to use working memory in partially observable environments through dopaminergic reinforcement[END_REF][START_REF] Luca | Adaptative agents with Reinforcement Learning and Internal Memory[END_REF] est une mémoire composées d'un nombre de cases prédéfinies à l'avance. Une case peut stocker une action ou une observation passée de l'agent [START_REF] Michael | Learning to use working memory in partially observable environments through dopaminergic reinforcement[END_REF] ou un encore un bit [START_REF] Luca | Adaptative agents with Reinforcement Learning and Internal Memory[END_REF]. Pour déterminer ce que la mémoire doit contenir, les auteurs proposent d'utiliser l'apprentissage par renforcement. Ils définissent ainsi des actions pour chaque case permettant d'effacer le contenu de la case, de le remplacer par une valeur donnée ou de la maintenir. Durant l'apprentissage de ses actions, l'agent effectuera simultanément autant d'apprentissage pour déterminer comment modifier sa mémoire qu'il existe de case dans sa mémoire. La limite principale de ce modèle est la taille de la mémoire qui est définie a priori. Elle ne doit pas être trop petite afin de stocker les informations nécessaires à l'apprentissage de l'agent, mais elle ne doit pas non plus être trop grande afin de limiter le nombre d'états créés durant l'apprentissage.

La mémoire cognitive [START_REF] Nuxoll | Extending cognitive architecture with episodic memory[END_REF][START_REF] Zilli | Modeling the role of working memory and episodic memory[END_REF] est un modèle de mémoire complexe basé sur l'utilisation d'une mémoire épisodique couplée à une mémoire de travail. La mémoire épisodique stocke l'ensemble des expériences de l'agent c'est un historique complet des actions et des observations de l'agent. Du fait que la mémoire épisodique est potentiellement de taille infinie, elle ne peut être utilisée telle quelle pour l'apprentissage. L'agent doit extraire de cette mémoire les informations nécessaires et les stocker dans sa mémoire de travail qui est utilisée pour l'apprentissage. La limite de ce modèle est qu'il n'existe pas de mécanisme d'extraction utilisable sur des problèmes réels.

Chaque structure de mémoire présente des avantages et des inconvénients dans le contexte de l'apprentissage de communication. C'est pourquoi, dans cet article, nous proposons un autre modèle, fondé sur une combinaison de la mémoire de travail et de la mémoire temporelle. Cependant du fait que cette durée dépend de l'état des agents (qui détermine les actions que l'agent effectue), nous considérons qu'elle est constante pour un état s (Agt) donné de l'agent.

Dans le cas de l'agent apprenant Agt l , une seule action est exécutée par cycle d'exécution comme le nécessite les algorithmes d'apprentissage par renforcement. De plus cette action sera choisie à l'aide de l'algorithme d'apprentissage contrairement aux autres agents. Enfin, un cycle d'exécution correspond à un pas de temps d'apprentissage. Ce pas de temps est local à l'agent apprenant est ne correspond pas au pas de temps d'un autre agent du système. En effet, chaque agent a une durée d'éxecution qui lui est propre. L'agent apprenant Agt l possède aussi une action supplémentaire : l'action wait. Cette action est particulière car elle n'a pas d'effets que ce soit sur l'environnement ou sur l'agent apprenant. Lorsque l'agent choisit d'exécuter l'action wait durant un cycle d'exécution, il n'effectue ni action propre ni communication. Ainsi cette action permet à l'agent d'apprendre à ne rien faire. Cette action est nécessaire pour que l'agent est la possibilité d'apprendre à attendre les effets des messages qui le nécessitent. En effet, la fin d'un message du point de vue de l'agent est déterminée par l'arrivée d'un message réponse. Or dans le cas des commandes (envoi d'un message request), la réception d'un message agree spécifiant que l'agent a accepté de recevoir la commande ne signifie pas que l'action demandée a été effectivement exécutée. Or dans certains cas l'agent a besoin que les effets de la pré-cédente commande soient avérés pour pouvoir effectuer une autre commande ou exécuter une action. Dans ce cas l'agent a donc besoin d'attendre. De plus l'agent ne connaissant pas les effets de ses commandes, il ne sait pas combien de temps il doit attendre. Il est donc nécessaire que l'agent apprenne à attendre.

Besoin

Pour apprendre à communiquer et plus exactement apprendre à commander via un message request et contrôler via un message query, un agent a besoin de mémoriser un certain nombre d'éléments.

Premièrement, l'agent doit pouvoir mémoriser les commandes précédemment envoyées. En effet, le système étant asynchrone les effets d'une commande peuvent être différés du point de vue de l'agent apprenant. Or le système étant faiblement couplé, l'agent ne connaît pas ses effets. L'agent ne peut donc pas tout simplement attendre d'observer les effets de sa précédente commande car il ne les connaît pas avant d'en envoyer une nouvelle. Par conséquent, l'agent peut envoyer une commande avant que la précédente soit terminée et ainsi observer au même instant des effets dus à différentes commandes. C'est pourquoi il est nécessaire que l'agent mémorise les commandes qu'il a précédemment envoyée. Cependant certaines commandes peuvent ne pas aboutir, c'est le cas par exemple lorsque l'agent qui a reçu la commande refuse de l'exécuter. Dans ce cas il n'est pas nécessaire de mémoriser la commande envoyée. D'autre part, un agent peut accepter d'effectuer une commande de différentes manières. Il peut accepter de le faire maintenant ou plus tard ou encore il peut demander à l'agent de lui "rappeler" la commande à effectuer dans un certain nombre de pas de temps. Mémoriser simplement la commande envoyée fera perdre cette information, c'est pourquoi nous pensons qu'il est nécessaire de mémoriser les réponses des commandes plutôt que les commandes elles-même et de ne mémoriser ces réponses seulement quand celles-ci sont du type "acceptation". Pour cela nous faisons l'hypothèse que l'agent possède une fonction rew(p) où p est le performatif de la réponse reçue qui renvoie une valeur positive si le message de performatif p est considéré comme positif pour l'agent et une valeur négative dans le cas contraire.

Cependant mémoriser les réponses n'est pas suffisant. En effet que ce soit des réponses re-latives à des commandes ou à de la demande d'information, l'agent peut avoir parfois besoin de savoir quand il a reçu cette réponse. Ainsi, si un agent cuisinier délègue à un autre une action comme allumer la plaque, l'agent a besoin de mémoriser quand cette commande a eu lieu. Ceci lui permettra en autre de savoir quand son diner est prêt et aussi de ne pas le brûler. De même la date est nécessaire pour les informations stockées par l'agent. Un agent a besoin généralement de mémoriser depuis combien de temps il détient une information afin de déterminer si celle-ci est toujours vrai et par conséquent s'il a besoin de renvoyer un message permettant de la mettre à jour. D'autre part, il peut-être plus compacte de mémoriser qu'un agent n' a pas encore envoyé un message m. Imaginons que dans un état s l'agent doit envoyer le message m s'il ne l'a pas encore fait et sinon il doit envoyer un message m . si l'agent ne mémorise que les messages qu'il a envoyé dans le passé alors il va avoir besoin de beaucoup de mémoire pour agir correctement dans l'état s. En effet avec x crans de mémoire, il sait s'il a ou non effectué m il y a x pas de temps, mais il ne sait pas s'il a envoyé le message m il y a plus de x pas de temps. Il serait donc plus compact de mémoriser les messages que l'agent n'a pas envoyé.

Enfin, il est important qu'un agent puisse mémoriser les phases où il n'envoie pas de commande et est en train d'attendre en utilisant l'action wait. Plus exactement, il doit mémoriser les périodes d'attentes afin d'apprendre s'il doit encore attendre ou s'il peut envoyer une commande. Cependant la mémorisation de cette période d'attente n'est pertinente que dans les cas où l'agent est effectivement en train d'attendre. Dans les autres cas, c'est-à-dire mémoriser que l'agent a attendu puis envoyer la commande B puis la commande C, la période d'attente n'est pas utile pour l'apprentissage de l'agent.

Pour résumer, l'agent a besoin de mémoriser les réponses "positives" des messages qu'il a envoyé et la date à laquelle il les a envoyé, les messages qu'il n'a pas encore envoyés ainsi que ses périodes d'attentes.

Notre modèle de mémoire

La structure de notre mémoire est décrite à un instant t par un (n+1)-uplet m t = m 1 t , ..., m n t , w où : -n est le nombre total de messages que peut envoyer l'agent ;

-∀k ∈ [1, n], m k t = delai, answer tel que answer = p(c) contienne la dernière réponse positive (rew(p) > 0) au k-ème message de l'agent apprenant. delai ∈ [0, T m] ∪ ∞ correspond au nombre de pas de temps écoulés depuis que la réponse a été reçue, où ∞ s'il est supérieur à la limite T m. delai = 0 signifie que l'agent n'a encore jamais envoyé de k-ème message ; -w ∈ N + stockant les durées d'attente de l'agent. Notre modèle de mémoire permet donc à la fois de stocker les réponses de notre agent et les dates via la variable delai comme l'illustre la figure 1. Lorsque l'agent n'a pas effectué une action alors sa variable delai est à 0. Ainsi, l'agent peut vérifier rapidement qu'il n'a pas encore effectué l'action.

Pour limiter le nombre de configurations possibles pour la mémoire, et donc faciliter la convergence de l'apprentissage, nous avons choisi de borner le delai par une valeur T m. La valeur ∞ permet alors à l'agent de mémoriser qu'il a reçu une réponse, même si la date exacte n'est pas précisée.

Mise-à-jour de la mémoire

La mémoire de l'agent est mise à jour à chaque cycle d'apprentissage. Cette mise à jour est constituée de trois étapes.

La première va consister à incrémenter de 1 la valeur de la variable delai de chaque case m k t . Cette action permet donc à l'agent de mémoriser le délai exact écoulé depuis le dernier envoi de chaque message m k . Dans le cas où la valeur de délai dépasse T m, elle est remplacé par le symbole ∞ signifiant « j'ai reçu cette réponse il y a longtemps ».

La deuxième consiste à modifier la case w. Si l'agent vient d'effectuer une action wait alors la valeur contenue par w est augmentée de 1. Sinon, l'agent n'est pas dans une période d'attente par conséquent la case w est remise à 0.

La troisième étape consiste à mémoriser la dernière réponse reçue par l'agent, lorsque la dernière action effectuée par l'agent est l'envoi d'un message m et que la réponse reçue r = p, c est telle que rew(p) > 0. Alors le contenu de la case m k t correspondant au message m prendra la valeur r, 1 .

Si n est le nombre de messages que l'agent peut envoyer, la mise-à-jour consistera en θ(n) opérations. Cependant comme nous le verrons, l'algorithme d'apprentissage nécessite de stocker et d'apprendre θ(n * (T m+1) n ) valeurs correspondant à l'espérance de récompense obtenue par l'agent pour chaque couple (s, a) où s ∈ S (Agt l ) est un état et a ∈ A (Agt l ) une action. Par conséquent, le stockage de la variable délai et l'opération de mise-à-jour sont négligeables en terme de complexité dans ce processus.

Algorithme d'apprentissage

Notre algorithme d'apprentissage a pour but de déterminer une politique d'action et de communication en utilisant le modèle de mémoire que nous avons détaillé à la section 2.3. Dans cette section nous avons montré que le nombre de configurations possibles de notre mémoire dépendait de la valeur de la variable T m qui borne la valeur maximale que peut prendre la variable delai. La difficulté dans ce cas est de déterminer la meilleure valeur de la variable T m permettent à l'agent d'apprendre à agir et à communiquer. C'est pourquoi nous proposons un algorithme d'apprentissage incrémental qui va progressivement augmenter la valeur de T m et effectuer pour chaque valeur de T m un cycle d'apprentissage par renforcement. Notre algorithme est décrit brièvement par la figure 1. Dans la suite de cette section, nous expliquons plus en détails les quatre points importants de notre algorithme : -l'utilisation de l'algorithme du Q-Learning pour apprendre à communiquer (représenté par la fonction Ql dans l'algorithme 1) ; -l'utilisation d'un ensemble d'états restreint de l'agent sur lequel appliqué le Q-Learning(noté S l ) ; -l'utilisation d'une heuristique pour construire l'ensemble d'états S l (représenté par la fonction detection) ; -l'arrêt de notre algorithme.

Algorithme 1 Algorithme incrémental utilisant notre modèle de mémoire pour l'apprentissage de la communication. Entrées: γ, , N e , T e , E, T, T d , N

S l ← ∅ T m ← 1 R 1 , Q, ∆Q, ν, S l ← Ql(T m, γ, N e , T e , E, T, T d , S l ) S * l ← detection(S l , Q, ∆Q, ν, N ) R 0 ← 0 tant que |R 1 -R 0 | < faire R 1 ← R 0 R 1 , Q, ∆Q, ν, S l ← Ql(T m, γ, N e , T e , E, T, T d , S l ) S * l ← detection(S l , Q, ∆Q, ν, N ) T m ← T m + 1 fin tant que pour s ∈ S l faire π(s) ← arg max a∈A Q(s, a)
fin pour Sorties: π Q-Learning. Le Q-Learning [START_REF] Christopher | Learning from delayed rewards[END_REF] est un algorithme d'apprentissage par renforcement qui repose sur l'utilisation d'une fonction de valeur où α t ∈ [0, 1] est le taux d'apprentissage et γ est le facteur d'actualisation (il permet de modéliser les préférences de l'agent en matière de récompense. Si l'agent préfère une récompense immédiate γ sera proche de 0, si au contraire toutes les récompenses sont importantes pour lui γ tendra vers 1).

Q : E * A -→ R où Q(e,
La stratégie de sélection utilisée pour l'action à exécuter est la température de Boltzman où la probabilité de sélectionner l'action a dans l'état e est égale à :

P (a t = a|e t = e) = e Q(e
m 1 = m 1 1 , ..., m n 1 , w 1 et m 2 = m 1 2 , ..., m n 2 , w 2 . Nous considérons que m 1 généralise m 2 si et seulement si : -w 1 = w 2 ; -∀i ∈ [1, n], m i 1 .answer = m i 2 .answer ; -∀i ∈ [1, n], m i 1 .delai = ∞, m i 1 .delai = m i 2 .
delai Par extension, nous définissons la relation de généralisation entre deux états. Soit deux états

s 1 = Ω 1 , D 1 , m 1 et s 2 = Ω 2 , D 2 , m 2 , s 1 gé- néralise s 2 si et seulement si : -Ω 1 = Ω 2 -D 1 = D 2 -m 1 généralise m 2
La construction de S l se fait de manière incrémentale : à T = 0, T m = 1 et S l = ∅ L'algorithme effectue un cycle d'apprentissage. Durant l'apprentissage, chaque nouvel état s t / ∈ S l est automatiquement ajouté à l'ensemble S l et l'agent effectue donc son apprentissage sur l'ensemble S (Agt l ) . Une fois l'apprentissage terminé, l'algorithme détecte l'ensemble des états S * app ⊂ S l qui ont besoin d'un T m plus grand. Pour cela l'algorithme utilise la notion d'ambiguïté telle que définie par [START_REF] Dutech | Un algorithme d'apprentissage par renforcement pour les processus décisionnels de Markov partiellement observés : apprendre une extension sélective du passé[END_REF] que nous présentons ci-dessous. Si un état est considéré comme ambigu alors il est ajouté à l'ensemble S * app et il est supprimé de l'ensemble S l ; à T = 1, T m = T m + 1 . L'algorithme effectue un nouvel apprentissage. À chaque nouvel état rencontré s t / ∈ S l , l'algorithme détermine l'état s l ∈ S l qui généralise s t . Si s l existe alors l'agent apprend à agir en fonction de s l . Sinon, l'état s t est ajouté à l'ensemble S l . L'agent effectue donc son apprentissage à la fois sur des états où T m = 1 et des états où T m = 2. Une fois l'algorithme d'apprentissage terminé, l'ensemble des états S * app ⊂ S l est de nouveau détecté et supprimé de l'ensemble S l ; à T=N, T m = N + 1 . L'algorithme effectue de nouveau un cycle d'apprentissage et continue à augmenter l'ensemble d'états S l en augmentant la valeur de T m dans les états qui le nécessitent. Cet ensemble d'états contient alors des états s l ayant une variable delai = T m mais aussi des états où la variable delai la plus grande < T m.

Detection des états ambigus. La détection des états ambigus reposent sur les travaux de [START_REF] Dutech | Un algorithme d'apprentissage par renforcement pour les processus décisionnels de Markov partiellement observés : apprendre une extension sélective du passé[END_REF]. Dans ces travaux les auteurs proposent une heuristique, pour déterminer si un état s l a besoin de mémoire, fondée sur trois critères : une convergence plus lente, i.e. la valeur de la fonction de Q-Value Q(s l , a) converge plus lentement pour toutes les actions a ; le nombre de mises à jour, i.e. un élément a plus de chance d'être ambigu si son nombre de mises à jour est grand ; l'ambiguïté dans les actions, i.e. l'action optimale d'un état n'est pas clairement définie car les valeurs de Q des deux meilleures actions sont très proches.

L'ambiguïté d'un état s se définit donc de la manière suivante :

amb(s) = 1 3 (rg s [up(s)] + rg s [ 1 Z a∈As
∆q a ] + rgD s [q a1 -q a2 ]) où :

a 1 et a 2 représentent les deux meilleures actions dans l'état s (elles maximisent la valeur Q(s,a)) ; -q a = Q(s,a) et ∆q a est la dernière modification apportée à q a ; -Z est le nombre de valeur Q(s,a) de l'état s ; -rg s (x) (respectivement rgD s (x)) renvoie la position de l'état s si on ordonne tous les états dans l'ordre croissant(respectivement décroissant) en fonction de x. Cette fonction établit donc le taux d'ambiguïté d'un état s l . Une fois ce taux calculé pour chaque élément de l'ensemble S l , il est alors possible de déterminer les N 2 plus ambigus.

Arrêt de l'algorithme. Comme nous l'avons expliquer précédemment, pour déterminer la meilleure taille de T m nous utilisons un algorithme incrémental qui augmente la valeur de T m de 1 en 1. À chaque incrémentation de la valeur de T m, un cycle d'apprentissage est effectué par l'agent. Ce cycle consiste à effectuer l'algorithme du Q-Learning durant N e expériences. Comme T m peut-être insuffisante pour apprendre au début, nous limitons à T e le nombre de cycles d'exécution que peut effectuer l'agent durant une expérience. Lorsque l'agent a effectué T e cycles d'exécution, l'expérience est arrêtée et l'agent reçoit une récompense négative. Si ce cas se reproduit E fois, alors nous considérons que la valeur de T m est insuffisante et qu'il n'est donc pas nécessaire de continuer l'apprentissage. Nous stoppons l'apprentissage de l'agent et augmentons T m. Ainsi nous limitons la durée des cycles d'apprentissage où l'agent n'arrive pas à apprendre dans le but d'augmenter la vitesse de convergence de notre algorithme vers une solution.

Évaluation

Nous avons testé notre modèle de mémoire sur un problème d'apprentissage mono-agent dans un SMA asynchrone, faiblement couplé et partiellement observable. Nous présentons dans une première partie les caractéristiques du problème étudiés. Puis nous présentons nos résultats.

où N est déterminé expérimentalement

Problème

Dans cet exemple, le système est composé de trois agents : l'agent apprenant L, l'agent A et l'agent B. L'agent A possède deux actions : l'action creerX et l'action charger_batterie. L'action charger_batterie est un processus que l'agent peut exécuter s'il n'est pas en train d'effectuer une autre action. L'agent A a une probabilité p = 1/2 de choisir cette action. L'action creerX est une commande par conséquent l'agent A l'exécute seulement lorsqu'il reçoit un message request(creerX) et à condition qu'il n'y a pas de ressource X déjà présente dans l'environnement. Lorsque l'agent reçoit un message request(creerX), il peut y répondre de trois manières différentes en fonction de son état et de l'action qu'il est potentiellement en train d'exécuter : -via un message agree(creerX) lorsqu'il n'y a pas de ressources X dans l'environnement et qu'il n'est pas en train d'exécuter une autre action ; -via un message agree(creerX ;plus tard) lorsqu'il n'y a pas de ressources X dans l'environnement et qu'il est en train d'exécuter l'action charger_batterie ; -via un message impossible(creerX) lorsqu'il est déjà en train d'effectuer l'action creerX ou que la ressource X est déjà présente dans l'environnement. L'agent B possède une seule action : l'action creerY qui permet de transformer une ressource X en ressource Y . L'agent B peut exécuter l'action creerY si et seulement si il reçoit une commande request(creerY) et qu'il y a une ressource X présent dans l'environnement. L'agent apprenant possède trois actions : les commandes request(creerX), request(creerY) et wait, dont il ne connait pas les effets. Il évolue dans un environnement partiellement observable car il ne peut observer la présence de la ressource X dans l'environnement. Enfin, le système est asynchrone car chaque action peut avoir une durée d'exécution différente. Pour notre évaluation nous avons utilisé les durées suivantes :

-d request(creerX) = d request(creerY) = d wait ; -d charger_batterie = 2 * d wait ; -d creerX = 4 * d wait ; -d creerY = 3 * d wait .
Par conséquent du point de vue de l'agent apprenant, la commande request(creerX) peut se terminer 3 à 5 pas de temps après l'avoir envoyé et traitée la réponse. De même la commande request(creerY) se terminera 2 pas de temps après avoir l'avoir exécutée. La difficulté pour l'agent apprenant est donc d'apprendre quand envoyer la commande request(creerY) après l'envoi d'une commande request(creerX) en fonction des réponses obtenues et de ses temps d'attentes.

Résultats

Nous avons implémenté notre modèle sur la plateforme multi-agent VDL [START_REF] Sabouret | A Model of Requests about actions for active components in the semantic web[END_REF]. Nous avons aussi implémenté le modèle de mémoire temporelle proposé par [START_REF] Dutech | Un algorithme d'apprentissage par renforcement pour les processus décisionnels de Markov partiellement observés : apprendre une extension sélective du passé[END_REF]. Le but est de comparer les résultats obtenus sur l'exemple des ressources d'un agent apprenant utilisant notre modèle de mémoire et ceux obtenus par un agent utilisant une mémoire temporelle. Nous n'avons pas utilisé la mémoire de travail comme outil de comparaison car comme nous l'avons montré la taille de la mémoire doit être choisi arbitrairement et de plus nécessite d'effectuer plusieurs algorithme d'apprentissage en parallèle rendant la comparaison innapropriée. De même, la mémoire cognitive n'est pas exploitable car il n'existe pas de mécanisme permettant de déterminer ce qu'il faut récupérer dans l'historique de l'agent.

Notre modèle de mémoire utilise les paramètres suivants : T m = 1 et nous avons défini la fonction rew(p) de la manière suivante : -rew(agree) = 0 ; -rew(impossible) = -5 ; Pour la mémoire temporelle, nous stockons les actions, c'est-à-dire les commandes ou l'action wait, effectuée par l'agent. La taille de la mémoire de l'agent est initialisée à 1.

Dans les deux cas, nous utilisons notre algorithme incrémental pour augmenter la taille du paramètre T m de notre modèle ou la taille de la mémoire temporelle. Les paramètres d'initialisation de l'algorithme d'apprentissage utilisés pour obtenir nos résultats sont les suivants : γ = 0.9, T = 5, T d = 0.99, = 0.001, N e = 1000, T e = 1000, E = 10, N = 4.

La fonction de récompense R (R : S → R) de l'agent est définie comme la somme de deux fonctions r 1 et r 2 où r 1 vaut 10 si l'agent obtient la ressource Y et 0 sinon ; -r 2 dépend de la réponse obtenue à l'envoi d'une commande. L'agent obtient la valeur 0 si c'est un message agree et -5 sinon ; Nous considérons la somme totale des récompense obtenues par l'agent durant une expérience en fonction du nombre d'itération de l'algorithme d'apprentissage. La figure 2 représente la moyenne de la récompense obtenue La figure 3 représente le nombre d'actions effectuées par l'agent durant une expérience ainsi que le nombre de messages envoyés. De même, que sur la courbe précédente, nous représentons la moyenne obtenue sur 50 expériences consécutives. Les courbes (+) et ( * ) représentent les résultats obtenues avec notre modèle de mémoire alors que les courbes (×) et ( ) représentent les résultats obtenues avec une mémoire temporelle. Dans les deux cas, l'agent apprend rapidement à n'envoyer que les deux seuls messages nécessaires à l'obtention de sa ressource Y. Cependant nous pouvons noter que l'agent utilisant notre modèle de mémoire effectue cependant moins d'actions que l'agent utilisant une mémoire temporelle. Ceci peut s'expliquer par le fait que la mémoire temporelle ne stocke pas les réponses des commandes. Ainsi l'agent ne pouvant faire la différence entre les réponses agree(creerX) et agree(creerX ;plustard) apprend qu'il vaut mieux attendre plus longtemps et être donc sur que l'agent A ait bien effectuer creerX plutôt que de recevoir un message négatif de la part de l'agent B. Ce problème ne se pose pas avec notre modèle de mémoire où l'agent est donc capable d'adapter son comportement en fonction des réponses qu'il reçoit.

Conclusion et perspectives

Dans cet article, nous avons présenté un modèle de mémoire pour l'apprentissage de la communication et tout particulièrement pour les messages de type commande et contrôle. Notre solution repose sur la mémorisation des réponses et des dates couplée à un algorithme itératif permettant d'augmenter progressivement les valeurs que peuvent prendre la mémoire.

Nous avons évalué notre modèle en le comparant à un modèle de mémoire temporelle dont la taille est elle aussi définie en utilisant notre algorithme incrémental. Nous avons montré que sur un exemple simple, notre modèle était capable d'apprendre une politique pour la communication en effectuant moins de cycles d'apprentissage que la mémoire temporelle. De plus, notre modèle de mémoire permet à l'agent d'atteindre son but en effectuant moins de cycles d'exécution. En effet, en stockant plus d'information comme les réponses, l'agent utilisant notre modèle de mémoire est capable d'adapter au mieux son comportement alors qu'un agent utilisant une mémoire temporelle doit opter pour une politique moins risquée (plus de temps d'attente après l'envoi d'un message) mais donc moins optimale.

Ces résultats sont donc encourageants et nous aimerions les confirmer en testant notre modèle de mémoire sur des problèmes plus complexe en augmentant par exemple le nombre d'agents et de messages que l'agent apprenant peut envoyer. Cependant, nous pouvons présager des problèmes de convergence avec un nombre de messages très grands dû à l'utilisation du Q-Learning.

Une autre perspective de ce travail serait d'étendre notre modèle de communication à d'autres messages que la commande et le contrôle. Nous aimerions pouvoir apprendre à communiquer des réponses mais aussi pouvoir effectuer des engagements ou des promesses. Dans ce cas il sera probablement nécessaire d'étoffer notre modèle de mémoire pour pouvoir prendre en compte ces nouveaux messages.

Enfin nous aimerions à plus long terme déterminer de nouveaux mécanismes permettant de réduire la taille de la mémoire utilisée. Pour cela, nous nous intéressons à la généralisation des éléments mémorisés sous forme de concepts plus facile à réutiliser dans de nouveaux contextes et plus simple à stocker. Ceci nous permettrait d'adapter notre algorithme à l'apprentissage de la communication pour les problèmes de grandes tailles.

FIGURE 1 -

 1 FIGURE 1 -Un exemple de la mémoire d'un agent Agt l tel que A Agt l = {request(a), request(b), query(c), request(d), wait} et utilisant une valeur de T m = 3. Dans cet exemple, l'agent est en train d'attendre depuis 2 pas de temps. Il a reçu un message agree() il y a trois pas de temps suite à l'envoi d'un request(a). Il a reçu deux messages agree(with_delai) et query(c=3) il y a plus de trois pas de temps. Et il n'a jamais envoyé de messages request(d).

  a) correspond à la récompense attendue lorsque l'agent exécute l'action a lorsqu'il se trouve dans l'état e. La meilleure action pour chaque état est alors définie par : a * = arg max a∈A Q(s, a). Le principe du Q-Learning est de construire itérativement la fonction Q pour chaque couple (e, a) en expérimentant les actions dans l'environnement. A chaque prise de décision (c'est à dire choix d'une action à effectuer) l'agent choisit une action a dans A e , exécute a, reçoit une récompense r(e, a) et observe son nouvel état e . Il met alors à jour la valeur Q(e,a) en fonction de e et de r(e, a) selon la formule suivante : Q(e, a) = (1-α t )Q(e, a)+α t (r+γ max a∈A Q(e , a ))

FIGURE 2 -

 2 FIGURE 2 -Récompenses moyennes obtenues par l'agent durant un cycle d'apprentissage en utilisant soit notre modèle et 1 cran de mémoire (+) soit la mémoire temporelle et 5 crans de mémoire (x)

FIGURE 3 -

 3 FIGURE 3 -Nombres d'action (ou de messages envoyés) durant un cycle d'apprentissage.

  Agt peut donc exécuter plusieurs actions par cycle par conséquent, la durée d'un cycle n'est pas la même pour tous les agents.

		FIPA. Ainsi l'envoi d'un message de performa-
		tif request nécessite une réponse de performatif
		impossible, not-understood ou agree. Les mes-
		sages impossible, not-understood ou agree eux
		ne nécessitent pas de réponse.
	2 Stockage des messages	Un agent Agt a un comportement cyclique. À
	2.1 Nomenclature	chaque cycle d'exécution, l'agent : 1. observe l'environnement et met à jour son
	Dans cet article, nous notons A l'ensemble des agents et Agt l ∈ A l'agent apprenant. Un agent quelconque Agt ∈ A est décrit à un instant t par son état s Agt t ∈ S (Agt) où S (Agt) est l'ensemble des états possibles de l'agent. L'état s Agt t d'un agent est constitué : -de l'ensemble des observations de l'agent	ensemble d'observation Ω (Agt) ; 2. traite l'ensemble des messages qu'il a reçu depuis son dernier cycle d'exécution (le traitement consiste à répondre aux mes-sages le nécessitant) ; 3. détermine les actions A ∈ A (Agt) qu'il peut effectuer dans l'état s t ;
	Ω (Agt) t var, val où var est une variable décrivant . Une observation est un couple	4. exécute l'ensemble des actions A . Un agent
	un élément de l'environnement et val la va-
	leur observée par l'agent à l'instant t ;
	-de l'ensemble des données internes de l'agent
	D (Agt) t où var est une variable décrivant l'état interne . Une donnée est un couple var, val
	de l'agent et val sa valeur à l' instant t ;
	-de la mémoire de l'agent m (Agt) t ture est décrite en détails dans la section 2.3. . Cette struc-
	Un agent Agt ∈ A possède un ensemble d'ac-
	tion A (Agt) qui est constitué :
	-des actions propres de l'agent, c.-à-d. les ac-
	tions que l'agent peut exécuter pour modifier
	soit des variables de l'environnement soit ses
	données propres ;
	-de messages que l'agent peut envoyer aux
	autres agents de l'environnement.
	Un message est décrit selon la nomenclature
	FIPA 1 par un n-uplet em, p, c, dst où :
	-em, dst ∈ A sont respectivement l'émetteur
	et le destinataire du message ;
	-p est le performatif du message ;
	-c est le contenu du message.
	Un message est considéré comme une action par
	nos agents. Parce que nous nous appuyons sur
	un algorithme d'apprentissage par renforcement
	(cf. section 2.5), nos agents ont besoin de déter-
	miner la fin de chaque action, y compris les ac-
	tions de communication. Dans cet article, nous
	faisons le choix qu'une action de communica-
	tion est terminée soit à la réception du message
	réponse, lorsque le message envoyé en néces-
	site une, soit à la fin de l'envoi du message lui-
	même s'il ne nécessite pas de réponse. Pour dé-
	terminer si un message nécessite ou non une ré-
	ponse, nous utilisons les protocoles définis par
	1. http://www.fipa.org/

  Avec T t le paramètre de température qui décroît lentement en fonction du temps t. Lorsque la température au départ est très élevée alors la probabilité de choisir une action a ne dépend pas de Q(e, a) et est uniforme. Au contraire lorsque la température est plus faible et proche de 0, la probabilité de choisir l'action a dépend de la valeur de Q(e, a), ainsi une action avec un Q élevé a alors plus de chance d'être choisie.

	Un ensemble d'états restreints. L'algorithme du
	Q-Learning nécessite de construire la fonc-
	tion de Q-Value pour l'ensemble des couples
	(état,action) de l'agent. Dans, la cas où l'en-
	semble d'actions soit constitué de n messages et
	l'état de l'agent soit décrit uniquement par une
	mémoire m alors le Q-Learning requiera de sto-
	Pour construire S l , nous avons besoin de définir
	la relation de généralisation entre deux configu-
	rations de mémoire. Soit deux configurations de
	mémoire d'un agent

,a)/Tt b∈A e Q(e,b)/Tt cker et d'apprendre θ(n * (T m + 1) n ) valeurs pour la fonction Q(s,a) ce qui peut s'avérer très grand. Comme nous ne pouvons pas limiter le nombre de messages que l'agent peut envoyer il est impératif de limiter la valeur de T m tout en essayant d'obtenir une valeur de T m suffisament grande pour permettre à l'agent d'apprendre à communiquer. Pour cela nous proposons d'utiliser un algorithme incrémental qui va augmenter de manière progressive la valeur de T m durant l'apprentissage. Néanmoins, si l'agent doit mémoriser qu'il a fait A il y a 4 pas de temps lorsqu'il observe o 1 , alors T m doit être égale au moins à 4. Ainsi, pour l'observation o 2 , l'agent mémorisera aussi tout ce qu'il a fait depuis 4 pas de temps même si cela n'est pas nécessaire. C'est pourquoi, nous proposons de n'augmenter T m que dans les états qui le nécessitent. Pour ce faire, nous n'appliquons pas l'algorithme d'apprentissage sur l'ensemble d'états S (Agt l ) de l'agent Agt l mais sur un ensemble plus restreint que nous noterons S l .