Optimisation des contraintes distribuées

L'optimisation par contraintes distribuées ( DCOP ou DisCOP ) est l' analogue distribué de l'optimisation par contraintes . Une DCOP est un problème dans lequel un groupe d'agents doit choisir de manière distribuée des valeurs pour un ensemble de variables de telle sorte que le coût d'un ensemble de contraintes sur les variables soit minimisé.

La satisfaction de contraintes distribuées est un cadre permettant de décrire un problème en termes de contraintes connues et appliquées par des participants distincts (agents). Les contraintes sont décrites sur certaines variables avec des domaines prédéfinis et doivent être affectées aux mêmes valeurs par les différents agents.

Les problèmes définis avec ce cadre peuvent être résolus par n’importe lequel des algorithmes conçus pour cela.

Le framework a été utilisé sous différents noms dans les années 1980. La première utilisation connue sous le nom actuel date de 1990.

Les principaux ingrédients d'un problème DCOP sont les agents et les variables . Il est important de noter que chaque variable appartient à un agent ; c'est ce qui rend le problème distribué. Formellement, un DCOP est un tuple , où :

• agents , .
• variables , .
• domaines de variables , , où chacun est un ensemble fini contenant les valeurs possibles de la variable .
  • Si contient seulement deux valeurs (par exemple 0 ou 1), alors est appelée une variable binaire .
• fonction de coût . C'est une fonction qui associe chaque affectation partielle possible à un coût. En général, seules quelques valeurs de sont différentes de zéro et elle est représentée sous la forme d'une liste de tuples auxquels est attribuée une valeur différente de zéro. Chaque tuple de ce type est appelé une contrainte . Chaque contrainte de cet ensemble est une fonction attribuant une valeur réelle à chaque affectation possible des variables. Voici quelques types particuliers de contraintes :
  • Contraintes unaires - contraintes sur une seule variable, c'est-à-dire pour un certain .
  • Contraintes binaires - contraintes sur deux variables, c'est-à-dire pour certains .
• fonction de propriété . C'est une fonction qui associe chaque variable à son agent associé. signifie que la variable « appartient » à l'agent . Cela implique qu'il est de la responsabilité de l'agent d'assigner la valeur de la variable . Notez qu'il ne s'agit pas nécessairement d'une injection , c'est-à-dire qu'un agent peut posséder plusieurs variables. Il ne s'agit pas non plus nécessairement d'une surjection , c'est-à-dire que certains agents peuvent ne posséder aucune variable.
• fonction objective . C'est un opérateur qui agrège tous les coûts individuels pour toutes les affectations de variables possibles. Cela se fait généralement par sommation :

L'objectif d'un DCOP est que chaque agent attribue des valeurs à ses variables associées afin de minimiser ou de maximiser une affectation donnée des variables.

Une affectation de valeur est une paire où est un élément du domaine .

