144
Dr Amar ISLI Département d’Informatique Faculté d’Electronique et d’Informatique Université des Sciences et de la Technologie Houari Boumediène BP 32, El-Alia, Bab Ezzouar DZ-16111 ALGER Nouvelle page : http://www.usthb.dz/perso/info/aisli Ancienne page : http://www.usthb.dz/fei-deptinfo/perso/aisli/amarisli.htm 05/01/2011 Master2SII->Programmation Par Contraintes 1 Programmation Par Contraintes Cours du Master “Systèmes Informatiques Intelligents” 2ème année

Programmation par contraintes

Embed Size (px)

DESCRIPTION

Cours de master 1 du module programmation sous contraintes de la spécialité SII (système informatique intéligent)

Citation preview

Page 1: Programmation par contraintes

Dr Amar ISLIDépartement d’Informatique

Faculté d’Electronique et d’InformatiqueUniversité des Sciences et de la Technologie Houari Boumediène

BP 32, El-Alia, Bab EzzouarDZ-16111 ALGER

Nouvelle page :http://www.usthb.dz/perso/info/aisli

Ancienne page :http://www.usthb.dz/fei-deptinfo/perso/aisli/amarisli.htm

05/01/2011Master2SII->Programmation

Par Contraintes 1

Programmation Par Contraintes

Cours du Master “Systèmes Informatiques Intelligents” 2ème année

Page 2: Programmation par contraintes

CHAPITRE IContraintes et problèmes de satisfaction de contraintes

Contrainte Une contrainte est une relation sur un

nombre fini de variables (inconnues) Une variable admet un domaine

(d’instanciation) : l’ensemble où elle prend ses valeurs

Une contrainte restreint les valeurs que peuvent prendre simultanément les variables qu’elle relie

05/01/2011Master2SII->Programmation

Par Contraintes 2

Page 3: Programmation par contraintes

CHAPITRE IContraintes et problèmes de satisfaction de contraintes

Définition d’une contrainte Définition en extension Définition en intention

05/01/2011Master2SII->Programmation

Par Contraintes 3

Page 4: Programmation par contraintes

CHAPITRE IContraintes et problèmes de satisfaction de contraintes

Problème de satisfaction de contraintes CSP : Constraint Satisfaction Problem Triplet P=(X,D,C) :

X ensemble fini de variables : X={X1, …,Xn} D fonction associant à chaque variable Xi un

domaine D(Xi) C ensemble fini de contraintes sur les variables de

P : C={C1, …,Cm}

05/01/2011Master2SII->Programmation

Par Contraintes 4

Page 5: Programmation par contraintes

CHAPITRE IContraintes et problèmes de satisfaction de contraintes

Instanciation d’un CSP Une instanciation est un élément

du produit cartésien D(X1)x…xD(Xn)

une instanciation associe à chacune des variables du CSP un élément de son domaine, le ième élément étant la valeur associée à la variable Xi

05/01/2011Master2SII->Programmation

Par Contraintes 5

Page 6: Programmation par contraintes

CHAPITRE IContraintes et problèmes de satisfaction de contraintes

Solution d’un CSP Une solution est une instanciation

satisfaisant chacune des contraintes du CSP

pour chacune des contraintes, si on remplace chacune des variables sur lesquelles elle porte par la valeur que lui associe l’instanciation, ladite contrainte s’évalue à vrai

05/01/2011Master2SII->Programmation

Par Contraintes 6

Page 7: Programmation par contraintes

CHAPITRE IContraintes et problèmes de satisfaction de contraintes

Exemple : le problème de coloriage d’un graphe

Description : Un graphe et une fonction cl associant à chaque

nœud un ensemble de couleurs permises Question :

Peut-on colorier les nœuds du graphe, chacun avec une couleur de l’ensemble que lui associe la fonction cl, de telle sorte que deux noeuds adjacents (i.e., reliés par une arête) n’aient pas la même couleur ?

05/01/2011Master2SII->Programmation

Par Contraintes 7

Page 8: Programmation par contraintes

CHAPITRE IContraintes et problèmes de satisfaction de contraintes

Exemple : le problème de coloriage d’un graphe

Le graphe peut être vu comme une représentation graphique d’une carte géographique à colorier :

Les nœuds du graphe sont les différents pays de la carte

Les couleurs associées à un nœud sont celles avec lesquelles le pays correspondant peut être colorié (drapeau)

Deux nœuds sont adjacents si et seulement si les pays correspondants sont limitrophes (voisins) l’un de l’autre

05/01/2011Master2SII->Programmation

Par Contraintes 8

Page 9: Programmation par contraintes

CHAPITRE IContraintes et problèmes de satisfaction de contraintes

Exemple : une instance du problème de coloriage d’un graphe

G=<V,E> V={R,S,T,U} E={(R,S),(R,T),(R,U),(S,U)}

cl(R)=cl(S)={c1,c2} ; cl(T)={c1} ; cl(U)={c2}

05/01/2011Master2SII->Programmation

Par Contraintes 9

Page 10: Programmation par contraintes

CHAPITRE IContraintes et problèmes de satisfaction de contraintes

Exemple : modélisation de l’instance avec un CSP

CSP P=(X,D,C) avec : X={X1,X2,X3,X4} D(X1)=D(X2)={c1,c2} ; D(X3)={c1} ; D(X4)={c2} C={X1X2,X1X3,X1X4,X2X4}

Le CSP admet quatre instanciations possibles, qui sont tous les éléments du produit cartésien des domaines

(c1,c1,c1,c2), (c1,c2,c1,c2), (c2,c1,c1,c2), (c2,c2,c1,c2)

Le CSP n’admet néanmoins aucune solution

05/01/2011Master2SII->Programmation

Par Contraintes 10

Page 11: Programmation par contraintes

CHAPITRE IICSP binaires

CSP binaires Chacune des contraintes porte sur au plus deux variables

Une contrainte unaire est un cas particulier de contrainte binaire

Un CSP binaire peut donc être vu comme un CSP dont chacune des contraintes porte exactement sur deux variables

CSP discrets On se restreint aux domaines finis Un sous-ensemble fini de IN : Pairs_10={0,2,4,6,8,10} Un ensemble fini de couleurs : Couleurs={Blanc,Rouge,Vert} Un ensemble de personnes : Cadets=

{Hacène,Kamélia,Lilia,Ouerdouche,Younès}

05/01/2011Master2SII->Programmation

Par Contraintes 11

Page 12: Programmation par contraintes

CHAPITRE IICSP binaires

CSP binaires CSP binaires continus

Le domaine de chacune des variables est continu L’ensemble continu des points du temps modélisé

par IR L’ensemble continu des points du plan modélisé

par IR2

Le sous-ensemble de IR2 constituant les intervalles de temps : toutes les paires (d,f) de IR2 vérifiant d<f

05/01/2011Master2SII->Programmation

Par Contraintes 12

Page 13: Programmation par contraintes

CHAPITRE IICSP binaires

CSP binaires CSP continus

CSP quantitatifs TCSP : Temporal Constraint Satisfaction Problems

CSP qualitatifs « make only as many distinctions as necessary » L’algèbre des points L’algèbre des intervalles L’algèbre des directions cardinales

05/01/2011Master2SII->Programmation

Par Contraintes 13

Page 14: Programmation par contraintes

CHAPITRE IICSP binaires

