Extensions de la théorie des hiérarchies de contraintes

Extensions de la théorie des hiérarchies de contraintes

Les cinq parties qui composent ce chapitre visent à donner un aperçu sur les extensions de la théorie des hiérarchies de contraintes décrite au chapitre précédent. Dans un premier temps, on verra les annotations que l’on peut poner sur des variables dans une hiérarchie de contraintes. Nous mon­trons l’intérêt de ces annotations à travers des exemples pratiques et réels. Dans un deuxième temps, nous verrons la notion des hiérarchies partiellement ordonnées et ce qu’il résulte de cet ordre. En troisième partie de ce chapitre, nous présenterons l’intégration des fonctions objectifs aux hiérar­chies de contraintes. En quatrième partie, on discutera de la variation du critère selon les niveaux d’une hiérarchie ainsi que de l’intérêt de cette variation. Et en dernière partie, nous parlerons de l’intégration des hiérarchies de contraintes dans la programmation logique par contraintes. Les systèmes de contraintes basés sur le modèle de perturbation utilisent souvent le principe de l’annotation lecture-seulement. Ceci a pour but d’aider à limiter le choix des variables à recalculer pour resatisfaire les contraintes après une perturbation introduite dans le système. Les hiérarchies de contraintes peuvent être vues comme une solution alternative pour spécifier ce choix sans avoir à soulever la généralité des contraintes multi-directionnelles. Cependant, la notion de lecture-seule­ ment est utile dans les hiérarchies de contraintes multi-directionnelles. Cette notion est utile à la résolution de contraintes qui font référence à un support externe pour l’acquisition d’une donnée ou qui font référence à une autre source d’information hors site. Un exemple simple est celui de la sou­ ris. La contrainte possédant un point qui suit la position de la souris doit être en lecture-seulement sur cette position.

Un autre exemple est celui des contraintes qui sont des relations entre des états anciens et des états nouveaux d’un robot. Dans ce cas, on aimerait que les états anciens soient en lecture-seulement afin que le futur ne change pas le passé. Intuitivement, lorsqu’on choisit les meilleures solutions d’une hiérarchie de contraintes, les con­traintes ne doivent pas influencer le choix des valeurs de leurs variables marquées par l’annotation lecture-seulement. Au contraire, les contraintes peuvent influencer le choix des valeurs de leurs variables qui ne sont pas annotées. Cependant, on veut que les contraintes soient satisfaites si possi­ble tout en respectant leurs niveaux de préférence. En particulier, lorsque les contraintes requises sont soumises à l’annotation lecture-seulement, on doit avoir leur satisfaction. Une esquisse infor­melle de la définition est donnée dans [BFW92. BFW94] et consiste à remplacer les occurrences des variables (marquées par la notation lecture-seulement) par des constantes. Ceci a pour but d’empê­cher la contrainte d’influencer le choix de ces variables marquées. Ainsi nous commençons la défini­tion de l’ensemble de solutions de la hiérarchie H en formulant un ensemble Q de hiérarchies de contraintes. Chaque élément dans Q est une hiérarchie de contraintes avec un domaine arbitraire d’éléments substitué pour les variables marquées par la notation lecture-seulement.

Cette démarche est réalisée en suivant les étapes suivantes: une valeur pour la variable est choisie et une hiérarchie est formulée en considérant cette valeur. Après avoir choisi toutes les valeurs possi­bles, les solutions résultantes sont triées en enlevant celles qui sont incorrectes (il est à signaler que cette approche a pour objectif de spécifier la sémantique de la notation lecture-seulement, et que cela ne construit pas un algorithme raisonnable pour la résolution d’une hiérarchie de contraintes. Les algorithmes de résolution sont discutés dans les chapitres suivants de ce mémoire). La figure 3 montre une hiérarchie à deux niveaux de préférences (cet exemple est emprunté à [BFW94]). Le symbole « ? » symbolise la notation lecture-seulement. Les éléments de Q sont formu­lés en remplaçant les occurrences de la variable y par les éléments du domaine D. Dans la figure 4, on résout les hiérarchies de contraintes dans Q en éliminant les valuations qui asso­cient aux occurrences des variables (non marquées) une valeur différente de celle associée à l’occur­rence marquée par la notation lecture-seulement. On observe que la valuation {y —» 4, x —» 4/ est la seule consistante et constitue une solution à la hiérarchie initiale.