De nombreux probl�mes r�els peuvent �tre repr�sent�s sous la forme d'un probl�me de satisfaction de contraintes (CSP). En particulier, le formalisme CSP permet d'exprimer des probl�mes d'ordonnancement, de vision, de concep�tion, de configuration, etc. Il vise � repr�senter sous forme de contraintes les propri�t�s et les relations qui existent entre les objets manipul�s. Elles traduisent l'autorisation ou l'interdiction d'une combinaison de valeurs. Dans le formalisme CSP, la recherche d'une solution requiert de satisfaire toutes les contraintes. Dans la mesure o� certaines contraintes doivent �tre obligatoirement satisfaites, on les qualifie g�n�ralement de contraintes "dures". Cependant, pour certains probl�mes r�els, certaines contraintes dites "molles" ne traduisent, dans la r�alit�, qu'une pr�f�rence, une possibilit�, etc. Leur satisfaction n'est donc pas forc�ment n�cessaire. Repr�senter ces contraintes par des contraintes dures rend souvent les CSP correspondants inconsistants. Afin de pouvoir exprimer de telles contraintes, plusieurs extensions des CSP ont �t� propos�es parmi lesquelles les CSP valu�s (VCSP) (Schiex, 1995, 1997) (Jegou, 2003). Le formalisme VCSP augmente le pouvoir d'expression du formalisme CSP en introduisant une graduation dans la violation des contraintes. Une valeur (appel�e valuation) est associ�e � chaque contrainte. La valuation d'une contrainte traduit l'importance de la violation de cette contrainte. Autrement dit, le cadre VCSP autorise la violation de certaines contraintes, les contraintes �tant soit dures, soit molles. L'objectif est alors de trouver une affectation de toutes les variables qui optimise un crit�re donn� et portant sur la satisfaction des contraintes. En d'autres termes, une solu�tion du probl�me est une affectation qui peut �ventuellement violer certaines contraintes et dont l'importance des violations est minimale suivant un crit�re et un ordre donn�s. La m�thode de base pour la r�solution de VCSP est l'algorithme Branch and Bound (s�paration et �valuation). Bien s�r, de nombreuses am�liorations ont �t� propos�es, no�tamment � partir du cadre CSP. N�anmoins, � l'heure actuelle, les meilleurs r�sultats semblent �tre fournis par des m�thodes comme la m�thode des poup�es russes (not�e RDS pour Russian Doll Search (Verfaillie, 1996) ou par des m�thodes issues de la programmation dynamique (Koster, 1999). Il s'agit de m�thodes qui divisent le probl�me en plusieurs sous-probl�mes et qui exploitent les informations qu'elles produisent durant la r�solution de chacun de ces sous-probl�mes.

Les DisCSP consistent � repr�senter les syst�mes � contraintes en agents, entit�s ind�pendantes et communicantes capables d?agir sur elles-m�mes et sur l?environnement (Yokoo, 1990). Plusieurs travaux envisagent la distribution du probl�me de satisfaction de contraintes. Ils sont motiv�s par l'existence de probl�mes naturel�lement distribu�s, pour lesquels il est impossible ou peu souhaitable de rassembler toutes les donn�es du probl�me sur un site, pour le r�soudre par un algorithme centralis�. Les raisons les plus imm�diates sont le temps de communication requis ou le sur-co�t de traduction de tous les sous-probl�mes dans un format commun. Mais donner � un agent unique toutes les donn�es du probl�me peut aussi �tre exclu pour des raisons de s�curit� ou de confidentialit�. Les algorithmes complets pour la r�solution de CSP distribu�s doivent beaucoup � Yokoo et � ses collaborateurs, pionniers du domaine avec asynchronous backtracking (ABT) et asynchronous weak-commitment search (WCS) (Yokoo, 1992, 1998). Ces algorithmes imposent un ordre total entre les agents, ordre statique pour ABT, dynamique pour WCS. Distributed Intelligent Backtracking (DIBT) (Hamadi, 1999) propose une approche diff�rente, sans �change de nogoods. Malheureusement, DIBT n'est pas complet (Bessi�re, 2001). Plus r�cemment, Optimal Distributed Intelligent Backtracking (ODIBT) est pr�sent� dans (Belaissaoui, 2002). ODIBT est une version compl�te et optimale en envois de messages de DIBT.