CSP binaire discret P=(X,D,C)

X={X1, …,Xn} D={D(X1), …,D(Xn)} : tous les domaines

sont discrets finis C={C1, …,Cm} : toutes les contraintes sont

binaires

05/01/2011Master2SII->Programmation

Par Contraintes 14

Page 15: Programmation par contraintes

CHAPITRE IICSP binaires

Relations associées à une contrainte Soit P=(X,D,C) un CSP binaire discret, Ck

une contrainte de P, et Xi et Xj les variables de P sur lesquelles porte Ck

Les relations binaires associées à Ck, notées Rk(Xi,Xj) et Rk(Xj,Xi), sont définies comme suit : Rk(Xi,Xj)={(a,b)D(Xi)xD(Xj) : (Xi,Xj)=(a,b) satisfait Ck} Rk(Xj,Xi)={(a,b)D(Xj)xD(Xi) : (Xj,Xi)=(a,b) satisfait Ck}

05/01/2011Master2SII->Programmation

Par Contraintes 15

Page 16: Programmation par contraintes

CHAPITRE IICSP binaires

Relations associées à une contrainte Si un CSP binaire est discret, les relations

Rk(Xi,Xj) et Rk(Xj,Xi) associées à la contrainte Ck peuvent être représentées, respectivement, par les matrices booléennes Mk(Xi,Xj) et Mk(Xj,Xi) suivantes :

Mk(Xi,Xj) a |D(Xi)| lignes et |D(Xj)| colonnes Mk(Xi,Xj)[p,q]=1 si (Xi,Xj)=(ap,bq) satisfait Ck, 0 sinon Mk(Xj,Xi) a |D(Xj)| lignes et |D(Xi)| colonnes Mk(Xj,Xi)[p,q]=1 si (Xj,Xi)=(ap,bq) satisfait Ck, 0 sinon

05/01/2011Master2SII->Programmation

Par Contraintes 16

Page 17: Programmation par contraintes

CHAPITRE IICSP binaires

Inverse d’une matrice L’inverse d’une matrice M à m lignes et

n colonnes est la matrice à n lignes et m colonnes notée M-1 définie comme suit :Pour tout i=1..n, pour tout j=1..m, M-1[i,j]=M[j,i]

Les matrices booléennes Mk(Xi,Xj) et Mk(Xj,Xi) représentant les relations associées à la contrainte Ck d’un CSP binaire discret sont inverses l’une de l’autre

05/01/2011Master2SII->Programmation

Par Contraintes 17

Page 18: Programmation par contraintes

CHAPITRE IICSP binaires

Intersection de deux matrices booléennes

L’intersection de deux matrices M et N, à m lignes et n colonnes chacune, est la matrice booléenne à m lignes et n colonnes notée P=MN définie comme suit :

Pour tout i=1..m, pour tout j=1..n :P[i,j]=1 si M[i,j]=1 et N[i,j]=1, 0 sinon

05/01/2011Master2SII->Programmation

Par Contraintes 18

Page 19: Programmation par contraintes

CHAPITRE IICSP binaires

Union de deux matrices booléennes L’union de deux matrices booléennes

M et N, à m lignes et n colonnes chacune, est la matrice booléenne à m lignes et n colonnes notée P=MN définie comme suit :

Pour tout i=1..m, pour tout j=1..n :P[i,j]=1 si M[i,j]=1 ou N[i,j]=1, 0 sinon

05/01/2011Master2SII->Programmation

Par Contraintes 19

Page 20: Programmation par contraintes

CHAPITRE IICSP binaires

Produit de deux matrices booléennes Le produit de deux matrices booléennes

M et N, M à m lignes et n colonnes, et N à n lignes et p colonnes, est la matrice booléenne à m lignes et p colonnes notée P=MN définie comme suit :Pour tout i=1..m, pour tout j=1..p :

P[i,j]=1 s’il existe k=1…n tel que M[i,k]=1 et N[k,j]=1

P[i,j]=0 sinon

05/01/2011Master2SII->Programmation

Par Contraintes 20

Page 21: Programmation par contraintes

CHAPITRE IICSP binaires

Représentation graphique d’un CSP binaire La représentation graphique d’un CSP discret

P=(X,D,C) est un graphe orienté étiqueté GP=(X,E,l) défini comme suit :

L’ensemble des sommets de GP est l’ensemble X des variables de P Pour toutes variables Xi et Xj, si P admet une contrainte portant sur Xi

et Xj, alors GP contient un et un seul des deux arcs (Xi,Xj) et (Xj,Xi) Pour toutes variables Xi et Xj, si P n’admet aucune contrainte portant

sur Xi et Xj, alors GP ne contient ni l’arc (Xi,Xj) ni l’arc (Xj,Xi) Pour tout arc (Xi,Xj) de GP, l’étiquette l(Xi,Xj) de (Xi,Xj) est l’intersection

de toutes les matrices booléennes Mk(Xi,Xj) représentant les relations Rk(Xi,Xj) associées aux différentes contraintes Ck de P portant sur Xi et Xj

05/01/2011Master2SII->Programmation

Par Contraintes 21

Page 22: Programmation par contraintes

CHAPITRE IICSP binaires

Exemple Kamélia est moins de huit ans plus jeune que Hacène,

qui lui n’a pas le même âge que Younès Younès, à son tour, est plus jeune que Lilia, qui elle a

le même âge que Hacène Ouerdouche est plus de dix ans plus jeune que

Hacène La différence d’âge entre Ouerdouche et Hacène est

impaire et n’est pas multiple de trois Tous les âges varient entre onze et vingt-quatre ans

05/01/2011Master2SII->Programmation

Par Contraintes 22

Page 23: Programmation par contraintes

CHAPITRE IICSP binaires

Exemple Cinq variables : X1 (Hacène), X2 (Kamélia), X3 (Lilia), X4 (Ouerdouche),

X5 (Younès) Kamélia est moins de huit ans plus jeune que Hacène, qui lui n’a pas

le même âge que Younès 0<X1-X2<8 (C1), X1X5 (C2)

Younès, à son tour, est plus jeune que Lilia, qui elle a le même âge que Hacène

X3-X5>0 (C3), X3=X1 (C4) Ouerdouche est plus de dix ans plus jeune que Hacène

X1-X4>10 (C5) La différence d’âge entre Ouerdouche et Hacène est impaire et n’est

pas multiple de trois |X1-X4| impair (C6), |X1-X4| non multiple de 3 (C7)

05/01/2011Master2SII->Programmation

Par Contraintes 23

Page 24: Programmation par contraintes

CHAPITRE IICSP binaires

Exemple Tous les âges varient entre onze et vingt-

quatre ans D(X1)=D(X2)=D(X3)=D(X4)=D(X5)={11,12,…,24}

05/01/2011Master2SII->Programmation

Par Contraintes 24

Page 25: Programmation par contraintes

CHAPITRE IICSP binaires

Représentation graphique d’un CSP binaire

Un CSP binaire est également appelé réseau de contraintes :

Parce que facilement représentable sous forme d’un graphe orienté étiqueté

CSP binaire discret mais également CSP binaire continu

05/01/2011Master2SII->Programmation

Par Contraintes 25

Page 26: Programmation par contraintes

CHAPITRE IICSP binaires

Représentation matricielle d’un CSP binaire La représentation matricielle d’un CSP discret P=(X,D,C)

