Optimización de restricciones distribuidas

La optimización de restricciones distribuidas ( DCOP o DisCOP ) es el análogo distribuido de la optimización de restricciones . Un DCOP es un problema en el que un grupo de agentes debe elegir de forma distribuida valores para un conjunto de variables de modo que se minimice el costo de un conjunto de restricciones sobre las variables.

La satisfacción de restricciones distribuidas es un marco para describir un problema en términos de restricciones que son conocidas y aplicadas por distintos participantes (agentes). Las restricciones se describen sobre algunas variables con dominios predefinidos y deben ser asignadas a los mismos valores por los diferentes agentes.

Los problemas definidos con este framework se pueden resolver mediante cualquiera de los algoritmos que están diseñados para ello.

El marco se utilizó con diferentes nombres en los años 1980. El primer uso conocido con el nombre actual es en 1990. ^{[ cita necesaria ]}

Definiciones

DCOP

Los ingredientes principales de un problema DCOP son agentes y variables . Es importante destacar que cada variable es propiedad de un agente; esto es lo que hace que el problema se distribuya. Formalmente, un DCOP es una tupla , donde: ${\displaystyle \langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle }$

• ${\displaystyle A}$es el conjunto de agentes , . ${\displaystyle \{a_{1},\dots ,a_{|A|}\}}$
• ${\displaystyle V}$es el conjunto de variables , . ${\displaystyle \{v_{1},v_{2},\dots ,v_{|V|}\}}$
• ${\displaystyle {\mathfrak {D}}}$es el conjunto de dominios variables , , donde cada uno es un conjunto finito que contiene los valores posibles de la variable . ${\displaystyle \{D_{1},D_{2},\dots ,D_{|V|}\}}$ ${\displaystyle D_{j}\in {\mathfrak {D}}}$ ${\displaystyle v_{j}}$
  • Si contiene sólo dos valores (por ejemplo, 0 o 1), se denomina variable binaria . ${\displaystyle D_{j}\in {\mathfrak {D}}}$ ${\displaystyle v_{j}}$
• ${\displaystyle f}$es la función de costos . Es una función ^[1] que asigna cada posible asignación parcial a un costo. Por lo general, solo unos pocos valores de son distintos de cero y se representan como una lista de tuplas a las que se les asigna un valor distinto de cero. Cada una de estas tuplas se denomina restricción . Cada restricción de este conjunto es una función que asigna un valor real a cada posible asignación de las variables. Algunos tipos especiales de restricciones son: $${\displaystyle f:\bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}\to \mathbb {R} }$$ ${\displaystyle f}$ ${\displaystyle C}$ ${\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} }$
  • Restricciones unarias : restricciones sobre una sola variable, es decir, para algunas . ${\displaystyle f_{C}:D_{j}\to \mathbb {R} }$ ${\displaystyle v_{j}\in V}$
  • Restricciones binarias : restricciones sobre dos variables, es decir, para algunas . ${\displaystyle f_{C}:D_{j_{1}}\times D_{j_{2}}\to \mathbb {R} }$ ${\displaystyle v_{j_{1}},v_{j_{2}}\in V}$
