Optimización de restricciones distribuidas

La optimización distribuida por restricciones ( DCOP o DisCOP ) es el análogo distribuido de la optimización por restricciones . Una 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 coste de un conjunto de restricciones sobre las variables.

La satisfacción distribuida de restricciones 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 en algunas variables con dominios predefinidos y los diferentes agentes deben asignarles los mismos valores.

Los problemas definidos con este marco pueden resolverse mediante cualquiera de los algoritmos diseñados para él.

El marco se utilizó con diferentes nombres en la década de 1980. El primer uso conocido con el nombre actual es de 1990. ^{[ cita requerida ]}

Definiciones

DPO

Los principales componentes de un problema DCOP son los agentes y las variables . Es importante destacar que cada variable es propiedad de un agente; esto es lo que hace que el problema sea distribuido. 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 posibles valores 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), entonces se denomina variable binaria . ${\displaystyle D_{j}\in {\mathfrak {D}}}$ ${\displaystyle v_{j}}$
• ${\displaystyle f}$es la función de costo . Es una función ^[1] que asigna cada asignación parcial posible a un costo. Por lo general, solo unos pocos valores de son distintos de cero, y se representa como una lista de las 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 asignación posible 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 algún . ${\displaystyle f_{C}:D_{j}\to \mathbb {R} }$ ${\displaystyle v_{j}\in V}$
  • Restricciones binarias : restricciones sobre dos variables, es decir, para algún . ${\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, algunos agentes pueden no poseer 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 de variables posibles. Esto se logra generalmente 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)}$

Tareas

Una asignación de valor es un par donde es 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 denomina contexto. Esto puede considerarse como una función que asigna variables en el DCOP a sus valores actuales: Nótese que un contexto es esencialmente una solución parcial y no necesita contener valores para cada variable en el 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 un contexto (es decir, la función) como una 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 denomina solución al DCOP. ${\displaystyle v_{j}}$

Una solución óptima es una asignación completa en la que la función objetivo se optimiza (es decir, se maximiza o se minimiza, dependiendo del tipo de problema). ${\displaystyle \eta (f)}$

Problemas de ejemplo

Se pueden presentar como DCOP diversos problemas de distintos dominios.

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 , asigne a cada vértice , , un color, , tal 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 , hay 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 mochilas múltiples distribuidas

La variante distribuida múltiple 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 modo que se minimice la cantidad de desbordamiento. Sea el conjunto de artículos, el conjunto de mochilas, una función que asigna artículos a su volumen y 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 un DCOP, para cada uno crea una variable con dominio asociado . Luego, para todos los contextos posibles : donde representa el peso total asignado por contexto a knapsack : ${\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 elementos distribuidos

El problema de asignación de ítems es el siguiente: hay varios ítems que deben dividirse entre varios agentes. Cada agente tiene una valoración diferente para los ítems. El objetivo es optimizar algún objetivo global, como maximizar la suma de utilidades o minimizar la envidia. El problema de asignación de ítems puede formularse 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 elemento y "0" en caso contrario. La variable es propiedad del agente i .
• Para expresar la restricción de que cada artículo se entrega 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 todos los elementos deben ser asignados, agregue una restricción n -aria para cada elemento (donde n es el número de agentes), con un costo infinito si ninguna variable relacionada con este elemento es "1".

Otras aplicaciones

El 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]

• Completitud : 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 en la que primero se obtiene lo mejor o búsqueda en profundidad con ramificación y acotación;
• Sincronización entre agentes – sincrónica o asincrónica;
• Comunicación entre agentes: punto a punto con vecinos en el gráfico de restricciones, o difusión;
• Topología de comunicación : cadena o árbol.

ADOPT, por ejemplo, utiliza búsqueda de mejor primero, sincronización asincrónica, 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 una búsqueda de mejor opción a una búsqueda de ramificación y acotación de profundidad.

DCOP asimétrico

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

• Programación de eventos : los agentes que asisten al mismo evento pueden obtener diferentes valores del mismo.
• Red inteligente : el aumento del precio de la electricidad en horas de carga puede deberse a 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 único coste sino un vector de costes, uno para cada agente implicado en la restricción. El vector de costes tiene una longitud k si cada variable pertenece a un agente diferente; si dos o más variables pertenecen al mismo agente, entonces el vector de costes es más corto: hay un único coste para cada agente implicado , no para cada variable.

Enfoques para resolver un ADCOP