Dans cet article, nous proposons une nouvelle m�thode pour le mod�le DisVCSP. Notre but en l'�crivant �tait de garder le meilleur de Distributed Dynamic Backtracking (Bessi�re, 2001), pour obtenir un algorithme aussi asynchrone que possible, qui minimise l'envoi de messages entre agents ind�pendants tout en restant complet. Notre algorithme a aussi une parent� �vidente avec Valued Dynamic Backtracking (Dago, 1997). Nous avons donc gard� les nogoods de ce dernier.

Un CSP est d�fini par la donn�e (X, D, C). X est un ensemble {x₁, .... x_n} de n variables, chaque variable x_i prenant ses valeurs dans un domaine fini D_xj issu de D. Ces variables sont soumises � des contraintes issues de C. Chaque contrainte c est d�finie comme un en�semble {x_c1, ...., x_ck} de variables telle que c repr�sente l'ensemble des tuples autoris�s sur d_xcl x ... x d_xck . Etant donn� Y X tel que Y={x₁,....x_k}, une instanciation des variables de Y est un tuple B= (v₁, .... v_k) de d_x1 x ... x d_xk. Nous appelons une affectation partielle un sous-ensemble de variables affect�es. Lorsque toutes les variables sont affect�es, l?affectation est dite compl�te. Deux affectations sont compatibles si les variables communes sont affect�es aux m�mes valeurs. A la difference du cadre CSP, les contraintes dans le cadre VCSP peuvent �tre soit dures soit molles. R�soudre un probl�me VCSP revient alors � rechercher une affectation qui optimise une fonction portant sur la satisfaction des contraintes. Autrement dit, une solution du probl�me est une affectation qui peut �ventuellement violer certaines contraintes et dont l'importance des violations est minimale suivant un crit�re et un ordre donn�s. Pour quantifier l'importance d'une violation, une valeur (appel�e valuation) est associ�e � chaque contrainte. Lorsque plusieurs contraintes sont viol�es simultan�ment, les valuations correspondantes doivent �tre agr�g�es pour d�terminer l'importance de la violation de l'ensemble de ces contraintes. Dans ce but, on se dote d'une structure de valuation�:

D�finition 1 (Schiex, 1995)�: Une structure de valuation est un triplet (E, ?, ) avec un ensemble E de valuations totalement ordonn� par ?, muni d'un �l�ment minimum (not� ?), d'un �l�ment maximum (not� T) et d'une loi de composition interne (not�e ) commutative, associative, monotone et telle que ? soit un �l�ment neutre pour et T un �l�ment absorbant.

Les valuations permettent d'exprimer diff�rents niveaux de violation. Par exemple, ? caract�rise une absence de violation (i.e. la satisfaction d'une contrainte) et T une insatisfaction totale. Quant � la loi , elle permet de calculer la valuation correspondant � la violation simultan�e de plusieurs contraintes. Notons que, dans certains cas, elle peut poss�der d'autres propri�t�s comme l'idempotence ou la stricte monotonie. A partir de cette structure de valuation, on peut d�finir formellement la notion de CSP valu�:

D�finition 2 (Schiex, 1995) Un VCSP est un CSP classique P = (X, D, C) dot� d'une structure de valuation S=(E, ?, ) et d'une application ? de C dans E, qui associe une valuation � chaque contrainte du CSP. On le note (X, D, C, S, ?).

Il est dit binaire si chaque contrainte de C implique au plus deux variables. La valuation d'une instanciation compl�te B des variables de X correspond � la combinaison des valuations des contraintes viol�es par B�:

D�finition 3 (Schiex, 1995) Soient un VCSP P = (X, D, C, S, ?) et une instanciation B sur X. La valuation de B dans P se d�finit par�:

�Etant donn�e une instance P, le probl�me VCSP consiste donc � trouver une affectation de toutes les variables de P qui soit de valuation minimale au sens de ?. Cette valuation optimale est appel�e valuation du VCSP. Par la suite, nous la noterons ?. D�terminer la valuation d'un VCSP est un probl�me NP-difficile.

Exemple�1 �Malek, Badr et Ali se rencontrent inopin�ment dans un couloir. Malek interpelle les deux autres et leur rappelle leur promesse de pr�sentation de leurs travaux respectifs. Badr et Ali doivent pr�senter leurs travaux � Malek qui lui m�me doit leur pr�senter ses travaux. Il y a 4 expos�s�: de Badr � Malek, d?Ali � Malek, de Malek � Badr et enfin de Malek � Ali. Ils conviennent de bloquer 4 demi-journ�es pour faire ces expos�s. Chaque expos� prend une demi-journ�e. D�s le d�but, Malek signale qu?il lui para�t important d?avoir �cout� Badr et Ali avant de faire ses pr�sentations. Puis, Malek indique qu?il aimerait pr�senter ses travaux � Badr lors de la deuxi�me demi-journ�e. Enfin, Malek signale qu?il ne veut pas pr�senter ses travaux � Badr et Ali en m�me temps.

