3. Algorithmes de recherche dans les systèmes à agents
3.3. Le problème de la satisfaction des contraintes (PSC)

3.3.2. Retour en arrière asynchrone (RAA)

Pour présenter cette méthode on va considérer une classe de PSC où toutes les contraintes sont binaires ( P_k(x_i,x_j) ). Un tel problème se peut représenter par un graphe où les variables constituent des nœuds x_i  et les contraintes P_k(x_i,x_j) sont des arcs orientés entre les nœuds x_i et x_j. Le graphe abstrait qui représente ce type de PSC est indépendant du réseau physique de communication entre les agents.

Exemple  Soit trois variables x₁, x₂, x₃ qui peuvent prendre des valeurs dans des domaines booléens et les contraintes

P₁(x₁,x₃) = x₁  Ú   x₃
P₂(x₂,x₃) = x₂ Ú  ~ x₃

Chaque variable est assignée à un seul agent (voir figure 3.3.1), donc un nœud va représenter aussi un seul agent.  La valeur choisie par un agent x_i  pour la variable propre doit être validée par les nœuds évaluateurs x_j qui vérifient la satisfaction des contraintes P_k(x_i,x_j). Dans le cas où deux agents x_i et x_j feraient partie d`une même contrainte P<sub>k</sub>(x<sub>i</sub>,x<sub>j</sub>),  ils seront liés par un arc (x<sub>i</sub>,x<sub>j</sub>) qui sera orienté de l`agent qui envoie la valeur de sa variable propre, vers l`agent qui va évaluer la contrainte.

Figure 3.3.1. Le graphe pour un problème à 3 agents avec 2 contraintes

Le fonctionnement de ce réseau des contraintes est basé sur l`échange de messages entre les agents. Chaque agent donne une valeur pour sa variable propre et émet ensuite un message contenant cette valeur vers tous les agents auxquels il est lié par des arcs ayant comme origine son nœud. Ensuite il attend des messages et répond aux messages reçus. Il existe deux types principaux de messages:

• “correcte_?” – envoyé par un agent qui demande à l`évaluateur de la contrainte de vérifier si la valeur choisie pour sa variable propre est correcte,
• ”incorrect”– la réponse de l`agent évaluateur à l`agent qui a transmis une valeur qui ne respecte pas la contrainte vérifiée par l`évaluateur.

Chaque agent i dispose d`une mémoire propre dans laquelle on garde les informations suivantes :

• la valeur courante de la variable propre x_i ;
• la liste état_des_voisins - contient les valeurs des variables correspondant aux agents voisins (représentés par les nœuds origines des arcs qui arrivent dans le nœud courant). Les éléments de cette liste sont des couples (x_j, d_j), avec d_j la valeur propre de l`agent x<sub>j</sub> ; on a un couple (x<sub>j</sub>, d<sub>j</sub>) pour chaque arc (x<sub>j</sub>, x<sub>i</sub>), où x<sub>i</sub> désigne le nœud courant ;
• la liste des valeurs refusées (valeurs_refusées) - contient les valeurs de sa variable propre indiquées comme erronées par les nœuds évaluateurs de contraintes, avec qui le nœud courant est lié ; cette liste est actualisée à la réception d`un message de type incorrect; les éléments de la liste sont aussi des couples (x_j, d_j), où x_j fait partie d`un arc (x_i , x_j), où x_i désigne le nœud courant ;
• les adresses des nœuds voisins qui lui communiquent des valeurs pour être évaluées (ces adresses sont nécessaires pour pouvoir leur répondre)
• les adresses des nœuds évaluateurs de contraintes auxquels il est lié à son tour (pour leur communiquer la valeur courante de la variable propre et leur demander leur "avis").

La liste état_des_voisins est actualisée à l`arrivée des messages de type “correcte_?”, mais à cause des délais dans la transmission des messages, elle ne représente pas toujours une image synchrone de l`état respectif des agents.

à l`arrivée d`un message de type “correcte_?” l`agent actualise la liste état_des_voisins et vérifie si la valeur reçue et sa valeur courante de la variable propre satisfont toutes les contraintes que l`agent connaît.

Chaque agent va considérer que la valeur assignée à sa variable propre est consistante avec toutes les valeurs qui se trouvent dans la liste état_des_voisins quand les deux conditions suivantes seront vérifiées :

1. toutes les contraintes évaluées par l`agent et qui utilisent des valeurs qui se trouvent dans la liste état_des_voisins et sa valeur courante sont satisfaites
2. toutes les valeurs de la liste valeurs _refusées sont incompatibles avec toutes les valeurs qui se trouvent dans la liste état_des_voisins et avec la valeur courante.

Si la valeur courante n`est pas compatible avec état_des_voisins, l`agent va essayer de la changer avec une autre valeur, qui à ce moment là est consistante. Cette nouvelle valeur sera envoyée pour évaluation aux nœuds évaluateurs auxquels le nœud courant est lié.

Eviter le traitement en cycle infini

Si dans le graphe des contraintes il existe un circuit x₁, x₂, ... , x_k,, x₁  alors il est possible qu`un changement de la valeur de x₁ provoque une modification de la valeur de x₂  et ensuite de x₃ etc, ce qui peut se répercuter par un nouveau changement de valeur de la variable x₁ , suite au circuit des nœuds évaluateurs x₁, x₂, ... , x_k,, x₁.

