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 ${\displaystyle \langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle }$, où:

• ${\displaystyle A}$ est un ensemble d' agents ;
• ${\displaystyle V}$ est un ensemble de variables, ${\displaystyle \{v_{1},v_{2},\cdots ,v_{|V|}\}}$ ;
• ${\displaystyle {\mathfrak {D}}}$ est un ensemble des domaines, ${\displaystyle \{D_{1},D_{2},\ldots ,D_{|V|}\}}$, où chaque ${\displaystyle D\in {\mathfrak {D}}}$ est un ensemble fini contenant les valeurs qui peuvent être affectées à la variable vi associée au domaine Di;
• ${\displaystyle f}$ est une fonction ^[1],[2] ${\displaystyle 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;
• ${\displaystyle \alpha }$ est une fonction ${\displaystyle \alpha :V\rightarrow A}$ qui associe les variables à l'agent qui leur est associé. ${\displaystyle \alpha (v_{i})\mapsto a_{j}}$ implique que l'agent ${\displaystyle a_{j}}$ a la responsabilité d'attribuer sa valeur à la variable ${\displaystyle v_{i}}$ . Notez qu'il n'est pas forcément vrai que ${\displaystyle \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
• ${\displaystyle \eta }$ est un opérateur qui agrège l'ensemble des fonctions ${\displaystyle 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: ${\displaystyle \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é) ${\displaystyle \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:

${\displaystyle 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 ${\displaystyle t(v_{i})\mapsto \emptyset }$ lorsque l'agent ${\displaystyle \alpha (v_{i})}$ n'a pas encore attribué de valeur à la variable ${\displaystyle v_{i}}$ . Compte tenu de cette représentation, le "domaine" (c'est-à-dire l'ensemble des valeurs d'entrée) de la fonction ${\displaystyle 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 ${\displaystyle t}$) comme entrée de la fonction ${\displaystyle f}$.

Exemples de problèmes

Coloration de graphique distribuée

Le problème de coloration de graphe est le suivant: étant donné un graphe ${\displaystyle G=\langle N,E\rangle }$ et un ensemble de couleurs ${\displaystyle C}$, on cherche à attribuer à chaque sommet du graphe ${\displaystyle n\subset N}$, une couleur, ${\displaystyle 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é ${\displaystyle |C|}$. Pour chaque sommet ${\displaystyle n_{i}\leq N}$, on crée dans le DCOP une variable ${\displaystyle v_{i}\in V}$ avec pour domaine domaine ${\displaystyle D_{i}=C}$ . Pour chaque paire de sommets adjacents ${\displaystyle \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:

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

L'objectif est ici de minimiser ${\displaystyle \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 ${\displaystyle I}$ l'ensemble des objets, ${\displaystyle K}$ l'ensemble des sacs à dos, ${\displaystyle s:I\rightarrow \mathbb {N} }$ une fonction qui associe les éléments à leur volume, et ${\displaystyle 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 ${\displaystyle i\in I}$ une variable ${\displaystyle v_{i}\in V}$ dont le domaine est ${\displaystyle D_{i}=K}$ . Puis pour tous les contextes possibles ${\displaystyle t}$ :

${\displaystyle 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ù ${\displaystyle r(t,k)}$ est une fonction telle que

${\displaystyle 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)^[3]. 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[4]	1997	Linéaire	Exponentiel	Complet	FRODO (GNU Affero GPL) pyDCOP (BSD-3)
AFB Asynchronous Forward Bounding[5]	2009	Linéaire	Exponentiel	Complet	FRODO (GNU Affero GPL)
ConcFB Concurrent Forward Bounding[6]	2012	Linéaire	Exponentiel	Complet	[réf. nécessaire]
Max-Sum[7]	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[8]	2004	Linéaire en le nombre de voisins	Linéaire	Incomplet	FRODO (GNU Affero GPL) pyDCOP (BSD-3)
DSA Distributed Stochastic Algorithm[9]	2005	Linéaire en le nombre de voisins	Linéaire	Incomplet	FRODO pyDCOP
D-Gibbs Distributed Gibbs[10]	2013	Linéaire en le nombre de voisins	Linéaire	Incomplet mais garantit une erreur d'approximation bornée	[réf. nécessaire]
NCBB No-Commitment Branch and Bound[11]	2006	Polynomial (ou any-space)[12]	Exponentiel	Complet	Implémentation de référence: indisponible publiquement DCOPolis (GNU LGPL)
DPOP Distributed Pseudotree Optimization Procedure[13]	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[14]	2004	Polynomial	Exponentiel	L'algorithme initial a été démontré incomplet[15], mais une autre version complète de l'algorithme existe [16]	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[17]	2003	Polynomial (ou any-space)[18]	Exponentiel	Complet	Implémentation de référence: Adopt DCOPolis (GNU LGPL) FRODO (GNU Affero GPL)
DBA Distributed Breakout Algorithm	1995	[réf. nécessaire]	[réf. nécessaire]	Note: incomplet mais rapide	FRODO (GNU Affero GPL)
AWC[réf. nécessaire] Asynchronous Weak-Commitment	1994	[réf. nécessaire]	[réf. nécessaire]	Note: reordonnancement, rapide, complet (seulement avec un espace exponentiel)	[réf. nécessaire]
ABT[réf. nécessaire] Asynchronous Backtracking	1992	[réf. nécessaire]	[réf. nécessaire]	Note: statique ordonnancement, complet	[réf. nécessaire]
CFL Communication-Free Learning[19]	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^[20] 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^[21], 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^[22], 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.

Voir aussi

• DisCSP
• Problème de satisfaction des contraintes
• Système multi-agents
• Optimisation

Livres et revues de littérature

• (en) Ferdinando Fioretto, Enrico Pontelli et William Yeoh, « Distributed constraint optimization problems and applications: A survey », Journal of Artificial Intelligence Research, vol. 61,‎ 2018, p. 623–698 (lire en ligne)
• (en) Boi Faltings, « Distributed Constraint Programming », Walsh, Toby (éd.) Handbook of Constraint Programming, Elsevier, vol. 2,‎ 2006, p. 699-729 (ISBN 978-0-444-52726-4, lire en ligne)
•  (en) Amnon Meisels, Distributed Search by Constrained Agents, Springer, 2008 (ISBN 978-1-84800-040-7, lire en ligne)
•  (en) Yoav Shoham et Kevin Leyton-Brown, Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge University Press, 2009 (ISBN 978-0-521-89943-7, lire en ligne), chap. 1 et 2.
•  (en) Makoto Yokoo, Distributed constraint satisfaction: Foundations of cooperation in multi-agent systems, Springer, 2001 (ISBN 978-3-540-67596-9, lire en ligne)
•  (en) Makoto Yokoo et Katsutoshi Hirayama, « Algorithms for distributed constraint satisfaction: A review », Autonomous Agents and Multiagent Systems, vol. 3, n^o 2,‎ 2000, p. 185–207 (lire en ligne)
• Gauthier Picard, Optimisation sous contraintes distribuée – une introduction. Tutoriel donné aux Journées Francophones sur les Systèmes Multi-Agents, 2018 [présentation en ligne]