Optimisation sous contraintes distribuée
# Optimisation sous contraintes distribuée

L'optimisation sous contraintes distribuées (en anglais Distributed Constraint Optimization Problem, DCOP ou DisCOP) est l'alter ego distribué de l'optimisation sous contraintes. Un DCOP est un problème dans lequel un groupe d'agents doit choisir de manière décentralisée des valeurs pour un ensemble de variables de manière à minimiser une fonction de coût ou à maximiser une fonction d'utilité.

La Satisfaction de Contraintes Distribuée (parfois appelée Distributed Constraint Satisfaction Problem, DCSP ou DisCSP) est une formalisation permettant d'écrire un problème en termes de contraintes qui sont connues et doivent être respectées par les participants (agents). Les contraintes s'appliquent à certaines variables, notamment à travers la définition de domaines prédéfinis en dehors desquelles les variables ne sont pas définies.

Les problèmes définis dans ce formalisme peuvent être résolus par n'importe lequel des algorithmes qui lui sont associés.

## Définitions

### DCOP

Un DCOP peut être défini comme un tuple $\langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle$, où:

* $A$ est un ensemble d' agents ;
* $V$ est un ensemble de variables, $\{v_{1},v_{2},\cdots ,v_{|V|}\}$ ;
* ${\mathfrak {D}}$ est un ensemble des domaines, $\{D_{1},D_{2},\ldots ,D_{|V|}\}$, où chaque $D\in {\mathfrak {D}}$ est un ensemble fini contenant les valeurs qui peuvent être affectées à la variable vi associée au domaine Di;
* $f$ est une $fonction^,$ $f:\bigcup _{S\in {\mathfrak {P}}(V)}\sum {v_{i}\in S}\left(\{v_{i}\}\times D_{i}\right)\rightarrow \mathbb {R} \cup \{\bot \}$ qui associe chaque affectation de variable possible à un coût ou une utilité. Cette fonction peut également être considérée comme définissant des contraintes entre les variables, mais les variables ne doivent pas être hermitiennes;
* $\alpha$ est une fonction $\alpha :V\rightarrow A$ qui associe les variables à l'agent qui leur est associé. $\alpha (v_{i})\mapsto a_{j}$ implique que l'agent $a_{j}$ a la responsabilité d'attribuer sa valeur à la variable $v_{i}$ . Notez qu'il n'est pas forcément vrai que $\alpha$ est une injection ou une surjection (i.e. un agent peut être responsable de plusieurs variables, ou d'aucune mais une variable n'est sous la responsabilité que d'un seul agent); et
* $\eta$ est un opérateur qui agrège l'ensemble des fonctions $f$ de coût ou d'utilité pour toutes les valeurs possibles (i.e. respectant leurs domaines) des variables. Cette fonction est généralement une somme: $\eta (f)\mapsto \sum _{s\in \bigcup _{S\in {\mathfrak {P}}(V)}\sum {v_{i}\in S}\left(\{v_{i}\}\times D_{i}\right)}f(s)$ .

