Compiling CSPs into Tree-Driven Automata for Interactive Solving

Abstract : Constraint programming techniques are widely used to model and solve decision problems and many algorithms have been developed to solve automatically and efficiently families of CSPs; nevertheless, they do not help solve interactive decision support problems, like product configuration. In such problems, the user chooses the values of the variables, and the role of the system is not to solve the CSP, but to help the user in this task. Dynamic global consistency maintaining is one of the most useful functionalities that should be offered by such a CSP platform. Unfortunately, this task is intractable in the worst case. Since interactivity requires short response times, intractability must be circumvented some way. To this end, compilation methods have been proposed that transform the original problem into a data structure allowing a short response time. In this paper, we extend the work of Amilhastre et al. [1] and Vempaty [15] by the use of a new structure, tree-driven automata, that takes advantage of the structural characteristics of configuration problems (decomposition of the components into independent subcomponents). Tree-driven automata can be far more compact than classical automata while keeping their good properties, especially a tractable complexity for the maintenance of global consistency.
Type de document :
Article dans une revue
Constraints, Springer Verlag, 2004, 9 (4), pp.263-287. 〈10.1023/B:CONS.0000049204.75635.7e〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00108574
Contributeur : Christine Carvalho de Matos <>
Soumis le : lundi 23 octobre 2006 - 07:43:14
Dernière modification le : jeudi 11 janvier 2018 - 06:26:54

Identifiants

Citation

Hélène Fargier, Marie-Catherine Vilarem. Compiling CSPs into Tree-Driven Automata for Interactive Solving. Constraints, Springer Verlag, 2004, 9 (4), pp.263-287. 〈10.1023/B:CONS.0000049204.75635.7e〉. 〈lirmm-00108574〉

Partager

Métriques

Consultations de la notice

38