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

Le problème de la satisfaction des contraintes (en anglais Constraint Satisfaction Problem - CSP)  représente un modèle abstrait applicable à une grande classe des problèmes dont la recherche de la solution a une complexité exponentielle. Pour définir le PSC on considère n variables x₁, x₂, ... , x_n, qui peuvent prendre leurs valeurs dans n ensembles finis et discrets D₁, D₂, ... , D_n et un ensemble de contraintes exprimées à l`aide d`un ensemble de prédicats P_k(x₁, x₂, ... , x_n),  définis sur le produit cartésien D₁ x D₂ x ...x D_n. Le problème de la satisfaction des contraintes consiste dans l'attribution d'un ensemble de valeurs aux variables xi de façon que toutes les contraintes soient satisfaites.

Pour trouver une solution du PSC on peut utiliser des algorithmes de recherche dans l`espace des solutions D₁ x D₂ x ...x D_n  .

Question. Formaliser le problème des n reines (on demande de placer n reines sur un échiquier à n n cases de façon à ce qu'aucune reine ne puisse être prise par une autre) comme un PSC.

Cliquez ici pour voir la réponse

3.3.1. Résolution distribuée du PSC

Dans le cadre d`un algorithme distribué de résolution du PSC on considère que les variables et les contraintes sont distribuées dans le cadre d`un système multi-agents caractérisé par le modèle de communication suivant :

• l`échange d`information entre agents se réalise par l`envoi de messages
• un agent peut envoyer des messages seulement aux agents dont il connaît l`adresse
• un message arrive à la destination dans un délai qui a une valeur finie, mais qui n`est pas forcément une constante du système
• la réception d'une suite de messages envoyés par un agent i vers un agent j se produit avec le maintien de l'ordre dans lequel les messages ont été émis par l'agent i.

Dans le cadre de ce modèle de système multi-agents on suppose que le réseau physique de communication assure complètement tous les échanges de messages nécessaires à une bonne coopération entre agents.

Pour trouver la solution du PSC il est nécessaire de déterminer un modèle de coopération: la structure physique de communication ne suffit pas.

La variante distribuée du PSC considère que chaque variable x_i reste sous la responsabilité d`un seul agent i qui est chargé de trouver pour x_i une valeur appartenant au domaine D_i . On considère aussi que toutes les contraintes exprimées par des prédicats sont distribuées aussi dans le système multi-agents, chaque agent connaissant les contraintes concernant sa propre variable.

Dans un tel système on obtient une solution lorsque chaque agent appartenant au système a attribué à chaque variable propre xi une valeur di dans Di qui satisfait toutes les contraintes Pk que cet agent connaît.

Il existe plusieurs stratégies pour trouver la solution grâce à un système multi-agents. Dans ce paragraphe introductif on va en présenter deux : la Recherche centralisée et la méthode Retour en arrière synchrone.

La recherche centralisée

On choisit un agent avec un rôle de leader, dans lequel sont concentrées toutes les informations concernant les variables, leurs domaines et les contraintes. Cet agent «leader» va diriger toutes les activités des autres agents dans le processus de résolution du problème.

On observe facilement que dans le cas des problèmes de grandes dimensions la centralisation de toutes les informations dans l`agent leader peut s`avérer coûteuse ou même impossible.

Algorithme de filtrage

Le but de cet algorithme est la diminution du cardinal des ensembles D₁, D₂, ... , D_n par l`exclusion des valeurs inconsistantes.

Chaque agent Ai est responsable d'une variable xi et connaît son domaine Di et les contraintes concernant sa variable propre. Tous les agents connaissent les adresses des agents voisins (ceux ayant des variables qui interviennent dans les mêmes contraintes que celle de l'agent).

L`algorithme de filtrage comprend pour chaque agent A_i les actions suivantes

• A_i communique à ses voisins l`ensemble D<sub>i</sub>  
• après la réception d`un domaine D_j exécute le filtrage des valeurs de son propre domaine D_i selon le pseudo code:

     elimine = vrai
     pour *) chacune di dans Di faire
     tant que elimine=vrai et Dj<>Ø faire
          *) soit x une valeur de Dj
          Dj = Dj – {x}
          si  *) di est consistante avec x alors
               elimine = faux
          fin si
     fin tant que
     si elimine alors
          Di = Di-{di}
     fin si
fin pour

à la fin on peut arriver dans une de situations suivantes :

• chaque domaine contient une seule valeur – alors on a trouvé une solution
• il existe au moins un domaine vide – le problème est très contraint
• il existe au moins un domaine avec plus d`une valeur –filtrage

L'algorithme est utilisé plutôt dans la pré-résolution d'un problème, il ne peut pas garantir de trouver une solution, même si le problème en admet une.

Retour en arrière synchrone (RAS)

Cette méthode consiste en la transformation de la méthode Retour en arrière standard, d`un système monoagent, à un système multi-agents par la synchronisation des activités des agents du système. à cette fin :

• on établit l`ordre dans lequel les agents vont agir
• le premier agent assigne une valeur à sa variable propre en établissant ainsi une solution partielle, et la transmet à l'agent suivant (dans l'ordre préétabli) ; le deuxième agent va ajouter une valeur consistante de son domaine et va envoyer les deux valeurs au troisième …
• chaque agent reçoit ainsi une solution partielle du problème obtenue par la concaténation des valeurs envoyées par les agents précédents ;
• après la réception de la solution partielle, un agent cherche une valeur pour sa variable propre, qui avec la solution partielle reçue doit satisfaire toutes les contraintes que l'agent connaît
• s`il a trouvé une telle valeur, alors il l`ajoute à la solution partielle reçue et transmet cette nouvelle solution partielle à l`agent suivant ; sinon, l`agent émet un message de type incorrect vers l`agent précèdent ;
• à la réception d`un message de type incorrect chaque agent reprend la recherche d`une valeur appartenant au domaine D_i qui, avec la solution partielle reçue de l'agent précédent, doit satisfaire les contraintes connues
• quand le dernier agent (dans l`ordre préétabli entre agents) a trouvé une attribution convenable pour sa propre variable, il annonce que la solution a été trouvée.

Question. Quels sont les messages changés entre les agents pour résoudre le problème de n reines, dans le cas particulier n=4 ? Codifiez les messages sous la forme :expéditeur->destinataire(message) et les agents par les symboles de variables x1,..,x4.

Cliquez ici pour voir la réponse

La résolution distribuée du problème de la satisfaction des contraintes par cet algorithme présente les inconvénients suivants:

• il est besoin d`établir un ordre initial - opération coûteuse du point de vue de la communication ;
• dans le processus de recherche de la solution on peut observer qu`à chaque moment un seul agent est en activité, donc on n'utilise pas l'avantage du parallélisme.

Malgré la distribution des tâches à plusieurs agents, la résolution par cette méthode du PSC est quand même séquentielle.