Définitions formelles des contraintes

Contraintes et hiérarchies de contraintes

Dans ce chapitre, nous présentons un état de l’art sous la forme de définitions formelles des contraintes, des hiérarchies de contraintes, et des solutions à une hiérarchie de contraintes [BFW94.WÜ92, HKS+94]. Nous incluons également des exemples d’utilisation des hiérarchies de contraintes tirés de [BFW92, WB89, FWB92] et des propriétés sur différents comparateurs qui servent à ordonner les solutions d’une hiérarchie de contraintes [BFW92, BFW94]. Une contrainte est une relation entre variables sur un domaine D (c.a.d. entiers, réels, booléens, domaine fini). Une contrainte étiquettée, notée ec, est une contrainte c avec une étiquette e qui exprime l’importance de la contrainte. Nous associons des noms symboliques aux différentes éti­quettes des contraintes. Dans la suite de ce chapitre, nous associons à chacun de ces noms symboli­ques un entier compris entre 0 et n, où n est le nombre de niveaux de la hiérarchie. Le premier niveau 0 est associé au nom symbolique requise. Ce niveau de ia hiérarchie est toujours réservé aux contraintes dures (c.a.d. absolues, requises). Une solution à la hiérarchie de contraintes H est une valuation pour les variables dans H (c.a.d. une fonction qui associe à chaque variable dans H un élément de D). On désire définir l’ensemble S qui contient toutes les solutions de H. Plus clairement, chaque valuation dans 5 doit satisfaire toutes les contraintes dures. De plus, elle doit satisfaire aussi bien que possible l’ensemble des contraintes de préférences en respectant leurs étiquettes relatives. Pour formaliser ce souhait, on définit en premier l’ensemble de valuations noté SQ tel que chaque valuation dans SQ satisfasse l’ensemble des con­ traintes dans HQ. Après et en utilisant SQ, on définit l’ensemble S en éliminant les valuations qui sont moins « bonnes » que d’autres dans SQ. Cette élimination est établie par l’utilisation d’un prédicat « meilleur » qui est un comparateur.

Le prédicat meilleur doit respecte la sémantique de la hiérarchie : s’il existe une valuation 0 dans SQ qui satisfait complètement toutes les contraintes jusqu’au niveau k, alors toute valuation dans 5 doit satisfaire toutes les contraintes jusqu’au niveau k. Borning et son équipe dans [BFW92, BFW94] définissent plusieurs alternatives pour le compara­teur meilleur. Dans chacune de ces alternatives, la fonction d’erreur e(c Q) est définie. Cette fonction retourne un nombre réel positif indiquant à quel degré la contrainte c n’est pas satisfaite par la valua­tion 8. Cette fonction retourne 0 si et seulement si la valuation 9 satisfait la contrainte c. Pour n’importe quel domaine, la fonction d’erreur triviale qui retourne 0 si la contrainte est satisfaite et 1 sinon, peut être utilisée. Le comparateur utilisant cette fonction est appelé comparateur-prédicat. Pour un domaine qui est un espace métrique, il peut être souhaitable d’utiliser sa métrique pour déterminer l’erreur plutôt que d’utiliser la fonction d’erreur triviale définie précédemment. Par exemple, l’erreur pour la contrainte x=y peut être la distance qui sépare x de y. Le comparateur utili­sant ce type d’erreur est appelé comparateur-métrique. La fonction d’erreur par niveau E/H, Q) applique la fonction e sur chacune des contraintes dans H¡ = ¡C], …, cj. Le vecteur d’erreurs obtenu par cette application est : El(H¡ Q) = [e(c¡ 8), …, e(c-k d)]. La séquence d’erreurs pour une hiérarchie de contraintes H contenant n niveaux est le vecteur : ¡E¡(H¡ 0j, …. En(HnB)].

Les Fonctions d’agrégation d’erreurs

Certains comparateurs auxquels nous nous sommes intéressés combinent les erreurs d’un niveau donné de la hiérarchie avant de comparer les valuations. Pour réaliser cela, ces comparateurs utili- sent une fonction d’agrégation g. Cette fonction est appliquée au vecteur de valeurs réelles et retourne des valeurs qui sont comparées en utilisant deux relations: <>„et <„. Quelques instances possibles de cette fonction d’agrégation g sont la somme des valeurs réelles dans le vecteur ou la valeur maximale dans le vecteur. On exige que la relation <g soit irréflexive et transitive. On exige également que la relation <>„ soit reflexive et symétrique. (On utilise la notation <>f au lieu d’utiliser = puisque pour quelques com­parateurs la relation n’est pas transitive). La relation <> indique deux valuations ne pouvant pas être ordonnées en utilisant la relation <g puisque, pour certains comparateurs, elles sont égales et que pour d’autres comparateurs elles sont incomparables.