LIPN

Au cours des prochaines années, l’activité de recherche du laboratoire se concentrera prioritairement sur les orientations scientifiques suivantes dont certaines sont inter-équipes.

Méthodes exactes et heuristiques pour l'optimisation combinatoire (OCAD)

Par rapport à nos objectifs antérieurs (contrat 2001-2004) nos recherches sur l’optimisation combinatoire multicritère (avec applications aux télécommunications) ont été couronnées de succès. Dans le domaine de la réoptimisation de problèmes en nombres entiers concernant l’évolution des données de l’objectif, des avancées significatives ont été obtenues pour le problème de biknapsack en variables binaires.

Nos recherches se poursuivront toujours en priorité vers la réoptimisation de problèmes en nombres entiers avec application au sac à dos multidimensionnel et au plus court chemin avec contraintes de ressources.

La problématique abordée est la résolution globale efficace d'une suite d'instances du problème traité. Trois axes seront développés :

- dans le cadre des dualités lagrangiennes et agrégées la prise en compte de l'évolution des données du problème (méthodes de sous-gradient, génération de colonnes),

- l'hybridation de métaheuristiques et d'heuristiques duales,

- l'incrémentalité, c'est-à-dire la prise en compte de l'évolution du nombre de contraintes et/ou de variables.

Nous continuerons également à développer l’étude de relaxations fortes pour les problèmes d'optimisation en variables 0-1 linéaires et non linéaires.

Combinatoire, analyse de structures discrètes et algorithmique distribuée (OCAD)

La combinatoire analytique vise à établir des propriétés statistiques de structures discrètes et à analyser la complexité en moyenne d’algorithmes par l’utilisation des séries génératrices, de l’asymptotique réelle et complexe et de méthodes stochastiques. La plupart de ces domaines de recherche reposent sur un nombre restreint de modèles combinatoires fondamentaux : graphes, permutations, arbres, mots, chemins, partitions, cartes etc. Des analyses quantitatives de ces structures qu’elles soient énumératives, en moyenne, ou en distribution, sont la clef de résultats importants, voire majeurs. L’activité de recherche du thème Combinatoire et algorithmique des systèmes distribués et parallèles sera donc centrée sur les problématiques suivantes :

- conception et analyse de complexité d’algorithmes pour la détection d'information structurelle dans les systèmes distribués :estimation de la taille, du diamètre, du degré maximal, etc. (recrutement de Jean-Marie Le Bars) ;

- complexité d'algorithmes et analyse perturbative : localisation des instances difficiles (recrutement de Cyril Banderier) ;

- étude de propriétés spécifiques des graphes aléatoires et de phénomènes de seuil associés (recrutement de Vlady Ravelomanana) ;