L'objectif d'un DCOP est que chaque agent attribue des valeurs aux variables qui lui sont associées afin que l'affectation globale de l'ensemble des variables minimise (ou de maximise dans le cas des fonctions d'utilité) $\eta (f)$.

### Contexte

Un contexte est une affectation d'une variable dans un DCOP. Il peut être considéré comme une fonction associant les variables du DCOP à leurs valeurs actuelles:

$t:V\rightarrow (D\in {\mathfrak {D}})\cup \{\emptyset \}.$

Notons qu'un contexte est essentiellement une solution partielle et n'a pas besoin de contenir des valeurs pour chaque variable du problème; on note donc $t(v_{i})\mapsto \emptyset$ lorsque l'agent $\alpha (v_{i})$ n'a pas encore attribué de valeur à la variable $v_{i}$ . Compte tenu de cette représentation, le "domaine" (c'est-à-dire l'ensemble des valeurs d'entrée) de la fonction $f$ peut être considéré comme l'ensemble de tous les contextes possibles pour le DCOP. Par conséquent, dans le reste de cet article, on utilisera la notion de contexte (c'est-à-dire la fonction $t$) comme entrée de la fonction $f$.

## Exemples de problèmes

### Coloration de graphique distribuée

Le problème de coloration de graphe est le suivant: étant donné un graphe $G=\langle N,E\rangle$ et un ensemble de couleurs $C$, on cherche à attribuer à chaque sommet du graphe $n\subset N$, une couleur, $c\leq C$ de manière que le nombre de sommets adjacents de même couleur soit minimisé.

Dans la formalisation DCOP du problème, on considère qu'il y a un agent par sommet, et qu'il a la responsabilité de décider de la couleur associée à ce sommet. Chaque agent a une seule variable (le sommet dont il est responsable) dont le domaine associé est l'ensemble des couleurs, de cardinalité $|C|$. Pour chaque sommet $n_{i}\leq N$, on crée dans le DCOP une variable $v_{i}\in V$ avec pour domaine domaine $D_{i}=C$ . Pour chaque paire de sommets adjacents $\langle n_{i},n_{j}\rangle \in E$, on ajoute une contrainte de coût 1 si les deux variables associées ont la même couleur:

$(\forall c\subseteq C:f(\langle v_{i},c\rangle ,\langle v_{j},c\rangle )\mapsto 1).$

L'objectif est ici de minimiser $\eta (f)$ .

### Problème distribué des sacs à dos multiples

Le problème du sac à dos multiple est une variante du problème du sac à dos où: étant donné un ensemble d'objets de volume variable et un ensemble de sacs à dos de capacité variable, on cherche à attribuer à chaque objet à un sac à dos de manière à minimiser le débordement des sacs. Soit $I$ l'ensemble des objets, $K$ l'ensemble des sacs à dos, $s:I\rightarrow \mathbb {N}$ une fonction qui associe les éléments à leur volume, et $c:K\rightarrow \mathbb {N}$ une fonction associant les sacs à dos à leurs capacités.

Pour formaliser ce problème sous la forme d'un DCOP, on crée pour chaque $i\in I$ une variable $v_{i}\in V$ dont le domaine est $D_{i}=K$ . Puis pour tous les contextes possibles $t$ :

$f(t)\mapsto \sum _{k\in K}{\begin{cases}0&r(t,k)\leq c(k),\\r(t,k)-c(k)&{\text{otherwise}},\end{cases}}$

où $r(t,k)$ est une fonction telle que

$r(t,k)=\sum _{v_{i}\in t^{-1}(k)}s(i).$

## Algorithmes

Les algorithmes DCOP peuvent être classés en fonction de la stratégie de recherche (algorithme de recherche best-first ou parcours en profondeur avec séparation et évaluation), de la synchronisation du protocole (synchrone ou asynchrone), de la communication entre agents (pair à pair avec ses voisins dans le graphe de contraintes ou diffusion à tous les autres) et de la topologie de communication principale (chaîne ou arborescence). ADOPT utilise par exemple un algorithme de recherche best-first asynchrone avec une communication pair à pair entre les agents voisins dans le graphe de contraintes, et une arborescence de contraintes comme topologie de communication principale.

| Nom de l'algorithme | Année | Complexité en mémoire | Nombre de messages | Correction/Complétude | Implémentations |
| - | - | - | - | - | - |
| SynchBB Synchronous Branch-and-Bound | 1997 | Linéaire | Exponentiel | Complet | FRODO (GNU Affero GPL) pyDCOP (BSD-3) |
| AFB Asynchronous Forward Bounding | 2009 | Linéaire | Exponentiel | Complet | FRODO (GNU Affero GPL) |
| ConcFB Concurrent Forward Bounding | 2012 | Linéaire | Exponentiel | Complet | |
| Max-Sum | 2008 | Exponentiel en le nombre moyen de voisins de l'agent | Linéaire | Incomplet, très rapide | FRODO (GNU Affero GPL) pyDCOP (BSD-3) |
| MGM Maximum Gain Message | 2004 | Linéaire en le nombre de voisins | Linéaire | Incomplet | FRODO (GNU Affero GPL) pyDCOP (BSD-3) |
| DSA Distributed Stochastic Algorithm | 2005 | Linéaire en le nombre de voisins | Linéaire | Incomplet | FRODO pyDCOP |
| D-Gibbs Distributed Gibbs | 2013 | Linéaire en le nombre de voisins | Linéaire | Incomplet mais garantit une erreur d'approximation bornée | |
| NCBB No-Commitment Branch and Bound | 2006 | Polynomial (ou any-space) | Exponentiel | Complet | Implémentation de référence: indisponible publiquement DCOPolis (GNU LGPL) |
| DPOP Distributed Pseudotree Optimization Procedure | 2005 | Exponentiel | Linéaire | Complet | Implémentation de référence: FRODO (GNU Affero GPL) pyDCOP (BSD-3) DCOPolis (GNU LGPL) |
| OptAPO Asynchronous Partial Overlay | 2004 | Polynomial | Exponentiel | L'algorithme initial a été démontré incomplet, mais une autre version complète de l'algorithme existe | Implémentation de référence: « OptAPO » [archive du 15 juillet 2007], Artificial Intelligence Center, SRI InternationalArtificial Intelligence Center. SRI International. Archived from the original on 2007-07-15. DCOPolis (GNU LGPL); en cours de développement |
| Adopt Asynchronous Backtracking | 2003 | Polynomial (ou any-space) | Exponentiel | Complet | Implémentation de référence: Adopt DCOPolis (GNU LGPL) FRODO (GNU Affero GPL) |
| DBA Distributed Breakout Algorithm | 1995 | | | Note: incomplet mais rapide | FRODO (GNU Affero GPL) |
| AWC Asynchronous Weak-Commitment | 1994 | | | Note: reordonnancement, rapide, complet (seulement avec un espace exponentiel) | |
| ABT Asynchronous Backtracking | 1992 | | | Note: statique ordonnancement, complet | |
| CFL Communication-Free Learning | 2013 | Lineaire | None Note: aucun message n'est envoyé; l'lagorithme repose sur la connaissance de la satisfactoin de contraintes locales | Incomplet | |

Des versions hybrides de ces algorithmes DCOP existent également. BnB-Adopt par exemple, modifie la stratégie de recherche d'Adopt passant d'un algorithme de recherche best-search à un algorithme de séparation et évaluation.

## Logiciels de simulation

Les logiciels de simulation DCOP permettent de formaliser un problème dans un format prédéterminé puis de choisir l'algorithme qui y sera appliqué dans une librairie rassemblant un certain nombre d'algorithmes. Deux plates-formes sont principalement utilisées: une bibliothèque écrite en Java, FRODO 2, sous licence GNU Affero General Public License, propose une interface pour Java, avec un module permettant de faire appel à la bibliothèque depuis python. Elle propose une bibliothèque de 16 algorithmes, notamment ADOPT, DPOP et des variantes, SynchBB, DSA, Max-Sum et MGM. La seconde plate-forme est pyDCOP, une bibliothèque écrite en python pour python par Orange (entreprise) sous licence Open Source BSD-3. pyDCOP inclut 13 algorithmes, notamment Max-Sum et des variantes, DSA et des variantes, DPOP, MGM et SynchBB. pyDCOP propose aussi une librairie permettant de déployre les algorithmes de manière décentralisée sur de l'IoT.

