Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 30 Janvier 2001

Restauration de la cohérence et explications dans les CSP dynamiques : application à la configuration de produit

par Hélène Fargier (IRIT Toulouse)

L'approche CSP (Constraint Satisfaction Problem) offre un cadre de représentation général pour de nombreux problèmes d'aide à la décision. La majorité des travaux dans ce domaine sont consacrés à la résolution automatique de CSP. Néanmoins, le traitement pratique de nombreux problèmes d'aide à la décision présente un caractère fortement interactif auquel la résolution automatique convient mal. Pour ces problèmes, c'est typiquement l'utilisateur qui fixe lui-même les valeurs des variables, au terme d'une séquence d'ajouts et de retraits de contraintes unaires. Dans un contexte interactif, le rôle d'un système d'aide à la décision est donc d'assurer que les choix de l'utilisateur sont cohérents avec la base de contraintes et si possible d'ôter des domaines les valeurs qui deviennent incompatibles. Si une incohérence apparaît, le système doit pourvoir l'expliquer aider l'utilisateur à trouver une relaxation cohérente de ses choix.

Apres une introduction générale sur les CSP, cet expose presentera une extension de ce modèle inspiree de l'utilisation d'hypotheses en logique propositionnelle, extension qui étend aux systemes à base de contraintes les notions d'explication, de nogood et d'interpretation. D'un point de vue théorique, les problèmes de complexité attachés à cette extension des CSP seront étudiés. D'un point de vue pratique, nous proposons de compiler le CSP initial sous la forme d'un automate, cette structure de données étant exploitée en ligne pour assurer le maintien de la cohérence globale et le calcul de restaurations. La derniere partie de l'exposé sera dediée à la validation experimentale de l'approche proposée sur notre domaine d'application, à savoir la configuration interactive de produit.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr