Intégration de Mécanismes de Réécriture dans un Système de
Satisfaction de Contraintes

A. Liret

LIP6 2001/009: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 LIP6 / LIP6 research reports
197 pages - Octobre/October 2000 - French document.

Get it : 1401 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Objets et Agents pour Systèmes d'Information et de Simulation

Titre français : Intégration de Mécanismes de Réécriture dans un Système de
Satisfaction de Contraintes
Titre anglais : Integrating Rewriting into a Constraint Satisfaction System

Résumé : Les techniques de satisfaction de contraintes (CSP pour Constraint Satisfaction Problems) permettent de traiter les situations où l'on souhaite résoudre un problème en décrivant les caractéristiques des solutions, plutôt qu'en décrivant une procédure de résolution. Ces techniques, apparues dans les années 70, connaissent depuis quelques années un succès considérable et permettent aujourd'hui de spécifier et de résoudre de nombreux problèmes combinatoires difficiles, dans les domaines tels que l'ordonnancement, la planification ou la configuration de systèmes complexes. Néanmoins, de nombreux problèmes combinatoires qui relèvent en principe de ces techniques restent difficiles, voire hors d'atteinte. Une des causes de ces échecs est la trop grande généralité des techniques de CSP, qui sont conçues pour être indépendantes des problèmes particuliers à résoudre. Cependant, il existe de nombreux contextes dans lesquels il est possible d'améliorer les performances d'un système général de contraintes, à l'aide de connaissances spécialisées, sans pour autant nuire à la généralité des techniques employées. Cette ambivalence de comportement des problèmes de CSP rend essentiel le choix du langage dans lequel exprimer les contraintes et des connaissances qu'il peut véhiculer. Plus précisément, nous nous intéressons dans cette thèse à une manière particulière d'adapter dynamiquement des techniques générales (CSP) à des problèmes spécifiques, en utilisant le paradigme de la réécriture et celui de la programmation par objets.
Nous identifions d'abord des situations concrètes dans lesquelles apparaissent clairement les faiblesses d'un système de CSP. Nous proposons un moteur de Réécriture de Contraintes Symboliques appelé RCS. RCS produit des contraintes redondantes, intégrées à l'ensemble de contraintes en cours de résolution. La mise en oeuvre de notre système complet (BackTalk + RCS) ainsi que nos expérimentations sur des problèmes combinatoires à domaines finis conduisent à proposer des critères spécifiques d'une catégorie de problèmes, et un langage de définition de stratégies déclaratives pour contrôler précisément l'application de RCS. Nous utilisons ce langage pour observer le comportement de RCS et mesurer dynamiquement son utilité. Nous identifions enfin des domaines d'application propices à une telle intégration.

Abstract : In the range of Constraint Satisfaction Problems (CSP), a great deal of techniques has been developed to deal with situations where problem solving is described by solution's characteristics, rather than a solving procedure. For several years, these techniques have been successfully applied to specify and solve a lot of difficult combinatorial problems, in numerous domains like planning, scheduling, time-tabling, dynamic network design. However, some combinatorial problems remain inappropriate or out of reach, essentially because of the general scope of the CSP formalism. This dilemma is not new: it's a classic effect of the NP-complete nature of CSP. However, there exist a lot of contexts where we can expect increasing the performances of a general constraint system, with the help of specialised knowledge, without decreasing the generality of applied techniques. Due to this duality of Constraint Satisfaction Problems' behaviour, on need to carefully choose a language which constraints are expressed in and also knowledge that we want this language to manipulate. In this thesis we study a particular manner of dynamically adding local knowledge with the aim to adapt CSP techniques to specific problem properties, using the Rewrite paradigm.
First, we identify concrete situations that clearly put in evidence the drawbacks of a CSP solver. We propose a solver dedicated to Rewriting Symbolic Constraints, called RCS. RCS produces redundant constraints, integrated to the constraint store, while solving the problem. Our implementation of our complete system (BackTalk+RCS) as well as our experiments upon finite-domain CSP problems lead us to propose on one hand, global criteria, which are particularly adapted to the category of cryptogram problems, and on the other hand, a language for defining declarative strategies to precisely control the execution of RCS. We use this language to observe the behaviour of RCS and dynamically measure the utility of RCS, regarding to the solution improvement. Finally we identify application domains which seem to be custom-built to such combination between constraints rewriting and constraint satisfaction-based solving.

Mots-clés : problèmes combinatoires, résolution, satisfaction de contrainte, réécriture de contraintes symboliques stratégie dynamique, contrôle déclaratif, langage à objets, réification

Key-words : constraint satisfaction problem, hybrid solving, symbolic constraint rewriting, dynamic control object-oriented language, declarative language

Publications internes LIP6 2001 / LIP6 research reports 2001

Responsable Éditorial / Editor :Valerie.Mangin@lip6.fr