• ${\displaystyle \alpha }$es la función de propiedad . Es una función que asigna cada variable a su agente asociado. significa que la variable "pertenece" al agente . Esto implica que es responsabilidad del agente asignar el valor de la variable . Tenga en cuenta que no es necesariamente una inyección , es decir, un agente puede poseer más de una variable. Tampoco es necesariamente una sobreyección , es decir, es posible que algunos agentes no posean variables. ${\displaystyle \alpha :V\to A}$ ${\displaystyle \alpha (v_{j})\mapsto a_{i}}$ ${\displaystyle v_{j}}$ ${\displaystyle a_{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle v_{j}}$ ${\displaystyle \alpha }$
• ${\displaystyle \eta }$es la función objetivo . Es un operador que agrega todos los costos individuales para todas las asignaciones variables posibles. Esto generalmente se logra mediante la suma: ${\displaystyle f}$ $${\displaystyle \eta (f)\mapsto \sum _{s\in \bigcup _{S\subseteq V}\times _{v_{j}\in S}D_{j}}f(s).}$$

El objetivo de un DCOP es que cada agente asigne valores a sus variables asociadas para minimizar o maximizar una asignación determinada de las variables. ${\displaystyle \eta (f)}$

Asignaciones

Una asignación de valor es un par donde hay un elemento del dominio . ${\displaystyle (v_{j},d_{j})}$ ${\displaystyle d_{j}}$ ${\displaystyle D_{j}}$

Una asignación parcial es un conjunto de asignaciones de valores donde cada una aparece como máximo una vez. También se le llama contexto. Esto puede considerarse como una función que asigna variables en el DCOP a sus valores actuales: tenga en cuenta que un contexto es esencialmente una solución parcial y no necesita contener valores para cada variable del problema; por lo tanto, implica que el agente aún no ha asignado un valor a la variable . Dada esta representación, el " dominio " (es decir, el conjunto de valores de entrada) de la función puede considerarse como el conjunto de todos los contextos posibles para el DCOP. Por lo tanto, en el resto de este artículo podemos usar la noción de contexto (es decir, la función) como entrada a la función. ${\displaystyle v_{j}}$ $${\displaystyle t:V\to (D\in {\mathfrak {D}})\cup \{\emptyset \}.}$$ ${\displaystyle t(v_{i})\mapsto \emptyset }$ ${\displaystyle \alpha (v_{i})}$ ${\displaystyle v_{i}}$f ${\displaystyle t}$ ${\displaystyle f}$

Una asignación completa es una asignación en la que cada una aparece exactamente una vez, es decir, se asignan todas las variables. También se le llama solución al DCOP. ${\displaystyle v_{j}}$

Una solución óptima es una tarea completa en la que la función objetivo está optimizada (es decir, maximizada o minimizada, según el tipo de problema). ${\displaystyle \eta (f)}$

Problemas de ejemplo

Se pueden presentar varios problemas de diferentes dominios como DCOP.

Coloración de gráficos distribuidos

El problema de coloración de gráficos es el siguiente: dado un gráfico y un conjunto de colores , asigna a cada vértice , un color, de modo que se minimice el número de vértices adyacentes con el mismo color. ${\displaystyle G=\langle N,E\rangle }$ ${\displaystyle C}$ ${\displaystyle n\subset N}$ ${\displaystyle c\leq C}$

Como DCOP, hay un agente por vértice que se asigna para decidir el color asociado. Cada agente tiene una única variable cuyo dominio asociado es de cardinalidad (hay un valor de dominio para cada color posible). Para cada vértice , hay una variable con dominio . Para cada par de vértices adyacentes , existe una restricción de costo 1 si a ambas variables asociadas se les asigna el mismo color: el objetivo, entonces, es minimizar . ${\displaystyle |C|}$ ${\displaystyle n_{i}\leq N}$ ${\displaystyle v_{i}\in V}$ ${\displaystyle D_{i}=C}$ ${\displaystyle \langle n_{i},n_{j}\rangle \in E}$ $${\displaystyle (\forall c\subseteq C:f(\langle v_{i},c\rangle ,\langle v_{j},c\rangle )\mapsto 1).}$$ ${\displaystyle \eta (f)}$

Problema de mochila múltiple distribuida

La variante múltiple distribuida del problema de la mochila es la siguiente: dado un conjunto de artículos de volumen variable y un conjunto de mochilas de capacidad variable, asigne cada artículo a una mochila de manera que se minimice la cantidad de desbordamiento. Sea el conjunto de artículos, sea el conjunto de mochilas, sea una función que asigna artículos a su volumen y sea una función que asigna mochilas a sus capacidades. ${\displaystyle I}$ ${\displaystyle K}$ ${\displaystyle s:I\to \mathbb {N} }$ ${\displaystyle c:K\to \mathbb {N} }$

Para codificar este problema como DCOP, para cada uno cree una variable con el dominio asociado . Luego, para todos los contextos posibles : donde representa el peso total asignado por contexto a la mochila : ${\displaystyle i\in I}$ ${\displaystyle v_{i}\in V}$ ${\displaystyle D_{i}=K}$ ${\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}}}$$ ${\displaystyle r(t,k)}$ ${\displaystyle t}$ ${\displaystyle k}$ $${\displaystyle r(t,k)=\sum _{v_{i}\in t^{-1}(k)}s(i).}$$