Mod�lisation du probl�me�: Ce probl�me se mod�lise sous forme d?un CSP ayant 4 varibles {M_b, M_a, B_m, A_m}, o� chaque variable repr�sente un expos�. Par exemple, M_b d�signe l?expos� que doit faire Malek � Badr? Les expos�s devant avoir lieu dans 4 demi-joun�es, les domaines des variables sont identiques: {1,2,3,4}. Les contraintes sont de deux sortes�: les contraintes d?integrit� et les contraintes de pr�f�rence exprim�es par Malek.

Contraintes d?int�grit�.

• Un orateur ne peut �tre auditeur dans la m�me demi-journ�e�: C_1�: M_a? A_m, C₂: M_b?B_m, C₃: M_a?B_m, C₄�: M_b?A_m.

• Une personne ne peut assister � deux pr�sentations en m�me temps�: C₅: A_m?B_m.

Contraintes de pr�f�rence.

• Malek signale qu?il lui para�t important �d?avoir ��cout� �Badr et Ali �avant de faire �ses �pr�sentations : C₆�: M_a>A_m, C₇�: M_a>B_m, C₈�: M_b>B_m, C₉�: M_b>A_m.

• Malek aimerait pr�senter ses travaux � Badr lors de la deuxi�me demi-journ�e et il ne veut pas pr�senter ses travaux � Badr et Ali en m�me temps�: C₁₀�: M_b=2, C₁₁: M_a?M_b.

Nous employons S=(N, <, +) avec l?�l�ment minimum est 0 et l?�l�ment maximum est +?. Nous d�finissons trois niveaux de violations�: pour chaque contrainte d?int�grit�, la valuation associ�e est 3 (contrainte "dure"). Les violations des contraintes d?ant�riorit� ont un poids de 2 et les contraintes de simultan�it� (C₁₀ et C₁₁) sont associ�es � une valuation de 1. Pour ce VCSP, nous obtenons ?=1 (il suffit de violer C₁₀ pour avoir une solution).

D�finition 4 (Schiex, 1995) Soient un VCSP P = (X, D, C, S, ?) et une instanciation B sur YX. La valuation locale de B dans P se d�finit par

Nous notons v_C(B) la valuation d?une affectation B sur le probl�me restreint au sous-ensemble de contraintes C C.

La m�thode de base pour r�soudre les CSP valu�s est l'algorithme branch and bound (s�paration et �valuation, not� BB). Cette m�thode �num�rative utilise la valuation lo�cale de l'affectation courante comme minorant et la valuation de la meilleure solution connue comme majorant. Si le minorant ne d�passe pas le majorant, alors on �tend l'ins�tanciation courante en affectant une nouvelle variable. Sinon, on revient en arri�re sur la derni�re variable instanci�e et on l'affecte avec une nouvelle valeur. Si toutes ses va�leurs ont �t� essay�es, on revient en arri�re une nouvelle fois, et ainsi de suite. Plusieurs am�liorations de cet algorithme ont �t� propos�es. La plupart d'entre elles proviennent du cadre CSP et ont conduit � des m�thodes comme les algorithmes Forward-Checking valu� (Schiex, 1995), Nogood Recording (Dago, 1996), la recherche arborescente born�e pour la r�solution de CSP valu� (Jegou, 2003), etc.

D�finition 5� Un DisVCSP est un VCSP o� les variables, valeurs, contraintes et valuations sont distribu�es parmi les agents A_i (i.e pour chaque agent A_i, on trouve un VCSP (X_i, D_i, C_i, S, ?)). Donc, un probl�me distribu� de satisfaction de contraintes valu�es (DisVCSP) est un �P=(X, D, C, S, ?, A) �o� X, D, C, S et ? sont d�finis comme pr�c�demment. A est un ensemble fini d'agents {A₁,.., A_p}. Chaque agent poss�de un sous ensemble des variables du probl�me. A constitue une partition de X.