Pour éviter ce cycle, on peut assigner des priorités aux agents. Par exemple, pour les valeurs des priorités on peut prendre en considération dans l`ordre lexicographique, des symboles des variables propres : si la variable propre de l`agent A a un symbole qui précède en ordre lexicographique le symbole de la variable propre de l`agent B, alors la priorité de l`agent A est plus grande que celle l`agent B.

Dans le cas de l`algorithme RAA les priorités sont fixes et chaque contrainte P_k(x_i,x_j) sera représentée par un arc qui part du nœud le plus prioritaire vers le moins prioritaire.

Exemple.  Soit un problème à 3 variables (agents) et 2 contraintes (liens) modélisé par le graphe de la figure 3.3.1. On remarque dans cette figure que

• la contrainte P₁(x₁,x₃) = x₁  Ú   x₃ est représentée par un arc orienté du nœud x₁ vers le nœud x₃
• la contrainte P₂(x₂,x₃) = x₂ Ú  ~ x₃ sera représentée par l`arc orienté (x₂ , x₃)

Suite à ce système des priorités, tous les messages " correcte_?" sont toujours transmis par le nœud le plus prioritaire vers le nœud le moins prioritaire (le nœud évaluateur) et les messages incorrects sont transmis vers le nœud le moins prioritaire existant dans la liste valeurs_refusées. En appliquant ce procédé, il n'est pas possible d'avoir un circuit des nœuds évaluateurs x1, x2, ... , xk,, x1 (le lien (xk,, x1) ne peut pas exister dans le graphe).

Question. Considérez 4 variables : a, b, c1, b2. et les contraintes P1(a,b), P2(b2,b), P3(c1,b2), P4(c1,a). Quels sont les liens représentant ces contraintes dans le graphe des agents ?

Cliquez ici pour voir la réponse

Eviter les inconsistances dues au traitement asynchrone

Il est possible qu'un agent reçoive un message de type incorrect pour une valeur communiquée antérieurement au nœud évaluateur, valeur qui entre temps a été corrigée suite à l'évaluation des autres contraintes. Le message incorrect arrivé pourrait conduire à un nouveau changement de valeur du nœud courant, ce qui peut engendrer des inconsistances. Pour éviter ceci, on va préciser aussi dans le cadre des messages de type incorrect la valeur erronée (le contexte) qui a déclenché l'envoi du message. Ainsi, l'agent qui reçoit un message de type incorrect va vérifier si la valeur transmise dans le message est compatible avec la valeur courante et la liste état_des_voisins et seulement dans un tel cas, l'agent va modifier sa valeur.

Remarque. La liste des valeurs refusées réceptionnées par les nœuds évaluateurs des contraintes se constitue en fait comme une liste des contraintes supplémentaires, ce qui évite la répétition des mêmes erreurs.

Le traitement des messages peut être décrit par une série de procédures associées à certains événements, des procédures représentées par le pseudo code suivant.

Procédure Réception_correcte_?_ (x_j, d_j) est

// La procédure est appelée à l`arrivée d`un message
// de type “correcte_?” émis par le nœud x_j qui transmet ainsi
// sa nouvelle valeur d_j au nœud courant (x_i) qui a le rôle 
// d`évaluateur de contrainte
//

Insert (état_des_voisins, (x_j, d_j) )
Vérifie_état_des_voisins()

Fin

Procédure Réception_incorrect_ (x_j , E) est

// La procédure est appelée à l`arrivée d`un message
// de type incorrect émis par le nœud x_j qui a un rôle
// d`évaluateur de contrainte pour le nœud courant (x_i)
// E = {(x_k, d_k)/ d_k est la valeur incorrecte pour le nœud x_k}
//

     pour *) chacune (x_k, d_k) dans E faire
     Insert ( valeurs_refusées, (x_k, d_k) )
     si *) le nœud (x_k) n`est pas lié au nœud courant (x<sub>i</sub>) alors
          *) demande au nœud (x<sub>k</sub>) d`établir un nouveau lien (x_k, x_i)
          Insert (état_des_voisins, (x_k, d_k) )
     fin si
fin pour

     vieille_valeur = valeur_courante
     Vérifie_état_des_voisins()

     si vieille _valeur = valeur_courante alors
           Envoyer (“correcte_?”, x_j, (x_i , valeur_courante))
     fin si
Fin

