Equipe-projet KAYOU

Faits marquants pour les années 2002-2005

Logiciels :

Problématique et activité scientifique

Agents à Ressources Limitées

Le premier but fédérateur pour le projet « Kayou » est de concevoir des agents capables de fournir des réponses satisfaisantes pour l'utilisateur tout en étant intrinsèquement limités par des ressources telles que le temps et l'espace de calcul, les capacités de perception et d'action, le type et le nombre de communications, etc. Dans ce contexte, l’agent est vu comme un système de résolution de problèmes, qui essaye de prendre des décisions satisfaisantes en fonction des données du problème fournies par l’utilisateur. Ce domaine de recherche s’articule autour de trois axes : le raisonnement à base de contraintes, l’apprentissage logique et l’aide à la découverte scientifique. Les deux premiers axes ont été prospectés par les chercheurs de Kayou bien avant la création de ce projet. Ces thèmes restent cependant très actifs en intelligence artificielle et constituent des piliers fondateurs pour l’étude des systèmes à ressources limitées. Le troisième axe « aide à la découverte scientifique» est plus récent et tire parti des divers domaines de compétence réunis dans le projet Kayou.

Raisonnement à base de contraintes

Ce thème de recherche est illustré par la figure 1. L’objectif général est de construire des agents capables de résoudre des problèmes combinatoires tels que, l'élaboration des emplois du temps du personnel dans une entreprise ou la planification de tâches pour des machines devant être  utilisées de façon optimale.  Le formalisme des réseaux de contraintes est particulièrement adapté à la modélisation de ces problèmes. Un réseau de contrainte est constitué d’un ensemble de variables, d’un domaine de valeurs pour chacune de ces variables et d’un ensemble de contraintes qui caractérisent les relations entre variables. Le point de départ consiste à modéliser le problème sous forme d’un réseau de contraintes qui représente ainsi les connaissances de l’utilisateur. Une fois le modèle élaboré, le but de l’agent est de trouver une solution, c'est-à-dire une interprétation ou affectation de variables qui permet de résoudre le problème. L’agent est donc un solveur qui doit traiter le problème avec un minimum de ressources possibles. Pour les problèmes « centralisés », la ressource principale est le temps. En effet, en dessus d'un temps allant de la dizaine de secondes à quelques minutes, l’utilisation du solveur reste limitée à de grosses applications manipulées par des experts. Dans le cadre des problèmes « distribués » sur plusieurs sites, les ressources incluent le temps de calcul, mais aussi le nombre de messages communiqués entre les solveurs locaux.

D'un point de vue combinatoire, le problème qui consiste à déterminer si un réseau de contraintes admet une solution est NP-complet. Dans ce contexte, le principal champ d'investigation dans le domaine du « raisonnement à base de contraintes » est de concevoir des algorithmes de propagation et des heuristiques pour améliorer les performances des solveurs à contraintes. Notamment, la tendance des quatre ou cinq dernières années est à la découverte de contraintes, dites « globales », bénéficiant d'algorithmes efficaces de propagation (en général polynomiaux). Ce sujet étant encore immature, nous essayons de formaliser le concept de contrainte globale, en proposant des définitions et en utilisant la théorie de la complexité pour séparer les contraintes pour lesquelles l'existence d'algorithmes de propagation efficaces est possible de celles où l'espoir se réduit à la conjecture P=NP. Une autre approche prometteuse est la technique de restart, qui consiste à arrêter une résolution dès qu'elle dépasse quelques secondes, et à la reprendre avec un autre ordre de traitement, de façon à éviter la « noyade » de la recherche dans un gros sous-arbre inconsistant [Bessiere 2002-2005].

Avec l'augmentation des applications en réseau, il est un second champ d’investigation qui risque de prendre de l'importance dans les années à venir, c'est la résolution de problèmes à contraintes distribués sur plusieurs sites. Ce problème, à la croisée des domaines « contraintes » et « multi-agents », est également traité dans l'équipe Kayou. Nous avons par exemple proposé une technique de résolution évitant l'ajout de liens de communication entre agents non connectés initialement. Cette technique, qui améliore le degré de confidentialité et limite le nombre de messages, nous a permis de résoudre efficacement des problèmes distribués de planification de réunions [Bessiere et Maestre 2004].

Apprentissage logique