Una forma sencilla de resolver un ADCOP es reemplazar cada restricción por una restricción , que es igual a la suma de las funciones . Sin embargo, esta solución requiere que los agentes revelen sus funciones de costo. 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 denomina Eventos Privados como Variables (PEAV, por sus siglas en inglés). ^[17] En este enfoque, cada variable posee, además de sus propias variables, también "variables espejo" de todas las variables que poseen sus vecinos en la red de restricciones. Hay 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 los 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 teórico de juego de un juego simultáneo . En ambos casos, hay agentes que controlan variables (en 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 un pago diferente para cada agente. Sin embargo, existe 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 tanto, el mejor resultado que se puede buscar en ese contexto es un equilibrio , una situación en la que ningún agente puede aumentar unilateralmente su propia ganancia.
• En un ADCOP, los agentes se consideran cooperativos: actúan según el protocolo incluso si esto disminuye su propia utilidad. Por lo tanto, el objetivo es más desafiante: nos gustaría maximizar la suma de utilidades (o minimizar la suma de costos). Un equilibrio de Nash corresponde aproximadamente a un óptimo local de este problema, mientras que buscamos un óptimo global.

Cooperación parcial

Existen algunos modelos intermedios en los que los agentes son parcialmente cooperativos : están dispuestos a disminuir su utilidad para ayudar a la meta global, pero sólo si su propio coste 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 a realizar otras tareas que consumen tiempo y que ayudan a la empresa, siempre que no sean demasiado onerosas para ellos. Algunos modelos de 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 : existe un parámetro : los agentes acuerdan actuar en pro del bien global si su propia utilidad es al menos igual a su utilidad no cooperativa. ${\displaystyle \lambda \in [0,1]}$ ${\displaystyle (1-\lambda )}$

Para resolver estos ADCOP de cooperación parcial se requieren adaptaciones de los algoritmos ADCOP. ^[18]

Véase también

• Problema de satisfacción de restricciones
• Algoritmo distribuido
• Diseño de mecanismos algorítmicos distribuidos

Notas y referencias

1. " " o "×" denota el producto cartesiano . ${\displaystyle \times }$
2. Netzer, Arnon; Meisels, Amnon; 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. Yeoh, William; Felner, Ariel; Koenig, Sven (2008), "BnB-ADOPT: Un algoritmo DCOP asincrónico de ramificación y acotación", Actas de la Séptima Conferencia Conjunta Internacional sobre Agentes Autónomos y Sistemas Multiagente , vol. 2, págs. 591–8, ISBN 9780981738116
4. Hirayama, Katsutoshi; Yokoo, Makoto (1997). "Problema de satisfacción parcial de restricciones distribuidas". En Smolka, Gert (ed.). Principles and Practice of Constraint Programming-CP97 . Apuntes de clase en 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, véase Modi, Pragnesh Jay; Shen, Wei-Min; Tambe, Milind; Yokoo, Makoto (2003), "Un método completo asincrónico para la optimización distribuida de restricciones" (PDF) , Actas de la segunda conferencia conjunta internacional sobre agentes autónomos y sistemas multiagente , ACM Press, pp. 161–168, archivado desde el original (PDF) el 2019-11-04 , consultado el 2009-09-07La versión original de Adopt se amplió posteriormente para que fuera informada, es decir, para utilizar estimaciones de los costos de la solución para enfocar su búsqueda y ejecutarla más rápido, consulte Ali, Syed; Koenig, 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 2009Esta 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 algoritmo de optimización de restricciones distribuidas asíncronas" (PDF) , Actas de inteligencia artificial y aplicaciones , págs. 727–732, CiteSeerX 10.1.1.408.7230 
7. Mailler, Roger; Lesser, Victor (2004), "Resolución de 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; Zazon, Moshe; Binshtok, Maxim; Meisels, Amnon (2007), "Problema de terminación del algoritmo APO" (PDF) , Actas del octavo taller internacional sobre razonamiento distribuido con restricciones , págs. 117–124
9. Petcu, Adrian; Faltings, Boi (agosto de 2005), "DPOP: un método escalable para la optimización de restricciones de múltiples agentes", Actas de la 19.ª Conferencia conjunta internacional sobre inteligencia artificial, IJCAI 2005, Edimburgo, Escocia, págs. 266-271
10. Chechetka, Anton; Sycara, Katia (mayo de 2006), "Búsqueda de rama y límite sin compromiso para optimización de restricciones distribuidas" (PDF) , Actas de la quinta conferencia conjunta internacional sobre agentes autónomos y sistemas multiagente , págs. 1427–9, doi :10.1145/1160633.1160900, ISBN 1595933034, Número de identificación del sujeto  43918609
11. Chechetka, Anton; 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 descentralizada de restricciones", IEEE/ACM Transactions on Networking , 21 (4): 1298–1308, arXiv : 1103.3240 , doi :10.1109/TNET.2012.2222923, S2CID  11504393
13. Grinshpoun, T.; Grubshtein, 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, Rachel; 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 21.ª Conferencia Nacional sobre Inteligencia Artificial - Volumen 1. AAAI'06. Boston, Massachusetts: AAAI Press: 647–653. ISBN 978-1-57735-281-5.
15. Maheswaran, Rajiv T.; Pearce, Jonathan P.; Bowring, Emma; Varakantham, Pradeep; Tambe, Milind (1 de julio de 2006). "Pérdida de privacidad en el razonamiento distribuido con restricciones: 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, Koutarou; Hirayama, Katsutoshi (2002). "Satisfacción segura y distribuida de restricciones: llegar a un acuerdo sin revelar información privada". En Van Hentenryck, Pascal (ed.). Principios y práctica de la programación con restricciones – CP 2002. Apuntes de clase en 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; Grubshtein, Alon; Friedman, Michal; Meisels, Amnon (4 de junio de 2012). "Cooperación parcial en la búsqueda de múltiples agentes". Actas de la 11.ª 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, Ferdinando; 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 algorítmicos, teóricos de juegos y lógicos, Nueva York: Cambridge University Press , ISBN 978-0-521-89943-7Ver capítulos 1 y 2; descargables gratuitamente en línea.
• Yokoo, Makoto (2001), Satisfacción distribuida de restricciones: 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 distribuida de restricciones: una revisión", Agentes autónomos y sistemas multiagente , 3 (2): 185–207, doi :10.1023/A:1010078712316, S2CID  2139298