______________________________________________________________________________ CONSTRAINT PROCESSING Rina Dechter Morgan Kaufmann, 2003 ______________________________________________________________________________ (Notes de lecture de : Pierre LOPEZ) (texte créé le : 15/11/2006 ) (mis à jour le : 17/01/2007 ) ______________________________________________________________________________ GENERALITES Un problème qui a au moins une solution est un problème satisfiable ou cohérent (ou encore consistant). Dans le cas contraire, il est insatisfiable ou incohérent (inconsistant). Exemple de modélisation CSP d´un problème d´ordonnancement : Variables = tâches Domaines = dates de début des tâches Contraintes = restrictions entre variables Autre modèle : Variables = positions des tâches dans une séquence (sur une machine) Domaines = toutes les positions permises dans la séquence Le « scope » (envergure, portée) est l´ensemble de variables sur lesquelles une relation est définie. Complexité Un polynôme de degré d est une fonction p(n) de la forme : p(n)=\sum_{i=1}^{d} a_i n^I , où les a_i sont des constantes. Un polynôme est asymptotiquement positif ssi a_d>0. Une fonction f(n) est bornée polynomialement si f(n)=O(n^k) pour une constante k. Pour une constante a, la fonction f(n)=a^n est une fonction exponentielle. Le taux de croissance des fonctions exponentielles et des polynômes est relié au fait que pour tout a et b tq a>1 : lim_{n \rightarrow \infty} \frac{n^b}{a^n} = 0 . Un algorithme est « tractable » s´il a une complexité polynomiale. On peut vérifier en temps polynomial une solution potentielle d´un pb NP- complet. On ne le peut pas pour un pb NP-difficile. PROPAGATION Algorithmes de consistance locale = propagation de contraintes En explicitant au maximum un système de contraintes (réseau minimal), la recherche de solutions devient plus efficace. Par inférence (non utilisable en pratique car demandant un nombre exponentiel de nouvelles contraintes), la recherche produit une solution (si elle existe) directement en évitant tout échec. Un algorithme de k-consistance garantit que toute instanciation consistante de k-1 variables peut être étendue à n´importe quelle kème variable. Les algorithmes de k-consistance sont basés sur le principe que si une valeur ne peut participer à la construction d´une solution d´un sous- réseau de k variables alors cette valeur ne peut pas, non plus, rentrer dans la construction d´une solution complète. ARC-CONSISTANCE La consistance d´arcs d´un réseau est obtenue en appliquant la procédure REVISE sur toutes les paires de variables. La complexité de la procédure REVISE est O(k^2) où k borne la taille des domaines de valeurs des variables (« domain tightness »). La complexité de l´algorithme AC-3 est O(ek^2) où k borne la taille des domaines de valeurs des variables et e le nombre de contraintes binaires. L´algorithme AC-4 associe chaque valeur ai dans le domaine de xi à un taux de support de la variable xi (nombre de valeurs de xj consistantes avec ai). La valeur ai est supprimée du domaine Di si elle n´a pas de support dans une variable voisine. L´algorithme AC-4 atteint une complexité temporelle optimale qui est en O(ek^2). Il a aussi une complexité spatiale en O(ek^2). D´un point de vue pratique, si k^2, qui est le nombre maximal de relations binaires, est bien en deçà du nombre réel de n-uplets dans chaque relation binaire t (« constraint tightness »), l´algorithme AC-3 (et même AC-1) peut être plus efficace que AC-4. L´algorithme AC-6 atteint la complexité optimale sans tomber dans les mauvais cas d´utilisation de AC-4. Des raffinements de AC-3 (AC-2001, etc.) rencontrent la complexité optimale et rivalisent en performance avec les meilleurs algorithmes de consistance d´arc. La consistance d´arcs généralisée et la consistance d´arcs relationnelle sont appliquées pour des réseaux de contraintes non binaires. CHEMIN-CONSISTANCE La complexité de l´algorithme PC-2 est O(n^3.k^5) ou O(n^3.t^2.k) (pour t proche de k^2). La complexité optimale de la consistance de chemins est obtenue avec l´algorithme PC-4 dont la complexité est O(n^3.k^3) ou O(n^3.t.k). Dans les meilleurs cas, PC-2 peut être plus performant que PC-4. Pour des réseaux de contraintes binaires, la 3-consistance est identique à la consistance de chemins. Dès que le réseau possède des contraintes ternaires, la vérification de la 3-consistance nécessite le test de contraintes ternaires (ce que ne réalise pas la consistance de chemins). CONSISTANCE DIRECTIONNELLE Il s´agit ici de restreindre les inférences de recherche des différents type de consistance à un ordre donné des variables. CONSISTANCE D´ARCS DIRECTIONNELLE Un réseau est arc-consistant directionnel (DAC) relativement à un ordre d=(x1,...,xn) ssi toute variable xi est arc-consistante avec toute autre variable xj telle que i \le j. Un résultat de DAC n´est pas pleinement arc-consistant mais l´avantage est que chaque contrainte n´est traitée qu´une fois. La complexité de DAC est O(ek^2) où k borne la taille des domaines de valeurs des variables et e le nombre de contraintes binaires. CONSISTANCE DE CHEMINS DIRECTIONNELLE Un réseau est chemin-consistant directionnel (DPC) relativement à un ordre d=(x1,...,xn) ssi, pour tout k \ge i,j, la paire {xi,xj} est chemin- consistante relativement à k. La chemin-consistance directionnelle forte implique l´arc-consistance directionnelle et la chemin-consistance directionnelle. k-CONSISTANCE DIRECTIONNELLE Un réseau est k-consistant directionnel (DIC) relativement à un ordre d=(x1,...,xn) ssi toutes les (k-1)èmes variables sont k-consistantes avec toute autre variable qui les suit dans l´ordre d. Un réseau est fortement k-consistant directionnel s´il est j-consistant directionnel pour tout j \le k. CONCEPTS DE GRAPHES Considérons un graphe ordonné, ie suivant un ordre d sur les sommets. Les sommets précédents d´un sommet v dans l´ordre d sont les parents de v. La largeur d´un sommet est le nombre de ses parents. La largeur d´un ordre est la largeur maximale sur tous les sommets La largeur d´un graphe est la largeur minimale sur tous les ordres. Problème de savoir à l´avance quel niveau de recherche de consistance faut-il appliquer pour générer une représentation sans backtrack pour un réseau de contraintes donné. (Un réseau de contraintes est dit sans backtrack selon un ordre si chaque feuille du graphe de recherche correspondant est une solution.) Pour un graphe ordonné de largeur 1 (arborescence), l´arc-consistance directionnelle permet de trouver une solution absente de backtrack. Pour un graphe ordonné de largeur 2 chemin-consistant directionnel, on peut trouver une solution absente de backtrack. S´il n´est pas chemin- consistant directionnel, on n´a pas de garantie. Un problème de recherche de solutions est sans backtrack suivant un ordre donné si le niveau de forte consistance directionnelle suivant cet ordre est plus grand que la largeur du graphe de contraintes ordonné : un problème de largeur k et (k+1)-consistant est sans backtrack. BACKTRACK Le Backtracking ne demande qu´une complexité linéaire mais, dans le pire des cas, il nécessite un temps exponentiel en le nombre de variables. Pour améliorer sa performance, on diminue la taille de son espace de recherche exploré. On peut ainsi utiliser des techniques de consistance locale et des heuristiques d´instanciation des variables adéquates afin de réduire la taille de l´espace de recherche sous-jacent. On peut utiliser ces techniques en « preprocessing » ou les inclure dans une stratégie de contrôle de la recherche. Le Backtracking souffre fréquemment d´un phénomène de « trashing », qui se traduit par le fait de redécouvrir de manière répétitive les mêmes inconsistances et les mêmes instanciations partielles durant la recherche. Les procédures dynamiques d´amélioration de l´élagage de l´arbre sont les schémas du type « moving-forward activity » ou « look- ahead » (sélection de variables et de valeurs) et « backtracking activity » ou « look-back » (« backjumping », apprentissage ou « constraint recording », « no-good learning »). LOOK-AHEAD ALGORITHMES DE LOOK-AHEAD POUR LA SELECTION DE VALEURS (algorithmes basés sur la consistance d´arcs) - Forward-Checking : propagation de la tentative d´instanciation de la variable courante sur les variables non instanciées impliquées dans les contraintes dont le scope inclut la variable courante. Complexité : O(ek^2). - Arc-Consistency Look-Ahead : aussi appelé real full look-ahead. Une version célèbre d´implémentation du RFLA est MAC. Fonctionnement de MAC : o Une instanciation entraîne une impasse : la valeur est retirée du domaine. o Sur le domaine réduit : - Si cela entraîne une impasse : le problème n´a pas de solution. - Sinon, reprendre la sélection de valeurs pour une prochaine variable (en prenant la réfutation de l´instanciation, sur le domaine réduit, de la variable précédente). Complexité : O(ek^3). - Full and Partial Look-Ahead Ces 2 algorithmes (FLA et PLA) font moins d´élagage que Arc- Consistency Look-Ahead. FLA fait une seule passe sur les variables non instanciées. PLA fait moins encore puisqu´il applique une DAC sur les variables non instanciées. Complexité : O(ek^3). - Dynamic Look-Ahead Value Orderings o Min-Conflicts (MC) : choix de la valeur qui supprime le plus petit nombre de valeurs des domaines des variables non instanciées. o Max-Domain-size (MD) : choix de la valeur qui crée le plus grand minorant sur la taille des domaines des variables non instanciées. o Estimate Solutions (ES) : choix de la valeur qui crée la plus grande borne supérieure sur le nombre de solutions (borne obtenue par la multiplication des tailles des domaines des variables non instanciées après filtrage compte tenu de l´instanciation de la variable courante). LOOK-AHEAD POUR LA SELECTION DE VARIABLES (ex : min-width, max-cardinality) - Dynamic Variable Orderings o First-fail, min-domain - Randomized Backtracking En cas d´égalité des critères dictés par les heuristiques d´instanciation, il est nécessaire de résoudre les conflits pour la sélection des variables/valeurs. La manière dont cela est fait peut avoir un impact très important sur les performances de l´algorithme de Backtracking. Fort de ce constat et devant l´impossibilité de trouver une heuristique d´instanciation qui marche bien dans tous les cas, l´idée est ici d´utiliser un ordre sur les variables (min-domain par exemple) et d´arbitrer les conflits éventuels aléatoirement. De manière similaire, une valeur peut être sélectionnée aléatoirement ou, alternativement, on peut utiliser une heuristique efficace (min-conflict par exemple) puis arbitrer aléatoirement les conflits éventuels. Comme le résultat de ce type d´algorithmes produit des variances importantes, il est généralement très efficace de redémarrer (« restart ») la recherche après que ce soit écoulé un temps imposé (« cutoff time »), temps qui est incrémentalement augmenté afin d´assurer de parvenir à une solution (ou à la preuve d´inconsistance). LOOK-BACK Les algorithmes de look-back veillent principalement à limiter le phénomène de trashing du backtracking (redécouverte d´une inconsistance ou d´une instanciation partielle consistante). Supposons qu´une inconsistance est rencontrée sur la variable x_i. Backtrack revient sur x_{i-1}. Si une autre valeur est possible pour x_{i-1} mais qu´aucune contrainte dont le scope inclut x_i et x_{i-1} n´existe. x_{i-1} ne peut être la cause de l´inconsistance rencontrée sur x_i et on retrouvera nécessairement une inconsistance sur x_i pour chaque valeur donnée à x_{i-1}. On peut améliorer ce processus en identifiant la variable coupable (« culprit ») de l´inconsistance et en effectuant le retour dans l´arbre sur cette variable. L´identification est basée sur la notion d´ensemble en conflit. Un ensemble en conflit est une instanciation d´un sous-ensemble de variables ne laissant aucune possibilité pour une certaine variable non encore instanciée. Si le cardinal de cet ensemble est minimal, on parle d´ensemble minimal en conflit. Une instanciation partielle qui n´apparaît dans aucune solution est un « no-good ». Un ensemble en conflit est un no-good, mais un no-good n´est pas nécessairement un ensemble en conflit. BACKJUMPING - Le Backjumping de Gaschnig remonte sur une variable coupable présente dans une « leaf dead-end », c.-à-d. un ensemble en conflit. - Le Backjumping basé sur les graphes remonte sur des « nonleaf ». - Le Backjumping dirigé par les conflits (CBJ) mixe les 2 précédents. ALGORIHMES D´APPRENTISSAGE Ils peuvent être « deep » s´ils s´appuient sur des ensembles minimaux en conflit, ou « shallow » si ces ensembles ne sont pas nécessairement minimaux. - graph-based learning - deep learning - jumpback learning COMBINAISONS LOOK-AHEAD / LOOK-BACK Un cas typique de combinaison est FC-CBJ, qui mélange le Backjumping dirigé par les conflits, Forward-Checking et un ordre dynamique d´instanciation des variables. Pour l´expérimentation et la comparaisons d´algorithmes, 3 cas s´offrent à nous : - les benchmarks : s´ils sont suffisamment variés, l´avantage est de traiter des problèmes proches de ceux de la réalité ; l´inconvénient est la difficulté d´extrapoler les résultats (un algorithme peut être supérieur à un autre sur une instance, moins bon sur une autre instance). - les problèmes aléatoires : l´avantage est de pouvoir tester les algorithmes sur un grand nombre d´échantillons de problèmes ; la difficulté concerne le réglage des paramètres. - les problèmes aléatoires centrés sur une application : ce sont des problèmes générés sur la base de paramètres spécifiques à une application donnée (ordonnancement par exemple) ; combine les vertus des deux types précédents. Le phénomène de transition de phase traduit le fait qu´il existe un pic de complexité pour un certain taux de contraintes d´un problème. Pour 3- SAT, il a été montré que le pic est à un ratio du nombre de clauses sur le nombre de variables de 4,2. Des expériences montrent que les choses suivantes sont utiles : - utiliser AC au sein d´une procédure de recherche - combiner apprentissage et ordre sur les variables - combiner FC et AC - etc. RESEAUX DE CONTRAINTES TEMPORELLES Intérêt de l´algorithme NPC-2 (page 354) en lieu et place de PC-2 pour la propagation de contraintes temporelles.