Ce deuxième axe de recherche est illustré dans la figure 2. L’objectif général ici est de caractériser les connaissances, régularités ou règles cachées, issues d’un ensemble d’observations provenant de bases de données médicales, biologiques, juridiques, etc.  Les seuls éléments dont dispose l’utilisateur sont des observations représentées sous forme d’exemples ainsi que des connaissances de base relatives au domaine d’étude. Le problème ici est donc de construire un agent « apprenant » capable de construire un modèle de représentation qui respecte diverses conditions. En particulier, le modèle doit être compréhensible pour l’utilisateur afin de pouvoir être utilisé pour de nouvelles taches. Le modèle doit aussi permettre de prendre des décisions correctes telles que, par exemple, la classification de nouvelles observations. Enfin, la construction d’un tel modèle doit nécessiter un minimum de ressources possibles.

Dans le projet Kayou, nous utilisons des modèles à base de règles construites sur la logique propositionnelle, la logique relationnelle et plus récemment les logiques modales (épistémique et déontique). Dans ce cadre logique, le temps et l’espace sont des paramètres cruciaux car l’espace des hypothèses augmente exponentiellement avec l’expressivité des règles logiques. Cette ressource devient critique dans le contexte de l’apprentissage relationnel : même pour de simples règles (ex. conjonction existentielle d’atomes), le problème qui consiste à déterminer si un exemple est couvert ou non par une règle est NP-difficile. Ainsi, un des problèmes centraux en apprentissage logique est de caractériser quels sont les biais ontologiques (vocabulaire, règles), épistémiques (pertinence des règles, préférences entre règles), et heuristiques (classification des règles et exploration de l’espace des règles). 

Une grande part des travaux de Kayou en apprentissage se concentre sur la découverte de biais et la combinaison de ces divers biais afin de construire des modèles de représentation satisfaisants. Un premier champ d’investigation est la découverte de biais en identifiant des éléments particuliers du treillis de Galois (irréductibles, essentiels..) utilisés pour caractériser l'espace de règles logiques [Liquière 2003]. L’intérêt de cette technique a été démontré tant au niveau propositionnel et qu’au niveau relationnel. Un deuxième champ est d’utiliser des opérateurs topologiques (fermeture, intérieur) pour restreindre l’exploration dans des grands espaces d’hypothèses. Cette méthode a récemment été  étudiée dans le cadre relationnel [Koriche 2005]. Un troisième champ est de construire des méthodes à base de distance topologique permettant de sélectionner et combiner des biais. Ce paradigme a été appliqué à la fois au cadre propositionnel et au cadre relationnel [Koriche et Quinqueton 2003, Koriche 2004]. Enfin, des travaux récents ont été élaborés pour la construction d’une algèbre catégorielle des biais d’apprentissage afin de formaliser les opérateurs qui permettent de les construire et de les combiner [Sallantin et al. 2003]. En plus de son intérêt théorique, ce champ d’investigation a permis d’identifier des premiers biais pour l’apprentissage modal ainsi qu’une application pour la construction interactive de règles en logique déontique défaisable et paraconsistante [Sallantin et al 2003].

Aide à la découverte de règles

Cet axe de recherche s’inspire à la fois des travaux dans le raisonnement par contraintes et des investigations réalisées en apprentissage et contraintes. L’aide à la découverte reprend le paradigme poppérien de preuve et de réfutation peut se décomposer en deux parties : la modélisation interactive et la résolution interactive et s’appuie sur la théorie d’Angluin sur l’apprentissage à partir de différents instructeurs.

Dans la modélisation interactive, l’utilisateur cherche à construire une base de règles logiques ou un réseau de contraintes qui modélise les connaissances relatives à son domaine d’étude. L’utilisateur maîtrise son domaine mais ne possède pas une expertise suffisante lui permettant de caractériser précisément quelles sont les règles ou contraintes correspondant à son domaine d’étude. Mais il dispose d’un agent apprenant capable de compléter son modèles par apprentissage à partir de cas concrets L’objectif est ici de découvrir les biais venant de l’échantillonnage ou encore de contraintes sur la formulation de la théorie. . L’objectif ici est de découvrir quelles sont les règles cachées qui peuvent être induites des exemples. Ainsi l’utilisateur interagit avec l’agent apprenant, par le jeu d’exemples, de validations et de réfutations qui permettent d’ajuster le modèle de représentation.