Problema de asignación de artículos distribuidos

El problema de asignación de artículos es el siguiente. Hay varios elementos que deben dividirse entre varios agentes. Cada agente tiene una valoración diferente de los artículos. El objetivo es optimizar algún objetivo global, como maximizar la suma de utilidades o minimizar la envidia. El problema de asignación de artículos se puede formular como un DCOP de la siguiente manera. ^[2]

• Agregue una variable binaria v _ij para cada agente i y elemento j . El valor de la variable es "1" si el agente obtiene el artículo y "0" en caso contrario. La variable es propiedad del agente i .
• Para expresar la restricción de que cada artículo se le da como máximo a un agente, agregue restricciones binarias para cada dos variables diferentes relacionadas con el mismo artículo, con un costo infinito si las dos variables son simultáneamente "1" y un costo cero en caso contrario.
• Para expresar la restricción de que se deben asignar todos los artículos, agregue una restricción n -aria para cada artículo (donde n es el número de agentes), con un costo infinito si ninguna variable relacionada con este artículo es "1".

Otras aplicaciones

DCOP se aplicó a otros problemas, como:

• coordinación de sensores móviles;
• programación de reuniones y tareas.

Algoritmos

Los algoritmos DCOP se pueden clasificar de varias maneras: ^[3]

• Integridad : algoritmos de búsqueda completos que encuentran la solución óptima, frente a algoritmos de búsqueda locales que encuentran un óptimo local .
• Estrategia de búsqueda : búsqueda de mejor primero o búsqueda de ramificación y límite de primero en profundidad;
• Sincronización entre agentes: síncrona o asíncrona;
• Comunicación entre agentes: punto a punto con vecinos en el gráfico de restricciones o transmisión;
• Topología de comunicación : cadena o árbol.

ADOPT, por ejemplo, utiliza la búsqueda "mejor primero", sincronización asíncrona, comunicación punto a punto entre agentes vecinos en el gráfico de restricciones y un árbol de restricciones como topología de comunicación principal.

También existen híbridos de estos algoritmos DCOP. BnB-Adopt, ^[3] por ejemplo, cambia la estrategia de búsqueda de Adopt de la mejor búsqueda primero a la búsqueda profunda, ramificada y limitada.

DCOP asimétrico

Un DCOP asimétrico es una extensión del DCOP en el que el costo de cada restricción puede ser diferente para diferentes agentes. Algunas aplicaciones de ejemplo son: ^[13]

• Programación de eventos : los agentes que asisten al mismo evento pueden obtener valores diferentes del mismo.
• Red inteligente : el incremento del precio de la electricidad en las horas de carga puede tener diferentes agentes.

Una forma de representar un ADCOP es representar las restricciones como funciones: $${\displaystyle f_{C}:D_{1}\times \dots \times D_{k}\to \mathbb {R} ^{k}}$$

Aquí, para cada restricción no hay un costo único sino un vector de costos: uno para cada agente involucrado en la restricción. El vector de costos es de longitud k si cada variable pertenece a un agente diferente; Si dos o más variables pertenecen al mismo agente, entonces el vector de costos es más corto: hay un costo único para cada agente involucrado , no para cada variable.

Enfoques para resolver un ADCOP

Una forma sencilla de resolver un ADCOP es reemplazar cada restricción con una restricción que sea igual a la suma de las funciones . Sin embargo, esta solución requiere que los agentes revelen sus funciones de costos. A menudo, esto no es deseable debido a consideraciones de privacidad. ^{[14] [15] [16]} ${\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}}$ ${\displaystyle f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R} }$ ${\displaystyle f_{C}^{1}+\cdots +f_{C}^{k}}$