Chaque agent poss�de l'ensemble des donn�es du probl�me relatives � son sous-ensemble des variables (domaines, contraintes et valuations). Chaque variable appartient � un agent. La distribution des variables forme une bi-partition de C en C_intra={c_ij / x_i et x_j appartiennent au m�me agent} et C_inter={ c_ij / x_i et x_j appartiennent �� des agents diff�rents }, qu'on nomme ensemble des contraintes intra-agents et inter-agents, respectivement.

Comme dans le cadre centralis�, une solution est une affectation de valeurs aux va�riables qui optimise les valuations portant sur la satisfaction des contraintes. Les DisVCSP sont r�so�lus par l'action collective et coordonn�e des agents de A, chacun ex�cutant un processus de satisfaction de contraintes. Les agents communiquent par envois de messages, avec les postulats suivants (Yokoo, 1998): Un agent ne peut envoyer de message que s'il conna�t l'adresse du destinataire. Le d�lai de r�ception d'un message est fini mais al�atoire. Pour une paire d'agents donn�e, les messages sont re�us dans l'ordre dans lequel ils ont �t� envoy�s.

Pour des raisons de simplicit�, et pour mettre l'accent sur les aspects relatifs � la distribution, dans la suite de cet article nous supposons que chaque agent a une seule variable. Nous identifions l'indice de l'agent � celui de sa variable.

Le Backtrack Dynamique valu� (Dago, 1997) m�morise les zones de l'espace de recherche explor�es et reconnues comme sans solution sous la forme d'affectations partielles qu'il est interdit de reproduire : les nogoods. Dans le cadre d'une optimisation, l'exploration constate que les valuations des solutions dans une certaine zone sont sup�rieures � une valeur donn�e ?. Si cette valuation est suffisamment �lev�e, l'interdiction d'explorer � nouveau devient effective. Afin de s'adapter � ce contexte, nous rappelons le concept de nogood valu� ainsi que les propri�t�s qui permettent sa mise en oeuvre. Ces proprit�s simples ne sont pas d�montr�es ici ; on en trouvera une preuve formelle dans (Dago, 1996).

D�finition 6 (Nogood valu�) Un nogood valu� est un triplet (B, v, C) , o� B est une affectation partielle, v une valuation et C un ensemble de contraintes (appel� justification) tel que, pour toute affectation B? extension compl�te de B, v ? v_C(B?).

Un Nogood valu� est, en quelque sorte, une pr�vision par d�faut de la valuation des violations que l'on obtiendrait � terme si l'extension compl�te d'une affectation �tait effectu�e. Un nogood (B, v, C) donne un minorant des valuations globales de toutes les affectations partielles contenant B.

Propri�t� 1 ((Dago, 1996) construction) Soit B une affectation partielle, et C un ensemble de contraintes qu'elle viole, alors (B, v_C(B), C) est un nogood.