- méthodes asymptotiques et modélisations stochastiques (marches aléatoires sur les graphes, modèles d'urne, etc.), applications à la génération aléatoire de structures combinatoires fondamentales.

Ces orientations de recherche supposent l’utilisation des méthodes classiques de la combinatoire bijective et analytique. Ils rejoignent ainsi la problématique d’un thème de l’équipe de LCR, à savoir la combinatoire algébrique, et sous-tendent la coopération inter-équipes (OCAD-LCR). Par ailleurs, une autre coopération OCAD-LCR peut d’ores et déjà s’envisager sur le thème de l'énumération des arbres intervenant en théorie des types.

Combinatoire et Physique (LCR)

Depuis 2001, un groupe de travail du LIPN développe une approche combinatoire et algorithmique de problèmes empruntés à la physique. Il s'agit avant tout de parvenir à une meilleure compréhension des algèbres qui jouent un rôle de premier plan en physique mathématique, afin de pouvoir y mener des calculs efficaces. Cette orientation est en grande partie due au recrutement de Frédéric Toumazet comme maître de conférences en 2000 et au lancement en octobre 2001 d'une action JemSTIC au LIPN.

Des résultats partiels ont déjà été obtenus dans cette direction (interprétation combinatoire des opérateurs de création et d'annihilation de l'algèbre de Weyl non commutative). Nous poursuivrons nos travaux en étudiant les algèbres de la théorie des champs (algèbres de fusion en théorie conforme, algèbres de substitution pour la théorie quantique des champs).

Nous nous appuierons sur le séminaire "Combinatoire, informatique et physique" (installé à Villetaneuse à la rentrée 2002) et sur ses ateliers et travaillerons en étroite collaboration avec les chercheurs du phalanstère de combinatoire algébrique de Marne-la-Vallée, où est mise en oeuvre une approche algébrico-combinatoire de la théorie quantique de l'information. Nous espérons aussi resserrer nos liens avec les chercheurs de l'équipe OCAD qui développent pour des physiciens des techniques de combinatoire analytique et asymptotique.

Logique linéaire, interactivité et modélisations (LCR)

En théorie de la preuve (en particulier en logique linéaire, en logique non-commutative, ou dans la ludique), on peut trouver trace de deux modes d'exécution. Un mode est lié à la recherche de preuve, celle-ci représente les interactions internes à l'évolution de processus. Un autre mode découle du mécanisme d'élimination des coupures, lesquelles représentent l'interaction externe entre des preuves interprétées comme programmes. Nous poursuivrons la mise en œuvre de ces interprétations opérationnelles des preuves pour la conception de langages de programmation, l'étude de mécanismes calculatoires ou la modélisation :

- après la thèse de Rémi Baudot sur la non-commutativité et la focalisation en programmation logique, étude de l'apport de la logique non-commutative et de la notion de réseau de preuves dans le cadre de la programmation distribuée (recrutement de Virgile Mogbil) ;

- utilisation du typage en logique linéaire (ou ses variantes) pour la garantie de propriétés de complexité de programmes et pour l'étude des calculs de processus (recrutement de Patrick Baillot).

Spécification, modélisation, validation, et certification de logiciels (LCR)

Nous étudierons les apports de la spécification pour la modélisation et la validation de systèmes informatiques (notamment les systèmes concurrents ou réactifs, et ceux qui mettent en œuvre des bases de données objets et les entrepôts de données). Cet axe sera abordé sous différents angles, tels que la définition d'une sémantique (par exemple pour Java) ou la définition de cadre méthodologique précis (établissant un lien avec la notation UML) avec des concepts orientés objet (types abstraits algébriques munis de notion d'état, de transition,...) .

Avec ces mêmes concepts et avec la notion de module, on étudiera la structuration des modèles et ses conséquences tant sur la spécification que sur la validation de propriétés. Ces travaux entamés dans le cadre des réseaux de Petri seront poursuivis pour prendre en compte les spécificités des réseaux de Petri de haut niveau (algébriques, colorés, …) (recrutement de Laure Petrucci).

Analyse du contenu textuel (RCLN)

Au-delà des techniques de recherche d'information qui associent un ensemble de documents à une requête, un enjeu majeur aujourd'hui est l'accès au contenu même des documents textuels. Nous travaillons à deux niveaux de granularité :

• Travail sur corpus spécialisé pour créer les ressources sémantiques nécessaires à la construction d'index de documents et à l'extraction d'information. Ce travail donne lieu à une collaboration interne à l'Université avec le L.L.I. (Laboratoire de Linguistique Informatique) ;

• Étude sémantique « fine » permettant de déterminer, en fonction du contexte, la signification des constituants d'une phrase ou d'un texte. Cette étude porte notamment sur l'interprétation en contexte des éléments lexicaux et des informations temporelles ainsi sur l'explicitation des normes de référence implicites dans les textes.