Otro enfoque se llama Eventos privados como variables (PEAV). ^[17] En este enfoque, cada variable posee, además de sus propias variables, también "variables espejo" de todas las variables propiedad de sus vecinos en la red de restricciones. Existen restricciones adicionales (con un costo infinito) que garantizan que las variables espejo sean iguales a las variables originales. La desventaja de este método es que el número de variables y restricciones es mucho mayor que el original, lo que conduce a un mayor tiempo de ejecución.

Un tercer enfoque consiste en adaptar los algoritmos existentes, desarrollados para DCOP, al marco ADCOP. Esto se ha hecho tanto para algoritmos de búsqueda completa como para algoritmos de búsqueda local. ^[13]

Comparación con juegos estratégicos.

La estructura de un problema ADCOP es similar al concepto de juego simultáneo de la teoría de juegos . En ambos casos, hay agentes que controlan las variables (en la teoría de juegos, las variables son las posibles acciones o estrategias de los agentes). En ambos casos, cada elección de variables por parte de los diferentes agentes da como resultado una recompensa diferente para cada agente. Sin embargo, hay una diferencia fundamental: ^[13]

• En un juego simultáneo, los agentes son egoístas: cada uno de ellos quiere maximizar su propia utilidad (o minimizar su propio coste). Por lo tanto, el mejor resultado que se puede buscar en tal situación es un equilibrio : una situación en la que ningún agente puede aumentar unilateralmente su propia ganancia.
• En una ADCOP, los agentes se consideran cooperativos: actúan según el protocolo incluso si éste disminuye su propia utilidad. Por tanto, el objetivo es más desafiante: nos gustaría maximizar la suma de las utilidades (o minimizar la suma de los costos). Un equilibrio de Nash corresponde aproximadamente a un óptimo local de este problema, mientras que buscamos un óptimo global.

Cooperación parcial

Hay algunos modelos intermedios en los que los agentes son parcialmente cooperativos : están dispuestos a disminuir su utilidad para ayudar al objetivo global, pero sólo si su propio costo no es demasiado alto. Un ejemplo de agentes parcialmente cooperativos son los empleados de una empresa. Por un lado, cada empleado quiere maximizar su propia utilidad; por otro lado, también quieren contribuir al éxito de la empresa. Por lo tanto, están dispuestos a ayudar a otros o realizar otras tareas que requieren mucho tiempo y que ayudan a la empresa, siempre que no les resulte demasiado gravoso. Algunos modelos para agentes parcialmente cooperativos son: ^[18]

• Beneficio personal garantizado : los agentes acuerdan actuar por el bien global si su propia utilidad es al menos tan alta como en el entorno no cooperativo (es decir, el resultado final debe ser una mejora de Pareto del estado original).
• Cooperación lambda : hay un parámetro . Los agentes acuerdan actuar por el bien global si su propia utilidad es al menos tan alta como su utilidad no cooperativa. ${\displaystyle \lambda \in [0,1]}$ ${\displaystyle (1-\lambda )}$

Resolver estos ADCOP de cooperación parcial requiere adaptaciones de los algoritmos ADCOP. ^[18]

Ver también

• Problema de satisfacción de restricciones
• Algoritmo distribuido
• Diseño de mecanismo algorítmico distribuido.

notas y referencias