Cette propri�t� permet la production des nogoods. Il en d�coule en particulier que si C est l'ensemble de toutes les contraintes viol�es, (B, v(B), C) est un nogood. Nous noterons n(B) ce nogood particulier. La propri�t� suivante permet d'agr�ger en un nouveau nogood plusieurs nogoods qui impliquent toutes les valeurs d'une variable. Intuitivement, puisque le choix d'une valeur pour cette variable est n�cessaire, on peut pr�voir (ind�pendamment de l'affectation de la variable) une valuation au moins �gale � la plus optimiste des pr�visions fournies par les nogoods.

Propri�t� 2 ((Dago, 1996) union) Soit B une affectation partielle, et x¹ ,. . . ,x^m les valeurs d'une variable x n?appartenant pas � B. Soient B₁,...,B_m des sous ensembles de B tels que (B₁ {x¹}, v₁, C₁),.., (B_m{x^m}, v_m, C_m) sont des nogoods.

Propri�t� 3 ((Dago, 1996) projection) Soit (B, v, C) un nogood, et B? �l'ensemble des valeurs de B absentes des n�uplets interdits par les contraintes de C.

Propri�t� 4 ((Dago, 1996) augmentation) Soit (B, v, C) un nogood, B? �une affectation compatible avec B et c une contrainte viol�e par B? .

Propri�t� 5 ((Dago, 1996) r�duction) Soit (B, v, C) un nogood, et c une contrainte de C.

Soit B une affectation et n un nogood d'affectation compatible, nous noterons ?^B(n) le r�sultat des augmentations successives de n avec toutes les contraintes viol�es par B, et ?^B(n) le r�sultat des r�ductions successives du nogood n avec toutes les contraintes viol�es par l'affectation B. Ici intervient la pr�cision d'un nogood : plus il est pr�cis, plus il touche un grand nombre d'affectations (apr�s r�duction) et plus il fournira une borne inf�rieure �lev�e de leur valuation globale (apr�s augmentation). La propri�t� qui suit prouve que la r�duction n'entra�ne aucune d�gradation des pr�visions.

Propri�t� 6 ((Dago, 1997) �quivalence) Soit n = (B, v, C) un nogood, et c une contrainte de C viol�e par une affectation B? compatible. Le nogood n? obtenu par r�duction puis augmentation de n avec c poss�de une valuation sup�rieure ou �gale � celle de n.

Corrolaire (Dago, 1997) la valuation d'un nogood n est inf�rieure ou �gale � celle de ?^B (?^B(n)).

D�finition 7 ((Dago, 1997) R�duction partielle) Soit B une affectation partielle et n un nogood portant sur B. Soit C_B?n l'ensemble des contraintes viol�es par B et pr�sentes dans n, et C_B-n les autres contraintes viol�es par B. Nous appelons r�duction partielle d'un nogood par B et n l'augmentation (propri�t� 4) avec les contraintes de C_B?n suivie de la r�duction (propri�t� 5) avec les contraintes de C_B-n par B.

Nous noterons ?? _{(B, n)} cet op�rateur de r�duction. Il a pour effet de projeter un nogood n? �de mani�re � ce que le r�sultat n?? ait une valuation sup�rieure � son pr�d�cesseur n.

Dynamic Backtracking Valu� (VDB) (Dago, 1997) est une proc�dure de recherche arborescente qui m�morise pour chaque valeur xi, i�me valeur de Dx, un nogood N_xi donnant un minorant de la valuation globale de l?extension d?une affectation B avec la valeur xi. Ce nogood est une m�moire des anciennes tentatives infructueuses d?extension avec xi. VDB choisit une variable non instanci�e, et tente de lui affecter une valeur. Si cette valeur et les variables d�j� instanci�es, donnent une valuation sup�rieure � ?, elle est supprim�e et le nogood correspondant est m�moris�. Lorsque toutes les valeurs de la variable courante x sont �limin�es, les justifications de retrait sont utilis�es pour g�n�rer un nouveau nogood comme suit. Soit B l?ensemble des variables d�j� instanci�es (x n?appartient pas � B). Le nouveau nogood n est l?union des nogoods de �valuations maximales de B {xi}, ?xiDx. Pour avoir un nogood de valuation maximale, il suffit d?utiliser la propri�t� d?augmentations successives de N_yj avec toutes les contraintes viol�es par

L?algorithme impose des conditions d?ordre entre les variables de l?affectation du nogood et la variable sur laquelle se porte le backtrack. �Soit y^j appartenant � B, une valeur qui ne soit inf�rieure � aucune autre valeur de n selon l?ordre partiel. Les nogoods N_zk, dont l?affectation contient y^j, sont initialis�s par le nogood n_�=(�, ?, �). N_yj est initialis� par ?? (N, N_yj) (n) y^j est supprim�e de B et l?algorithme cherche � r�instancier y. Il a �t� prouv� que cet algorithme est correct et complet (Dago, 1997).

Valued Dynamic Backtracking Distribu� (voir algorithme ci-dessous) est un algorithme calqu� sur le mod�le du Backtrack dynamique distribu� pr�sent� dans (Bessi�re, 2001). Il r�alise des sauts dynamiques sur l'en�semble des agents en conflit. La recherche arborescente d'une solution n�cessite la mise en place d'un ordre total entre les agents destin�s au calcul. Le calcul de cet ordre revient � affecter des priorit�s entre agents. L'objectif commun des approches distribu�es de types arborescents est d'offrir des m�thodes distribu�es calculant un ordonnancement des agents. Ces m�thodes sont ex�cut�es avant la m�thode de r�solution proprement dite. Dans ce sens, DisVDB utilise l'algorithme d'ordonnancement EDisAO (Extension Distributed Agents Ordering) (Belaissaoui, 2002). EDisAO prend en entr�e ?, f et op. ? est l?ensemble des agents du syst�me avec lesquels self, l?agent g�n�rique, partage au moins une contrainte inter-variable. f et op sont respectivement la fonction heuristique et l'op�rateur de comparaison. Il construit une hi�rarchie d'agent en utilisant des crit�res heuristiques�: ? ^?(self) d�signe l'ensemble des agents partageant une contrainte avec self et class�s plus haut dans la hi�rarchie. R�ciproquement, ?⁺(self) est l'ensemble des voisins de self class�s plus bas dan la hi�rarchie.

Chacun des agents ex�cute l'algorithme DisVDB et m�morise un contexte et un en�semble de nogoods. Le contexte de self est l'ensemble des valeurs qu'il cro�t affect�es aux agents le pr�c�dant dans l'ordre. Il est toujours coh�rent avec l'ensemble des nogoods m�moris�s localement. Les agents �changent des affectations et des nogoods. Les affectations sont toujours accept�es, et le contexte mis � jour en cons�quence. Un nogood est accept� s'il est coh�rent avec le contexte de l'agent et sa propre ins�tanciation, sinon il est obsol�te. S'il est accept�, il est m�moris� comme justification du retrait de la valeur courante. Lorsque toutes les valeurs d'un agent sont �limin�es, il g�n�re un nouveau nogood n de la m�me mani�re que dans VDB, et l'envoie � l'agent qui ne soit inf�rieure � aucun autre agent selon l?ordre partiel (entre les agents responsables des variables de l?affectation de n). Self d�sinstancie cette variable dans le contexte, ainsi que toutes celles qui apparaissent dans le nogood n, mais pas dans ?^?(self ), et on actualise les nogoods en cons�quence. Le processus s'ach�ve lorsque les agents se stabilisent�: une solution a �t� trouv�e, ou le nogood vide est g�n�r�, ce qui signifie que le probl�me est insoluble. Les messages �chang�s sont de trois types�: Stop(system), il n'y a pas de solution et le destinataire arr�te la recherche. Ce message implique un agent suppl�mentaire appel� system, qui est responsable de l'arr�t du r�seau. Info(fils,v, N_v ), informe l'agent fils, qui est dans ?⁺(self ), que self a pris la valeur v et que le nogood g�n�r� pour cette valeur est N_v, c?est pour que l?agent fils peut calculer la valuation �de son nogood g�n�r�, s?il n?arrive pas � instancier sa variable. Back(nogood, A), message de retour arri�re. Il contient un nogood et est adress� � l?agent A. A est le dernier agent qui a envoy� un message de type info, par exemple. Par ce que, self croit que ce dernier est la cause du retrait. Les messages sont �chang�s via les primitives getMsg et sendMsg.

DisVDB (voir algorithme ci-dessous) est la proc�dure principale. C?est une boucle de r�ception qui commute l'ex�cution suivant le type de message re�u. Apr�s r�ception d'un message Stop de l'agent System, la proc�dure s'ach�ve. Une borne sup�rieure ? fournie par la derni�re solution trouv�e et fix�e a priori � la valuation maximale. A chaque valeur i de la variable de self est associ� un nogood N_i donnant un minorant de la valuation globale de l?extension d?un contexte avec la valeur i. Ce nogood est une m�moire des anciennes tentatives infructueuses d?extension avec i. L?ensemble des N_i est initialis� par des nogoods nuls�: n_�=(�, ?, �).

GoAhead est ex�cut�e lors de la r�ception d'un message de type Info. Elle tente d�tendre le contexte re�u par self. Apr�s une mise � jour du contexte de self, d�sign� comme myContext (ligne 1), si la valeur courante myValue (ligne 2) est supprim�e par la fonction Evalue, qui fournit sous forme de nogoods une estimation des valuations globales, GoAhead fait appel � la proc�dure ChooseValue pour trouver une autre valeur qui respecte la borne sup�rieure ? avec myContext (ligne 3). Si c'est possible, self informe ?⁺(self) de sa nouvelle valeur (ligne 4). Sinon, self appelle la proc�dure ResolveNogoods (ligne 5). Si �l?argument de GoAhead est vide, elle essaye de trouver une valeur de self respectant avec myContext la borne ? (ligne 2 de DisVDB et ligne 10 de ResolveNogoods).

Un nogood, dans un message de type Back, est obsol�te (ligne 1 de ResolveConflict), si son contexte ne respecte pas les valeurs des agents de ?^-(self) et la valeur de self existants dans myContext. S'il n'est pas obsol�te, ResolveConflict actualise myContext au vu des nouvelles informations (ligne 2). Elle construit un nouveau nogood, par la d�finition de la r�duction partielle (d�finition 7), et elle le m�morise (lignes 3 et 4). Ensuite, elle tente de trouver une autre valeur. Si c'est possible, self informe ?⁺(self) (ligne 6). Sinon, ResolveConflict fait appel � la proc�dure ResolveNogoods (ligne 7). Si le message de type back respecte seulement la valeur de self, self renvoie cette valeur � l'exp�diteur (lignes 8 et 9).

La proc�dure ResolveNogoods utilise la propri�t� de l?union (propri�t� 2) sur les nogoods g�n�r�s par la fonction Evalue appliqu�e sur chaque valeur de D_self et myContext. Elle g�n�re un nouveau nogood n. Si l?affectation de ce nogood est vide, le probl�me est insoluble et un message de type Stop est envoy� (ligne 4). Sinon, ResolveNogoods localise l?agent A qu?a envoy� le dernier message de type Info. Elle envoie � A un message de type Back contenant n (ligne 7). Self oublie l'instanciation de A ainsi que toutes les affectations de n n?appartenants pas aux agents de ?^-(self). Il oublie aussi les nogoods locaux qui sont obsol�tes.

La fonction ChooseValue choisit une valeur respectant la borne sup�rieure ? avec myContext. Si une valeur est supprim�e par la fonction Evalue, qui fournit sous forme de nogoods une estimation des valuations globales (propri�t�s 2 et 4), un nouveau nogood est g�n�r� par cette derni�re. L?ensemble des nogoods (myNogoods) est actualis�. Si toutes les valeurs de D_self sont supprim�es, la fonction renvoie la valeur vide.

Nous v�rifions ici que l'arr�t qui n'est pas d� � l'obtention d'une meilleure solution (ResolveNogoods ligne 2) correspond � l'absence de solutions de valuation inf�rieure � la borne ?. Evalue(myContext {i}) renvoie au moins la valuation locale v(myContext {i}). Le test ligne 2 dans ChooseValue assure que toute affectation compl�te produite poss�de une valuation strictement inf�rieure � la borne maximale ?. Il faut constater que le nogood n produit dans ResolveNogoods (ligne 1), comme tous les nogoods dont il est issu, poss�de une valuation sup�rieure ou �gale � ?. En cas d'arr�t, on dispose d'un nogood n d'affectation vide et de valuation sup�rieure ou �gale � ?. Ce nogood est la preuve que toute solution poss�de une valuation inf�rieure � ?.

La terminaison est la propri�t� qui manque � la compl�tude de cet algorithme. Elle r�side dans le choix de la valeur s�lectionn�e comme cible du backtrack (ResolveNogoods, ligne 5). Les nogoods produits par union ont toujours une valuation sup�rieure ou �gale � ?. Ils correspondent donc � des nogoods classiques interdisant une affectation. Pour assurer la terminaison, il suffit d'appliquer la m�thode EDisAO (Belaissaoui, 2002) pour �tablir un ordre partiel entre les agents responsables des variables contenues dans le nogood n. Si le choix du point de backtrack se fait de telle mani�re que l'ordre partiel �tabli par EDisAO est respect�, alors le processus termine (Belaissaoui, 2002)(Bessi�re, 2001).

Ces exp�rimentations mettent en ?uvre DisDB (Bessi�re, 2001) et notre m�thode DisVDB dans un environnement distribu� utilisant une granularit� p < n (p agents et n variables).

Une approche plus th�orique et couramment utilis�e consiste � tester les algorithmes sur un �chantillon de probl�mes tir�s al�atoirement (voir algorithme ci-dessous) ; on prend habituellement pour mesure la moyenne des performances r�alis�es sur l?�chantillon test�. Ceci implique : la description du mod�le des DisCSP g�n�r�s (param�tres et algorithme de g�n�ration) ; les tests pour chaque valeur du ou des param�tres de g�n�ration. Il reste enfin � d�finir les unit�s de mesure utilis�es. Puisque nous cherchons l?optimalit� de la recherche d?une solution, nous avons choisi l?unit� couramment utilis�e : la moyenne des temps d?ex�cution.

Notre g�n�rateur de probl�mes distribu�s al�atoires est l?extension du g�n�rateur de Van Beek (VanBeek)] (la biblioth�que de programmes concernant les CSP de Van Beek) au cadre de DisCSP. Il n�cessite cinq param�tres : le nombre de variables n, le nombre de valeurs par domaine d, la proportion (probabilit�) de contraintes dans le r�seau, p₁, la proportion de paires interdites dans une contrainte, p₂, et le nombre d?agents p < n. Nous avons g�n�r� deux types de probl�mes : des probl�mes faiblement contraints ou peu denses pour les petites valeurs de p₁ et des probl�mes ou graphes complets pour p₁=1.

