Un nouveau résolveur : HOuria

Vue générale de Houria

Dans le cadre théorique des hiérarchies de contraintes, nous avons vu que la résolution d’une telle hiérarchie équivaut à partitionner l’ensemble des valuations en deux ensembles : un ensemble S0 qui contient les valuations qui satisfont les contraintes étiquetées par requise et un autre qui contient son complémentaire. Ensuite, les valuations dans ce premier ensemble sont ordonnées selon un critère de comparaison intégré dans le résolveur et par conséquent on obtient l’ensemble S (qui contient les solutions à la hiérarchie). Ici, on se place de plus dans le cadre où les contraintes sont fonctionnelles (chaque contrainte possède une méthode ou plusieurs méthodes qui peuvent être sélectionnées pour la satisfaction de cette contrainte). Le principe décrit auparavant reste le même sauf qu’une facilité supplémentaire s’ajoute pour la résolution d’une telle hiérarchie. Il suffit de construire un graphe de méthodes des contraintes de la hiérarchie sous deux conditions. 

Integration du premier critère de comparaison

La première condition est que ce graphe doit contenir une méthode de chacune des contraintes requises de la hiérarchie. La deuxième condition est que cette construction doit satisfaire le critère intégré dans le résolveur. Lorsqu’un graphe de méthodes est construit en respectant la première condition, on parle de graphe admissible. Lorsqu’un graphe de méthodes est construit en respectant la première et la deuxième conditions, on parle de graphe-solution qui est un Graphe-Lexicographiquement-Meilleur (GLM ). L’exécution dans un ordre topologique des méthodes qui composent un graphe-solution GLM produit une solution dans l’ensemble S. Houria est un algorithme incrémental. Il permet le maintien de solutions préférées qui sont dans les noeuds de l’arbre (graphes-solutions) selon le premier critère qui est le nombre de contraintes non satisfaites par niveau, dans une hiérarchie de contraintes fonctionnelles. L’ensemble des noeuds de l’arbre de recherche est dans G. Cet algorithme modifie le noeud courant qui comporte la solution courante ou tente de développer d’autres noeuds afin de trouver une autre solution en fonction des modifications portées sur l’ensemble des contraintes de la hiérarchie. Ces modifications peuvent être soit l’ajout, soit le retrait d’une contrainte. Houria gère les contraintes dans un ensemble G de graphes-admissibles par construction d’un Graphe-Lexicographiquement-Meilleur (GLM) qui est un graphe-solution. Cet ensemble G peut être vu comme l’ensemble des noeuds de l’arbre de recherche. G possède la propriété de contenir le meilleur noeud en tête. Ce noeud comporte un ou plusieurs graphes-admissibles qui sont des graphes-solutions (GLM). Les autres noeuds dans G contiennent des graphes-admissibles. Une fois le graphe-solution GLM construit, Houria exécute ses méthodes (dite actives) pour satisfaire les contraintes correspondantes (dite actives)’. Les contraintes fonctionnelles traitées par ce système peuvent être des contraintes possédant plusieurs méthodes (multi-directionnelles) et chacune des méthodes peut être une méthode multi-sorties (possédant plusieurs variables de sortie). Le mode de représentation des contraintes utilisé par Houria est souple : il permet de manipuler les graphes-admissibles dans G comme des ensembles de variables, ce qui rend les calculs moins coûteux pour la détermination d’une solution à l’issue de l’ajout ou du retrait d’une contrainte. Deux propriétés essentielles caractérisent les graphes-admissibles dans G, la première est qu’aucun de ces graphes ne possède de conflit de méthodes. La deuxième est qu’aucun de ces graphes n’a de méthodes qui forment un circuit. 

Définition formelle du critère utilisé