1. " " o "×" denota el producto cartesiano . ${\displaystyle \times }$
2. Netzer, Arnón; Meisels, Amnón; Zivan, Roie (1 de marzo de 2016). "Minimización de la envidia distribuida para la asignación de recursos". Agentes Autónomos y Sistemas Multiagente . 30 (2): 364–402. doi :10.1007/s10458-015-9291-7. ISSN  1387-2532. S2CID  13834856.
3. Sí, William; Felner, Ariel; Koenig, Sven (2008), "BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm", Actas de la Séptima Conferencia Internacional Conjunta sobre Agentes Autónomos y Sistemas Multiagentes , vol. 2, págs. 591–8, ISBN 9780981738116
4. Hirayama, Katsutoshi; Yokoo, Makoto (1997). "Problema de satisfacción de restricciones parciales distribuidas". En Smolka, Gert (ed.). Principios y práctica de la programación con restricciones-CP97 . Apuntes de conferencias sobre informática. vol. 1330. Berlín, Heidelberg: Springer. págs. 222-236. doi :10.1007/BFb0017442. ISBN 978-3-540-69642-1.
5. La versión publicada originalmente de Adopt no estaba informada, ver Modi, Pragnesh Jay; Shen, Wei-Min; Tambe, Milind; Yokoo, Makoto (2003), "Un método completo asíncrono para la optimización de restricciones distribuidas" (PDF) , Actas de la segunda conferencia conjunta internacional sobre agentes autónomos y sistemas multiagente , ACM Press, págs. 161-168, archivado desde el original (PDF) ) el 4 de noviembre de 2019 , consultado el 7 de septiembre de 2009. La versión original de Adopt se amplió posteriormente para ser informada, es decir, utilizar estimaciones de los costos de la solución para enfocar su búsqueda y ejecutarla más rápido, ver Ali, Syed; König, Sven; Tambe, Milind (2005), "Técnicas de preprocesamiento para acelerar el algoritmo DCOP ADOPT" (PDF) , Actas de la cuarta conferencia conjunta internacional sobre agentes autónomos y sistemas multiagente , ACM Press, págs. 1041–8, doi :10.1145/1082473.1082631, ISBN 1595930930, S2CID  10882572, archivado desde el original (PDF) el 7 de julio de 2010 , consultado el 7 de septiembre de 2009. Esta extensión de Adopt se utiliza normalmente como implementación de referencia de Adopt.
6. Matsui, Toshihiro; Matsuo, Hiroshi; Iwata, Akira (febrero de 2005), "Método eficiente para el algoritmo de optimización de restricciones distribuidas asincrónicas" (PDF) , Actas de aplicaciones e inteligencia artificial , págs. 727–732, CiteSeerX 10.1.1.408.7230 
7. Mailer, Roger; Lesser, Victor (2004), "Resolver problemas de optimización de restricciones distribuidas mediante mediación cooperativa" (PDF) , Actas de la Tercera Conferencia Conjunta Internacional sobre Agentes Autónomos y Sistemas Multiagente , IEEE Computer Society , págs. 438–445, ISBN 1581138644^{[ enlace muerto permanente ]}
8. Grinshpoun, Tal; Zazón, Moshé; Binshtok, Maxim; Meisels, Amnon (2007), "Problema de terminación del algoritmo APO" (PDF) , Actas del octavo taller internacional sobre razonamiento de restricciones distribuidas , págs.
9. Petcu, Adrián; Faltings, Boi (agosto de 2005), "DPOP: A Scalable Method for Multiagent Constraint Optimization", Actas de la 19ª Conferencia Internacional Conjunta sobre Inteligencia Artificial, IJCAI 2005, Edimburgo, Escocia, págs. 266-271
10. Chechetka, Antón; Sycara, Katia (mayo de 2006), "No-Commitment Branch and Bound Search for Distributed Constraint Optimization" (PDF) , Actas de la Quinta Conferencia Internacional Conjunta sobre Agentes Autónomos y Sistemas Multiagentes , págs. 1427–9, doi :10.1145/1160633.1160900 , ISBN 1595933034, S2CID  43918609
11. Chechetka, Antón; Sycara, Katia (marzo de 2006), "Un algoritmo de cualquier espacio para la optimización de restricciones distribuidas" (PDF) , Actas del Simposio de primavera de la AAAI sobre gestión distribuida de planes y cronogramas
12. Duffy, KR; Leith, DJ (agosto de 2013), "Satisfacción de restricciones descentralizadas", IEEE/ACM Transactions on Networking , 21 (4): 1298–1308, arXiv : 1103.3240 , doi : 10.1109/TNET.2012.2222923, S2CID  11504393
13. Grinshpoun, T .; Grubstein, A.; Zivan, R.; Netzer, A.; Meisels, A. (30 de julio de 2013). "Problemas de optimización de restricciones distribuidas asimétricas". Revista de investigación en inteligencia artificial . 47 : 613–647. arXiv : 1402.0587 . doi : 10.1613/jair.3945 . ISSN  1076-9757.
14. Greenstadt, Raquel; Pearce, Jonathan P.; Tambe, Milind (16 de julio de 2006). "Análisis de la pérdida de privacidad en la optimización de restricciones distribuidas". Actas de la XXI Conferencia Nacional sobre Inteligencia Artificial - Volumen 1 . AAAI'06. Boston, Massachusetts: Prensa AAAI: 647–653. ISBN 978-1-57735-281-5.
15. Maheswaran, Rajiv T.; Pearce, Jonathan P.; Arqueándose, Emma; Varakantham, Pradeep; Tambe, Milind (1 de julio de 2006). "Pérdida de privacidad en el razonamiento de restricciones distribuidas: un marco cuantitativo para el análisis y sus aplicaciones". Agentes Autónomos y Sistemas Multiagente . 13 (1): 27–60. doi :10.1007/s10458-006-5951-y. ISSN  1573-7454. S2CID  16962945.
16. Yokoo, Makoto; Suzuki, Koutaro; Hirayama, Katsutoshi (2002). "Satisfacción segura con restricciones distribuidas: llegar a un acuerdo sin revelar información privada". En Van Hentenryck, Pascal (ed.). Principios y práctica de la programación de restricciones - CP 2002 . Apuntes de conferencias sobre informática. vol. 2470. Berlín, Heidelberg: Springer. págs. 387–401. doi :10.1007/3-540-46135-3_26. ISBN 978-3-540-46135-7.
17. Rajiv T. Maheswaran, Milind Tambe, Emma Bowring, Jonathan P. Pearce, Pradeep Varakantham (2004). "Llevando DCOP al mundo real: soluciones completas y eficientes para la programación distribuida de múltiples eventos". www.computer.org . Consultado el 12 de abril de 2021 .{{cite web}}: CS1 maint: multiple names: authors list (link)
18. Zivan, Roie; Grubstein, Alon; Friedman, Michal; Meisels, Amnón (4 de junio de 2012). "Cooperación parcial en búsqueda multiagente". Actas de la XI Conferencia Internacional sobre Agentes Autónomos y Sistemas Multiagente - Volumen 3 . AAMAS '12. 3 . Valencia, España: Fundación Internacional para Agentes Autónomos y Sistemas Multiagente: 1267–1268. ISBN 978-0-9817381-3-0.

