Arc-Consistency in Dynamic Constraint Satisfaction Problems - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 1991

Arc-Consistency in Dynamic Constraint Satisfaction Problems

Résumé

Constraint satisfaction problems (CSPs) provide a model often used in Artificial Intelligence. Since the problem of the existence of a solution in a CSP is an NP-complete task, many filtering techniques have been developed for CSPs. The most used filtering techniques are those achieving arc-consistency. Nevertheless, many reasoning problems in AI need to be expressed in a dynamic environment and almost all the techniques already developed to solve CSPs deal only with static CSPs. So, in this paper, we first define what we call a dynamic CSP, and then, give an algorithm achieving arc-consistency in a dynamic CSP. The performances of the algorithm proposed here and of the best algorithm achieving arc-consistency in static CSPs are compared on randomly generated dynamic CSPs. The results show there is an advantage to use our specific algorithm for dynamic CSPs in almost all the cases tested.
Fichier principal
Vignette du fichier
aaai91.pdf (216.48 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-02310575 , version 1 (10-10-2019)

Identifiants

  • HAL Id : lirmm-02310575 , version 1

Citer

Christian Bessiere. Arc-Consistency in Dynamic Constraint Satisfaction Problems. AAAI Conference on Artificial Intelligence, Jul 1991, Anaheim, CA, United States. pp.221-226. ⟨lirmm-02310575⟩
154 Consultations
124 Téléchargements

Partager

Gmail Facebook X LinkedIn More