Compilation des contraintes booléennes n-aires et application aux CSPS dynamiques
PIECHOWIAK ; RODRIGUEZ
Type de document
ARTICLE DE PERIODIQUE
Langue
francais
Auteur
PIECHOWIAK ; RODRIGUEZ
Résumé / Abstract
Beaucoup de travaux ont été réalisés dans le but d'améliorer les performances des solveurs de CSP. La plupart des résultats ont été obtenus pour les CSP binaires, mais il est également utile de pouvoir manipuler des contraintes n-aires. Dans cet article nous traitons les CSP surcontraints pour lesquels il faut déterminer l'origine de l'absence de solution et l'expliquer. Nous prenons l'exemple du diagnostic à base de modèle abordé comme un CSP dynamique pour illustrer la démarche. Celle-ci se base sur une gestion fine des dépendances entre les valeurs et les contraintes propagées. Cette gestion est obtenue en exploitant les règles de propagation pour lesquelles nous proposons un algorithme de génération. Les traitements se font en deux étapes distinctes. La première consiste à compiler les contraintes du CSP sous forme de règles. La seconde étape est une phase de filtrage du CSP durant laquelle un graphe de dépendances est construit à partir des règles et permet d'expliquer les incohérences.