Libros y encuestas

• Fioretto, Fernando; Pontelli, Enrico; Yeoh, William (2018), "Problemas y aplicaciones de optimización de restricciones distribuidas: una encuesta", Journal of Artificial Intelligence Research , 61 : 623–698, arXiv : 1602.06347 , doi : 10.1613/jair.5565, S2CID  4503761
• Faltings, Boi (2006), "Programación con restricciones distribuidas", en Walsh, Toby (ed.), Manual de programación con restricciones , Elsevier , ISBN 978-0-444-52726-4Un capítulo de un libro editado.
• Meisels, Amnon (2008), Búsqueda distribuida por agentes restringidos , Springer , ISBN 978-1-84800-040-7
• Shoham, Yoav; Leyton-Brown, Kevin (2009), Sistemas multiagente: fundamentos lógicos, algorítmicos y de teoría de juegos, Nueva York: Cambridge University Press , ISBN 978-0-521-89943-7Véanse los Capítulos 1 y 2; descargable gratis en línea.
• Yokoo, Makoto (2001), Satisfacción de restricciones distribuidas: fundamentos de la cooperación en sistemas multiagente , Springer , ISBN 978-3-540-67596-9
• Yokoo, M. Hirayama K. (2000), "Algoritmos para la satisfacción de restricciones distribuidas: una revisión", Agentes autónomos y sistemas multiagente , 3 (2): 185–207, doi :10.1023/A:1010078712316, S2CID  2139298