est une matrice carrée de matrices, notée MP, à |X| lignes et |X| colonnes définie comme suit :

Pour toute variable Xi, MP[i,i] est la matrice carrée identité à |D(Xi)| lignes et |D(Xi)| colonnes

Pour toutes variables distinctes Xi et Xj, telles que (Xi,Xj) est arc de GP, Mp[i,j] est l’étiquette de l’arc (Xi,Xj) et Mp[j,i] est l’inverse de Mp[i,j]

Pour toutes les autres paires (Xi,Xj) de variables : Mp[i,j] est la matrice universelle à |D(Xi)| lignes et |D(Xj)| colonnes Mp[j,i] est la matrice universelle à |D(Xj)| lignes et |D(Xi)| colonnes

05/01/2011Master2SII->Programmation

Par Contraintes 26

Page 27: Programmation par contraintes

CHAPITRE IICSP binaires

Sous-CSP d’un CSP binaire Soit P=(X,D,C) un CSP binaire discret et X’ un sous-

ensemble de X Le sous-CSP de P sur les variables appartenant à X’

est le CSP (X’,D’,C’) défini comme suit : D’={D(Xi) : XiX’} C’ est l’ensemble des contraintes de C portant

exclusivement sur les variables appartenant à X’ Une instanciation d’un sous-CSP strict de P est une

instanciation partielle de P Une solution d’un sous-CSP strict de P est une solution

partielle de P

05/01/2011Master2SII->Programmation

Par Contraintes 27

Page 28: Programmation par contraintes

CHAPITRE IICSP binaires

Raffinement d’un CSP binaire Soit P=(X,D,C) un CSP binaire discret Un raffinement de P est un CSP P’ de la forme (X,D’,C’)

vérifiant D’(Xi)D(Xi), pour toute variable Xi

C C’ Une instanciation d’un raffinement de P est une

instanciation de P Une solution d’un raffinement de P est une solution de P Un raffinement de P est strict si son ensemble de

solutions est strictement inclus dans l’ensemble des solutions de P

05/01/2011Master2SII->Programmation

Par Contraintes 28

Page 29: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

Résolution d’un CSP binaire Le CSP admet-il des solutions ? Le CSP admet-il des solutions ? Si oui,

en exhiber une Le CSP admet-il des solutions ? Si oui,

les exhiber toutes

05/01/2011Master2SII->Programmation

Par Contraintes 29

Page 30: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

Algorithmes de résolution Algorithmes complets naïfs (recherche systématique d’une

solution) Générer et tester (GET) Simple retour arrière (SRA)

Algorithmes de propagation de contraintes Consistance locale : incomplets en général Consistance de nœud : consistance des sous-CSP de

taille 1 consistance d’arc : consistance des sous-CSP de taille 2 consistance de chemin : consistance des sous-CSP de

taille 3 Complets pour certaines classes de CSP

05/01/2011Master2SII->Programmation

Par Contraintes 30

Page 31: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

Algorithmes de résolution Algorithmes complets intelligents

Quand une variable est instanciée, propager le changement aux variables non encore instanciées

À toutes les contraintes portant sur la variable venant d’être instanciée et les variables non encore instanciées (forward-checking)

à toutes les contraintes dont au moins une des variables sur lesquelles elles portent est non encore instanciée (look-ahead)

Instancier-et-propager

05/01/2011Master2SII->Programmation

Par Contraintes 31

Page 32: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

Algorithmes de résolution d’un CSP binaire Heuristiques

Ordre d’instanciation des variables (statique, dynamique)

Ordre sur les valeurs du domaine de la variable en cours d’instanciation (statique, dynamique)

05/01/2011Master2SII->Programmation

Par Contraintes 32

Page 33: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

Algorithme « générer et tester » (GET)1. Initialement, aucune instanciation n’est marquée2. Considérer une instanciation i=(e1,…,en) non

marquée3. Marquer i4. Si i satisfait toutes les contraintes du CSP :

Retourner i

5. Si toutes les instanciations sont marquées Retourner « échec : le CSP n’admet pas de solution »

6. Aller en 2.

05/01/2011Master2SII->Programmation

Par Contraintes 33

Page 34: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

Algorithme GETfonction GET(A,(X,D,C)) : booléendébutsi toutes les variables de X sont instanciées alors

si A est solution alors retourner VRAI Sinon retourner FAUX finsiSinon

choisir une variable Xi de X qui n’est pas encore instanciée

pour toute valeur Vi du domaine D(Xi) faire

si GET(A ∪ {(Xi,Vi )}, (X,D,C)) alors retourner VRAI finsi finpour

retourner FAUXfinsifin

05/01/2011Master2SII->Programmation

Par Contraintes 34

Page 35: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

Algorithme GETfonction GET(A,(X,D,C)) : Au niveau de la racine de l’arbre de recherche (niveau 0):

A vaut l’ensemble vide : aucune variable n’est instanciée

Au niveau d’un noeud de niveau i1 : A est de cardinal i, et est de la forme {(X1,V1),…,(Xi,Vi)} A représente une instanciation du sous-CSP de (X,D,C) sur les variables X1,

…,Xi

A est une instanciation partielle du CSP (X,D,C)

05/01/2011Master2SII->Programmation

Par Contraintes 35

Page 36: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

Algorithme GET : inconvénient majeur Si inexistence de solution ou unique solution consistant en

la toute dernière instanciation Parcours exhaustif de toutes les 2n instanciations possibles

Algorithme GET : amélioration Instancier pas à pas les variables (selon ordre préétabli) Si l’instanciation de la variable en cours ne permet plus de satisfaire

toutes les contraintes portant exclusivement sur les variables déjà instanciées

Instancier avec une autre valeur du domaine si possible Si toutes les valeurs déjà essayées

Retourner échec si toute première variable Retourner à la variable précédente

Si toute dernière variable retourner “succès” sinon passer à la variable suivante

05/01/2011Master2SII->Programmation

Par Contraintes 36

Page 37: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

Algorithme « simple retour arrière » (SRA)fonction SRA(A,(X,D,C)) : booléendébut

si A n’est pas solution partielle alors retourner FAUX finsisi toutes les variables de X ont été instanciées alors retourner VRAI

finsichoisir une variable Xi non encore instanciée

pour toute valeur Vi du domaine D(Xi) faire

si SRA(A ∪ {(Xi ,Vi )}, (X,D,C)) alors retourner VRAI finsi

finpourretourner FAUX

fin

05/01/2011Master2SII->Programmation

Par Contraintes 37

Page 38: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

Exemple : le problème des quatre reines Echiquier de 16 cases (4x4) 4 lignes L1, L2, L3 et L4 4 colonnes C1, C2, C3 et C4 4 reines R1, R2, R3 et R4 :

La reine R1 se déplace sur la colonne C1 La reine R2 se déplace sur la colonne C2 La reine R3 se déplace sur la colonne C3 La reine R4 se déplace sur la colonne C4

05/01/2011Master2SII->Programmation

Par Contraintes 38

Page 39: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

Exemple : le problème des quatre reines Modélisation à l’aide d’un CSP P=(X,D,C)

X = {X1, X2, X3, X4} D = {D(X1),D(X2),D(X3),D(X4)} avec

D(X1)=D(X2)=D(X3)=D(X4)}={1,2,3,4}

C=CLICDACDD

