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 10 Juin 2008 à 14:00

Conditional Constraints and Composite Variables with Preferences

par Malek Mouhoub (Université de Régina Canada)

We present an extension of the well known Constraint Satisfaction Problem (CSP) framework in order to manage constraint problems in a dynamic environment and when the information corresponding to any possible change is known and available a priori. The new model is called Conditional and Composite CSP (CCCSP) and enables the addition|retraction of problem variables (and their corresponding constraints), during the constraint solving process, via conditional constraints and composite variables. A conditional constraint restricts the participation of a variable in a feasible scenario while a composite variable allows us to express a disjunction of variables where only one will be added to the problem to solve. Using the Allen Interval Algebra and a discrete representation of time, the CCCSP is adapted in order to handle the particular case of numeric and symbolic temporal constraints. Through the C-semiring structure, we show how to integrate preferences into the CCCSP and its temporal variant that we call Temporal CCCSP (or TCCCSP). Finally, we report the results of an extensive experimental study we conducted in order to evaluate the time performance of the complete and incomplete methods, we propose, for solving CCCSPs and TCCCSPs.

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