Apr�s la cr�ation du CSP global (voir algorithme ci-dessous), nous l?avons distribu� comme suit. Dans un premier temps, nous avons initialis� chaque sous-probl�me CSP_j (CSP_j est le sous-probl�me de l?agent j, 1? j ? p) par la variable i appartient � {1,.., n} telle que i = j ainsi que son domaine D_i et l?ensemble des relations R_ik telle que 1? k ? n et k ?i. L?extension de ces sous-probl�mes CSP_j est faite suivant la valeur d?une variable x tir�e al�atoirement entre 0 et 1. Pour DisDB, les valuations de contraintes sont g�n�r�es, aussi, d?une fa�on al�atoire. Ainsi que la valeur de ?.

Pour chacune des m�thodes que nous avons test�, nous avons utilis� la d�marche suivante : chaque agent est activ� � tour de r�le par un processus syst�me, pour un cycle durant lequel l?agent peut lire tous les messages qui lui ont �t� adress�s au cycle pr�c�dent, effectuer localement les calculs qui s?y rapportent et envoyer les messages ad�quats. Lorsqu?il y a stabilisation de tout les processus, le processus syst�me d�tecte la terminaison. Puisque tout les processus utilisent un seul processeur, nous avons mesur� le temps processeur permettant la r�solution de chaque probl�me.