CLI={XiXj,ij,i∈{1,2,3,4},j∈{1,2,3,4}} CDA={Xi+iXj+j,ij,i∈{1,2,3,4},j∈{1,2,3,4}} CDD={Xi−iXj−j,ij,i∈{1,2,3,4},j∈{1,2,3,4}}

05/01/2011Master2SII->Programmation

Par Contraintes 39

Page 40: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

Résolution du problème des quatre reines algorithme GET

05/01/2011Master2SII->Programmation

Par Contraintes 40

Page 41: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

Résolution du problème des quatre reines algorithme SRA

05/01/2011Master2SII->Programmation

Par Contraintes 41

Page 42: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

05/01/2011Master2SII->Programmation

Par Contraintes 42

Page 43: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

05/01/2011Master2SII->Programmation

Par Contraintes 43

Algorithme SRA : inconvénient majeur Améliore l’algorithme GET

Réduction de l’espace de recherche Mais la détection des conflits reste tardive Solution : dans la construction pas à pas d’une

instanciation consistante Dès qu’une nouvelle variable est instanciée, propager

le changement aux variables non encore instanciées Consistance de nœud Consistance d’arc Consistance de chemin

Page 44: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

05/01/2011Master2SII->Programmation

Par Contraintes 44

Filtrage durant la recherche récursive d’une solution :

Filtrage à priori Prétraitement Avant le début effectif de la recherche Aucune variable n’est encore instanciée Réduction de l’espace de recherche CSP surcontraint et inconsistant : inconsistance

généralement détectée par le prétraitement Filtrage après chaque instanciation d’une nouvelle

variable Instancier puis propager

Page 45: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

05/01/2011Master2SII->Programmation

Par Contraintes 45

Consistance de nœud (node-consistency) Un CSP P=(X,D,C) est consistant de noeud si pour toute variable Xi de

X, et pour toute valeur v de D(Xi), l’instanciation partielle {(Xi,v)} satisfait toutes les contraintes unaires de C portant sur Xi

Principe d’un algorithme de consistance de noeud

filtrage des domaines pour chaque variable Xi

enlever de D(Xi) toute valeur v telle que l’affectation partielle {(Xi,v)} viole les contraintes unaires portant exclusivement sur Xi

Page 46: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

05/01/2011Master2SII->Programmation

Par Contraintes 46

consistance d’arc (arc-consistency) Un CSP P=(X,D,C) est consistant d’arc si pour tout couple (Xi,Xj)

de variables, et pour toute valeur vi de D(Xi) , il existe une valeur vj de D(Xj) telle que l’instanciation partielle {(Xi,vi),(Xj,vj)} satisfait toutes les contraintes binaires de C portant exclusivement sur Xi et Xj

Principe d’un algorithme de consistance d’arc filtrage des domaines

pour chaque variable Xi

enlever de D(Xi) toute valeur vi telle qu’il existe une variable Xj pour laquelle, pour toute valeur vj de D(Xj), l’instanciation partielle {(Xi,vi),(Xj,vj)} viole les contraintes binaires portant exclusivement sur Xi et Xj

Page 47: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

05/01/2011Master2SII->Programmation

Par Contraintes 47

consistance de chemin (path-consistency) Un CSP P=(X,D,C) est consistant de chemin si pour tout triplet (Xi,Xj,Xk) de

variables, et pour toute paire de valeurs (vi,vj) de D(Xi)x D(Xj) , il existe une valeur vk de D(Xk) telle que l’instanciation partielle {(Xi,vi),(Xj,vj),(Xk,vk)} satisfait toutes les contraintes binaires de C portant exclusivement sur Xi, Xj et Xk

Principe d’un algorithme de consistance de chemin filtrage des paires de valeurs permises

pour chaque paire (Xi,Xj) de variables enlever de Mp[i,j) toute paire (vi,vj) de valeurs telle qu’il existe une

variable Xk pour laquelle, pour toute valeur vk de D(Xk) l’instanciation partielle {(Xi,vi),(Xk,vk)} viole les contraintes

binaires portant exclusivement sur Xi et Xk

ou l’instanciation partielle {(Xk,vk),(Xj,vj)} viole les contraintes binaires portant exclusivement sur Xk et Xj

Page 48: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

05/01/2011Master2SII->Programmation

Par Contraintes 48

consistance de chemin (path-consistency) Pour les CSP binaires discrets, la consistance de chemin

est généralement jugée trop coûteuse On se restreint aux consistances de noeud et d’arc Un CSP binaire discret dont les domaines sont des

singletons Si arc-consistant alors consistant

CSP temporels et CSP spatiaux Vérifient les propriétés de consistance de noeud et de

consistance d’arc La consistance de chemin prend toute son importance

Page 49: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

05/01/2011Master2SII->Programmation

Par Contraintes 49

Algorithmes de consistance d’arc AC ou REVISE :

réduit la taille des domaines supprime les valeurs qui violent les contraintes binaires

AC1 :1. appliquer REVISE à tous les arcs sur lesquels il y a une contrainte2. Si aucun domaine n’a été modifié, la procédure prend fin3. Sinon aller à 1 Inconvénient : réapplique REVISE à tous les arcs sur les lesquels

il y a une contrainte : Même aux arcs non modifiés par la passe précédente jusqu’à fermeture

AC3 : ne réapplique REVISE qu’aux arcs modifés

Page 50: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

05/01/2011Master2SII->Programmation

Par Contraintes 50

fonction REVISE((Xi , Xj ),(X,D,C)) : booléendébutDELETE ← FAUXpour tous les Vi de D(Xi) faire

si il n’y a pas de Vj dans D(Xj) telle que {(Xi,vi),(Xj,vj)} satisfait les contraintes binaires entre Xi et Xj alors

supprimer Vi de D(Xi)

DELETE ← VRAIfinsi

fin pourretourner DELETEfin

Page 51: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

05/01/2011Master2SII->Programmation

Par Contraintes 51

fonction AC1((X,D,C))débutQ ← {(Xi,Xj) : il existe une contrainte entre Xi et Xj }

répéterR ← FALSEpour tous les (Xi,Xj) de Q faire

R ← (R ou REVISE((Xi,Xj),(X,D,C)))

fin pourjusqu’à non Rretourner (X,D,C)fin

Page 52: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

05/01/2011Master2SII->Programmation

Par Contraintes 52

fonction AC3((X,D,C))débutQ ← {(Xi,Xj ) : il existe une contrainte entre Xi et Xj }

tantque Q fairePrendre une paire (Xi,Xj) de variables de Qsupprimer la paire de Q : Q ← Q\{(Xi,Xj)}

si REVISE((Xi,Xj),(X,D,C)) alors

Q←Q∪{(Xk,Xi) : il existe une contrainte entre Xk et Xi et XkXi et XkXj}

finsifin-tantqueretourner (X,D,C)

fin

Page 53: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

05/01/2011Master2SII->Programmation

Par Contraintes 53

Forward checking et Look-ahead Combinaison du filtrage et du retour-arrière :

filtrage durant la résolution : Quand une variable est instanciée, propager le changement aux variables non encore instanciées

Forward checking : Propager le changement à toutes les contraintes portant sur la

variable venant d’être instanciée et les variables non encore instanciées

Look ahead : Propager le changement à toutes les contraintes dont au moins

une des variables sur lesquelles elles portent n’est pas encore instanciée

Page 54: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

