l’utilisation de Houria dans la programmation logique par hiérarchie de contraintes

Les contraintes fonctionnelles sont utilisées dans plusieurs applications gérées par des langages de programmation logique par contraintes comme par exemple dans les interfaces graphiques, pour des simulations physiques ou encore des contraintes géométriques. Dans plusieurs situations, il est nécessaire de pouvoir exprimer dans ces langages des contraintes dures qui doivent être satisfaites et les contraintes de préférences à satisfaire au mieux selon le comparateur utilisé. La Programmation Logique par Hiérarchie de Contraintes (PLHC) étend la Programmation Logique par Contraintes (PLC) en incluant les hiérarchies de contraintes. La PLC comme la PLHC sont para­ métrées par D qui est le domaine des contraintes. De plus, la PLHC est paramétrée par le compara­ teur C utilisé. Des prototypes de la PLHC(D.LPM) sont décrit dans [WÍ192, WB89, BMM+89, BDF+87] où D est l’ensemble des réels et LPM est le comparateur Localement-Prédicaî-Meilleur. Comme il est mentionné par les auteurs de ces prototypes, l’expérience d’écrire des programmes en PLHC(R,LPM) montre que le comparateur Localement-Prédicat-Meilleurproduit des solutions non intuitives. Ceci résulte du fait que le comparateur Localement-Prédicat-Meilleur ne peut comparer que des solutions résultant d’une seule hiérarchie (ceci est appelé comparaison intra-hiérarchie). Cependant, plusieurs applications pratiques en PLHC suggèrent le besoin d’une comparaison entre les solutions résultant des différents choix de règles du programme afin d’éliminer celles qui sont non intuitives (c.à.d. jugées moins bonnes) (ceci est appelé comparaison inter-hiérarchies).

Ce chapitre décrit un algorithme basé sur notre résolveur présenté dans les chapitres 5 et 6 et sur le fondement théorique de comparaison inter-hiérarchies que nous rappellerons dans ce chapitre. Ce fondement est décrit en détail dans [Wil92. WB89], il étend la définition de l’ensemble de solutions afin de donner la possibilité de pouvoir comparer deux solutions résultant de différentes hiérarchies. Ce chapitre est composé de quatre parties. La première partie est un état de l’art ou nous présente­ rons l’intégration des hiérarchies de contraintes dans les langages de programmation logique. Il s’agira tout d’abord de décrire globalement la programmation logique par contraintes, ensuite la programmation logique par hiérarchie de contraintes ainsi que le schéma général étendu du compa­ rateur Globalement-Meilleur utilisé pour la comparaison inter-hiérarchies. On montre via deux exemples le besoin de comparaison inter-hiérarchies. On discutera sur l’aspect des comparateurs, sur les contraintes non primitives et enfin sur les travaux existants dans ce domaine. Ces travaux avaient pour objectif d’obtenir les mêmes résultats que la comparaison inter-hiérarchies. L’exposé de cette partie ne se veut pas exhaustif mais ciblé sur la description des points théoriques auxquels nous ferons référence ultérieurement dans ce chapitre. Dans la deuxième partie, on présente les idées sur lesquelles est basé un nouvel algorithme pour la réalisation de cette comparaison inter-hié­ rarchies. La troisième partie décrit cet algorithme. Enfin, la quatrième partie décrit un exemple pour bien illustrer cet algorithme.

Hiérarchie de contraintes et programmation logique

Initialement, les hiérarchies de contraintes ont été une extension du système Thinglab [BDF+87]. Par rapport aux hiérarchies de contraintes et à la programmation logique, nous avons vu que la théo­ rie des hiérarchies de contraintes permet à l’utilisateur de spécifier non seulement les contraintes dures mais aussi les contraintes de préférences réparties en un ou plusieurs niveaux. Ce schéma de hiérarchie de contraintes est paramétré par un comparateur C qui permet la comparaison des diffé­ rentes solutions possibles d’une seule hiérarchie et le choix de la meilleure solution. Récemment, le paradigme des hiérarchies de contraintes a été intégré avec le schéma de programmation logique par contraintes (PLC) afin de produire la programmation logique par hiérarchie de contraintes (PLHC). PLC et PLHC sont paramétrées par D qui est le domaine des contraintes. De plus la PLHC est para­ métrée par le comparateur C. Cette intégration de hiérarchies de contraintes dans la PLC permet à la théorie de la programmation logique d’être complétée par l’expressivité des contraintes de préfé­ rence. Les travaux précédents concernant ce domaine sont scindés essentiellement en deux : la Program­ mation Logique par Contraintes {PLC) et l’utilisation des contraintes dans les applications. Le schéma de la PLC est décrit dans [JL87]. Un certain nombre d’interprètes PLC ont été implémentés Nons pouvons citer Prolog III [Col871, CLP(R) [HJM+87, JM87] et CHIP [DVS+88]. Il existe aussi des travaux considérables sur l’utilisation des contraintes dans les applications comme par exemple les contraintes géométriques, les simulations physiques, les interfaces utilisateurs, le dessin et le for­ matage de document, les algorithmes d’animations ou encore le dessin et l’analyse d’instruments mécaniques et de circuits électriques. Dans cette section, nous illustrons l’extension de la notion de comparateur appliquée à la comparai­ son inter-hiérarchies. Les définitions précédentes des comparateurs données au chapitre 2 sont des cas particuliers dans le sens où elles utilisent une seule hiérarchie. Etant données les nouvelles défi­ nitions de cette section, il serait facile de voir que ces comparateurs inter-hiérarchies exhibent une conduite non monotone. On présentera aussi quelques propriétés intéressantes sur les hiérarchies de contraintes.