Procédure Vérifie_état_des_voisins() est

     si *)la valeur_courante n`est pas consistante avec état_des_voisins alors
          si *)aucune valeur de D<sub>i</sub> n`est consistante avec état_des_voisins alors
               RetourEnArrière()
          sinon
               d = Choix_valeur_consistante (D_i , état_des_voisins)
               valeur_courante = d
               pour *) tous les nœuds évaluateurs x_j Î (x_i, x_j) faire
                    Envoyer (“correcte_?”, x_j, (x_i , valeur_courante))
               fin pour
          fin si
      fin si
Fin

Procédure RetourEnArrière() est

     F = { A / A un sous-ensemble inconsistant de la liste  état_des_voisins }

     si F = f alors
          *)transmet aux autres agents qu`il n`existe pas de solution
          *) termine l`algorithme
     fin si
     pour *) chacune A dans F faire
          *) sélecte (x_j, d_j), où (x_j) a la plus petite priorité dans A
          Envoyer (incorrect, x_j, (x_i , A))
          Effacer (état_des_voisins, (x_j, d_j))
     fin pour
     Vérifie_état_des_voisins()
Fin

Exemple  Soit trois variables a, b, c booléennes (les domaines représentés par l`ensemble {0,1} ) et les contraintes : R₁= a Ú c  et  R₂= b Ú ~c

Figure 3.3.2. Agents, variables, domaines et contraintes

Le graphe des contraintes est présenté dans la figure 3.3.2. On va supposer que l`ordre chronologique des événements et celui décrit plus loin, mais ce système à 3 agents pourra bien avoir un autre ordre des événements, suite au parallélisme des traitements et aux délais de communication.

1.      les nœuds a et b

Figure 3.3.3. Les agents a et b envoient leurs essais des valeurs
pour leurs variables propres à l`agent l`évaluateur

          envoient vers le nœud c  les messages  (“correcte_?”, c_, (a ,0)) et respectivement  (“correcte_?”, c_, (b ,0))

2.      dans le nœud c

• arrive le message (correcte_?, c, (a, 0)) transmis par le nœud a;
• on insère dans la propre liste état_des_voisins l`élément (a,0), mais on ne peut pas déterminer une valeur courante consistante, parce qu`on ne peut pas évaluer R₂, la valeur de la variable b ne se trouvant pas dans la liste état_des_voisins
• arrive le message (correcte_?, c, (b,0)) envoyé par le nœud b;
  • après sa réception, on insère (b,0) dans la liste état_des_voisins  qui devient {(a,0), (b,0)};
  • aucune valeur de c ne peut satisfaire les deux contraintes ; on exécute donc la procédure RetourEnArrière() qui copie les éléments de la liste état_des_voisins dans l`ensemble F
  • envoie un message de type incorrect (figure 3.3.4)  vers le nœud le moins prioritaire de tous les nœuds qui sont en F, par l`appelle Envoyer (incorrect, b_, (c , {(a,0), (b,0)}))

   

Figure 3.3.4. Le nœud évaluateur transmet les valeurs inacceptables

3. le nœud b

• reçoit le message de type incorrect transmis par c et insère les éléments (a,0), (b,0) dans sa propre liste valeurs_refusées;
  • parce que le nœud a n'est pas lié à b, le nœud b émet vers a une demande d'établir un nouveau lien entre a et b (figure 3.3.5.a) et insère dans sa propre liste état_des_voisins l'élément (a ,0)
  • exécute Vérifie_état_des_voisins(); la valeur courante (0) n`est pas consistante parce qu'elle se trouve dans la liste des valeurs refusées ; on fixe la valeur courante à 1 et puis on envoie le message  (“correcte_?”, c_, (b ,1)) (figure 3.3.5.c)

(a)	(b)
(c)

Figure 3.3.5. Actions effectuées par l'agent b après la réception
du message 'incorrecte' transmis par l'agent c

4. le nœud a

• établit le lien demandé par le nœud b et transmet vers b le message ("correcte_?", b, (a ,0))

5. le nœud b

• reçoit ce message
• parce qu'on constate que la liste état_des_voisins est compatible avec la liste valeurs_refusées ,(l'élément (a ,0) se trouve dans les deux listes) exécute Envoyer (incorrect,a,(b,{(a,0)}) (figure 3.3.5.b)

6. le nœud a

• reçoit le message (incorrect,(b,{(a,0)}) transmis par b
  • modifie sa valeur à 1 et communique cette modification en envoyant des messages de type correcte_? vers les nœuds successeurs b et c (figure 3.3.6)

7. le nœud c

• reçoit le message ("correcte_?", c, (b ,1)) transmis par le nœud b, actualise sa liste état_des_voisins à {(a,0),(b,1)} et trouve c=1 comme une valeur consistante

Figure 3.3.6. L'agent a communique sa nouvelle valeur courante

8. les nœuds c et b

• en chaque nœud arrive un message de type "correcte_?" transmis par le nœud a qui communique ainsi sa nouvelle valeur aux nœuds c et b,
• ce message sert seulement à la mise à jour des listes état_des_voisins de chaque nœud

À ce stade aucun message n'est plus transmis et l'algorithme se termine.