05/01/2011Master2SII->Programmation

Par Contraintes 54

fonction FC(A,(X,D,C)) : booléendébutsi toutes les variables de X sont instanciées alors retourner VRAIsinon

choisir une variable Xi de X qui n’est pas encore instanciée

pour toute valeur Vi de D(Xi) faire

non_instanciees={XjX : Xj non encore instanciée}

domaine_vide=fauxD’=D //D’(Xj)=D(Xj), pour toute variable Xj

tantque (non_instanciees) et (domaine_vide=faux) faireconsidérer une variable Xj de l’ensemble non_instanciees

non_instanciees=non_instanciees\{Xj}

D’(Xj)={VjD(Xj)|A{(Xi,Vi),(Xj,Vj)} est consistante }

si D’(Xj) vide alors domaine_vide=vrai finsi

fin-tantquesi (domaine_vide=faux) alors si FC(A ∪{(Xi,Vi)},(X,D’,C)) alors retourner VRAI finsi finsi

fin-pourretourner FAUX //l’instanciation partielle A ne peut pas être étendue à la variable X i

finsifin

Page 55: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

05/01/2011Master2SII->Programmation

Par Contraintes 55

Page 56: Programmation par contraintes

CHAPITRE IIIRésolution d’un CSP binaire

05/01/2011Master2SII->Programmation

Par Contraintes 56

fonction Look_Ahead(A,(X,D,C)) : booléendébutsi toutes les variables de X sont instanciées alors retourner VRAIsinon

choisir une variable Xi de X qui n’est pas encore instanciée

pour toute valeur Vi de D(Xi) faire

D’(Xi)={Vi}

D’=(D\{D(Xi)}){D’(Xi)}

AC3(X,D’,C)si (aucun domaine de D’ n’est vide) alors

si Look_Ahead(A ∪{(Xi,Vi)},(X,D’,C)) alors retourner VRAI finsi finsifin-pourretourner FAUX //l’instanciation partielle A ne peut pas être étendue à la variable Xi

finsifin

Page 57: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 57

CSP binaires continus Le domaine de chacune des variables est

continu L’ensemble continu des points du temps

modélisé par IR L’ensemble continu des points du plan modélisé

par IR2

Le sous-ensemble de IR2 constituant les intervalles de temps : toutes les paires (d,f) de IR2 vérifiant d<f

Page 58: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 58

CSP binaires continus CSP quantitatifs

TCSP : Temporal Constraint Satisfaction Problems

CSP qualitatifs « make only as many distinctions as

necessary » L’algèbre des points L’algèbre des intervalles L’algèbre des directions cardinales

Page 59: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 59

CSP binaires continus TCSP : Temporal Constraint Satisfaction

ProblemsPaire P=(X,C) :

X ensemble fini de variables : X={X1, …,Xn} C ensemble fini de contraintes sur les variables

de P Le domaine de chacune des variables est

l’ensemble IR des réels ou l’ensemble Q des rationnels

Le domaine commun des variables sera noté D(P)

Page 60: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 60

CSP binaires continus TCSP P=(X,C) : Contraintes

Contraintes binaires (Xj-Xi)Cij, avec CijD(P)

Contraintes unaires Xi Ci, CiD(P)

Page 61: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 61

CSP binaires continus TCSP P=(X,C) : ajout d’une variable X0

origine du monde X={X0,X1, …,Xn} Contraintes unaires transformées en

contraintes binaires Xi Ci devient (Xi-X0)C0i

C0i =Ci

Page 62: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 62

Représentation graphique d’un TCSP La représentation graphique d’un TCSP P=(X,C)

est un graphe orienté étiqueté GP=(X,E,l) défini comme suit :

L’ensemble des sommets de GP est l’ensemble X des variables de P Pour toutes variables Xi et Xj, si P admet une contrainte portant sur Xi

et Xj, alors GP contient un et un seul des deux arcs (Xi,Xj) et (Xj,Xi) Pour toutes variables Xi et Xj, si P n’admet aucune contrainte portant

sur Xi et Xj, alors GP ne contient ni l’arc (Xi,Xj) ni l’arc (Xj,Xi) Pour tout arc (Xi,Xj) de GP, l’étiquette l(Xi,Xj) de (Xi,Xj) est tirée de la

contrainte (Xj-Xi)Cij de P portant sur Xi et Xj : l(Xi,Xj)= Cij

Page 63: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 63

Représentation matricielle d’un TCSP La représentation matricielle d’un TCSP P=(X,C) est

une matrice carrée notée MP, à |X| lignes et |X| colonnes définie comme suit :

Pour toute variable Xi, MP[i,i]={0} Pour toutes variables distinctes Xi et Xj, telles que (Xi,Xj)

est arc de GP : Mp[i,j] est l’étiquette de l’arc (Xi,Xj) Mp[j,i] est l’inverse de Mp[i,j]

Pour toutes les autres paires (Xi,Xj) de variables : Mp[i,j]=Mp[j,i]=D(P)

Page 64: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 64

CSP binaires continus TCSP P=(X,C)

Inverse d’une contrainte Intersection de deux contraintes Composition de deux contraintes

Page 65: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 65

CSP binaires continus TCSP P=(X,C)

Nœud-consistant Arc-consistant

Page 66: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 66

CSP binaires continus TCSP P=(X,C)

Consistance de chemin : répéter jusqu’à fermeture Pour tout triplet (Xi,Xj,Xk) de variables ne vérifiant pas

CijCikCkj

Cij=CijCikCkj

Page 67: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 67

CSP binaires continus TCSP P=(X,C)

STP : Simple Temporal Problem Toutes les contraintes sont convexes

Page 68: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 68

CSP binaires continus TCSP P=(X,C) : résolution

Recherche d’un raffinement convexe chemin-consistant Ordre d’instanciation sur les paires de variables Une paire de variables est instanciée avec les blocs

convexes constituant son étiquette A chaque fois qu’une nouvelle paire est instanciée

Filtrage : consistance de chemin Si inconsistance détectée : échec (retour arrière)

Si instanciation avec succès de toutes les paires de variables

raffinement convexe chemin-consistant (consistant)

Page 69: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 69

Algèbre des points Objets et relations

Objets : les points de la droite réelle (temps) Relations qualitatives sur des paires de points :

Relations atomiques : < = > Relations générales (disjonctives) :

Sous-ensembles de {<,=,>}

Page 70: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 70

Algèbre des pointsRelation Notation

{}

{<}

{=} =

{>}

{<,=}

{<,>}

{>,=}

{<,=,>} ?

Page 71: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 71

Algèbre des points CSP qualitatif de points

Paire P=(X,C) : X ensemble fini de variables : X={X1, …,Xn} C ensemble fini de contraintes binaires sur des

paires de variables de P Le domaine de chacune des variables est

l’ensemble IR des réels ou l’ensemble Q des rationnels

Le domaine commun des variables sera noté D(P)

Page 72: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 72

Algèbre des points CSP qualitatif de points P=(X,C) :

Contraintes R(Xi,Xj), R étant une des huit relations de

l’algèbre des points

Page 73: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 73

Algèbre des points CSP qualitatif de points P=(X,C)

Représentation graphique Représentation matricielle

Page 74: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 74

Algèbre des points Inverse

Relation atomique r Inverse r-1 de r

< >

= =

> <

Page 75: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 75

Algèbre des points Intersection

