narendra jussien | professeur, équipe contraintesécole des mines de nantes - lina |
» accueil » recherche » domaines couverts
premiers pas : systèmes à base de connaissances
Mes activités de recherche ont débuté dès 1992 pendant mon année de Licence à l'occasion d'un projet en binôme sur la réalisation d'un système à base de connaissances pour la reconnaissance d'annélides polychètes (vers marins). Les résultats obtenus ont fait l'objet d'une communication lors d'un congrès international [Jussien et al., 1992] et ont fait l'objet d'une publication dans une revue internationale [Jussien et al., 1994]. Le système obtenu est référencé parmi l'Annelid Worm Bio-diversity resources et continue d'évoluer.
La programmation par contraintes est un sujet de recherche qui
intègre les travaux de divers domaines comme les mathématiques
discrètes, l'analyse numérique, l'intelligence artificielle, la
programmation mathématique (ou plus généralement la recherche
opérationnelle) ou le calcul formel. La communauté
contraintes peut s'enorgueillir de réussites marquantes
dans des domaines d'applications réellement diversifiés : les
problèmes combinatoires, l'ordonnancement, l'analyse financière,
la simulation et la synthèse de circuits intégrés, le diagnostic
de pannes, l'aide à la décision, la biologie moléculaire, la
résolution de problèmes géométriques, ...
L'efficacité de la programmation par contraintes tient au fait
qu'elle est d'application très générale et qu'elle permet de
dissocier la représentation du problème (le réseau de
contraintes) de sa résolution (le solveur). Il reste, bien sûr,
encore de nombreuses limitations à la programmation par
contraintes. Parmi les verrous existants, on peut identifier les
difficultés suivantes :
Mes travaux dans ce domaine portent globalement sur les extensions
des systèmes actuels de résolution de contraintes, afin de proposer un système complet de résolution de problèmes dynamiques. Cet objectif m'a permis d'aborder différentes problématiques : amélioration des techniques de résolution, fourniture d'outils d'étude et de mise au point, ... Le thème fédérateur de mes activités dans ce contexte est la notion d'explication [Jussien, 2003] (voir aussi e-constraints.net).
En quelques mots, une explication est une forme interne
d'une trace limitée et relativement lisible de l'activité passée
du solveur de contraintes. Ce concept nouveau est apparu suite à mes
travaux de recherche lors de mon stage de DESS [Jussien, {1994}]et au cours de ma thèse [Jussien, 1997]. J'ai ainsi proposé
un cadre formel pour les explications (et leurs extensions
[Ouis et al., 2003]) dans le paradigme de la programmation par
contraintes [Jussien and Boizumault, 1997][Boizumault et al., 1994][Jussien, 2001][Jussien, 2003].
Programmation par contraintes et explications
Grâce à ce travail poussé, nous avons pu proposer, en collaboration avec Olivier Lhomme, un cadre théorique pour les algorithmes de recherche pour les problèmes de satisfaction de contraintes basé sur trois composantes essentielles : propagation, apprentissage et déplacement. Le lien entre ces trois composantes étant justement constitué par l'utilisation d'un système d'explications devenant ainsi crucial pour la programmation par contraintes [Jussien and Lhomme, 2003][Jussien and Lhomme, 2002].
Implémentations
Il est clair que ce travail n'est pas resté au niveau purement théorique. Une implémentation existe : c'est le système PaLM [Jussien and Boizumault, 1996][Jussien and Barichard, 2000][Jussien and Boizumault, 1995]. De plus, les aspects génie logiciel liés à l'implémentation de tels concepts dans les solveurs de contraintes continuent à faire l'objet de travaux [Douence and Jussien, 2002][Douence and Jussien, 2002].
Applications des explications
La notion d'explication a montré son utilité dans de nombreux domaines et en particulier pour s'attaquer efficacement aux trois verrous pré-cités.
La notion d'explication permet de rendre compte à l'utilisateur de
l'activité d'un solveur de contraintes. En effet, comme chaque
action du solveur est justifiée, il est assez aisé de fournir ces
justifications comme information sur le fonctionnement interne
d'un solveur de contrainte.
Bien sûr, il n'est pas raisonnable de fournir tout simplement
l'explication sous la forme d'un ensemble de contraintes. Il est
indispensable de passer par une phase de traduction de
cette explication en des termes compréhensibles par un utilisateur
néophyte : c'est ce qui a été proposé dans nos travaux sur les
explications user-friendly [Jussien and Ouis, 2001].
Il est possible aussi d'utiliser les explications pour développer
des outils de débogage et d'analyse de programmes avec
contraintes. Il s'agit d'une des idées ayant conduit au lancement
du projet RNTL OADymPPaC.
Parmi les résultats de ce projet, on peut citer le développement d'un outil de visualisation du réseau d'explications [Ghoniem et al., 2003] permettant de fournir des outils d'analyse puissants de la résolution d'un problème avec contraintes et le système COINS
[Ouis et al., 2003][Ouis et al., 2002] qui est basé
sur l'utilisation d'une version augmentée de la notion
d'explication.
D'une utilisation facilitée avec un utilisateur à une utilisation
automatique des explications, il n'y a qu'un pas [Verfaillie and Jussien, 2003] (voir aussi les notes en ligne de ce tutorial). Les explications
peuvent ainsi être utilisées pour réaliser des systèmes de
contraintes réellement incrémentaux (pour l'ajout et le
retrait de contraintes) [Jussien and Boizumault, 1996][Jussien and Boizumault, 1997] car les
explications permettent de déterminer aisément les effets passés
d'une contrainte [Debruyne et al., 2003]. L'étape suivante est naturellement de résoudre
automatiquement des problèmes sur-contraints : identification du
conflit puis retrait de la/les contrainte(s) responsable(s) de
l'échec [Jussien and Boizumault, 1997].
Ce type de travaux trouve son application dans différents
domaines : on peut citer le génie logiciel
[Albin-Amiot et al., 2001] [Gu{\'e}h{\'e}neuc and Jussien, 2001], la planification [Cambazard et al., 2004] ou l'ordonnancement
[Elkhyari et al., 2003].
La notion d'explication permet de donner une nouvelle dimension à
la programmation par contraintes, ce que j'appelle
e-constraints : la programmation par contraintes avec
explications [Jussien, 2001]. En effet, l'utilisation
d'une telle technique permet de développer de nouvelles techniques
d'exploration de l'espace de recherche : les méthodes
rétro-prospectives qui combinent approches prospectives (filtrage,
propagation, coupes) et les approches rétrospectives (analyse des
échecs, ...). J'ai ainsi proposé, en collaboration avec Olivier
Lhomme un cadre complet de description et de définition
d'algorithmes de recherche de solution dans les CSP
utilisant cette notion d'explication : le modèle PLM
[Jussien and Lhomme, 2003][Jussien and Lhomme, 2002].
Dans ce cadre, nous avons défini différents nouveaux algorithmes :
aussi bien des méthodes exactes (MAC-DBT
[Jussien et al., 2000], DynDS [Jussien and Lhomme, 1998], application aux problèmes d'open-shop
[Gu{\'e}ret et al., 2000]) que des méthodes approchées
(DECISION-REPAIR [Jussien and Lhomme, 2002][Jussien and Lhomme, 2003]).
Narendra Jussien
"The versatility of using explanations within constraint programming" , École des Mines de Nantes, technical report, no. 03-04-INFO, 2003
référence, résumé, article [pdf, 18 KB]
Ce rapport de recherche est la publication de mon mémoire d'habilitation à diriger des recherches. Il fait une synthèse complète de mes travaux de recherche dans le domaine des explications et permet d'articuler les différentes contributions sur ce sujet
Articles publiés dans des revues internationales
Narendra Jussien, Olivier Lhomme
"Local search with constraint propagation and conflict-based heuristics" , in: "Artificial Intelligence", vol. 139, no. 1, pp. 21-45, 2002
référence, résumé, article [pdf, 170 KB]
Cet article est une version étendue d'un article primé à AAAI'00 [Jussien and Lhomme, 2000]. Il montre bien l'intérêt d'une approche à base d'explications pour la programmation par contraintes
Christelle Guéret, Narendra Jussien, Christian Prins
"Using intelligent backtracking to improve branch and bound methods: an application to Open-Shop problems" , in: "European Journal of Operational Research", vol. 127, no. 2, pp. 344-354, 2000
référence, résumé, article [pdf, 146 KB]
Il s'agit, dans cet article, des premières utilisations des explications pour résoudre un problème dur d'ordonnancement
Christelle Guéret, Narendra Jussien, Olivier Lhomme, Claire Pavageau, Christian Prins
"Loading aircraft for military operations" , in: "Journal of the Operational Resarch Society", vol. 54, no. 5, pp. 458-465, 2003
référence, résumé, article [pdf, 149 KB]
Cet article fait suite à une collaboration avec l'équipe SLP (Systèmes Logistiques et de Production) de l'EMN. Il s'agit d'un exemple de valorisation en terme de recherche d'un contrat industriel.
Sélections d'articles présentés dans des conférences internationales
Abdallah Elkhyari, Christelle Guéret, Narendra Jussien
"Solving dynamic timetabling problems as dynamic resource constrained project scheduling problems using new constraint programming tools" , The Practice and Theory of Automated Timetabling, Lecture Notes in Computer Science, Springer-Verlag, to appear, 2003
référence, résumé, article [pdf, 286 KB]
Cet article est à paraître dans les LNCS. Il s'agit d'un article sélectionné suite à la conférence PATAT'02 (Practice and Theory of Automated Timetabling) [Elkhyari et al., 2002]. Il s'agit de l'utilisation des résultats obtenus pour la résolution de problèmes d'ordonnancement dynamique pour s'attaquer à des problèmes d'emploi du temps
Articles présentés dans des conférences internationales
Romuald Debruyne, Gérard Ferrand, Narendra Jussien, Willy Lesaint, Samir Ouis, Alexandre Tessier
"Correctness of Constraint Retraction Algorithms" , FLAIRS'03: Sixteenth international Florida Artificial Intelligence Research Society conference, pp. 172-176, AAAI press, 2003
référence, résumé, article [pdf, 134 KB]
Il s'agit du résultat d'une collaboration entre l'EMN et le LIFO (Laboratoire d'Informatique Fondamentale d'Orléans) en marge du projet OADYMPPAC. Il présente des développements théoriques formels autour des explications
Narendra Jussien, Romuald Debruyne, Patrice Boizumault
"Maintaining Arc-Consistency within Dynamic Backtracking" , Principles and Practice of Constraint Programming (CP 2000), Lecture Notes in Computer Science, no. 1894, pp. 249-261, Springer-Verlag, 2000
référence, résumé, article [pdf, 221 KB]
Cet article présente une extension de l'algorithme dynamic backtracking à la propagation de contraintes et représente une preuve de l'intérêt d'une approche à base d'explications pour résoudre des CSP, et plus particulièrement, des CSP structurés
Narendra Jussien, Olivier Lhomme
"Dynamic domain splitting for numeric CSP" , European Conference on Artificial Intelligence, pp. 224-228, 1998
référence, résumé, article [pdf, 165 KB]
Il s'agit d'un algorithme de type dynamic backtracking couplé à la propagation de contraintes pour les contraintes numériques (c'est le premier algorithme existant pour ce type de problèmes dans le cas dynamique)
Narendra Jussien, Patrice Boizumault
"Best-first search for property Maintenance in reactive constraints systems" , International Logic Programming Symposium, pp. 339-353, MIT Press, 1997
référence, résumé, article [pdf, 320 KB]
Il s'agit de la première publication internationale sur les explications et leur application à la résolution de problèmes dynamiques et sur-contraints
L'article intitulé Local search with constraint propagation and conflict-directed heuristics et écrit en collaboration avec Olivier Lhomme a été sélectionné comme Award winning paper lors de la conférence AAAI'00 [Jussien and Lhomme, 2000]. Cette récompense nous a valu une procédure accélérée de publication dans la revue AI Journal d'une version longue en 2002 [Jussien and Lhomme, 2002].
copyright © 2003-2008 narendra jussien