Cet axe de recherche s'intègre dans un projet de Programmme Pluriformation¹ réunissant 3 laboratoires de l'Université Paris13 (le nouveau Laboratoire d'Informatique Médicale et de Bioinformatique, le LIPN et le Laboratoire de Linguistique Informatique). Ce projet vise à développer des outils d'accès au contenu spécialement adaptés aux documents médicaux.

Ingénierie des connaissances à partir de textes (RCLN)

Notre méthode d'acquisition d'ontologies à partir de textes étant maintenant bien diffusée dans la communauté française et connue au niveau européen, nous nous proposons :

• d'étudier les problèmes inhérents à l'importation et l'exportation d'ontologies en OWL. Ce langage est actuellement le langage de description d'ontologies sur le Web. Il comporte plusieurs niveaux d'expression et de formalisation. Il faut définir un langage compatible avec OWL, et sans doute étendre Terminae à OWL-DL, tout en conservant les aspects linguistiques propres à Terminae. De plus, il serait intéressant, lors de l'importation d'une ontologie, de la relier à des textes du domaine sur lequel elle porte, dans un objectif de fusion, complétion et explicitation.

• d'intégrer l'utilisation des résultats de TreeTagger dans Terminae afin de relier les ontologies importées, qui sont rarement en français, à des textes du domaine sur lequel elles portent.

Analyse sémantique et apprentissage (RCLN + ADAge)

Nous projetons d'étudier, dans des applications concrètes, les complémentarités des méthodes d'apprentissage étudiées dans l'équipe ADAge et des méthodes plus classiques en analyse sémantique étudiées dans l'équipe RCLN. Plus spécifiquement, nous utiliserons des techniques d'apprentissage (symboliques et/ou connexionnistes) pour

• construire automatiquement des règles d'extraction et ainsi faciliter la mise au point de systèmes d'extraction d'information pour de nouveaux domaines et de nouvelles tâches ;

• produire une annotation sémantique de parties de textes techniques qui puisse servir de carte sémantique facilitant la navigation et la consultation des documents.

Apprentissage et exploration de données (ADAge)

La grande quantité de données collectées chaque jour doit être explorée afin d'en comprendre le sens, de déceler des relations entre elles, d'en déduire des modèles de comportement. Les recherches sur les techniques d'apprentissage se poursuivent à la fois selon les approches connexionniste et symbolique.

Pour l’approche connexionniste, les travaux réalisés concernent : la détection, l'extraction et la sélection d'informations pertinentes dans des grandes bases de données ; la fusion de données et de décisions dans les systèmes modulaires et hybrides. D’autres directions de recherche futures concernent l’exploration des données évolutives : classification évolutive, visualisation et analyse de trajectoires, sélection de variables pertinentes pour la classification. Ces travaux seront validés sur des applications concrètes comme la modélisation de comportements des internautes ou le diagnostic autonome et évolutif des systèmes complexes.

Pour l’approche symbolique, les travaux concernent : 1) l‘influence de la représentation et du contenu en information ainsi que de l'incomplétude des données dans les situations inductives (apprentissage de concepts, fouille de données relationnelles, apprentissage multi-agents, structuration de concepts en treillis à partir d’instances et bases de règles associées) 2) des méthodes issues des techniques de recherche de motifs, en particulier de motifs relationnels, inspirées de problèmes liés aux séquences biologiques (ADN, ARN, protéines) et pouvant s'étendre à d'autres domaines (comme l'apprentissage de chroniques temporelles). Le champ d’application privilégié est la bio-informatique (en collaboration avec le LIM&BIO à P13 et l’ABI à P6).

Une partie des acquis en recherche et les contacts industriels liés à ce thème ont été mis à profit pour la création en 2001 d’un DESS Exploration Informatique des Données, dont l’essentiel se retrouve dans le projet de Master professionnel pour la rentrée 2004.

Diagnostic autonome, évolutif et distribué (ADAge)

Les besoins en diagnostic technique et en supervision de systèmes industriels vont en croissant. La recherche menée sur ce thème se fonde principalement sur les techniques de diagnostic logique à base de modèles (explicites) issues de l'Intelligence Artificielle, mais s’enrichit actuellement de la mise en œuvre de techniques d’apprentissage, tant symbolique que numérique.

Nos priorités se concentrent sur les cinq axes complémentaires suivants, qui ont tous commencé à être explorés depuis quatre ans :

- l’aide automatique à l'acquisition de modèles, en particulier l’abstraction de modèles dynamiques.

- l’utilisation de techniques d’apprentissage statistique ou connexionniste (corrélation d’alarmes ou d’indicateurs, analyse de séquences temporelles pour du diagnostic prédictif et évolutif) et symboliques (apprentissage de chroniques).

- 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é), en collaboration avec RCLN.

- la problématique d’autonomie dans le cadre du diagnostic (diagnostic à bord) et de la reconfiguration, centrée sur une extension des travaux de la NASA du cas discret au cas hybride.

- l’étude du diagnostic distribué dans un cadre multi-agents.

Ces recherches continueront à être validées sur des applications dans des domaines variés : supervision de réseaux de télécommunications, diagnostic de systèmes électroniques, automobiles et spatiaux.