Centre de Recherche en Informatique de Lens

Valorisation : le projet Pajero en partenariat avec Horizontal software financé par Oseo

Cédric Piette, Christophe Lecoutre, Daniel Le Berre, Olivier Roussel — 2012-03-27T17:34:13Z

Le projet PAJERO a pour objectif de développer une plateforme logicielle permettant, pour la première fois, la gestion complexe de ressources multiples (ressources humaines, planification, gestion des temps et activités associées).

Il réunit Horizontal Software, en tant que chef de file, deux PME – EquiTime et Caps Entreprise – ainsi que trois partenaires académiques : le CRIL (Université d'Artois), le PRiSM (Équipe Caro, Université de Versailles-Saint-Quentin-en-Yvelines) et l'I3S (Pôle MDSC, Université Nice-Sophia-Antipolis).

Dans ce projet, le CRIL travaille sur deux axes :

Intégration : la définition et l'implantation d'un cadre unificateur permettant une modélisation naturelle de problèmes combinant contraintes (dures), préférences (contraintes souples), incertitudes, fonctions d'objectif multiples et composants conditionnels. Cet axe implique le développement de nouvelles techniques de résolution.

Parallélisation : le développement de nouvelles approches de parallélisation du processus de résolution, exploitant en particulier l'essor des processeurs multi-coeurs.

Pajero dans la presse :
Traces écrites, 12 octobre 2011
Les echos, 18 octobre 2011
Le journal de Saône et Loire, 23 mars 2012

Dynamique des systèmes d'argumentation

Fabien Delorme — 2012-03-14T07:56:47Z

Encadrants : S. Coste-Marquis, S. Konieczny et P. Marquis

(coste, konieczny, marquis)@cril.fr

Ce sujet s'inscrit dans le cadre des systèmes d'argumentation abstraits [4]. La problématique d'un tel système est de trouver, à partir d'un ensemble d'arguments et d'une relation binaire d'attaque entre ces arguments quels sont les arguments qui peuvent être inférés. Considérons l'exemple suivant dans lequel l'ensemble d'arguments est A = {a,b,c,d,e,f} avec la relation d'attaque R = {(a,b),(a,c),(b,d),(c,e),(e,f),(f,e)} représenté par le graphe suivant.

L'argument a n'est pas attaqué donc il peut être accepté. En revanche b et c sont attaqués par a et sont rejetés. d est défendu par a et est également accepté. e est défendu contre c par a mais est attaqué par f contre lequel il se défend lui-même. On peut alors soit accepter e soit accepter f.

De tels systèmes sont utilisés par exemple pour représenter des dialogues dans lesquels plusieurs agents échangent des arguments. Mais on peut également les utiliser pour représenter les connaissances contradictoires d'un seul agent. Dans un tel cadre, les informations que possède l'agent sont amenées à évoluer. Il faut alors que l'agent soit capable de modifier ses croyances, c'est-à-dire son système d'argumentation.

Le but de ce sujet de thèse est d'étudier la dynamique de ces systèmes d'argumentation. Nous souhaitons étudier comment définir des opérateurs de changement de croyances appliqués à ce cadre abstrait. L'idée est de définir des opérateurs concrets de révision , de fusion, etc. opérant sur des systèmes d'argumentation. Mais également de proposer des contreparties des postulats de ces opérateurs de changement usuels [1, 5, 6] dans le cadre des systèmes d'argumentation, et de confronter les opérateurs que nous auront proposé, ou ceux proposés dans la littérature [2, 3], à ces postulats.

Références

[1] C. E. Alchourròn, P. Gärdenfors, and D. Makinson. On the logic of theory change : Partial meet contraction and revision functions. Journal of Symbolic Logic, 50 :510–530, 1985.

[2] C. Cayrol, F. Dupin de Saint Cyr Bannay, and M.-C. Lagasquie-Schiex. Revision of an Argumentation System. In Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning, pages 124–134, 2008.

[3] S. Coste-Marquis, C. Devred, S. Konieczny, M.-C. Lagasquie-Schiex, and P. Marquis. On the merging of Dung's argumentation systems. Artificial Intelligence, 171 :730–753, 2007.

[4] P. M. Dung. On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games. Artificial Intelligence, 77(2) :321–358, 1995.

[5] H. Katsuno and A.O. Mendelzon. On the difference between updating a knowledge base and revising it. In Proceedings of the 2th International Conference on Principles of Knowledge Representation and Reasoning, pages 387–394, 1991.

[6] S. Konieczny and R. Pino Pérez. Merging information under constraints : a logical framework. Journal of Logic and Computation, 12(5) :773–808, 2002.

Olympiades des métiers

Fabien Delorme — 2012-03-12T09:31:23Z

Le CRIL sera présent lors de la sélection régionale des Olympiades des Métiers 2012, organisées à la Faculté Jean Perrin les jeudi 22 et vendredi 23 mars. - Actualités

Compilation : des formules logiques aux réseaux bayésiens

Fabien Delorme — 2012-02-24T11:40:17Z

Description du sujet et travail à réaliser

Compiler de l'information consiste à la pré-traiter de façon à rendre son exploitation plus efficace du point de vue calculatoire. Diverses approches ont été proposées depuis plus de vingt ans pour la compilation de formules logiques mais aussi de réseaux bayésiens, celle-ci pouvant être réalisée à partir de celle-là, en associant à chaque réseau un circuit arithmétique et donc une formule logique correspondante.

Pour permettre un calcul de probabilités conditionnelles efficace, il faut viser comme langage propositionnel cible pour la compilation un fragment permettant de réaliser en temps polynomial le conditionnement (CD) et le comptage de modèles (CT).

Cette dernière requête étant particulièrement difficile (le problème est #P-complet), les langages propositionnels expressifs offrant CD et CT sont peu nombreux. Citons les OBDDs et plus généralement les d-DNNFs.

Le sujet proposé comporte une partie théorique et une partie plus pratique.

La partie théorique a pour but d'étudier de nouvelles méthodes de compilation de formules logiques et de réseaux bayésiens, en particulier pour ces derniers, des méthodes à base de formules logiques, comme le langage des disjonctions déterministes de formules affines que l'on étudiera finement du point de vue de l'efficacité tant temporelle que spatiale.

La partie plus pratique a pour objectif de développer des compilateurs, d'évaluer leurs performances sur des jeux d'essai,

et de les comparer à l'existant.

Pré-requis et mots-clés

Des connaissances élémentaires en logique et en IA. Un goût certain pour la formalisation mais aussi pour l'implantation.

Les principaux mots-clés sont : représentation des connaissances, incertitude, réseaux bayésiens, logique propositionnelle, compilation de connaissances.

Encadrement

Pierre Marquis (directeur de thèse)

CRIL-CNRS/Université d'Artois

marquis@cril.univ-artois.fr

Jean-Marie Lagniez (co-encadrant)

CRIL-CNRS/Université d'Artois

lagniez@cril.univ-artois.fr

Quelques références

Mark Chavira, Adnan Darwiche : On probabilistic inference by weighted model counting. Artif. Intell. 172(6-7) : 772-799 (2008).

Mark Chavira, Adnan Darwiche : Compiling Bayesian Networks Using Variable Elimination. IJCAI 2007 : 2443-2449.

Mark Chavira, Adnan Darwiche, Manfred Jaeger : Compiling relational Bayesian networks for exact inference. Int. J. Approx. Reasoning 42(1-2) : 4-20 (2006).

Mark Chavira, Adnan Darwiche : Compiling Bayesian Networks with Local Structure. IJCAI 2005 : 1306-1312.

Adnan Darwiche, Pierre Marquis : A Knowledge Compilation Map. J. Artif. Intell. Res. (JAIR) 17 : 229-264 (2002).

Hélène Fargier, Pierre Marquis : Extending the Knowledge Compilation Map : Krom, Horn, Affine and Beyond. AAAI 2008 : 442-447.

Hélène Fargier, Pierre Marquis : On Valued Negation Normal Form Formulas. IJCAI 2007 : 360-365.

Jinbo Huang, Mark Chavira, Adnan Darwiche : Solving MAP Exactly by Searching on Compiled Arithmetic Circuits. AAAI 2006.

Mate Soos, Karsten Nohl, Claude Castelluccia : Extending SAT Solvers to Cryptographic Problems. SAT 2009 : 244-257.

Mate Soos : Enhanced Gaussian Elimination in DPLL-based SAT Solvers. Workshop paper "Pragmatics of SAT", 2010.

Opérateurs de changements en logique propositionnelle

Fabien Delorme — 2012-02-24T11:39:03Z

Description du sujet et travail à réaliser

Ce sujet concerne l'étude des opérateurs de changements de croyances en logique propositionnelle. Le domaine de la théorie du changement de croyances a défini et étudié beaucoup d'opérateurs différents, comme les opérateurs de révision, de contraction, de mise à jour, de fusion, etc...

Le but de cette thèse est l'étude des liens existants entre ces différents opérateurs et la définition de nouveaux opérateurs manquant dans la littérature.L'idée est de catégoriser les différents opérateurs suivant un certain nombre de critères, comme le fait de ne concerner qu'un seul agent ou un ensemble d'agents, le fait de considérer un monde statique ou dynamique, le fait de vouloir ajouter ou supprimer une information, etc... Cette catégorisation permettra de classer les opérateurs existants, mais aussi de trouver des "cases vides", c'est-à-dire des choix de critères qui ne correspondent à aucun opérateur existant. Le but sera alors de "remplir ces cases" en trouvant les propriétés logiques et les théorèmes de représentations correspondants.

Une première étape sera d'étudier les opérateurs de contraction en logique propositionnelle. En effet, Katsuno et Mendelzon ont proposé un ensemble de postulats pour les opérateurs de révision dans le cadre de la logique propositionnelle et un théorème de représentation en termes d'assignements fidèles (que l'on peut considérer comme un cas particulier des systèmes de sphères de Grove). Cette représentation est à l'origine des approches proposées pour modéliser la révision itérée, sur les traces de Darwiche et Pearl. Or, bien qu'il soit connu qu'opérateurs de révision et de contraction sont très étroitement liés, il n'existe pas, à notre connaissance, de contrepartie au théorème de représentation de Katsuno et Mendelzon pour la contraction. Nous chercherons donc d'abord à définir les postulats correspondants aux opérateurs de contraction en logique propositionnelle et à établir un théorème de représentation correspondant.Cela nous permettra ensuite d'étudier comment définir des opérateurs de contraction itérée, contrepartie des opérateurs de révision itérée. Cette problématique de la contraction itérée n'a été abordé jusqu'ici, à notre connaissance, que dans un seul article, alors qu'elle a engendrée une large littérature dans le cas de la révision itérée.

Pré-requis et mots-clés

Les pré-requis pour ce sujet sont des notions de bases en logique et en révision de croyances. Les domaines touchant à ce sujet peuvent se résumer dans les mots-clés suivants : modélisation du raisonnement, changement de croyances, révision de croyances, révision AGM, contraction, fusion.

Encadrement

Les deux co-directeurs de thèse seront Sébastien Konieczny et Pierre Marquis. Pour toute question supplémentaire sur ce sujet, s'adresser à :

Sébastien Konieczny. konieczny@cril.fr
Pierre Marquis. marquis@cril.fr

Quelques références

[1] C. E. Alchourrón, P. Gärdenfors et D. Makinson. On the logic of theory change : Partial meet contraction and revision functions. Journal of Symbolic Logic, 50 :510-530, 1985.

[2] P. Gärdenfors. Knowledge in flux. MIT Press, 1988.

[3] H. Katsuno et A. O. Mendelzon. Propositional knowledge base revision and minimal change. Artificial Intelligence, 52 :263-294, 1991.

[4] H. Katsuno, A. O. Mendelzon. On the Difference between Updating a Knowledge Base and Revising It. KR 1991:387-394.

[5] S. Konieczny, R. Pino Pérez. Logic Based Merging. Journal of Philosophical Logic. 40(2) .pages 239-270.2011.

[6] S. Konieczny, R. Pino Pérez. Confluence Operators. JELIA 2008 : 272-284.

[7] A. Darwiche, J. Pearl. On the Logic of Iterated Belief Revision. Artificial Intelligence 89(1-2) : 1-29 (1997).

[8] M. Hild, W. Spohn. The measurement of ranks and the laws of iterated contraction. Artificial Intelligence 172(10) : 1195-1218 (2008).

Fusion permissive de contraintes dans les CSPs

Fabien Delorme — 2012-02-23T08:03:52Z

Encadrement : Bertrand Mazure & Eric Grégoire mazure,gregoire @ cril.fr

L'une des méthodes principales de résolution de problèmes en Intelligence Artificielle est fondée sur le concept de CSPs (Constraint Satisfaction Problems). Le principe est de représenter le problème à résoudre par un ensemble de contraintes portant sur différentes variables, chacune ayant son propre domaine d'instanciations possibles. Résoudre un CSP revient à trouver des valeurs pour l'ensemble des variables de manière telle que l'ensemble des contraintes soient satisfaites. Un exemple traditionnel de CSPs est le problème des n-reines, consistant à trouver des coordonnées pour chacune des n reines sur l'échiquier de telle manière à ce qu'aucune ne soit en situation de prise.

Dans cette thèse, le problème générique qui est posé est le suivant. Supposons que nous devions fusionner plusieurs CSPs portant sur des ensembles partagés de variables. Si cette fusion consiste en la simple union ensembliste de toutes les contraintes, les plus restrictives vont occulter celles qui le sont moins. Par exemple, la juxtaposition d'une contrainte dans un premier CSP qui exige que X > 10 avec une contrainte d'un second CSP qui exige que X > 7 reviendra à exiger que X > 10 : la contrainte la plus forte, c.-à-d. celle qui autorise le moins de valeurs pour X, l'emporte sur la contrainte plus faible.

Pareil schéma ne convient pas à toutes les applications possibles. Dans certains cas, on peut souhaiter le contraire, à savoir la prééminence de la contrainte la plus faible. Ainsi, dans l'exemple, on veut vouloir privilégier la contrainte plus permissive X > 7 d'un premier CSP même en présence d'une seconde contrainte X > 10 provenant d'un second CSP , et donc autoriser les valeurs 8, 9 et 10 dans des solution du CSP fusionné. Par exemple, lors de la fusion de deux CSPs représentant des systèmes d'évaluation et d'alertes, lorsque ces deux contraintes représentent deux niveaux possibles de déclenchement d'alerte par le nombre minimal de facteurs inquiétants nécessaires, on peut vouloir décider l'alerte lorsque X dépasse 7 et non 10 dans le système globalisé. Un autre exemple pourrait concerner une notation financière globale qui résulterait de la fusion de différents CSPs traduisant des visions d'évaluateurs différents. Entre des seuils d'endettement différents dans chacun des CSPs, la fusion des deux CSPs pourrait ne retenir que le seuil le plus bas.

Bien évidemment ces contraintes n'apparaissent pas nécessairement explicitement dans les CSPs, mais peuvent résulter de l'interaction de l'ensemble des contraintes dans ceux-ci. Ce problème rejoint dans une certaine mesure la notion bien connue de relaxation de contraintes.

Le travail dans cette thèse présente deux facettes. Sur le plan théorique, il faudra poser le problème formellement. Il faudra ensuite proposer des stratégies et des algorithmes permettant de résoudre ainsi les CSPs ainsi fusionnés. L'approche qui est proposée reposera sur un concept de réfutation et de noyaux minimalement inconsistants de CSPs. L'idée à la base de l'approche est de fusionner d'abord les CSPs par simple union ensembliste des contraintes. Pour faire prédominer les contraintes les plus permissives sur les variables choisies, on procédera par réfutation. Dans l'exemple plus haut, X = 8 est incohérent avec l'ensemble simplement fusionné de contraintes. Si l'on trouve les plus petits ensembles de contraintes (noyaux) qui expliquent cette incohérence et si l'on « relâche » certaines de celles-ci de manière à ce que l'incohérence soit levée, X = 8 devient une solution. Dans un second temps, une implantation et une validation expérimentale de l'approche proposée pourront être effectuées.

Résolution du problème de Satisfiabilité propositionnelle (SAT) et ses applications

Fabien Delorme, Lakhdar Saïs — 2012-02-13T11:52:07Z

Titre : Résolution du problème de Satisfiabilité propositionnelle (SAT) et ses applications.

Doctorant : Jerry Lonlac.

Directeur : Lakhdar Saïs.

Thèse en co-tutelle.

Logiques qualitatives pour la gestion des préférences

Fabien Delorme, Salem Benferhat — 2012-02-13T11:50:58Z

Titre : Logiques qualitatives pour la gestion des préférences.

Doctorante : Lydia Bouzar.

Directeur : Salem Benferhat.

Analyse et regroupement automatique de textes courts à des fins statistiques

Fabien Delorme, Pierre Marquis — 2012-02-13T11:49:54Z

Titre : Analyse et regroupement automatique de textes courts à des fins statistiques.

Doctorant : Benoît Trouvilliez.

Directeur : Pierre Marquis.

Co-encadrant : Vincent Dubois.

Compilation de préférences - application à la configuration de produits

Fabien Delorme, Pierre Marquis — 2012-02-13T11:48:55Z

Titre : Compilation de préférences - application à la configuration de produits.

Doctorant : Nicolas Schmidt.

Directeurs : Hélène Fargier et Pierre Marquis.