< = > ?

< < < < <

= = = = =

> > > > >

< = < =

< > < >

= > = >

? < = > ?

Page 76: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 76

Algèbre des points Table de composition

< = >

< < < ?

= < = >

> ? > >

Page 77: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 77

Algèbre des points CSP qualitatif de points P=(X,C)

Nœud-consistant Arc-consistant

Page 78: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 78

Algèbre des points CSP qualitatif de points P=(X,C)

Consistance de chemin : répéter jusqu’à fermeture Pour tout triplet (Xi,Xj,Xk) de variables ne vérifiant pas

CijCikCkj

Cij=CijCikCkj

Page 79: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 79

Algèbre des points CSP qualitatif de points P=(X,C)

L’algèbre des points est un formalisme polynomial La consistance de chemin, qui est de complexité cubique,

décide la consistance d’un CSP qualitatif de points : Si la consistance de chemin ne rencontre pas la relation alors le CSP en

entrée est consistant

Il y a même mieux pour l’algèbre des points : Il y a un algorithme quadratique pour le problème de consistance d’un CSP

qualitatif de points

Page 80: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 80

Algèbre des intervalles Objets et relations

Objets : les intervalles de la droite réelle (temps) Relations qualitatives sur des paires d’intervalles :

Relations atomiques : 13 Relations générales (disjonctives) :

Sous-ensembles de relations atomiques : 213=8192

Page 81: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 81

Algèbre des intervalles Les 13 relations atomiques

Symbole Signification Traduction

< before avant

m meets rencontre

o overlaps chevauche

fi finished-by terminé-par

di contains contient

s starts commence

eq equals égale

si started-by commencé-par

d during durant

f finishes termine

oi overlapped-by chevauché-par

mi met-by rencontré-par

> after après

Page 82: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 82

Algèbre des intervalles CSP qualitatif d’intervalles

Paire P=(X,C) : X ensemble fini de variables : X={X1, …,Xn} C ensemble fini de contraintes binaires sur des

paires de variables de P Le domaine de chacune des variables est

l’ensemble {(d,f)IR2 : d<f} ou l’ensemble {(d,f)Q2 : d<f}

Le domaine commun des variables sera noté D(P)

Page 83: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 83

Algèbre des intervallesCSP qualitatif d’intervalles P=(X,C) :

Contraintes R(Xi,Xj), R étant une des 8192 relations de

l’algèbre des intervalles

Page 84: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 84

Algèbre des intervalles CSP qualitatif d’intervalles P=(X,C)

Représentation graphique Représentation matricielle

Page 85: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 85

Algèbre des intervalles Inverse

r r-1 r r-1

< > > <

m mi mi m

o oi oi o

s si si s

d di di d

f fi fi f

eq eq

Page 86: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 86

Algèbre des intervalles Intersection

R1R2={r : rR1 et rR2} Intersection ensembliste

Page 87: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 87

Algèbre des intervalles Composition

La composition faible de deux relations R1 et R2 est la plus petite relation R telle que pour tous intervalles I, J et K de la droite réelle :

Si R1(I,K) et R2(K,J) alors R(I,J)

R coïncide avec la composition exacte R1R2 si pour tous intervalles I et J tels que R(I,J), il existe un intervalle K tel que R1(I,K) et R2(K,J)

Page 88: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 88

Algèbre des intervalles Composition

Composition faible = composition exacte

R1R2=r1r2

r1R1,r2R2

Page 89: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 89

Algèbre des intervalles Table de composition

Table 13x13 dont les lignes et les colonnes sont indicées par les relations atomiques

L’élément (r1,r2) donne la composition r1r2 de r1 et r2

Page 90: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 90

Algèbre des intervalles Table de composition

< … oi … > eq

< < … {d,s,o,m,<}

… ? <

… … … … … … …

s < … {oi,f,d} … > s

… … … … … … …

> ? … > … > >

eq < … … > eq

Page 91: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 91

Algèbre des intervalles CSP qualitatif d’intervalles P=(X,C)

Nœud-consistant Arc-consistant

Page 92: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 92

Algèbre des intervalles CSP qualitatif d’intervalles P=(X,C)

Consistance de chemin : répéter jusqu’à fermeture Pour tout triplet (Xi,Xj,Xk) de variables ne vérifiant pas

CijCikCkj

Cij=CijCikCkj

Page 93: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 93

Algèbre des intervalles CSP qualitatif d’intervalles P=(X,C)

L’algèbre des intervalles est un formalisme NP-complet La consistance de chemin, qui est de complexité cubique,

décide la consistance d’un CSP qualitatif atomique d’intervalles :

Si la consistance de chemin ne rencontre pas la relation alors le CSP en entrée est consistant

Pour résoudre un CSP général d’intervalles : Utiliser la consistance de chemin comme algorithme de

validation Choix (non-déterminisme) d’une relation atomique sur chacun

des arcs disjonctifs Appliquer la consistance de chemin au CSP atomique résultant

Page 94: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 94

Algèbre des directions cardinales Objets et relations

Objets : les points du plan (espace 2-dimensionnel) Relations qualitatives sur des paires de points :

Relations atomiques : 9 Relations générales (disjonctives) :

Sous-ensembles de relations atomiques : 29=512

Page 95: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 95

Algèbre des directions cardinales Les 9 relations atomiques

Symbole Signification Traduction Algèbre des points

SW South-West sud-ouest (<,<)

W West ouest (<,=)

NW North-West nord-ouest (<,>)

S South sud (=,<)

EQ Equal Egal (=,=)

N North nord (=,>)

SE South-East sud-est (>,<)

E East est (>,=)

NE North-East nord-est (>,>)

Page 96: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 96

Algèbre des directions cardinales CSP qualitatif de directions cardinales

Paire P=(X,C) : X ensemble fini de variables : X={X1, …,Xn} C ensemble fini de contraintes binaires sur des

paires de variables de P Le domaine de chacune des variables est

l’ensemble IR2 ou l’ensemble Q2

Le domaine commun des variables sera noté D(P)

Page 97: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 97

Algèbre des directions cardinales

CSP qualitatif de directions cardinales P=(X,C) : Contraintes

R(Xi,Xj), R étant une des 512 relations de l’algèbre des directions cardinales

Page 98: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 98

Algèbre des directions cardinales CSP qualitatif de directions cardinales

P=(X,C) Représentation graphique Représentation matricielle

Page 99: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 99

Algèbre des directions cardinales InverseRelation atomique r Inverse r-1 de r

SW NE

W E

NW SE

S N

EQ EQ

N S

SE NW

E W

NE SW

Page 100: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 100

Algèbre des directions cardinales Intersection

R1R2={r : rR1 et rR2} Intersection ensembliste

Page 101: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 101

Algèbre des directions cardinales Table de composition

SW … N … NE EQ

SW SW … {SW,W,NW}

… ? SW

… … … … … … …

S SW … {S,EQ,N} … {SW,W,NW}

S

… … … … … … …

NE ? … NE … NE NE

EQ SW … N … NE EQ

Page 102: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 102

Algèbre des directions cardinales CSP qualitatif de directions cardinales

P=(X,C) Nœud-consistant Arc-consistant

Page 103: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 103

Algèbre des directions cardinales CSP qualitatif de directions cardinales

P=(X,C) Consistance de chemin : répéter jusqu’à fermeture