Nous avons g�n�r� deux types de probl�mes : des probl�mes denses <p, n, d, p₁, p₂> = <5,15, 5, 1, p₂> et des probl�mes peu denses <p, n, d, p₁, p₂> = <5,15, 5, 0.3, p₂>, pour diff�rentes valeurs de p₂. Sur chaque instanciation de p₂, nous avons compar� les performances de DisDB et de notre m�thode DisVDB, en utilisant l?heuristique MaxDeg pour ordonner les agents.

La figure 1 montre nos r�sultats sur un ensemble de probl�mes denses en faisant varier p₂ par pas de 0.1. DisVDB s?est r�v�l� nettement meilleur que DisDB pour p₂ dans [0.3,.., 0.5]. Ceci s?explique par le fait que le degr� de connectivit� des variables est de 100% (p₁=1) et si p₂ appartient � l?intervalle [0.3,.., 0.5], le nombre d?envois de message augmente parce que le nombre de contextes de retour en arri�re s?�l�ve en balayant l?ensemble de valeurs avec presque 50% de valeurs interdites. Puisque DisVDB proc�de par des valuations de contraintes, ce dernier d�cide, soit de poursuivre la recherche de la solution, soit d?arr�ter le processus de la recherche en trouvant une solution, s?elle existe, avec un co�t inf�rieur � ?. Ceci explique l?�cart en temps de calcul dans cet intervalle.