Le premier critère de comparaison intégré dans cet algorithme est le comparateur Nombre-Conîrainte-Non-Satisfaite qui cherche l’ensemble des valuations qui satisfont le maximum de contraintes de préférence dans chaque niveau de la hiérarchie. Ce comparateur utilise le nombre de contraintes non-satisfaites dans chaque niveau de la hiérarchie. Il s’agit d’un comparateur global qui discrimine mieux l’ensemble des valuations qui satisfont les contraintes requises qu’un comparateur local. Par conséquent, la taille de l’ensemble des solutions d’une hiérarchie en utilisant ce critère est généralement plus petite que si on utilise le critère localement-meilleur. Dans le pire des cas, cette taille est identique. Pour illustrer ceci, considérons l’exemple suivant : 1. Ici. GLM designe Graphe Lexieographiquement Meilleur et non Graphe Localement Meilleur utilisé dans le chapitre précédent. 2. une contrainte est active dans le graphe-solution GLM si elle possède une méthode active dans ce graphe-solution GLM 76 Un nouveau résolveur : Houria Exemple : Soient H= ( % H¡, H2}, HQ= {c01,c02}, Hj = (cn, cn, c13}, H2 = fc2J, c22, c23, c33, c43, c53}, S0 = {Q,r\, Q. On suppose aussi que les séquences d’erreurs obtenues par les valuations 6, r¡, Ç sur les classes H0, H¡ et H2 sont : E(H0 Q) = (0,0), E(H0 n) = (0,0), E(H0 Q = (0,0), E(Hj 8j = (0.0,1), E{Hj T\) = (0,1,0), E(Hj Q = (1,0,1), E(H2 6) = (0,0,0,0,1), E(H2 T)) = (0,0,0,1,1), E(H2 0 = (0,0,0,0,0). Avec le critère de comparaison Localement-Prédicat-Meilleur l’ensemble S est fB, r\J. La valuation Ç est éliminée à cause de la valuation 8 qui satisfait un sur-ensemble de contraintes au niveau H¡. Les valuations 8 et T) ne peuvent pas être départagées par ce critère de comparaison puisqu’elles satisfont des ensembles non inclus l’un dans l’autre de contraintes au niveau H¡ de la hiérarchie. Tandis qu’avec le critère global Nombre-Contrainte-Non-Satisfaite, on jugera au niveau H¡ de la hiérarchie que 6 et Tj sont meilleures que Ç et au niveau H2 on jugera que la valuation 6 est meilleure que r) et par conséquent l’ensemble S contient la seule valuation 8. Définition 5.1: Une valuation 8 est Globalement-Meilleure qu’une autre valuation TJ, si et seulement si, pour chacun des niveaux jusqu’au niveau k-1, le nombre de contraintes non satisfaites après application de 6 est égal à celui après application de r¡, et au niveau k, ce nombre est strictement inférieur. Nombre-Contrainte-Non-Satisfaite(Q, r\, H)<ï> Globalement-MeilleurfQ, Tj, H, g), (v, -0 si la contrainte est satisfaite et 1 sinon) ,iv. avec g(V) = ! X ] ^ Í = i D’après cette définition, S ne peut pas contenir une valuation jugée par ce critère moins bonne qu’une autre valuation dans S. Cependant, du fait que « meilleur » ne crée pas un ordre total, S peut contenir plusieurs solutions telles qu’aucune d’entre elles n’est meilleure que les autres. Si plusieurs solutions existent, notre résolveur donne une de ces solutions, et peut calculer les autres solutions de S si le besoin se présente, contrairement à la technique utilisée dans [Fre88], qui fournit un algorithme basé sur le comparateur Localement-Prédicat-Meilleur, et qui donne une seule solution de S. Une autre technique existante permet d’énumérer les solutions de S une par une en effectuant des retours arrière. Ceae dernière est fournie par l’interprète de contraintes hiérarchiques dans les langages de programmation logique [BMM+89], Dans le paragraphe suivant, nous allons présenter comment trouver les valuations de l’ensemble S, en construisant en premier le(s) graphe(s) appelé(s) graphe(s)-solution(s), et en exécutant dans un ordre topologique les méthodes qui composent ce(s) graphe(s).