Pour tout triplet (Xi,Xj,Xk) de variables ne vérifiant pas CijCikCkj

Cij=CijCikCkj

Page 104: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 104

Algèbre des directions cardinales CSP qualitatif de directions cardinales P=(X,C)

L’algèbre des directions cardinales est un formalisme NP-complet

La consistance de chemin, qui est de complexité cubique, décide la consistance d’un CSP qualitatif atomique de directions cardinales :

Si la consistance de chemin ne rencontre pas la relation alors le CSP en entrée est consistant

Pour résoudre un CSP général de directions cardinales : Utiliser la consistance de chemin comme algorithme de

validation Choix (non-déterminisme) d’une relation atomique sur chacun

des arcs disjonctifs Appliquer la consistance de chemin au CSP atomique résultant

Page 105: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 105

Algorithmes de consistance de chemin REVISE :

réduit les éléments de la représentation matricielle (les étiquettes des arcs de la représentation matricielle)

supprime des paires de valeurs permises par une contrainte binaire, et qui n’ont pas de correspondant dans au moins une troisième variable

PC1 :1. appliquer REVISE à tous les triplets de variables2. Si aucune étiquette n’a été modifiée, la procédure prend fin3. Sinon aller à 1 Inconvénient : réapplique REVISE à tous les triplets de variables :

jusqu’à fermeture PC3 :

ne réapplique REVISE qu’aux triplets présentant une étiquette modifiée

Page 106: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 106

fonction REVISE((Xi,Xk,Xj),(X,D,C)) : booléen

débuttemp=Cik

Cik=CikCijCjk

si temp=Cik alors retourner FAUX

sinon{Cki=(Cik)-1

retourner VRAI}

finsifin

Page 107: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 107

fonction PC1((X,D,C))débutQ ← {(Xi,Xk,Xj) : i<k et j{i,k}}

répéterR ← FALSEpour tous les (Xi,Xk,Xj) de Q faire

R ← (R ou REVISE((Xi,Xk,Xj),(X,D,C)))

fin pourjusqu’à non Rretourner (X,D,C)fin

Page 108: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 108

fonction PC3((X,C))débutQ ← {(Xi,Xj) : (i<j) et il existe une contrainte entre Xi et Xj}

tantque Q fairePrendre une paire (Xi,Xj) de variables de Qsupprimer la paire de Q : Q ← Q\{(Xi,Xj)}

pour toute variable Xk différente de Xi et de Xj faire

si REVISE((Xi,Xk,Xj),(X,C)) alors Q←Q∪{(Xk,Xi)}

finsisi REVISE((Xj,Xk,Xi),(X,C)) alors Q←Q∪{(Xk,Xi)}

finsifait

fin-tantqueretourner (X,C)fin

Page 109: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 109

fonction Look_Ahead((X,C)) : booléendébutPC3(X,C)si (C contient des éléments vides) alors retourner FAUX finsisi toutes les paires de variables sont instanciées alors retourner VRAISinon

choisir une paire (Xi,Xj) de variables qui n’est pas encore instanciée

pour tout élément r de C[i,j] faire //r bloc convexe si TCSPC’=C //r relation atomique si CSP qualitatifC’[i,j]=rC’[j,i]=r-1

Look_Ahead((X,C’)) fin-pour

finsifin

Page 110: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 110

Exemple 1 : TCSP Le problème de fragmentation Remède : consistance de chemin faible

XjXi

Xk[-2,-1][5,6] [-4,-3][10,15]

[-7,-1][1,20]

[-6,-4][1,3][8,14][15,20]

Page 111: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 111

Exemple 2 : CSP qualitatif de directions cardinales

Béjaia est à l’est d’Alger Oran est à l’ouest d’Alger Le bâteau est au nord-est d’Alger

satellite 1 à l’instant t Le bâteau est au nord ou au nord-est d’Oran

satellite 2 au même instant t

Page 112: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 112

Exemple 3 : CSP qualitatif de directions cardinales

Béjaia est à l’est d’Alger Oran est à l’ouest d’Alger Le bâteau est au au nord ou au nord-est

d’Alger satellite 1 à l’instant t

Le bâteau est au nord-est d’Oran satellite 2 au même instant t

Page 113: Programmation par contraintes

CHAPITRE IVCSP binaires continus

05/01/2011Master2SII->Programmation

Par Contraintes 113

Exemple 4 : CSP qualitatif de directions cardinales

Béjaia est à l’est d’Alger Oran est à l’ouest d’Alger Le bâteau est au nord-ouest d’Alger

satellite 1 à l’instant t Le bâteau est au nord-est de Béjaia

satellite 2 au même instant t

Page 114: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 114

Les termes Les objets manipulés par un programme

(données) Les variables Les termes élémentaires (termes atomiques) Les termes composés

Page 115: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 115

Les variables Chaîne alphanumérique commençant par

une majuscule (Var, X, Var_longue_2) ou par un souligné (_objet, _100)  

La variable anonyme est notée "_"

Page 116: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 116

Les termes élémentaires (termes atomiques)

Les nombres entiers ou flottants

Les identificateurs (aussi appelés atomes) chaîne alphanumérique commençant par une

minuscule Exemples : alger bureau226 bab_ezzouar

Les chaînes de caractères entre guillemets Exemples : "\#\{@"  "alger"  "2010’’

Page 117: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 117

Les termes composés : foncteur(t1,…,tn) foncteur : chaine alphanumérique

commençant par une minuscule t1, …,tn : termes n : arité du terme Exemples

adresse(18,"rue de la dignité",Ville) cons(a,cons(X,nil))

Page 118: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 118

Les relations ou atomes logiques symbole_de_prédicat(t1, ..., tn ) symbole_de_prédicat : chaîne

alphanumérique commençant par une minuscule

t1, …, tn : termes Exemples

pere(rachid,ines) habite(X,adresse(1,"rue de la dignité",alger))

Page 119: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 119

Les clauses Une clause

affirmation inconditionnelle (fait) affirmation conditionnelle (règle)

Page 120: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 120

Les clauses fait : atome logique A

la relation définie par A est vraie (sans condition)

Exemple pere(rachid,ines) la relation "rachid est le père de ines" est

vraie (sans condition)

Page 121: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 121

Les clauses règle : A0 :- A1,…,An.

A0,A1,…,An : atomes logiques La relation A0 est vraie si les relations

A1,…,An sont vraies A0 : tête de clause A1,…,An : corps de clause

Page 122: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 122

Les clauses  Une variable apparaissant dans la tête d'une

règle (et éventuellement dans son corps) est quantifiée universellement

Une variable apparaissant dans le corps d'une clause mais pas dans sa tête est quantifiée existentiellement

Page 123: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 123

Les clauses : exemple meme_pere(X,Y) :- pere(P,X), pere(P,Y). pour tout X et pour tout Y

meme_pere(X,Y) est vrai s'il existe un P tel que pere(P,X) et pere(P,Y) soient vrais

Page 124: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 124

Un programme prolog  Suite de clauses regroupées en paquets L’ordre dans lequel sont définis les paquets n’est pas significatif Paquet :

Suite de clauses ayant le même atome de tête L’arité de l’atome de tête (d’un même paquet) est la même au

niveau de toutes les clauses du paquet Un paquet définit un prédicat (dont le nom est l’atome de tête du

paquet) Un paquet définit une disjonction de clauses L’ordre des clauses dans un paquet est donc important, voire crucial