La figure 2 montre aussi nos r�sultats sur des probl�mes peu denses avec une variation de p₂ par pas de 0.1. Dans l?intervalle [0.5,.., 0.8] de p₂, DisVDB se comporte encore mieux que DisDB. Cet intervalle est sup�rieur � celui des probl�mes denses parce que le degr� de connectivit� est inf�rieur � celui de ces derniers.

Dans le domaine des Probl�mes de Satisfaction de Contraintes Valu�s et Distribu�s (DisVCSP), nous avons consacr� notre �tude � la distribution de l'algorithme Valued Dynamic Backtracking VDB (Dago, 1997) et la valuation de la m�thode Distributed Dynamic Backtracking (Bessi�re, 2001). C?est � dire, nous avons d�velopp� une m�thode permettant de r�soudre les DisVCSP�: Distributed Valued Dynamic Backtracking (DisVDB). Nous avons d'abord d�fini comme algorithme d'ordonnancement des agents EDisAO (Extension Distributed Agents Ordering) (Belaissaoui, 2002). EDisAO est utilis�e pour accro�tre les performances des algorithmes de r�solution des DisCSP. DisVDB a vis�e � b�n�ficier des avantages des deux approches : la gestion des nogoods valu�s, la compl�tude de la recherche et un haut niveau d'asynchronisme entre les agents. Il a �t� prouv� que cet algorithme est correct et complet. Les exp�rimentations mettent en ?uvre DisDB (Bessi�re, 2001) et notre m�thode dans un environnement distribu� utilisant une granularit� p<n (p agents et n variables).