ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique

APPEL À
CONTRIBUTION
Masses de données hétérogènes
En savoir plus >>
Autres revues >>

Revue d'Intelligence Artificielle

0992-499X
Revue des Sciences et Technologies de l'Information
 

 ARTICLE VOL 15/2 - 2001  - pp.219-245  - doi:10.3166/ria.15.219-245
TITRE
Compilation des contraintes booléennes n-aires pour le traitement des CSP dynamiques

RÉSUMÉ

. 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.

ABSTRACT

A lot of work has been made to improve CSP solvers capabilities. Most of the results concern binary CSP. But, it is useful to manipulate n-ary constraints. In this paper, CSP are over constrained and the goal consists in finding origin of this lack of solution or in explaining them. We take the model-based diagnosis as a dynamic CSP to illustrate our approach. The method is based on a precise management of dependencies between values and constraint propagation. This management explore a propagation rules representation of the constraints. These rules are calculated with the algorithm we propose in this paper. The processing of a CSP is made in two steps. In the first step, the constraints are compiled into a set of rules. In the second step, variables domains are filtered. A dependency graph based on the rules allows explaining inconsistencies.

AUTEUR(S)
Sylvain PIECHOWIAK, Joaquín RODRIGUEZ

MOTS-CLÉS
raisonnement par contraintes, CSP, diagnostic par contraintes.

KEYWORDS
constraint reasoning, dynamic CSP, constraint based diagnosis.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 7.5 €
• Non abonné : 15.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (353 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier