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 , où:
- est un ensemble d' agents ;
- est un ensemble de variables, ;
- est un ensemble des domaines, , où chaque est un ensemble fini contenant les valeurs qui peuvent être affectées à la variable vi associée au domaine Di;
- est une fonction [1] - [2]
- est une fonction qui associe les variables à l'agent qui leur est associé. implique que l'agent a la responsabilité d'attribuer sa valeur à la variable . Notez qu'il n'est pas forcément vrai que 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
- est un opérateur qui agrège l'ensemble des fonctions 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:
.
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é) .
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:
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 lorsque l'agent n'a pas encore attribué de valeur à la variable . Compte tenu de 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, on utilisera la notion de contexte (c'est-à -dire la fonction ) comme entrée de la fonction .
Exemples de problèmes
Coloration de graphique distribuée
Le problème de coloration de graphe est le suivant: étant donné un graphe et un ensemble de couleurs , on cherche à attribuer à chaque sommet du graphe , une couleur, 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é . Pour chaque sommet , on crée dans le DCOP une variable avec pour domaine domaine . Pour chaque paire de sommets adjacents , on ajoute une contrainte de coût 1 si les deux variables associées ont la même couleur:
L'objectif est ici de minimiser .
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 l'ensemble des objets, l'ensemble des sacs à dos, une fonction qui associe les éléments à leur volume, et 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 une variable dont le domaine est . Puis pour tous les contextes possibles :
où est une fonction telle que
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 | |
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 |
D-Gibbs
Distributed Gibbs[10] |
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[11] |
2006 | Polynomial (ou any-space)[12] | Exponentiel | Complet | Implémentation de référence: indisponible publiquement |
DPOP Distributed Pseudotree Optimization Procedure[13] |
2005 | Exponentiel | Linéaire | Complet | Implémentation de référence: FRODO (GNU Affero GPL) |
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 ], Artificial Intelligence Center, SRI InternationalArtificial Intelligence Center. SRI International. Archived from the original on 2007-07-15. |
Adopt Asynchronous Backtracking[17] |
2003 | Polynomial (ou any-space)[18] | Exponentiel | Complet | Implémentation de référence: Adopt |
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[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.
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,‎ , p. 623–698 (lire en ligne)
- (en) Boi Faltings, « Distributed Constraint Programming », Walsh, Toby (éd.) Handbook of Constraint Programming, Elsevier, vol. 2,‎ , p. 699-729 (ISBN 978-0-444-52726-4, lire en ligne)
- (en) Amnon Meisels, Distributed Search by Constrained Agents, Springer, (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, (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, (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, no 2,‎ , 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]
Notes et références
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Distributed constraint optimization » (voir la liste des auteurs).
- "" représente l'Ensemble des parties de
- "" et "" représente le produit cartésien.
- (en) Yeoh, William, Felner, Ariel et Koenig, Sven, « BnB-ADOPT: An asynchronous branch-and-bound DCOP algorithm », Journal of Artificial Intelligence Research, vol. 38,‎ , p. 85–133 (lire en ligne)
- (en) Katsutoshi Hirayama et Makoto Yokoo, « Distributed partial constraint satisfaction problem », International conference on principles and practice of constraint programming, Springer, Berlin, Heidelberg,‎ (lire en ligne)
- (en) Amir Gershman, Amnon Meisels et Roie Zivan, « Asynchronous forward bounding for distributed COPs », Journal of Artificial Intelligence Research, vol. 34,‎ , p. 61–88
- (en) Arnon Netzer, Alon Grubshtein et Amnon Meisels, « Concurrent forward bounding for distributed constraint optimization problems », Artificial Intelligence,‎ , p. 186–2016 (lire en ligne)
- (en) Alessandro Farinelli, Alex Rogers, Adrian Petcu et Nick R. Jennings, « Decentralised coordination of low-power embedded devices using the max-sum algorithm », Proceedings of the International Conference onAutonomous Agents and Multiagent System,‎ , p. 639–646 (lire en ligne)
- (en) Rajiv T. Maheswaran, Jonathan P. Pearce et Milind Tambe, « Distributed Algorithms for DCOP: A Graphical-Game-Based Approach », Proceedings of the International Conference on Parallel and Distributed Com-puting System,‎ , p. 432–439 (lire en ligne)
- (en) Weixiong Zhang, Guandong Wang, Zhao Xing et Lars Wittenburg, « Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks », Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks, vol. 161, nos 1-2,‎ , p. 55–87 (lire en ligne)
- (en) Duc Thien Nguyen, William Yeoh et Hoong Chuin Lau, « Distributed Gibbs: A memory-bounded sampling-based DCOP algorithm », Proceedings of the International Conference on Autonomous Agents and Multi-agent System,‎ , p. 167–174 (lire en ligne)
- (en) Chechetka, Anton et Sycara, Katia P, « No-commitment branch and bound search for distributed constraint optimization », Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems,‎ , p. 1427–1429 (lire en ligne)
- (en) Chechetka, Anton et Sycara, Katia P, « An Any-space Algorithm for Distributed Constraint Optimization », AAAI Spring Symposium: Distributed Plan and Schedule Management,‎ , p. 33–40 (lire en ligne)
- (en) Adrian Petcu et Boi Faltings, « A scalable method for multiagent constraint optimization », Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence,‎ , p. 266-271 (lire en ligne)
- (en) Roger Mailler et Victor Lesser, « Solving Distributed Constraint Optimization Problems Using Cooperative Mediation », Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, IEEE Computer Society,‎ , p. 438–445 (ISBN 1581138644, lire en ligne)
- (en) Tal Grinshpoun, Moshe Zazon, Maxim Binshtok et Amnon Meisels, « Termination Problem of the APO Algorithm », Proceedings of the Eighth International Workshop on Distributed Constraint Reasoning,‎ , p. 117–124 (lire en ligne)
- (en) Tal Grinshpoun et Amnon Meisels, « Completeness and performance of the APO algorithm », Journal of Artificial Intelligence Research,‎ , p. 223–258 (lire en ligne)
- La version initiale d'Adopt n''utilisait pas d'heuristique voir Modi, Pragnesh Jay; Shen, Wei-Min; Tambe, Milind; Yokoo, Makoto (2003), "An asynchronous complete method for distributed constraint optimization", Proceedings of the second international joint conference on autonomous agents and multiagent systems, ACM Press, pp. 161–168. Une seconde version voir Ali, Syed; Koenig, Sven; Tambe, Milind (2005), "Preprocessing Techniques for Accelerating the DCOP Algorithm ADOPT" (PDF), Proceedings of the fourth international joint conference on autonomous agents and multiagent systems, ACM Press, pp. 1041–8, doi:10.1145/1082473.1082631, (ISBN 1595930930), S2CID 10882572 a ensuite été développée; dans cette version, l'algorithme utilise une heuristique basée sur des estimations des coûts des solutions explorées. C'est généralement cette implémentation qui fait foi lorsqu'il est question d'Adopt.
- (en) Toshihiro Matsui, Hiroshi Matsuo et Akira Iwata, « Efficient Method for Asynchronous Distributed Constraint Optimization Algorithm », Proceedings of Artificial Intelligence and Applications,‎ , p. 727–732 (lire en ligne)
- (en) Ken R. Duffy, Charles Bordenave et Douglas J. Leith, « Decentralized Constraint Satisfaction", IEEE/ACM Transactions on Networking », IEEE/ACM Transactions on Networking, vol. 21, no 4,‎ , p. 1298–1308 (lire en ligne)
- (en) William yeoh, Ariel Felner et Sven Koenig, « BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm », Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multiagent Systems, vol. 38, no 2,‎ , p. 591–598 (ISBN 9780981738116, lire en ligne)
- (en) Thomas Léauté, Brammert Ottens et Radoslaw Szymanek, « FRODO 2.0: An open-source framework for distributed constraint optimization », Proceedings of the IJCAI'09 Distributed Constraint Reasoning Workshop (DCR'09),‎ , p. 160–164 (lire en ligne)
- (en) Pierre Rust, Gauthier Picard et Fano Ramparany, « pyDCOP: a DCOP library for Dynamic IoT Systems », International Workshop on Optimisation in Multi-Agent Systems,‎ (lire en ligne)