|
|
|
L'équipe est fédérée autour de trois axes de recherche en forte synergie : l'apprentissage symbolique, connexionniste et statistique ; le diagnostic à base de modèles de systèmes complexes ; l'étude des aspects distribués et coopératifs dans les systèmes d'agents autonomes. Ces recherches sont alimentées, coordonnées et évaluées grâce à diverses applications : génomique, exploration des traces de navigations sur Internet, identification vocale et visuelle, supervision de réseaux de télécommunications, gestion de la qualité de service dans les réseaux IP, diagnostic de systèmes électroniques, automobiles et spatiaux, indexation coopérative de l’information, environnement coopératif pour le e-learning et le e-commerce, planification réactive de missions aériennes.
Thèmes de recherche :
|
Equipe ADAge : Apprentissage, Diagnostic et Agents
Cette équipe a été créée en 1999 avec la volonté de tirer parti de la complémentarité de ses thèmes de recherche et de mettre en œuvre leur coopération. Parallèlement à la prolongation des recherches au sein de chaque thème, cette collaboration s’est déjà largement manifestée.
C’est ainsi qu’a commencé et que va se renforcer l’utilisation de techniques d’apprentissage pour le diagnostic, en complément des techniques à base de modèles explicites utilisées jusqu’alors. Il s’agit tout à la fois de techniques statistiques ou connexionnistes (pour la corrélation d’alarmes ou d’indicateurs, l’analyse de séquences temporelles à des fins de diagnostic prédictif et évolutif) et de techniques symboliques (pour l’apprentissage de chroniques). Dans le futur une coopération entre ces techniques, par exemple par apprentissage de modèles, est envisagée.
L’apprentissage symbolique multi-agents, dans le cadre d’agents communicants de type BDI (Beliefs, Desires, Intentions), donne lieu à un travail de thèse.
La spécification d’agents intelligents pour la gestion autonome et contextuelle de réseaux, qui donne lieu également à plusieurs travaux de thèse, est une recherche conjointe aux thèmes diagnostic et SMA, tout comme la spécification de la conception d’un système de diagnostic à base de modèles en termes d’agents logiciels autonomes. La nécessité croissante de recourir à un diagnostic distribué de même que l’émergence de la problématique de diagnostic autonome vont sûrement conduire à élargir la collaboration entre ces deux thèmes.
Les axes de recherche inter-équipes sont également présents. La problématique du diagnostic est déjà largement partagée avec l’équipe RCLN, en la personne de François Lévy, tout comme le raisonnement temporel et causal. La classification hybride combinant un réseau connexionniste à un système de raisonnement à partir de cas est aussi une collaboration avec l’équipe RCLN. La résolution de problèmes de satisfaction de contraintes, utile notamment en raisonnement spatio-temporel, donne lieu à une coopération avec l’équipe OCAD sur le problème MAX-CSP.
Citons également un axe de recherche inter-équipes, qui devrait démarrer avec RCLN : l’utilisation de techniques d'apprentissage connexionnistes pour obtenir efficacement une annotation sémantique de parties de textes techniques. Enfin, des chercheurs en apprentissage symbolique de l’équipe participent à l’EPML IAPuces dirigée par Jean-Daniel Zucker, du LIM&BIO Bobigny de Paris-Nord.
Soulignons enfin qu’une caractéristique essentielle du mode de fonctionnement de cette équipe est que les recherches y sont alimentées et évaluées grâce à de nombreuses applications, concernant la génomique, la parole, l’image, les télécommunications, Internet, le e-commerce et le e-learning, l’électronique, l’automobile, les satellites, etc, donnant lieu pour la plupart à des contrats industriels. Un autre atout de cette équipe est son nombre élevé de doctorants.
Thème : Apprentissage Symbolique (Dominique Bouthinon, Marc Champesme, Aomar Osmani, Henry Soldano, Nahla El Zant-El Kadhi, Alejandro Guerra Hernandez).
Ils s’organisent autour de l’analyse de l’information utilisée dans l’apprentissage (biais, contenu en information, incertitude), de la nature des objets et de la représentation (séquences, séquences temporelles, systèmes multi-agents),ordre de finesse sur les treillis de concepts). Les applications qui inspirent et utilisent certains de ces travaux proviennent de la bioInformatique (génomique , biologie moléculaire et structurale)
Il s’agit ici de la formalisation en logique du premier ordre de différents cadres d'apprentissage dont les données recèlent des formes variées d'incomplétude et de la mise en évidence d’un cadre qui rend compte de situations d'apprentissage jusqu'ici inexprimables du fait de la nature de l'incomplétude (incertitude + abstraction).
Cette recherche vise à identifier et quantifier l'information mise en jeu pendant le processus d'apprentissage. En se fondant sur la théorie de l'information on interprète l'induction comme une reformulation de l'information fournie par les exemples et les biais inductifs. Ce modèle propose de plus une mesure quantitative de l'information apportée par différents types d'incomplétudes des exemples. Une des perspectives est le changement dynamique du niveau d'abstraction lors de l’induction. Une application de cette analyse informationnelle est prévue dans un projet en soumission sur l'étude des duplications dans les gènes selon plusieurs niveaux de représentations (ADN et protéines).[Bouthinon, CAP 2002]
Ce thème poursuit l’étude d'une Logique de description, conçue pour l’apprentissage et la représentation de connaissances de type « défaut ». En particulier nous avons proposé une stratégie d’apprentissage dans laquelle des règles strictes et des règles défaut de type « les A devraient être des B » sont utilisées pour saturer la description des exemples avant l’apprentissage [Ventos et al, LPNMR 2001]. Une étude en cours concerne la construction d'ensembles minimaux de règles à partir d'un ensemble d'instances dans le cas où les instances sont typées, et où le type détermine les connaissances par défaut. Cette dernière étude est liée au thème "Treillis de Galois" ci-dessous.
Treillis de Galois emboîtés et construction de taxonomies sur des données semi-structurées
Nous nous sommes intéressés en collaboration avec l'équipe IASI du LRI, à la construction de treillis de Galois correspondant à des grains de représentations plus ou moins grossiers. Nous avons ainsi défini un ordre partiel, nommé emboîtement (nesting) sur des treillis de Galois [Pernelle et al., 2002]. Nous étudions dans ce cadre une notion d’extension prenant en compte (selon un degré variable) l'influence d'un typage des instances sur la formation des concepts [Pernelle et al., atelier Galois AFIA 2003, ICFCA 2003]. Nos recherches s'orientent actuellement vers l'algorithmique associée à ces nouveaux treillis et leur traduction en termes de règles valides sur les instances. Les perpsectives en Data Mining sont prometteuses.
Cette recherche est motivée par la découverte de régularités au sein de divers types d'informations séquentielles (topologie de gènes dans des séquences d'ADN, chroniques temporelles …). Plus précisément nous travaillons sur la détection de motifs relationnels répétés dans les séquences, c’est-à-dire de motifs décrivant non seulement leurs composants mais aussi les relations qui les lient. Nous avons décrit récemment [El-zant & Soldano, 2003] l'algorithme KMRRelat et les conditions de son application à la recherche de motifs structuraux 3D sur les protéines. Le logiciel de recherche de motifs structuraux associé est en cours de développement.
Cette recherche porte sur l'apprentissage de motifs temporels dans des bases de données. La partie théorique de ce travail consiste à associer les régularités de sous-séquences à des connaissances du domaine pour comprendre, expliquer ou prédire le fonctionnement d'un système en fonction des connaissances partielles disponibles. Les outils utilisés sont en particulier : la théorie des treillis et les algèbres du temps [Osmani, 2002].
Parmi les applications potentielles de ce travail :
la gestion de réseaux de télécommunications (qualité de service et pannes)-projet MAGDA 2
le diagnostic automobile-projet RESEDA.
Cet axe est commun avec le thème SMA de l’équipe. Dans le cadre de la thèse d’Alejandro Guerra Hernandez, nous nous sommes intéressés à l'apprentissage symbolique multi-agents. Le SMA considéré est composé d'agents communicants de type BDI (Beliefs, Desires, Intentions). Pour cela, nous avons défini une architecture BDI intégrant un module d’apprentissage (existant) basé sur des techniques inductives d'ordre un. (précisément le programme ACE). Au niveau individuel, un agent apprend les contextes de plans BDI. Au niveau collectif, un groupe d'agents BDI améliore son apprentissage de contextes de plans en échangeant des croyances avec d'autres agents.
L'ordre partiel (nesting) sur les treillis de concepts, et en particulier la construction d'un treillis utilisant la notion d'extension d'un concept relativement au typage initial des objets.
Un modèle pour formaliser l'apprentissage à partir d'observations partiellement décrites, et en particulier des résultats portant sur l'expressivité.
Un algorithme efficace de recherche de mots relationnels répétés et son application à la recherche de motifs 3D.
La stratégie de saturation des exemples à partir de "défauts" et d"exceptions" représentant le point de vue de l'expert-utilisateur avant de procéder à un apprentissage à partir d'exemples.
Une plate-forme pour l’apprentissage multi-agents (cf. le thème SMA).
Henry Soldano a participé (fin en novembre 2002), en compagnie de Dominique Bouthinon et Nahla El Zant, au projet « Caractérisation et recherche des motifs de fixation des transposases dans les génomes » (resp. D. Anxolabehère, Institut Jacques Monod) sur la partie méthodologique de la recherche de motifs.
L’apprentissage symbolique est un de sous-thèmes des projets RNTL RESEDA et RNRT MAGDA2 (cf. le thème diagnostic).
- Avec l’atelier de BioInformatique de Paris VI (J. Pothier, E. Coissac, I . Goncalves) pour la recherche de mots relationnels et en particulier dans le projet CNRS mentionné ci-dessus.
- Avec l’équipe IASI du LRI , Paris XI (Véronique Ventos, Nathalie Pernelle, Marie-Christine Rousset) sur l’axe Treillis de concepts.
- Avec le LIM&BIO (J-D Zucker) dans le cadre de l’EPML IAPuces.
L'intégration de Pierre Gérard au LIPN, sur des thèmes à l’intersection de l’apprentissage symbolique et de l’apprentissage numérique, renforce le thème de l’apprentissage incrémental, un modèle réaliste de la manière dont les informations devraient être traitées par un système apprenant. Ce thème est transversal dans les thèmes évoqués ci-dessus. D’autre part la création du LIM&BIO à Paris-Nord sur des thèmes d’investigation de données bio-médicales et de génétique humaine renforce l’intérêt existant déjà pour la BioInformatique au sein d’ADAge, à travers le traitement de données de séquences et de structures. Enfin l’apprentissage joue un rôle de plus en plus important en traitement du langage naturel, des problèmes nouveaux apparaissent, et des travaux transversaux sur ces deux thèmes du LIPN devraient se développer prochainement.
Thème : Apprentissage Numérique et Exploration des Données (Younès Bennani, Fabrice Bossaert, Emmanuel Viennet, Khalid Benabdeslem, Sebastien Guerif, Farida Zehraoui).
Depuis quelques années déjà, certains scientifiques se passionnent pour une nouvelle voie de recherche : les réseaux connexionnistes (réseaux de neurones artificiels). Ces techniques sont des méthodes numériques permettant de capturer des relations entre des événements ou des signaux caractéristiques d'un phénomène connu par des exemples. Ces méthodes sont utilisées le plus souvent pour des problèmes pour lesquels on est capable de réaliser un grand nombre de mesures et dont on ne connaît pas la loi sous-jacente. Cela couvre une large gamme de problèmes pouvant aller de la modélisation de phénomènes naturels à l'identification et la commande de processus industriels en passant par la reconnaissance des formes et l’exploration des données. Les recherches dans le domaine sont extrêmement actives depuis dix ans. Des laboratoires tant industriels qu'universitaires participent à cette recherche. Différentes voies ont déjà été explorées et les réseaux connexionnistes sont devenus des outils incorporés dans différents logiciels commercialisés pour les statistiques, la fouille de données (Data Mining), le traitement du signal et l'identification de systèmes.
Nos activités de recherche sont centrées sur les apports des techniques d'apprentissage connexionnistes à l'analyse, l'exploration et l'interprétation de données complexes et de taille importante. Notre travail de recherche s'oriente plus particulièrement vers l'extraction de connaissances à partir de données et l'aide à la décision. Nos objectifs et activités de recherche s'articulent autour de deux dimensions complémentaires : théorique et pratique. Les études théoriques portent sur la conception de nouveaux algorithmes d'apprentissage et le développement d’approches modulaires et hybrides faisant coopérer des techniques connexionnistes et classiques. La dimension pratique s'attache à valoriser les activités de recherche en intégrant les résultats dans des systèmes opérationnels. Cette intégration se fait dans le cadre d'applications réelles dans différents domaines : parole, image, diagnostic, Data Mining, Web Mining. Notre problème central est donc celui de l'analyse et l'exploration de données afin d'en comprendre le sens, de déceler des relations entre des événements, d'en déduire des modèles de comportement. Il s'agit de la transformation de données en connaissances qui est et sera de plus en plus touchée par la nécessité de développer, de maîtriser et de choisir de nouveaux outils d'analyse et d'exploration des données. Le principal objectif de ces outils est celui d'un processus automatisé qui prend ses sources dans les données et dont le but est l’extraction de connaissances pour l'aide à la décision.
Nous nous intéressons à la conception et la mise en œuvre d'algorithmes d'apprentissage permettant de prendre en compte :
les problèmes posés par le traitement d'applications de grande taille,
l'incorporation de connaissances liées au domaine d'application,
la capacité de généralisation et le choix des modèles.
Nous avons étudié des modèles prédictifs basés sur la modélisation des comportements dynamiques d’un processus. Cette modélisation a été réalisée à l’aide d’approximateurs de densités de probabilités conditionnelles à partir de données sous forme de séries chronologiques (temporelles). Nous avons développé des approches prédictives “à contexte borné” s’attachant à modéliser la dépendance d’une donnée à l’instant t à partir de données de contexte prises à différents instants proches. Dans le cas des séries multivariées, nous avons développé une méthode d’estimation de régions de confiance [Bennani, Bossaert, IJCIA 2001].
Par opposition aux données temporelles, le recueil des données évolutives ne se fait pas avec une périodicité de la mesure : des mesures peuvent avoir été recueillies en différents moments. Cela prive les données de leur caractère temporel au sens statistique. L’évolution de ces données peut être vue sous forme de trajectoires temporelles (de taille variable et parfois multivariées). La visualisation de ces trajectoires dans l'espace de l'évolution devient difficile à interpréter dès que le nombre de trajectoires est élevé. L'un des objectifs principaux de l’analyse de ce type de données est d'obtenir une classification (ou typologie) évolutive et incrémentale de trajectoires en fonction de leurs positions et leurs évolutions. Cette typologie permettra de diminuer le nombre de ces trajectoires, en assimilant les trajectoires de la même typologie à la trajectoire prototype de la typologie. Nous travaillons sur quelques approches à base d'algorithme d'apprentissage connexionniste non-supervisé pour traiter ce type de données en quatre phases :
- Modélisation globale : recherche d’un modèle unique de représentation qui résume d'une manière globale l'ensemble des données (compromis).
- Étude de l'interstructure : identification des proximités ou des différences entre les ensembles de données, sans description.
- Étude de l'intrastructure : analyse fine des ressemblances ou des différences permettant d'expliquer les structures identifiées.
- Étude de l'évolution des trajectoires : analyse et description de l'évolution du phénomène d'une manière globale ou étude des évolutions de chacun des éléments.
Un de nos thèmes de recherche majeur avait été la conception et la mise en œuvre de systèmes qui font coopérer différents modèles entre eux et avec des techniques plus classiques dans les différents domaines d'application. Ces systèmes constituent une autre génération des modèles connexionnistes et apparaissent comme la seule solution pour la réalisation de tâches complexes et de grande taille. Les études théoriques avaient porté sur les algorithmes d'apprentissage pour ce type de système, la décomposition de tâches, la conception de chaînes de traitement optimales. Nous avions travaillé sur la possibilité de coopération des algorithmes connexionnistes et d’autres méthodes plus classiques comme les Chaînes de Markov Cachées, afin de concevoir des systèmes modulaires hybrides.
La fonction de base d’une méthode de sélection de variables (caractéristiques) est de choisir un sous ensemble de variables pertinentes à partir de la représentation vectorielle des formes observées [Bennani, RIA, 2001, Cakmakov & Bennani, 2002]. Généralement les phases de sélection et de décision (classement) s’effectuent l’une après l’autre dans un système classique de reconnaissance des formes, les méthodes connexionnistes sont plus attrayantes car elles sont capables de mener les deux phases (sélection et classement) en parallèle : les variables sélectionnées optimisent le critère d’apprentissage. Nous avons proposé dans cette direction quelques mesures de pertinence, dont une dépendant uniquement du système [Yacoub, Bennani, IJNS, 2000].
Nous travaillons sur différents domaines d'applications, toutefois nous avons développé ces dernières années deux thèmes principaux qui sont le diagnostic des systèmes complexes et l'exploration de données issues du web : « Web Mining ».
Un premier travail rentrait dans le cadre d’un contrat avec le CNET en collaboration avec le LIP6. Le but du projet était le développement et l'adaptation de réseaux connexionnistes pour des tâches de diagnostic en temps réel dans le domaine des télécommunications [Bennani, Bossaert, 2001]. Dans le cadre d'un autre projet de recherche de type RNTL (RESEDA : Réalisation d’un Environnement Système Evolutif pour le Diagnostic Automobile), nous travaillons sur le développement de systèmes d'apprentissage connexionnistes évolutifs et autonomes pour réaliser d'une part des tâches de diagnostic automobile visant à assurer la détection de panne et d'autre part de prévision sur l'évolution à court terme d'indicateurs afin d'anticiper l'état du véhicule ou de détecter l'émergence de comportements caractéristiques de début de panne.
La croissance accélérée du nombre d’utilisateurs d’Internet, pour la plupart novices, motive fortement le développement des approches d’aide adaptative pour faciliter l’accès à l’information. L’objectif de cette étude est le développement de systèmes d'apprentissage connexionnistes pour réaliser d'une part des tâches de classification visant à détecter des profils de comportement et d'autre part de reconnaissance dynamique basée sur l'évolution à court terme des traces de navigations des internautes afin d'anticiper le profil du navigateur ou de détecter l'émergence de comportements caractéristiques d’un profil déjà connu par le système. Les systèmes de modélisation sur lesquels nous travaillons, sont des systèmes dynamiques : i.e. tiennent compte de l’évolution dans le temps des traces utilisateur. La modélisation dans ces systèmes est implicite et se fait par apprentissage : i.e. elle ne repose que sur l’analyse des traces et l'observation des interactions de l'internaute. Ces systèmes sont évolutifs : i.e. incrémentaux en classification afin d’intégrer de nouveaux types de comportement correspondant à de nouvelles classes d’utilisateurs [Benabdeslem, Bennani, ICCSA, 2001, ICANN, 2002, ICCSA, 2003].
Nous avions conçu un système modulaire d’identification vocale permettant de traiter un grand nombre de locuteurs. Pour la partie visuelle de l'identification, il s'agit de retrouver l'identité d'une personne à partir d'une vue du visage. Nous avons proposé un système d'identification de visages basé sur des architectures incluant des connaissances a priori sur le problème. Nous avons proposé une méthode permettant d'une part de réduire davantage la taille des architectures de ce type, et d'autre part de sélectionner les zones de l'image les plus pertinentes [Yacoub, Bennani, RIAO, 2000].
Parmi les nombreux résultas de nos activités de recherche, nous pouvons mettre en avant les trois contributions suivantes :
Mesures de pertinence pour la sélection de caractéristiques et l’optimisation des architectures connexionnistes.
Algorithme de pondération des variables, durant l’apprentissage, en fonction de leur pouvoir discriminant.
Classification incrémentale de données évolutives, séquences.
Nous continuons actuellement nos travaux sur la combinaison de modèles et la fusion de données et de décisions pour des problèmes de classement, de classification et de régression. Nous continuons également à travailler sur les techniques de sélection et d’extraction de caractéristiques dans les réseaux connexionnistes. Il nous paraît important de poursuivre l’étude en la généralisant à la modélisation de données dans de grandes bases de données issues du web ou des entrepôts de données. Nous envisageons aussi de développer des activités sur l'exploration de données textuelles. Les objectifs visés concernent l'accès à l'information textuelle (recherche d'information, navigation dans les documents, filtrage et routage de documents), la gestion de données textuelles (structuration de documents et indexation, classification de textes), et l'analyse de contenu (extraction d'information, acquisition de terminologie spécialisée).
• Projet de coopération FS-KD&DM, « Feature Selection for Knowledge Discovery & Data Mining » avec l'Université St. Cyril & Methodius à Skopje, Macédoine, l'Université de Sheffield, UK et le LIPN (Y. Bennani). Ce projet a donné lieu à la publication d’un ouvrage sur le thème [Cakmakov, Bennani, 2002].
• Projet MAXEEM avec NumSight Consulting : Exploration des traces de navigations des internautes. Les participants LIPN sont : Y. Bennani, R. Kanawati, S. Salotti (équipe RCLN), K. Benabdeslem, F. Zehraoui..
• Projet THALWEG (Y. Bennani) : Action de Recherche Coopérative avec le projet AIR de l’INRIA « Modèles de traitement d’image pour les données turbulentes ».
• Participation (Y. Bennani) au projet RNTL RESEDA : Réalisation d'un Environnement Système Evolutif pour le Diagnostic Automobile (cf. le thème diagnostic).
• Participation (E. Viennet) au projet RNRT MAGDA 2 : Modélisation et Apprentissage pour une Gestion Distribuée des Alarmes (cf. le thème diagnostic).
• 2001 : Brevet Maxeem™ (MaxeeMap, MaxeemFluence, DataWebhousing).
Procédé de traitement de fichiers de requêtes Internet. [WOR0200303]
Auteurs : Y. Bennani, K. Benabdeslem, E. Janvier (NumSight Consulting)
• 2003 : Brevet International
Procédé de création de cartes 2D [PCT FR02 00303]
Auteurs : Y. Bennani, K. Benabdeslem, E. Janvier (LD&A-NumSight Consulting)
Le raisonnement qualitatif, notamment appliqué à la modélisation des systèmes physiques, et le diagnostic logique à base de modèles, tous deux nés au début des années 80 aux États-Unis, se sont rapidement développés dans la communauté IA, devenant des thèmes à part entière représentés dans les conférences générales et faisant chacun l’objet de workshops spécialisés annuels.
Plusieurs chercheurs sont actifs dans les deux thèmes à la fois, ce qui s’explique assez aisément : le principe du diagnostic à base de modèles, dans sa version fondée sur la cohérence, est de comparer la situation prédite à partir d’une modélisation du comportement correct à la situation réellement observée, de détecter les contradictions entre les deux et d’en identifier les causes ; la grande force de cette approche est que l’on peut diagnostiquer un système sans avoir besoin de connaître quoi que ce soit a priori sur les défauts et/ou les symptômes possibles, contrairement aux méthodes classiques (une telle connaissance exhaustive n’étant pratiquement jamais réalisée) ; la contrepartie est que, pour des applications de taille réelle, le véritable problème réside dans la modélisation ; en l’absence de modèles numériques ou vu l’inadéquation de ceux-ci pour prendre en compte des comportements par définition atypiques et s’écartant du nominal en cas de panne ou pour fournir des explications compréhensibles par l’opérateur humain, la modélisation qualitative peut apporter des réponses.
Plus largement les deux thèmes peuvent être vus comme faisant partie de la problématique du raisonnement sur les systèmes physiques conçus et réalisés par l’homme, elle-même pierre angulaire d’une véritable IA pour les sciences de l’ingénieur.
Les recherches actuellement poursuivies ou à venir concernent :
• la théorie du diagnostic elle-même,
– l’extension de cette théorie au diagnostic dynamique où les fautes peuvent apparaître durant la surveillance, être éventuellement intermittentes, etc., donc l'intégration de la composante temporelle dans cette théorie pour assurer le suivi de trajectoires temporelles d’états possibles ;
– la succession des phases de diagnostic et de réparation (actions de correction, de contrôle, de reconfiguration) qui oblige à considérer l'incrémentalité de la tâche de diagnostic vis-à-vis d'un système qui évolue structurellement et la planification des actions ;
– l’interprétation et la gestion des alarmes d’un système de supervision de processus afin de proposer à l’opérateur humain une aide automatique à la prise de décision (prise en compte des délais d’acheminement des messages, des pertes de message, des masquages, etc. dans le cadre d’une modélisation et simulation événementielles) ;
– la prise en compte du caractère souvent distribué de la tâche de diagnostic, et donc l’extension de la théorie du diagnostic à un cadre d’algorithmique ou d’Intelligence Artificielle distribuée, voire à celui des systèmes multi-agents (conception de systèmes de diagnostic à l’aide d’agents logiciels autonomes) ;
– la problématique de l’autonomie (diagnostic et décision à bord) ;
– la comparaison et les apports respectifs des théories du diagnostic à base de modèles en Intelligence Artificielle et en Automatique ;
– la coopération éventuelle du diagnostic à base de modèles explicites avec le diagnostic à base d’apprentissage (connexionniste ou statistique en particulier) ;
• la modélisation,
– les différents niveaux d'abstraction de l'espace des valeurs des quantités physiques, fournis par le raisonnement qualitatif (signes, ordres de grandeur, intervalles numériques, etc.) ;
– les différents points de vue sous lesquels le système physique peut être considéré : structurel, comportemental, fonctionnel, téléologique (seuls les deux premiers sont actuellement bien maîtrisés) ;
– les différentes vocations des modèles : conception, prédiction, diagnostic, explication ;
– la causalité (les différentes façons de la définir, de la déterminer, et son utilisation, notamment pour l’explication) ;
– le problème fondamental et encore peu abordé de l'aide à l'acquisition de modèles, en étudiant notamment les techniques d'identification et d'apprentissage et la transformation automatique de modèles de conception en modèles de diagnostic ;
• les aspects temporels intervenant à la fois dans le diagnostic et la modélisation,
– l'ontologie du temps (instants échantillonnés, intervalles de durée, ordres partiels, abstractions temporelles, prise en compte de plusieurs échelles de temps) ;
– la cohabitation de modèles à événements discrets et de modèles à évolution continue, c’est-à-dire les modèles hybrides ;
– le rapport entre les représentations et raisonnements fondés sur la causalité et les représentations et raisonnements temporels ;
– les formalismes de représentation et les algorithmes de gestion du raisonnement temporel.
La plupart de ces travaux tirent leur essence de problèmes industriels et sont validés sur des applications réelles, dans les domaines des réseaux de télécommunications, des véhicules automobiles et des satellites. En plus de ses retombées industrielles variées et importantes, la problématique générale du diagnostic et de la modélisation de systèmes physiques est extrêmement riche du point de vue théorique et fait directement appel à ou peut concerner de nombreux domaines de l'IA : raisonnement non monotone, raisonnement à base d'hypothèses, révision de croyances, raisonnement abductif, systèmes de satisfaction de contraintes, calcul sur les intervalles, sur les ordres de grandeur, raisonnement temporel, raisonnement causal, planification, réseaux neuronaux, apprentissage symbolique, IA distribuée, etc.
La nécessité d'une telle approche multi-domaines s'étend même en celle d'une approche multidisciplinaire, notamment entre l'IA et l'Automatique, dont on étudie la complémentarité pour le diagnostic dans le cadre du groupe IMALAIA.
La croissance en complexité et en taille des réseaux de télécommunications nécessite l'application de techniques de plus en plus élaborées dans la gestion de pannes. Tout d’abord, les outils de gestion de panne doivent faire face à l'afflux important d'alarmes, par des techniques de filtrage et de corrélation de bas niveau. Aujourd'hui, des besoins nouveaux se font sentir pour étendre la portée de la corrélation. Il faut effectuer une analyse de haut niveau afin de corréler les phénomènes/événements de bout en bout. En fonction de l'étendue des connexions, cette propagation peut traverser plusieurs types de réseau : IP, ATM, FR, SDH, WDM, etc., d'où le besoin de solutions applicables sur des réseaux hétérogènes.
De plus, avec l'émergence des services électroniques (e-services) dans les réseaux de nouvelle génération, la gestion efficace de services et le développement des OSS (Operations Support Systems) revêtent une importance cruciale pour l'ensemble des acteurs du monde des télécommunications : les opérateurs, les fournisseurs de services, les équipementiers, les éditeurs de logiciels, etc. Ainsi, les systèmes de gestion doivent passer des fonctionnalités orientées vers les technologies à celles orientées vers les services et les utilisateurs finaux. Par exemple, pour pouvoir tenir ses engagements envers les clients (SLA - Service Level Agreement), les fournisseurs de services (ISP, ASP) ont besoin de suivi en-ligne de la qualité de service, de l'identification des ressources manquantes, de la détection des défaillances influençant leurs clients, de l'anticipation des problèmes par l'analyse de la dégradation et la gestion de trafic.
Dans ce contexte nous cherchons à :
- étendre la corrélation d'événements et le diagnostic à des environnements hétérogènes,
- déterminer l'impact des pannes techniques sur les services. Il s'agit de corréler les processus de gestion de pannes avec ceux de la gestion de services,
- proposer des solutions distribuées dans la mesure où l'ouverture et l'hétérogénéité sont peu compatibles avec une supervision centralisée.
Nos travaux de recherche, d’abord conduits au travers de deux contrats successifs de trois ans avec le CNET, sont menés depuis fin 1998 dans le cadre de contrats RNRT (Réseau National de Recherches en Télécommunications).
• Modèles pour des algorithmes distribués
Le projet RNRT exploratoire MAGDA « Modélisation et Apprentissage pour une Gestion Distribuée des Alarmes » (11/1998 - 11/2001) s’est focalisé sur la supervision distribuée. Le LIPN a été plus particulièrement chargé de la modélisation des équipements et d’un réseau prototype, en s’appuyant sur les normes SDH et sur les informations disponibles chez Alcatel, et des aspects liés à la normalisation [Lièvre et al., 2000 ; Dague et al., ISIS’2001 ; Krief, Osmani, 2002 ; Aghasarian et al., 2002]. Ces modèles, développés sous forme d’automates ou de pièces, alimentent les algorithmes distribués développés à l’INRIA/IRISA (diagnostiqueur et puzzle de Viterbi), qui ont été testés sur la plate-forme de gestion de réseau SDH ALMAP-IF d'ALCATEL [rapport MAGDA].
• Techniques d’apprentissage
Le projet RNRT exploratoire MAGDA2 « Modélisation et Apprentissage pour une Gestion Distribuée des Alarmes de bout en bout » (11/2001 -12/2003) étend la problématique de MAGDA à la gestion de réseaux hétérogènes et à la prise en compte d'événements faisant intervenir l'interaction entre la couche réseau et la couche service. A côté des méthodes de diagnostic à base de modèles, des méthodes à base d’apprentissage sont investiguées. Le LIPN est responsable du sous projet sur l’apprentissage. Des techniques d’apprentissage numérique (sélection de variables) ont permis d’obtenir une estimation de la QoS à partir des indicateurs locaux mesurés sur le réseau VTHD.
• Architecture générique pour la gestion des fautes
Dans le cadre de MAGDA2, une architecture générique pour la gestion des fautes a été proposée, qui s’appuie sur GMPLS (Generalized Multi Protocol Label Switching) [Aghasaryan et al. 2002] [B. At-Hiane et F. Krief. 2002] [B. At-Hiane et F. Krief. 2003]. En effet, cette technologie définit un plan homogène de contrôle pour de multiples réseaux de transport (OTN, SDH, ATM, IP, etc.),. De plus, les entités manipulées (path, link, etc.) dans un tel plan de contrôle peuvent être vues comme des abstractions homogènes d’éléments constituant des réseaux hétérogènes.
Les avantages de cette architecture basée GMPLS sont nombreux :
le diagnostiqueur ne dépend pas du réseau de transport utilisé,
les alarmes des différentes couches réseau peuvent être corrélées,
les différentes actions de corrélation répondent aux exigences d'échelle de temps,
grâce au protocole LMP les alarmes provenant du niveau transport sont abstraites et ensuite masquées.
Nous avons également introduit la qualité de service DiffServ dans cette architecture [B. At-Hiane et F. Krief 2002] [B. Bouchenak et F. Krief 2003] et travaillons actuellement sur un modèle générique DiffServ/GMPLS.
Prospectives
La recherche actuelle au sein de MAGDA2 est centrée sur l’utilisation de techniques d’apprentissage pour le diagnostic et rassemble donc les deux thèmes apprentissage et diagnostic de l’équipe, dont la collaboration s’en trouve renforcée. L’apprentissage de chroniques s’inscrit plus largement dans l’activité d’apprentissage symbolique de motifs structurés dans des séquences, la classification et la corrélation d’alarmes ou d’indicateurs font appel aux techniques d’apprentissage connexionniste ou statistique et d’exploration de données. La coopération entre les techniques d’apprentissage et de diagnostic à base de modèles pourrait en outre se faire, dans une démarche plus prospective, via l’apprentissage de modèles, donc l’automatisation partielle de leur acquisition.
La gestion autonome dénote la capacité des processus de gestion et de l’infrastructure sous-jacente à se déployer, s’organiser et opérer sans aide extérieure. Le rôle de l’administrateur se limite au guidage de ces processus en leur fixant des objectifs et des paramètres opérationnels. Offrir cette autonomie à la gestion est crucial pour prendre en compte la dynamicité des composants à gérer.
• Architecture générique de gestion autonome
Dans la gestion autonome, où les entités de gestion deviennent plus intelligentes et la dynamicité de la situation augmente, le gestionnaire doit éviter les méthodes de gestion s’appuyant sur la synchronisation d’état avec le réseau; il est nécessaire de découpler les informations concernant le contrôle des ressources et les informations sur leur état. L’approche déclarative de gestion à base de politiques (PBM – Policy-Based Management) suggère une telle séparation et permet à l’opérateur d’établir des objectifs de service et des politiques qui sont par la suite interprétés par les ressources réseau. Ainsi, la décision sur l’allocation et la configuration des ressources peut être prise localement de façon autonome. Nos études sur la conception et l’instrumentation seront orientées vers les infrastructures de gestion à base des politiques.
Dans le cadre du contrôle par politique, l’enjeu important pour permettre l’automatisation du processus de gestion est la traduction automatique, d’une part, du contrat de service (SLS – Service Level Specification) en règles de politique et, d’autre part, des règles de politiques obtenues en politiques finalement compréhensibles par les équipements. Ce processus est encore plus difficile à mettre en œuvre dans un cadre multi-domaines où, pour la livraison d’un service de bout en bout et l’assurance de sa SLS, les opérateurs (les fournisseurs de services intra-domaine) doivent établir dynamiquement des contrats de services inter-domaines.
• Approche agent
Les propriétés des agents, en particulier d’autonomie, d’adaptation et de distribution, répondent bien à notre problématique.
Trois axes de recherche en relation avec la gestion autonome et contextuelle ont été définis :
Axe I : la gestion dynamique de la qualité de service
Nous avons proposé une architecture intelligente pour le contrôle dynamique de la qualité de service dans un réseau IP contrôlé par politique [Boukhatem et al., 2001, 2002] (Contrat INRIA I3 "Internet 3ème génération" (2000-2001)).
La transposition de l’approche contrôle par politique dans le cadre de la gestion de réseaux d’opérateurs nous a permis également de définir une architecture à trois niveaux de politiques conformes au RGT (Réseau de Gestion des Télécommunications) [H. Moungla et F. Krief].
Nous cherchons également à rendre dynamique la gestion des mécanismes de qualité de service propre à DiffServ et travaillons actuellement sur la traduction du contrat de service en règles de politiques et leur déploiement dans le cadre des réseaux hétérogènes [thèse de Hassine Moungla].
Axe II : les interfaces de négociation intelligentes
Nous cherchons à rendre dynamique le niveau de service entre un utilisateur et un fournisseur de services en fonction des contraintes de l’application, des besoins de l’utilisateur et des ressources disponibles [thèse de Zeina Jrad].
D’abord axés sur la qualité de service (Contrat RNRT ARCADE "Architecture de Contrôle Adaptative Des Environnements IP" (2001-2002)) [F. Krief et Z. Jrad] [Z. Jrad, F. Krief et B. Benmammar], nos travaux portent aujourd’hui sur la négociation dynamique de contrats de service [G. Klein et F Krief] et de paramètres de mobilité et de sécurité (Contrat RNRT IP-SIG " SIGnalisation générique du monde IP ").
Axe III : la gestion contextuelle dans les environnements mobiles.
Nos premiers résultats dans ce domaine concernent l’adaptation du handover horizontal (changement au sein d’une même technologie d’accès) et/ou vertical (changement de technologie d’accès) aux besoins de qualité de service de l’utilisateur [B. Benmammar et F. Krief].
Plus généralement, il s’agit d’adapter les services au contexte (préférences et profil de l’utilisateur, localisation géographique, déplacement de l’utilisateur, type de terminal, réseau d’accès utilisé, ressources disponibles, etc.) tout en offrant un accès transparent aux services [thèse de Badr Benmammar].
Prospectives
Les différents axes de recherche convergent vers l’Internet ambiant. Aussi nous envisageons un projet fédérateur autour de l’Intelligence ambiante qui intégrerait de façon homogène nos différents travaux.
Deux impératifs techniques ont guidé les recherches dans ce domaine : la nécessité de penser la tâche de diagnostic dès la phase de conception ; le développement de nouvelles architectures distribuées X-by-wire qui rapprochent l’automobile de l’aéronautique ou du spatial et posent de nouveaux problèmes de diagnostic.
Faisant suite à un précédent (02/1996-03/1999) projet européen Brite-Euram III VMBD, « Vehicle Model-Based Diagnosis », qui avait démontré la faisabilité des techniques de diagnostic à base de modèles pour le diagnostic à bord de véhicules automobiles, l’objectif du projet IDD, « Integrated Design process for on-board Diagnosis » (02/2000-02/2003), soumis dans le cadre du premier appel d’offres du programme Croissance compétitive et durable du 5ième PCRDT, était d'intégrer l'approche du raisonnement à base de modèles au processus de conception et de développement, afin de prendre en compte dès cette phase les nécessités du diagnostic. Nous sommes convaincus que le raisonnement à base de modèles ne pénétrera réellement l'industrie que s'il accompagne tout le cycle de vie d'un produit, de la conception à la maintenance, en passant par le développement, le test et le diagnostic, avec un partage des modèles dans ces différentes tâches et leur mise à jour en amont au niveau de la conception.
Les principales tâches étudiées dans ce projet ont été la diagnosticabilité (détectabilité et discriminabilité) et la génération de systèmes de diagnostic à bord. Le LIPN a été en charge de la conception et la réalisation d’interfaces entre les outils de CAO ou de simulation numérique (MATLAB/Simulink dans ce cas) et les systèmes de diagnostic à base de modèles (RAZ’R d’OCC’M dans ce cas), ce qui a nécessité des études sur la transformation automatisée de modèles (modèles numériques vers modèles qualitatifs). Il a réalisé le logiciel MOUSE (MOdel StrUcture Extraction) qui extrait les caractéristiques structurelles (composants et connexions) du modèle MATLAB/Simulink et discrétise le modèle numérique de simulation en un modèle qualitatif de diagnostic au niveau des composants, fournissant en sortie, au format xml, un modèle directement exploitable par RAZ’R. L’application retenue par PSA était le système de climatisation du véhicule et MOUSE a exploité le modèle Simulink de ce système, conçu par Adersa [Dague et al., rapports IDD] [Brignolo et al., 2001] [Struss et al., 2002] [Picardi et al., 2002].
Prospectives
Deux problèmes difficiles n’ont reçu que des solutions partielles et nécessitent encore des recherches : l’automatisation du choix des seuils qualitatifs pertinents pour la discrétisation et le traitement de la dynamique (RAZ’R ne faisant que des suites de diagnostics instantanés sans utiliser la relation entre une variable et sa dérivée).
Dans l’immédiat, nous participons, dans la suite de VMBD et d’IDD, à la soumission d’un projet stratégique (STREPS) dans le cadre du 6ème PCRDT, PREDIC (« Preventive Diagnosis for Vehicles »), qui mêlera des techniques à base de modèles et des techniques d’exploration de données. Ceci s’inscrit dans le cadre de l’action Automotive du réseau d’excellence MONET II (12/2001-12/2004), qui vise toutes les applications à l’industrie automobile du raisonnement à base de modèles en IA.
L’objectif du projet précompétitif RESEDA, « Réalisation d’un Environnement Système Evolutif pour le Diagnostic Automobile » (06/2001-08/2004) soumis dans le cadre du premier appel d’offres lancé par le RNTL (Réseau National de recherche et d’innovation en Technologies Logicielles) est de développer, aux fins de déploiement sur les véhicules et dans les stations de dépannage, une nouvelle infrastructure de composants logiciels de diagnostic, qui soit évolutive avec le cycle de vie des véhicules [Mateos et al.]. L’architecture utilisera des techniques d’objets distribués et la technologie de code mobile Java afin de permettre le téléchargement de fonctions de diagnostic et les changements de version de logiciels enfouis. Silicomp et Trialog sont en charge de l’implémentation de cette infrastructure logicielle, que Renault validera par des applications de diagnostic.
Le LIPN est chargé, dans une démarche plus exploratoire, de spécifier et de mettre en œuvre de nouvelles méthodes et de nouveaux outils de diagnostic qui permettront de bénéficier du retour d’expérience sur un parc de véhicules en circulation pour faire évoluer les composants de diagnostic (diaglets) en tenant compte des problèmes constatés sur le terrain. Il réunit sur ce projet des compétences en méthodes formelles de spécification, en diagnostic à base de modèles et en apprentissage. L’application retenue par Renault est celle des nouvelles architectures X-by-wire, en l’occurrence le freinage électronique. Les problèmes de diagnosticabilité et de diagnostic à bord y sont étudiés.
Prospectives
Tout comme dans le projet MAGDA2, cette recherche vise à exploiter et, si possible, à combiner deux types d’approches : le diagnostic à base de modèles et l’apprentissage, réunissant deux thèmes de l’équipe. Mais le domaine applicatif (les modèles sont ici hybrides, alors que dans MAGDA2 ils sont discrets) ainsi que les objectifs (diagnostic à bord évolutif autonome, avec donc à plus long terme des problèmes de temps réel et de taille de code à résoudre) diffèrent, ce qui conduira sans doute à des solutions sensiblement différentes. On peut envisager d’y exploiter des retombées du projet IDD, en ce qui concerne la construction et la mise à jour automatiques de modèles de diagnostic à partir de modèles de conception, l’étude de la diagnosticabilité et du diagnostic à bord. Quant à l’autonomie, c’est le thème essentiel de la recherche concernant les satellites, décrite ci-après.
Le thème de l’autonomie est devenu crucial dans l’industrie spatiale. Les recherches, d’abord lancées par la NASA (expérimentation à bord de Deep Space 1) dans le cadre de missions lointaines, sont promues aussi en Europe, par exemple dans le cadre de constellations de satellites.
Après un travail préalable de consultance pour le CNES en collaboration avec le LAAS, cette collaboration s’est poursuivie par une nouvelle étude pour le CNES (06/2000-11/2001) sur l’architecture logicielle pour les satellites autonomes [Bénazéra et al., rapport CNES, 2002], par le co-encadrement d’un thésard au LAAS co-financé par le CNES et Astrium, et par la participation à une étude pour l’ESA concernant l’autonomie des futures constellations de satellites, où nous étions responsable du lot concernant le diagnostic à bord (détection, localisation de fautes et reconfiguration) [Bénazéra et al., rapport ESA, 2002].
Le travail du doctorant a consisté à étendre les techniques développées par la NASA pour le suivi d’états d’un système discret à la prise en compte des évolutions continues. Pour ce faire, on s’est placé dans une modélisation de type hybride, avec un niveau discret modélisé par des automates concurrents et un niveau continu modélisé par des équations aux différences d’où sont tirées des influences causales, les deux niveaux interagissant. L’incertitude sur les modèles est représentée par des probabilités au niveau discret et des intervalles numériques au niveau continu. Une interface continu/discret permet de construire en ligne la structure du nouveau modèle continu et de mettre à jour incrémentalement le nouvel ordre causal associé lors d’un changement de mode opératoire au niveau discret, en formulant ce problème en un problème de satisfaction de contraintes booléennes et en utilisant des algorithmes de changement de contexte au niveau du système de maintien de vérité (TMS). La détection s’effectue au niveau continu et l’identification d’état au niveau logique booléen, en cherchant la configuration actuelle du système hybride cohérente avec les observations [Bénazéra et al., 2001] [Bénazéra et al., 2002].
Prospectives
Le travail sur la reconfiguration n’a été qu’abordé et doit être poursuivi. Ces travaux, qui vont dans le sens de la construction de superviseurs autonomes intelligents pour des systèmes hybrides, ont potentiellement un bel avenir, le concept d’autonomie étant central dans beaucoup d’applications. A plus long terme, on peut penser que l’architecture de système autonome de la NASA devra s’enrichir, en plus des trois modules actuels d’identification de modes et de reconfiguration, de planification, et d’exécution temps réel, de modules d’apprentissage, de coopération et d’aide à la décision., domaines relevant des compétences d’ADAge et d’OCAD. Dans l’immédiat, nous participons à la soumission d’un projet intégré (IP) dans le cadre du 6ème PCRDT, AEDICOS (« Autonomous Networks with Robust Embedded Distributed Information and Control Structures for Real-Time Critical Function »), dans lequel, au sein du sous-projet Réactivité, nous sommes responsables avec le LAAS de la tâche « Gestion de fautes et reconfiguration par modèles hybrides ». Les systèmes étudiés concernent le spatial et l’automobile.
Une étude de 6 mois, réunissant les thèmes Systèmes Multi-Agents et Diagnostic de l’équipe, a été menée en 2000 avecThomson-CSF Detexis (maintenant Thales Systèmes Aéroportés). Il s’est agi d’étudier la faisabilité de l’utilisation du paradigme multi-agents, et plus spécifiquement du concept d’agent cognitif autonome, pour la conception de systèmes informatiques complexes. La principale retombée attendue est de rendre plus aisée l’évolutivité de ces systèmes, très limitée actuellement par l’utilisation des techniques classiques de génie logiciel, et d’accroître leurs fonctionnalités. La démarche retenue a consisté à effectuer la ré-ingénierie d’un prototype de diagnostic automatique de cartes électroniques, CDIAG, fondé sur l’approche à base de modèles de l’IA et actuellement implémenté de manière traditionnelle. Une architecture multi-agents du système de diagnostic a été élaborée. Cette étude s’est poursuivie par un stage de DEA chez Thales en 2001 aboutissant à la réalisation d’une plate-forme générique multi-agents (cf. le thème SMA).
Prospectives
L’utilisation du paradigme SMA pour concevoir des logiciels complexes en termes d’agents logiciels autonomes est un axe de recherche nouveau et prometteur. En ce qui concerne le thème diagnostic proprement dit, le travail accompli dans cette étude à partir d’un logiciel de diagnostic est un premier pas vers une architecture multi-diagnostiqueurs ou multi-superviseurs, qui est un prolongement du diagnostic distribué étudié par exemple dans MAGDA et dont le besoin va se faire rapidement sentir, comme on l’a vu ci-dessus pour les réseaux ou les constellations de satellites. Nous participons actuellement à la définition d’un projet d’Architecture Multi-agents et Communicante de Diagnostic Préventif Embarqué, à soumettre prochainement dans le cadre PREDIT ou RNTL.
La recherche au sein du groupe de travail IMALAIA, « Intégration de Modèles ALliant l'Automatique et l'Intelligence Artificielle », reconnu par le GDR Automatique et le PRC-GDR I3, est consacrée depuis 1999 à une comparaison en profondeur des techniques de diagnostic à base de modèles de l’IA, fondées sur la cohérence logique, et de l’Automatique, fondées sur les relations de redondance analytique (équations structurelles de parité), pour la détection et l’isolation de fautes, afin d'en faire ressortir les différences et les complémentarités. Les rapports entre conflit en IA et structure d’une RRA non satisfaite par les observations en Automatique ont été élucidés et des conditions suffisantes d’équivalence données. L’hypothèse implicite d’exonération par les RRAs satisfaites faite en Automatique a été explicitée et la façon de s’en affranchir a été décrite [Cordier et al., SAFEPROCESS, 2000] [Cordier et al., ECAI, 2000] [Cordier et al., IEEE Transactions on SMC, 2003].
Prospectives
Le rapprochement des communautés IA (DX) et Automatique (FDI) pour ce qui est du diagnostic et de la supervision est un thème très porteur sur lequel le groupe IMALAIA est particulièrement bien positionné. Les travaux décrits ci-dessus ont porté uniquement sur le cas atemporel. Or c’est évidemment le cas dynamique qui présente le plus d’intérêt. C’est pourquoi le groupe a décidé de consacrer ses efforts à étendre le cadre commun et l’intégration des méthodes complémentaires du cas atemporel au cas temporel. Au plan européen, cette recherche s’inscrit dans l’action BRIDGE du réseau d’excellence MONET II.
L’action de diffusion de la connaissance, tant en diagnostic qu’en modèles et raisonnements qualitatifs et en raisonnement causal s’est traduite par les ouvrages [Dague, Hermès, 2001], [Travé-Massuyès, Dague, Hermès, 2003], [Dague, Travé-Massuyès, Intellectica, 2003]. Il est à noter que le numéro sur la causalité de la revue Intellectica est coordonné par des membres des équipes RCLN et ADAge. Le raisonnement causal et différentes acceptions de la causalité qu’il recouvre est en effet un axe de recherche commun entre les deux équipes (causalité en linguistique, causalité en théorie de l’action d’un agent rationnel d’une part, causalité physique macroscopique, en particulier pour des systèmes conçus et fabriqués par l’homme, à des fins d’explication ou de raisonnement diagnostique d’autre part).
Après des recherches sur la représentation et le raisonnement sur les intervalles (extensions de l’algèbre de Allen) [Balbiani, Osmani, 2000], des travaux sont poursuivis sur le raisonnement spatio-temporel et l’utilisation des CSP dans le cadre de la mise à jour des informations géographiques. L’objectif est de proposer une modélisation des données géographiques pour permettre une mise à jour automatique de leurs évolutions [Kadri-Dahmani, Osmani, 2002].
Nous pouvons en résumé mettre en avant les contributions suivantes de ces quatre dernières années et dresser les projets de recherche qui les prolongent, dans un avenir proche ou à plus long terme :
L’aide à l'acquisition de modèles, à leur évolutivité et à leur réutilisabilité, en utilisant les spécifications et les données de conception. Le travail entrepris, concernant les véhicules automobiles, a déjà abouti à une maquette d’un logiciel qui extrait et discrétise automatiquement un modèle de CAO (en Matlab/Simulink) pour obtenir un modèle qualitatif de diagnostic qui alimente un outil à base de modèles. Ce travail est à poursuivre pour résoudre les problèmes posés par cette abstraction de modèles, comme le choix automatique des seuils et la prise en compte de la dynamique, ainsi que pour l’étude de la diagnosticabilité (détectabilité, discriminabilité, placement de capteurs).
L’utilisation de techniques d’apprentissage. Une collaboration très étroite a commencé avec le thème apprentissage pour des problèmes de diagnostic. Elle met en jeu tant de l’apprentissage statistique (corrélation d’alarmes ou d’indicateurs pour du diagnostic prédictif) que connexionniste (analyse de séquences temporelles), ou symbolique (apprentissage de chroniques). La coopération de ces techniques et de celles à base de modèles pourrait être envisagée dans un futur plus lointain sous la forme de l’utilisation de méthodes d’apprentissage pour l’acquisition ou la mise à jour de modèles explicites, ou encore la cohabitation de modèles explicites et de modèles boîte noire appris. Une soumission de projet européen vise à étudier cette coopération pour le diagnostic préventif.
La comparaison et la complémentarité des approches à base de modèles issues de l’Intelligence Artificielle et de l'Automatique (dans le cadre des résidus structurés issus des équations de parité). Elles ont été étudiées dans le cadre des PRC GDR I3 et Automatique. Les hypothèses parfois implicites des deux approches ont été explicitées et confrontées et des conditions suffisantes d’équivalence des résultats ont été fournies selon ces hypothèses, dans un cadre atemporel. Ce travail de recherche (en collaboration avec RCLN) va à présent se poursuivre dans le cadre temporel.
La problématique d’autonomie dans le cadre du diagnostic (diagnostic à bord). Une extension des travaux de la NASA du cas discret au cas hybride a été menée dans le cadre d’une bourse de thèse. Une soumission de projet européen vise à étendre ces travaux (notamment à la reconfiguration) pour aboutir à un prototype qui soit testé sur des applications spatiales et automobiles. A un horizon plus lointain, des modules de planification, de décision, voire d’apprentissage seraient nécessaires dans l ‘architecture d’agent autonome.
L’étude du diagnostic distribué dans un cadre multi-agents. La supervision de réseaux de télécommunications a déjà nécessité une approche décentralisée. Au delà du diagnostic distribué, un axe qui nous semble porteur est celui du diagnostic dans un cadre de systèmes multi-agents.Le concept d’agents est déjà utilisé dans la gestion autonome et contextuelle de réseaux. Une étude préliminaire a eu lieu avec Thales, qui a conduit à la spécification en termes d’agents logiciels autonomes d’un système de diagnostic de cartes électroniques. Un projet d’architecture multi-agents de diagnostic embarqué est actuellement à l’étude pour soumission dans un cadre national.
Fondements scientifiques (brève présentation du domaine)
Les Systèmes Multi-Agents (SMA) sont au carrefour de deux domaines : l'Intelligence Artificielle Distribuée (IAD) et les systèmes répartis (SR). De ce fait, les SMA offrent des avantages au niveau conception, mais aussi au niveau déploiement et exécution d’applications réparties et coopératives.
En tant que systèmes issus de l’IAD, les SMA reposent sur des entités de base (appelées agents) ayant des aptitudes cognitives (e.g. capacités de raisonnement) qui leur confèrent un comportement réflexif (niveau résolution de tâche et niveau contrôle de cette résolution au sein de l’agent) et par conséquent une certaine autonomie. Les agents peuvent également être dotés de capacités d’apprentissage pour mieux s’adapter aux environnements dynamiques ou instables. De plus, la décomposition et la distribution des traitements sur l’ensemble des agents permettent le traitement de problèmes simultanés et potentiellement corrélés avec des optimisations éventuelles. La distribution permet entre autres d'améliorer les performances globales du SMA.
En tant que paradigme de conception, les SMA offrent 2 approches :
une approche descendante (top-down) adaptée à la conception de systèmes complexes. Il s’agit de la décomposition en sous-systèmes interactifs assurant une résolution distribuée [cas du projet SyMAD pour le diagnostic distribué]
une approche ascendante (bottom-up) appropriée à la modélisation et la simulation de systèmes dynamiques. Dans ce cas, la décomposition est inhérente au problème et l’approche permet la composition de sous-systèmes en interaction assurant une exécution distribuée [e-commerce, Thèse de Guillaume Vauvert]
Les avantages de ces deux approches sont essentiellement l’adéquation à des applications distribuées et coopératives, la capacité de prendre en charge des systèmes ouverts et l’intégration d’opérateurs humains dans le cycle de vie du SMA.
Cependant, dans ces deux cas, l’interaction des sous-systèmes introduit du non déterminisme et la non monotonie dans l’exécution. La conciliation entre l'autonomie locale des agents et la cohérence globale du SMA requiert des modèles de coordination sophistiqués et surtout dynamiques (observation et contrôle réparti).
Nos activités de recherche portent sur des modèles formels de Systèmes Multi-Agents (SMA) en vue de la conception, de la vérification et de l'évaluation d'applications réparties coopératives. Nous nous plaçons dans le cadre d’agents potentiellement distribués sur des sites géographiquement distincts comme c’est le cas pour le diagnostic réparti, l’aérospatial, les applications réseaux de télécommunication, les applications autour du WEB (e.g. e-commerce, web services, etc.) ou encore l’enseignement à distance (e.g. e-learning, visioconférence), etc.
L’approche multi-agent que nous avons développée, au sein du thème SMA au LIPN, se caractérise par les aspects suivants :
L'intégration de la distribution comme propriété intrinsèque à tous nos modèles. De ce fait ils sont adaptés à des applications réellement distribuées.
La spécification formelle de nos modèles en vue de leur validation. Nous avons cherché à élaborer des modèles qui prennent en charge la concurrence et la vérification (e.g. modèle formel de planification distribuée, démarche méthodologique pour l'ingénierie des protocoles d'interaction, etc.).
L'application de nos modèles théoriques et leur implantation dans le cadre de plusieurs contrats de recherche et de développements avec des partenaires industriels.
Nous nous intéressons aux SMA en tant qu'approche cognitive pour la conception, la vérification et l’évaluation d’applications réparties coopératives à base d’agents intelligents. La démarche adoptée est la suivante : un SMA se situe au carrefour de 3 axes fortement :
La cognition qui fait référence aux aptitudes « intelligentes » d’un agent telles que l’autonomie, la capacité d’apprentissage, le raisonnement, etc. ;
La concurrence qui permet aux agents de distribuer la résolution des problèmes et de les optimiser, ou enfin de concourir à l’affectation et à la résolution de tâches;
L’interaction qui permet aux agents d’échanger leurs connaissances (ou croyances), de partager des objectifs ou de coordonner leurs activités.
Ces trois axes définissent ce que nous appelons un espace SMA dont les plans projections se reportent à des domaines de recherche bien connus et connexes (e.g. Systèmes répartis, Objets consurrents, etc.). Cette vision nous semble intéressante pour appréhender un SMA comme une fédération -au moins au niveau conceptuel- d’approches voisines et bien établies. L'intérêt est triple : 1) positionner l'approche SMA par rapport à ces approches; 2) cerner les spécificités et les difficultés intrinsèques de la problématique multi-agents ; 3) mesurer les apports réels de ces approches au domaine SMA, en les projetant sur les différents axes ou plans de l’espace SMA.
Nous avons donc mené un certain nombre de travaux qui s'articulent autour de ces trois axes :
Concernant les aptitudes cognitives des agents, nous nous sommes intéressés aux modèles de raisonnement collectifs dans le cadre d’agents intentionnels (de type BDI) et d’agents normatifs [Projet CONACYT], à la prise de décision distribuée dans le cadre d’agents rationnels [Collaboration avec le LAMSADE], à l'apprentissage multi-agents [Thèse d’Alejandro Guerra] dans le cadre d’agents intentionnels (BDI), à la spécification formelle des préférences d'agents rationnels [Thèse de Guillaume Vauvert], dans le cadre de la formation de coalitions, etc.
Concernant la répartition et la concurrence des traitements, nous nous sommes intéressés aux modèles de coordination distribuée par planification multi-agents [Thèse de Frédéric Marc, Dassault-Aviation], aux problèmes d'atteinte de consensus par formation de coalitions et protocoles de coopération et [Thèse de Guillaume Vauvert].
Concernant les interactions entre agents, nous nous sommes intéressés à la sémantique opérationnelle des protocoles d'interaction et nous avons proposé une démarche méthodologique pour l’ingénierie de ces protocoles [Collaboration LAMSADE dans le cadre de la thèse d’Hamza Mazouzi], à la sémantique intentionnelle des actes de communication [Projet CONACYT], et à la modélisation cognitive des interactions [Thèse d’Alexandre Pauchet], etc.
Nous continuons à développer ces axes et plusieurs prolongements ont été initiés (cf. thèses, contrats de recherche et collaborations). Cependant, la volonté de mettre en pratique nos modèles théoriques, nous a conduits à développer un axe de recherche à part entière autour de l'ingénierie des SMA (Framework d'agents et framework de SMA développé dans la section Perspectives de recherche) [Thèse de Nejla Amara] [DEA d’Alexandru Suna].
Résultats nouveaux
Nous citons les plus importantes et plus récentes contributions dans le domaine.
Le formalisme Réseaux de Petri Récursifs pour la représentation et de manipulation de plans multi-agents et son extension des Réseaux de Petri Récursifs par la couleur : Réseaux de Petri Récursifs de haut niveau [AAMAS’02].
Algorithme de coordination de n agents.
Algorithmes de fusion, de séquentialisation et paralléllisation de plans (dans le cas des Réseaux de Petri Récursifs).
Algorithme de reconnaissance de protocoles d'interaction basé sur les techniques de dépliage RdP [IJCA 01].
Algorithme de consensus pour la formation de coalitions [MAAMAW’01]
Méthodologie pour l’ingénierie des protocoles d’interaction [AAMAS’02].
Logique modale pour le raisonnement sur les attitudes intentionnelles d’agents complexes.
Logique déontique dynamique pour le raisonnement sur les communications entre agents normatifs [MICAI 02].
Un prototype “ RAPID ” dans le cas du projet CNET (en C++, sous Unix) en collaboration avec le LAMSADE.
Une plate-forme dans le cas du projet GIS pour la simulation de résolution collectives (en JAVA).
Une plate-forme dans le cadre de la thèse d'Alejandro Guerra pour l'apprentissage multi-agents (en LISP et JAVA)
Une plate-forme dans le cadre de la thèse de Guillaume Vauvert pour la formation de coalitions (en JAVA).
Une plate-forme générique (en JAVA) orientée communications dans le cadre du stage de DEA de Gilles Klein et en collaboration avec Patrick Taillibert (Thalès Systèmes Aéroportés).
Perspectives de recherche
A moyen terme, nous nous intéressons à l’élaboration d’un langage de programmation orienté agent. L’intérêt escompté d’un tel langage est la définition d'une sémantique opérationnelle des SMA en vue de leur conception et vérification. Depuis peu de temps, nous avons commencé l'exploration de la définition d'un langage à base du -calcul mais qui intègre la dimension cognitive des agents, dans le cadre du stage de DEA d'Alexandre Cruz (Marne La Vallée - Promotion 2001). Ce stage a été co-encadré par Amal El Fallah-Seghrouchni (ADAGE), Christophe Fouqueré et Christophe Tollu de l’équipe LCR (équipe Logique, Calcul et Raisonnement). Cette voie est poursuivie en collaboration avec Christophe Fouqueré et Patrick Baillot. Nous avons explorons, dans le stage de DEA d'Alexandru Suna (LIPN - Promotion 2002), le calcul des « ambients » de Cardelli et Gordon. Ce travail de collaboration est poursuivi dans le cadre d’un projet LAFMI (Laboratoire Franco-Mexicain en Informatique).
L’évolution grandissante du réseau mondial aussi bien en termes du volume d’information disponible qu’en termes de services offerts a rendu nécessaire la proposition des outils d’aide à la localisation et l’exploitation de l’information pertinente. Trois grandes approches complémentaires sont explorées dans la littérature afin de faciliter l’accès à l’information. 1) renforcer la description sémantique de l’information disponible (i.e. le Web sémantique), 2) améliorer l’efficacité des méthodes de recherche d’information par le biais de l’élaboration des modèles effectifs des utilisateurs et 3) fournir des outils de coopération (directe et/ou indirecte) afin de permettre la (ré)utilisation des expériences passées des utilisateurs dans les tâches de recherche d’information. Dans nos travaux nous explorons essentiellement la troisième approche. Notre objectif est de fournir un environnement logiciel qui permet à un groupe d’utilisateurs de partager les différents types d’expériences acquises lors des tâches de recherche d’information (où chercher, comment chercher, trier l’information en fonction de sa pertinence pour la tâche actuelle, etc.). La coopération entre les utilisateurs peut se faire d’une manière directe (par l’utilisation d’outils collecticiels) ou indirecte (par des agents logiciels interposés). En effet les utilisateurs cibles tous comme les sources d’informations sont géographiquement réparties. Le paradigme des systèmes multi agents est alors adopté. Chaque utilisateur est assisté par un groupe d’agents logiciels personnels. Chaque agent assistant est spécialisé dans un type d’activité de recherche d’information (i.e. Aide à la navigation sur le Web [MALEK01], aide à la gestion de signets [Kanawati02] aide au tri des résultats des moteurs de recherche [Kanawati03]. L’aide apportée par un agent est calculée en fonction du modèle utilisateur appris par l’agent et en fonction des expériences acquises par des agents homologues associés à d’autres utilisateurs. La méthodologie du raisonnement à partir de cas (RàPC) est utilisée comme une méthodologie d’apprentissage et de modélisation de l’expérience des utilisateurs.
A moyen terme, nous voudrions permettre à des agents hétérogènes (du point de vue de la tâche cible) d’interagir afin de confronter et améliorer leurs modélisation de l’utilisateur et des communautés d’utilisateurs. A long terme, notre objectif est de fournir un environnement où cohabitent agents logiciels et agents humains qui interagissent et collaborent dans des tâches de recherche d’information et de veille informationnel.
Selon notre approche, les agents assistants utilisent la méthodologie du RàPC pour modéliser l’expérience de l’utilisateur associé à partir des données de traces (log) de son utilisation de l’outil de recherche ou d’indexation d’information. Les traces d’usages sont des données évolutives et de nature temporelle (ou séquentielle). De plus, la quantité des informations brutes à manipuler (les données de traces) est très volumineuse. L’application du RàPC dans ce contexte pose de nombreux défis (thèse de Farida Zehraoui) : la définition de la structure d’un cas qui prend en compte la notion d’historiques, l’extraction des cas à partir des données bruts, la cohabitation des cas et des données bruts dans le système, la maintenance du système (en particulier la maintenance de la base de cas). Nous nous sommes intéressé dans un premier temps à la maintenance de la base de cas. Des nouvelles mesures de qualité de cas sont proposées afin de réduire le volume de la base de cas sans pour autant réduire la compétence du système. Cette stratégie a été testée avec succès dans le cadre d'une application de prédiction en temps réel de l'objectif d'un utilisateur navigant dans un site de commerce électronique [ZEH02a, ZEH02b, ZEH03a]. Nous travaillons actuellement sur l’élaboration d’un système hybride combinant le RàPC et des techniques connexionnistes afin d’améliorer à la fois l’indexation des séquences, des cas extraits des séquences mais aussi pour améliorer la phase de la réutilisation dans le cycle d’un système RàPC dédié pour le prédiction de l’évolution des séquences.
Les travaux menés dans ce thème sont faits en coopération avec M. MALEK (LAPI-EISTI). Deux thèmes sont étudiés :
Système multi agents pour le RàPC. Nous étudions les différentes approches de la distribution du cycle du raisonnement à partir de cas et les protocoles d’échanges des connaissances utilisées dans un système RàPC.
RàPC pour les systèmse multi agents. Nous nous intéressons particulièrement à la problématique d’identification automatique des communautés d’intérêts dans le cadre d’un système d’agents assistants.
Deux domaines d’applications sont considérés :
Le développement des sites Web adaptatifs. Différents types d'applications sont étudiés : la personnalisation de sites Web [MAL01b], l'aide à la navigation dans un hypermédia éducatif [ELY01] et la reconnaissance et la prédiction des objectifs utilisateurs dans un site de commerce électronique [ZEH02a]. Un nouveau schéma de codage des fichiers log de sites Web est proposé. Le principe de ce schéma est de recoder les sessions de navigations en termes d'actions comportementales. L'identification des actions comportementales repose sur l'utilisation des connaissances sur l'organisation et/ou le contenu du site. Le schéma proposé permet aux systèmes de prédiction et de classification de comportements des utilisateurs de mieux prendre en compte la nature dynamique des sites Web actuels. L'expérimentation de ce schéma est faite dans le cadre du système Cobra [MAL01b, KAN02a].
La recherche d’information sur l’Internet. Nous nous intéressons à la problématique de l'identification automatique des communautés d'intérêt par l'analyse des comportements des utilisateurs lors de l'indexation des sources d'information. Nous nous somme intéressé en particulier à l'analyse de comportements des utilisateurs lors de la gestion des leurs collections de signets (i.e. bookmarks) de sites Web. Un système multi agents appelé CoWing, pour la gestion coopérative de signet a été développé. Chaque utilisateur est associé à un agent assistant, appelé Wing (Web Indexing Agent). Un agent Wing a pour rôle d'apprendre la stratégie de classification de signets appliquée par l'utilisateur auquel il est associé. Un système de classification supervisé et hybride combinant un réseau connexionniste et un système de raisonnement à partir de cas est utilisé à cet effet [MAL01a]. Un protocole de coopération, « peer to pee », entre les différents agents est défini afin d'identifier les communautés d'intérêt [KAN01a]. Une autre application multi agents a été développée [Kanawati03] dont l’objectif est d’utiliser l’expérience passée d’un groupe lors d’utilisation des moteurs de recherche sur le Web afin d’améliorer le tri des réponses rendues par les moteurs de recherche.