Dans la résolution interactive, le modèle de représentation construit par l’apprenant est à son tour utilisé par l’agent solveur pour le raisonnement ; trouver une solution au problème sous-jacent, répondre à des requêtes, expliquer de nouveaux cas, etc. Par exemple, le juriste peut demander de vérifier si un nouveau contrat est valide ou non,  en se basant sur l’information induite des contrats précédents. Dans ce cadre, l’apprentissage possède des incidences sur le raisonnement, en particulier dans le choix des biais adoptés pour la construction du modèle de représentation.  Par exemple, l’apprenant peut chercher à induire des théories de Horn ou des réseaux arborescents qui garantissent l’efficacité du solveur pour les problèmes de déduction. De manière duale, les solutions fournies par le solveur peuvent avoir des incidences sur l’apprentissage. Notamment l’utilisateur peut juger une solution non satisfaisante et donc demander une révision du modèle en fournissant à l’apprenant des contre-exemples.  Ainsi, la résolution interactive est un jeu de communications entre trois partenaires, l’utilisateur, l’apprenant et le solveur.

L’aide à la découverte scientifique constitue une perspective de recherche fédératrice du projet Kayou. Bien que nos investigations dans ce domaine soient très récentes, nous pouvons faire référence à plusieurs travaux dont les résultats sont prometteurs : acquisition interactive de contraintes [Bessiere et al. 2003-05], négociation interactive de contrats [Sallantin 2003], utilisation de la théorie des jeux pour la construction de théories déontiques [Sallantin et al 2004].

Sociétés d’agents

Le second but fédérateur de « Kayou » consiste à étudier et formaliser des systèmes composés de plusieurs agents, artificiels et/ou humains. Ce domaine de recherche est examiné en détail selon quatre points de vue : les modèles d'organisation (théorie AGR, systèmes de coalition), les modèles de rationalité (juridiques et économiques), les modèles cognitifs (états mentaux, actes de langage et dialogues), et les théories de l’émergence (calcul émergent, vie artificielle) et de l’interaction (MIC*). Dans ce cadre, le projet s'inspire des divers travaux issus des quatre pôles du projet, notamment les algorithmes distribués, l’apprentissage décentralisé, les logiques et modèles de calcul pour les systèmes multi-agents, ainsi que les méthodologies de conception orientées agent.

Enfin, une découverte est faite par des agents dont les interactions sont organisées par un jeu social ; elle est souvent conséquence de l’observation d’un événement surprenant inexpliqué dans la théorie abduite. Nous avons réalisé un environnement expérimental pour étudier ce phénomène en collaboration avec des chercheurs en psychologie et en économie cognitive

Action Aalaadin : organisation dans les SMA

AALAADIN est un projet qui porte sur l’analyse, la conception, la formalisation et la réalisation de systèmes multiagents à partir d’une perspective organisationnelle. Le modèle conceptuel sous-jacent (AGR) est fondé sur les notions d’agents, de groupes et de rôles, un SMA étant vu comme un ensemble de groupes d’agents interconnectés par l’intermédiaire d’agents appartenant à plusieurs groupes. A partir de ce modèle conceptuel, novateur dans le domaine des SMA, nous avons développé une méthodologie qui s’exprime de manière omplémentaire par rapport aux méthodologies classiques (UML par exemple) ou centrées sur l’agent [Gutknecht 2001]. Il s’agit d’un «framework organisationnel», un cadre méthodologique volontairement partiel et complété par des modèles externes. Des notations spécifiques, conçues comme des extensions d’UML ont été développées à cet effet. [Ferber et al 2003]. Le problème de la dynamique des groupes dans AGR qui avait été formalisée en termes de pi-calcul, a été repensé dans le cadre du calcul MIC* permettant de modéliser l’interaction [Gouaich et al 2002].

La mise en œuvre de ce modèle s’est effectuée dans l’environnement de développement MadKit, qui implémente les concepts AGR et permet d’écrire des applications directement avec ce modèle. Disponible en ligne, MadKit possède plusieurs centaines d’utilisateurs dans tous les pays du monde (USA, Europe, Maghreb, Chine, Japon, etc…) qui travaillent et l’utilisent dans de nombreux domaines d’application : biologie, simulation multi-agents, acquisition de connaissances. Plus d’une vingtaine d’équipes en France travaillent sur ce domaine.

