Latíf : résolveur d’une hiérarchie de contraintes à sorties multiples utilisant plusieurs critères

Motivations et vue générale sur Latif

Cycles et conflit

L’algorithme de la propagation locale est très efficace pour des hiérarchies utilisant un critère de comparaison basé sur l’erreur prédicat et ne formant pas de circuits de méthodes des contraintes qui la compose. Malheureusement, beaucoup de hiérarchies du monde réel contiennent des contraintes où leurs méthodes forment des circuits. Ces hiérarchies utilisent aussi des critères basés sur l’erreur métrique. Ces deux cas ne peuvent pas être résolus par la propagation locale. Par exemple, considérons le système de contraintes de la figure 46. Ce système représente une situation typique où le point-milieu M d’un segment ayant pour extrémités les points A et B est déplacé avec une souris. Le point M est marqué par la notation écriture-seulement et L (qui est la longueur du segment [A,B]) est marqué par la notation lecture-seulement (car on souhaite que cette longueur reste fixe). Pour avoir une solution à ce problème, on est ramené à résoudre un circuit de méthodes. La figure 47 illustre ce fait.

Le besoin de considérer des contraintes ayant des méthodes multi-sorties

 Une méthode d’une contrainte est dite multi-sorties si elle détermine plusieurs variables. L’utilisation de ce type de contrainte est considérée pour la résolution des problèmes de cycles. Elle est considérée aussi pour une meilleure modélisation de certaines applications comme par exemples TRIp et TRIpII [KK91 .SSA91 ] qui sont deux applications d’interfaces graphiques. Plusieurs articles de la littérature présentent les avantages et la facilité d’utilisation des contraintes ayant plusieurs variables de sortie [ROS94, San94. HÍ193]. Généralement, la modélisation par des contraintes ayant des méthodes multi-sorties a pour but de donner un aspect élégant pour l’expressivité des contraintes du problème traité. Par exemple, considérons les variables x et y qui représentent les coordonnées cartésiennes d’un point, et les variables p et G qui représentent les coordonnées polaires de ce même point. Pour garder ces deux représentations consistantes, on peut définir une contrainte possédant deux méthodes à deux-sorties qui sont m¡c¡ dans un sens et w2c/ ° »ans ¡’autre sens définies dans la figure 50. 

Vue générale sur Latif

L’algorithme que nous allons présenter dans ce chapitre est une extension de LSCS présenté dans [HKS+94]. Notre algorithme résout une hiérarchie de contraintes multi-directionnelles et multi-sorties, et de plus, manipule différents types de contraintes. On s’intéresse au cas où les modes de combinaison peuvent varier selon les niveaux. Par exemple, dans une hiérarchie contenant n niveaux d’importance, on peut utiliser pour les n-î premiers niveaux un critère local, et pour le n’em£ niveau un critère global plus fin qui impose un ordre total sur les configurations pour départager les solutions. Partant d’ici, les hiérarchies pouvant être traitées par Latif sont celles ayant à leur dernier niveau des contraintes associées au comparateur global Moindre-Carrés-Métrique ou au comparateur global Pire-Cas-Métrique et celles des niveaux supérieurs sont associées à un comparateur local. Latif peut être vu comme un système de pilotage de résolveurs spécifiques pour le traitement d’une hiérarchie contenant plusieurs types de contraintes. Chacun de ces résolveurs est basé sur un comparateur bien déterminé. Pour résoudre une hiérarchie de contraintes, cet algorithme prend en compte le fait que certaines des contraintes de cette hiérarchie doivent être résolues ensemble pour former des cellules de contraintes. Dans ce cas, on parie aussi de subdivision de l’ensemble des contraintes de la hiérarchie en des sous ensembles de contraintes qui doivent être résolus séparément.

On pourrait tout résoudre par une optimisation globale, mais ici, on espère qu’en traitant séparément chaque cellule, on arrivera à réduire la complexité de la résolution. L’ensemble des cellules formé par cet algorithme ne doit pas contenir de dépendance cyclique entre les cellules. Donc, on doit définir un ordre partiel entre les cellules de cet ensemble qui permette de propager les valeurs des variables d’une cellule à une autre. Chacune de ces cellules formées est résolue par un ou plusieurs résolveurs selon les types de contraintes qui la composent. Les valeurs des variables ainsi obtenues à la suite de cette résolution sont propagées à d’autres cellules de contraintes non encore résolues. Cette propagation se fait par l’algorithme de propagation locale. Il s’agit d’un résolveur incrémental : les contraintes peuvent être ajoutées ou retranchées du système. A chaque ajout ou retrait de contrainte, un nouveau graphe solution de cellules de contraintes est formé et la résolution locale de ces cellules est exécutée. La formation d’une cellule est soumise à des conditions qui favorisent la planification d’un graphe admissible.

Des conditions supplémentaires sont ajoutées pour générer un graphe solution à partir du graphe admissible. Ce graphe solution obtenu permet de trouver les solutions S après résolution des cellules qui le composent. Les graphes admissibles et les graphes solutions créés par cet algorithme ont une sémantique légèrement différente de celle des graphes admissibles et des graphes solutions obtenus par les autres résolveurs présentés dans les autres chapitres (il est à rappeler que ces résolveurs sont des algorithmes de propagation locale et que chacun d’eux implémente un critère local ou global utilisant l’erreur prédicat). un graphe admissible créé par les algorithmes de propagation locale est un graphe qui contient toutes les contraintes requises actives (satisfaites), tandis qu’un graphe admissible créé par Latif est un graphe de cellules contenant toutes les contraintes de la hiérarchie. un graphe solution créé par les autres résolveurs est un graphe, qui respecte le critère local ou le critère global utilisé, tandis qu’un graphe solution créé par Latif est un graphe qui respecte, le critère global utilisé dans le dernier niveau de la hiérarchie, et le critère local utilisé pour les niveaux supérieurs de la hiérarchie.

Il faut signaler que cet algorithme suppose que chaque contrainte portant sur un ensemble de variables de taille n et ayant m variables en sortie (n>m) possède un ensemble de méthodes de taille C™ (c.à.d. n’importe quelles m variables de cet ensemble peuvent être déterminées par les n-m variables qui restent ). La résolution d’une cellule de contraintes peut nécessiter un appel à un ou plusieurs résolveurs si cette dernière contient plusieurs types de contraintes. Par exemple, si l’on considère une hiérarchie à trois niveaux (fort, moyenne, faible) de contraintes, que les deux premiers niveaux sont associés au comparateur Localement-Prédicai-Meilleur (I¡J>M), et que le troisième niveau est associé au comparateur Pire-Cas-M étriqué (xPCM), alors une cellule du graphe solution peut contenir ces deux types de contraintes. La résolution de cette cellule consiste à appeler un résolveur spécifique sachant résoudre les deux types de contraintes.