L’efficacité de la résolution en dépend Un programme prolog définit une conjonction de paquets

Page 125: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 125

Un programme prolog : exemplepersonne(X) :- homme(X).personne(X) :- femme(X).

Un paquet à deux clauses pour tout X

personne(X) est vrai si homme(X) est vrai ou femme(X) est vrai

Page 126: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 126

Exécution d’un programme prolog Exécuter un programme prolog revient à poser

une question à l’interprète PROLOG Question (également appelée but ou activant)

Suite d’atomes logiques séparés par des virgules Réponse de l’interprète PROLOG à une question

yes si la question est une conséquence logique du programme

no sinon (si la question n’est pas une conséquence logique du programme)

Page 127: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 127

Exécution d’un programme prolog une question peut inclure des variables, qui

sont alors quantifiées existentiellement La réponse de Prolog à une telle question est

l'ensemble des valeurs des variables pour lesquelles la question est une conséquence logique du programme

Toutes les instanciations satisfaisant la formule"programme implication-logique question"

Page 128: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 128

Exécution d’un programme prolog?- pere(rachid,X), pere(X,Y).

Existe-t-il un X et un Y tels que pere(rachid,X) et pere(X,Y) soient vrais

Réponse de prolog : enfants et petits-enfants de rachid si

rachid est grand-père

Page 129: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 129

Substitution Fonction s de l’ensemble des variables dans

l’ensemble des termes s={XY,Zf(a,Y)} est la substitution

remplaçant X par Y et Z par f(a,Y), et laisse inchangées les autres variables

Une substitution peut être appliquée à un atome :

s(p(X,f(Y,Z)))=p(s(X),f(s(Y),s(Z))=P(Y,f(Y,f(a,Y)))

Page 130: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 130

Instance Une instance d’un atome logique A est

l’atome s(A) obtenu par application d’une substitution s à A

L’atome pere(rachid, ines) est une instance de l’atome pere(rachid,X) :

Appliquer, par exemple, la substituion s={Xines}

Page 131: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 131

Unificateur Un unificateur de deux atomes logiques A1

et A2 est une substitution s telle que s(A1)=s(A2)

s={Xa,Zf(a,Y)} est un unificateur des deux atomes A1=p(X,f(X,Y)) et A2=p(a,Z)

s(A1)=s(A2)=p(a,f(a,Y))

Page 132: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 132

Unificateur plus général Un unificateur s de deux atomes logiques

A1 et A2 est dit unificateur le plus général (upg) si pour tout autre unificateur s’, il existe une substitution s’’ telle que s’=s’’(s)

s={XY} est un upg des deux atomes p(X,b) et p(Y,b)

s’={Xa,Ya} est un unificateur de p(X,b) et p(Y,b) mais pas un upg

Page 133: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 133

Algorithme d’unification de Robinson Entrée : deux atomes A1 et A2 Sortie :

un upg de A1 et A2 si A1 et A2 sont unifiables Échec sinon

Page 134: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 134

Dénotation d’un programme Prolog La dénotation d’un programme Prolog P est

l’ensemble de tous les atomes logiques A qui sont des conséquences logiques de P

Lorsqu’on exécute un programme Prolog P en posant une question (ou but) Q :

La réponse de Prolog est l’ensemble des instances de la question Q qui font partie de la dénotation de P

Page 135: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 135

Dénotation d’un programme Prolog La dénotation d’un programme Prolog P

peut être calculée par une approche ascendante (en chaînage avant)

Partir des faits Appliquer les règles pour déduire de nouveaux

faits, jusqu’à fermeture

Page 136: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 136

Dénotation d’un programme Prologparent(rachid,ines).parent(ines,mohamed).parent(ali,younes).parent(younes,said).

homme(rachid).homme(ali).

pere(X,Y):-parent(X,Y),homme(X).

gdpere(X,Y):-pere(X,Z),parent(Z,Y).

Page 137: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 137

Dénotation d’un programme Prolog L’ensemble des faits de P (relations vraies sans

condition) : E0={parent(rachid,ines),

parent(ines,mohamed),parent(ali,younes),parent(younes,said),homme(rachid),homme(ali)}

On applique les règles de P à E0 pour obtenir : E1={pere(rachid,ines),

pere(ali,younes)}

Page 138: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 138

Dénotation d’un programme Prolog On applique les règles de P à E0E1 pour obtenir :

E2={gdpere(rachid,mohamed),

gdpere(ali,said)} L’application des règles de P à E0E1E2 ne permet pas de

déduire de nouveaux faits La dénotation de P est donc

E0E1E2 ={parent(rachid,ines),parent(ines,mohamed),

parent(ali,younes),parent(younes,said),homme(rachid),homme(ali),pere(rachid,ines),pere(ali,younes), gdpere(rachid,mohamed),

gdpere(ali,said)}

Page 139: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 139

Dénotation d’un programme Prolog La dénotation d’un programme peut être infinie :

plus(0,X,X).plus(succ(X),Y,Z):-plus(X,Y,Z).

E={plus(0,X,X),plus(succ(0),X,succ(X)),plus(succ(succ(0)),X,succ(succ(X))),plus(succ(succ(succ(0))),X,succ(succ(succ(X)))), …}

Page 140: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 140

Dénotation d’un programme Prolog Sémantique logique

Page 141: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 141

Sémantique opérationnelle L’ensemble de toutes les conséquences

logiques d’un programme (dénotation) ne peut donc pas toujours être calculé

MAIS on peut montrer si une but (question) est une conséquence logique d’un programme

But : suite d’atomes logiques (conjonction d’atomes)

Page 142: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 142

Sémantique opérationnelle Pour prouver si un but B=A1,…,An est une conséquence

logique d’un programme P : Approche descendante (en chaînage arrière) Commencer par prouver que A1 est une conséquence

logique de P Chercher une clause règle de P dont l’atome de tête

s’unifie avec A1C0:-C1,…,Cm telle que upg (A1,C0)=s

Le nouveau but à prouver estBut=s(C1),…,s(Cm),s(A2),…,s(An)

Réitérer le processus jusqu’à ce que le but à prouver devienne vide

Page 143: Programmation par contraintes

CHAPITRE IVProgrammation logique

05/01/2011Master2SII->Programmation

Par Contraintes 143

procedure prouver(But: liste d'atomes logiques )si But = [] alors

/* le but initial est prouvé *//* afficher les valeurs des variables du but initial */

sinon soit But = [A1, A2, .., An]pour toute clause (C0 :- C1, C2, ..,Cm) du programme:

            (où les variables ont été renommées)            s=upg(A1 ,C0)

si s != echec alorsprouver([s(C1), s(C2), .. s(Cm), s(A2), .. s(An)])

finsifinpour

finsi

Page 144: Programmation par contraintes

CHAPITRE IVProgrammation logique par

contraintes

05/01/2011Master2SII->Programmation

Par Contraintes 144

Programmation logique Programmation logique par contraintes :

Fixer une structure d’interprétation S représentant l’univers du discours

Distinguer dans un programme les deux choses suivantes :

Le langage de contraintes défini sur S, supposé décidable Le langage des prédicats défini par des formules logiques

Les formules logiques permettant de définir des prédicats sont restreintes aux clauses de Horn de la forme :

A:-c1,…,cm,A1,…,An. CLP(S)