LIP6 2001/009
- Thèse
Intégration de Mécanismes de Réécriture dans un Système de Satisfaction de Contraintes - A. Liret
- 197 pages - 12/10/2000- document en - http://www.lip6.fr/lip6/reports/2001/lip6.2001.009.pdf - 1,434 Ko
- Contact : Anne.Liret (at) nullbte.bt.com
- Ancien Thème : OASIS
- 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
- Directeur de la publication : Valerie.Mangin (at) nulllip6.fr
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.
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.