Mais si l’agent est autonome, qu’est ce qui le relie au système collectif et donc aux organisations auxquelles il appartient ? C’est à la composante normative que revient cette responsabilité, c'est-à-dire aux concepts de droits et de devoirs imposés à l’agent au sein d’une organisation.

Le problème de cette composante normative a été approfondie récemment au sein de Kayou à partir d’un fragment de logique déontique modale disposant de bonnes propriétés de complexité tout en offrant une capacité d’expressivité remarquable [Tranier et al. 2003]. Cette approche va se renforcer à l’avenir car il correspond à un besoin manifeste pour coordonner le comportement autonome des agents lorsque le nombre des agents devient important (plus d’une centaine d’agents). Le recrutement de T. Stratulat en 2003 s’inscrit d’ailleurs totalement dans cette démarche.

Informatique Sociale / Services Interactifs (Social Informatics)

L’action IS/SI considère que les processus de communication, entre agents artificiels d’une part mais aussi entre humains et agents artificiels ainsi que entre humains à travers les agents artificiels (enhanced presence), constituent le cœur de la résolution collaborative distribuée des problèmes. Un cas particulier de collaboration porte négotiation et la fourniture de services. La notion de service devient intéressante toutefois quand elle n’est plus considérée comme un simple appel de procédure mais devient un processus interactif (persistant et avec état). L’action IS/SI étudie donc ces processus interactifs entre Agents qui intègrent les contributions des SMA, IHM, Web Sémantique et Grille Sémantique avec une modélisation en langage fonctionnel (Scheme), des expérimentations ainsi que des développements purement techniques dans le contexte de Madkit et de  GT 3.2 -> 4 (OGSA compliant). 

         Dans [Jonquet et Cerri, 2005a], [Jonquet et Cerri, 2005c], [Jonquet et Cerri, 2004] on présente en détail l’état d’avancement du modèle STROBE par rapport aux systèmes multi-agents vus comme des communautés virtuelles d’agents artificiels et d’agents humain qui communiquent et apprennent. Un prototype d’environnement de développement d’agents STROBE a été produit, sous le nom de STROBEKIT car il s’appui fortement sur Madkit. D’une coté le modèle permet aussi de considérer les dialogues comme des objets d’étude [Jonquet et Cerri, 2005b], de l’autre il remet l’humain dans la boucle permettant d’intégrer les humains dans les « Grid Virtual Organisations » comme demandeurs et fournisseurs de services [Jonquet et al, 2005b], [Eisenstadt et al, 2005 ] , [Eisenstadt et al, 2004 ]  [Cerri, 2003], [Allison et al., 2005]. Ces concepts de convergence entre Agents et Services Grille d'une coté, et de "homme comme ressource pour des services" de l’autre nous a permis de déposer trois propositions de projets EU dont une comme coordonnateur et les autres deux coordonnés par IBM Belgique et le CEA .

         D’un point de vue technique, à l’intérieur du projet intégré EleGI (www.elegi.org ; [Allison et al, 2003] nous avons développé un premier prototype de Service GRID pour la collaboration : GVD (Grid Virtual Desktop) [Dugenie et Jonquet, 2005] qui va être expérimentée dans les mois qui viennent à l’intérieur du projet EnCOrE (Encyclopédie de Chimie Organique Eléctronique) en collaboration avec les chimistes de FUNDP, Namur ; en particulier Prof . Alain Krief [Lemoisson et Cerri, 2005] ; [Lemoisson et al., 2005 ] ;  [Lemoisson et al., 2004 ] [Lemoisson et al., 2003].

         La construction de théorie par collaboration et apprentissage à distance, grâce à la négociation d’une ontologie commune étant un sujet très étudié dans KAYOU [Da Nobrega et al., 2004a] ; [De Castro et al., 2004] ; [Da Nobrega et al., 2004b] , [Da Nobrega et al., 2003] ; [Maraschi et al., 2002] ; [Da Nobrega et al., 2002] , [Trausan-Matu et al., 2002]  les travaux EnCOrE ont pu progresser avec des résultats importants même si les outils de construction en collaboration d’ontologies ne sont pas vraiment disponible.

         D’un point de vue « apprentissage » nos agents humains apprennent par effet de bord de la collaboration (constructivisme social). Dans EleGI nous nous occupons seulement de scénarios d’apprentissage « informel ». A cet effet, nous avons étudié dans quelle mesure on pouvait analyser des conversations réelles, les formaliser en « actes de langages » et en induire des règles qui puissent aider à mieux gérer nos communautés. L’étude a développé une Théorie cognitive (Activity Theory, Binti Abdullah) sous-jacente à la formalisation et des expérimentations sont en cours pour l’induction de règles à partir des cas particuliers de conversations formalisées (collaboration avec Michel Liquière) [Binti Abdullah et Cerri, 2005 a] ; [Binti Abdullah et al. ; 2003] ; [Binti Abdullah et al. ; 2005] ; [Binti Abdullah et Cerri, 2005 b] ; [Binti Abdullah et al. ; 2004].

Architectures pour les simulations multi-agents et modélisation de systèmes naturels et sociaux

Les systèmes multi-agents sont de plus en plus utilisés dans les sciences de la vie et de l’environnement pour leur possibilité de représenter directement les différents acteurs biologiques, sociaux et économiques, leurs comportements et leurs interactions. Malgré leur intérêt, ils soulèvent plusieurs problèmes. Un problème important porte sur la définition d'un modèle « sans biais », c'est-à-dire d’un modèle permettant effectivement d’assurer au modélisateur que l’outil informatique implémente bien le modèle que le modélisateur a décrit (on ne s’intéresse pas ici au problème de l’adéquation entre le modèle et la réalité qui est un problème de modélisation), et que les conséquences observée lors de la simulation sont bien directement des conséquences du modèles et non le produit d’un comportement non désiré du système informatique. Le problème n’est pas seulement technique, il est aussi théorique : il a nécessité le développement d’une théorie de l’action, le modèle « influence/réaction », une extension du calcul situationnel, qui permet de décrire des comportements simultanés d’action. Ce modèle a été formalisé par le modèle algébrique d’interaction MIC* développé au sein de Kayou [Guiraud et Gouaich 2002][Gouaich et al. 2003] [Gouaich 2005] et a été appliqué avec succès au problème des actions simultanées [Michel et al. 2003][Michel 2005]. Une architecture de simulation de systèmes multi-agents fondée sur ce principe a été réalisée dans le cadre de la thèse F. Michel [2005] et intégré à Madkit.

Méthodes Multi-agents appliquées aux problèmes de robotique collective avec forte hétérogénéité

Une partie de notre activité s’est consacrée au développement d’architecture de robots réactifs disposant de capacités intentionnelles pouvant leur permettre de réaliser des tâches coopératives dans un cadre de robotique collective. Cette action, qui s’est passé en collaboration avec l’équipe d’A. Liégeois puis, lors de son décès, de celle de R. Zapata, a donné llieu à la réalisation d’un modèle d’agent basé sur une architecture réactive et des communications par émission de signaux. Le problème de la sélection d’actions, ainsi que la gestion des interactions entre agents, sont gérés par une fonction d’état de satisfaction. Cette satisfaction étant elle-même décomposée en trois sous-satisfactions : personnelle (progression de la tâche courante de l’agent), interactive (réaction aux actions des agents voisins) et coopératives (fonction de la satisfaction des autres agents).

Des robots ont été réalisés au LIRMM et ont été équipés de ce modèle d’architecture pour gérer la coopération entre robots. Les résultats actuels montrent une bonne performance de ce modèle et une utilisation possible dans le cadre de flottes d’agents mobiles devant travailler en coopération [Simonin 2002][Ferber 2005]. Le travail actuel consiste à rendre encore plus souple cette architecture d’agent pour qu’elle puisse être considérée elle même comme un système multiagent et offrir des capacités de coordination œil/bras accrues.

 

Bibliographie de Kayou

Production scientifique pour la période 2002-2005

Thèses

6

HDR

0

Brevets

0
 

Audience internationale

Audience nationale

Livres

1

  

Chapitre d’ouvrages

11

3

Edition d’ouvrages

5

2

Revues avec comité de lecture

12

3

Conférences avec actes publiés et comité de lecture

58

15

Conférences invitées

4

  

Autres conférences

3

4

Autres publications

6

4