Une affectation partielle est un ensemble d'affectations de valeurs où chacune apparaît au plus une fois. On l'appelle aussi contexte. On peut le considérer comme une fonction mappant les variables du DCOP à leurs valeurs actuelles : Notez qu'un contexte est essentiellement une solution partielle et n'a pas besoin de contenir des valeurs pour chaque variable du problème ; par conséquent, cela implique que l'agent n'a pas encore attribué de valeur à la variable . Étant donné cette représentation, le « domaine » (c'est-à-dire l'ensemble des valeurs d'entrée) de la fonction peut être considéré comme l'ensemble de tous les contextes possibles pour le DCOP. Par conséquent, dans le reste de cet article, nous pouvons utiliser la notion de contexte (c'est-à-dire la fonction) comme entrée de la fonction. f

Une affectation complète est une affectation dans laquelle chaque variable apparaît exactement une fois, c'est-à-dire que toutes les variables sont affectées. On l'appelle également solution du DCOP.

Une solution optimale est une affectation complète dans laquelle la fonction objective est optimisée (c'est-à-dire maximisée ou minimisée, selon le type de problème).

Différents problèmes de différents domaines peuvent être présentés sous forme de DCOP.

Le problème de coloration d'un graphe est le suivant : étant donné un graphe et un ensemble de couleurs , attribuez à chaque sommet , , une couleur, , telle que le nombre de sommets adjacents ayant la même couleur soit minimisé.

En tant que DCOP, il existe un agent par sommet qui est chargé de décider de la couleur associée. Chaque agent possède une seule variable dont le domaine associé est de cardinalité (il existe une valeur de domaine pour chaque couleur possible). Pour chaque sommet , il existe une variable de domaine . Pour chaque paire de sommets adjacents , il existe une contrainte de coût 1 si les deux variables associées sont affectées de la même couleur : L'objectif est alors de minimiser .

La variante multiple distribuée du problème du sac à dos est la suivante : étant donné un ensemble d'articles de volume variable et un ensemble de sacs à dos de capacité variable, assignez chaque article à un sac à dos de telle sorte que la quantité de débordement soit minimisée. Soit l'ensemble d'articles, soit l'ensemble de sacs à dos, soit une fonction associant les articles à leur volume, et soit une fonction associant les sacs à dos à leurs capacités.

Pour encoder ce problème en tant que DCOP, créez pour chaque variable une variable avec un domaine associé . Ensuite, pour tous les contextes possibles : où représente le poids total attribué par le contexte au sac à dos :

Le problème de répartition des éléments est le suivant. Il y a plusieurs éléments qui doivent être répartis entre plusieurs agents. Chaque agent a une évaluation différente des éléments. L'objectif est d'optimiser un objectif global, comme maximiser la somme des utilités ou minimiser l'envie. Le problème de répartition des éléments peut être formulé comme un DCOP comme suit.

• Ajoutez une variable binaire v _ij pour chaque agent i et élément j . La valeur de la variable est « 1 » si l'agent obtient l'élément, et « 0 » sinon. La variable appartient à l'agent i .
• Pour exprimer la contrainte que chaque élément est donné à au plus un agent, ajoutez des contraintes binaires pour chacune des deux variables différentes liées au même élément, avec un coût infini si les deux variables sont simultanément "1", et un coût nul sinon.
• Pour exprimer la contrainte selon laquelle tous les éléments doivent être alloués, ajoutez une contrainte n -aire pour chaque élément (où n est le nombre d'agents), avec un coût infini si aucune variable liée à cet élément n'est « 1 ».

Le DCOP a été appliqué à d’autres problèmes, tels que :

• coordination des capteurs mobiles ;
• planification des réunions et des tâches.

Les algorithmes DCOP peuvent être classés de plusieurs manières :

• Exhaustivité - algorithmes de recherche complets trouvant la solution optimale, par opposition aux algorithmes de recherche locale trouvant un optimum local .
• Stratégie de recherche - recherche du meilleur en premier ou recherche de branches et de limites en profondeur d'abord ;
• Synchronisation entre agents - synchrone ou asynchrone ;
• Communication entre agents - point à point avec voisins dans le graphe de contraintes, ou diffusion ;
• Topologie de communication - chaîne ou arbre.

ADOPT, par exemple, utilise la recherche du meilleur premier, la synchronisation asynchrone, la communication point à point entre les agents voisins dans le graphique de contraintes et un arbre de contraintes comme topologie de communication principale.

Il existe également des hybrides de ces algorithmes DCOP. BnB-Adopt, par exemple, modifie la stratégie de recherche d'Adopt en passant d'une recherche par le meilleur en premier à une recherche par branchement et limite en profondeur.

Un DCOP asymétrique est une extension du DCOP dans laquelle le coût de chaque contrainte peut être différent pour différents agents. Voici quelques exemples d'applications :

• Planification d'événements : les agents qui participent au même événement peuvent en tirer des valeurs différentes.
• Smart grid : l'augmentation du prix de l'électricité aux heures chargées peut être le fait de différents agents.

Une façon de représenter un ADCOP est de représenter les contraintes sous forme de fonctions :

Ici, pour chaque contrainte, il n'y a pas un coût unique mais un vecteur de coûts - un pour chaque agent impliqué dans la contrainte. Le vecteur de coûts est de longueur k si chaque variable appartient à un agent différent ; si deux ou plusieurs variables appartiennent au même agent, alors le vecteur de coûts est plus court - il y a un coût unique pour chaque agent impliqué , et non pour chaque variable.

Une façon simple de résoudre un ADCOP consiste à remplacer chaque contrainte par une contrainte égale à la somme des fonctions . Cependant, cette solution nécessite que les agents révèlent leurs fonctions de coût. Souvent, cela n'est pas souhaité en raison de considérations de confidentialité.

Une autre approche est appelée Private Events as Variables (PEAV). Dans cette approche, chaque variable possède, en plus de ses propres variables, également des « variables miroir » de toutes les variables possédées par ses voisins dans le réseau de contraintes. Il existe des contraintes supplémentaires (avec un coût infini) qui garantissent que les variables miroirs sont égales aux variables d'origine. L'inconvénient de cette méthode est que le nombre de variables et de contraintes est beaucoup plus grand que l'original, ce qui conduit à un temps d'exécution plus long.

Une troisième approche consiste à adapter les algorithmes existants, développés pour les DCOP, au cadre ADCOP. Cela a été fait pour les algorithmes de recherche complète et les algorithmes de recherche locale.

La structure d'un problème ADCOP est similaire au concept théorique de jeu simultané . Dans les deux cas, il y a des agents qui contrôlent des variables (dans la théorie des jeux, les variables sont les actions ou stratégies possibles des agents). Dans les deux cas, chaque choix de variables par les différents agents entraîne un gain différent pour chaque agent. Cependant, il existe une différence fondamentale :

• Dans un jeu simultané, les agents sont égoïstes : chacun d'eux veut maximiser sa propre utilité (ou minimiser son propre coût). Par conséquent, le meilleur résultat que l'on puisse rechercher dans un tel contexte est un équilibre , c'est-à-dire une situation dans laquelle aucun agent ne peut augmenter unilatéralement son propre gain.
• Dans un ADCOP, les agents sont considérés comme coopératifs : ils agissent selon le protocole même si cela diminue leur propre utilité. L'objectif est donc plus ambitieux : on souhaite maximiser la somme des utilités (ou minimiser la somme des coûts). Un équilibre de Nash correspond approximativement à un optimum local de ce problème, alors que l'on recherche un optimum global.

Il existe des modèles intermédiaires dans lesquels les agents sont partiellement coopératifs : ils sont prêts à diminuer leur utilité pour aider à l'objectif global, mais seulement si leur propre coût n'est pas trop élevé. Un exemple d'agents partiellement coopératifs sont les employés d'une entreprise. D'une part, chaque employé veut maximiser sa propre utilité ; d'autre part, ils veulent aussi contribuer au succès de l'entreprise. Par conséquent, ils sont prêts à aider les autres ou à effectuer d'autres tâches chronophages qui aident l'entreprise, tant que cela ne leur représente pas un fardeau trop lourd. Voici quelques modèles d'agents partiellement coopératifs :

• Bénéfice personnel garanti : les agents acceptent d'agir pour le bien global si leur propre utilité est au moins aussi élevée que dans le cadre non coopératif (c'est-à-dire que le résultat final doit être une amélioration de Pareto de l'état d'origine).
• Lambda-coopération : il existe un paramètre . Les agents acceptent d'agir pour le bien global si leur propre utilité est au moins aussi élevée que fois leur utilité non coopérative.

La résolution de tels ADCOP à coopération partielle nécessite des adaptations des algorithmes ADCOP.