La optimización de restricción distribuida ( DCOP o DisCOP ) es el análogo distribuido a la optimización de restricción . 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 en algunas variables con dominios predefinidos y deben ser asignadas a los mismos valores por los diferentes agentes.
Los problemas definidos con este framework pueden resolverse mediante cualquiera de los algoritmos que están 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 en 1990. [ cita requerida ]
Definiciones
DCOP
Los ingredientes principales de un problema de 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 , dónde:
- es el conjunto de agentes ,.
- es el conjunto de variables ,.
- es el conjunto de dominios variables ,, donde cadaes un conjunto finito que contiene los posibles valores de la variable.
- Si contiene solo dos valores (por ejemplo, 0 o 1), entonces se llama variable binaria .
- es la función de costo . Es una función [1]que asigna cada posible asignación parcial a un costo. Por lo general, solo unos pocos valores deson 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 en este conjunto hay una función asignando un valor real a cada posible asignación de las variables. Algunos tipos especiales de restricciones son:
- Restricciones unarias : restricciones en una sola variable, es decir, para algunos .
- Restricciones binarias : restricciones sobre dos variables, es decir, para algunos .
- es la función de propiedad . Es una función mapeando cada variable a su agente asociado. significa que la variable "pertenece" al agente . Esto implica que es agentees la responsabilidad de asignar el valor de la variable . Tenga en cuenta queno es necesariamente una inyección , es decir, un agente puede poseer más de una variable. Tampoco es necesariamente un rechazo , es decir, algunos agentes pueden no poseer variables.
- es la función objetivo . Es un operador que agrega a todos los individuoscostos para todas las posibles asignaciones de variables. Esto generalmente se logra mediante la suma:
El objetivo de un DCOP es que cada agente asigne valores a sus variables asociadas para minimizar o maximizar para una asignación dada de las variables.
Asignaciones
Una asignación de valor es un par dónde es un elemento del dominio .
Una asignación parcial es un conjunto de asignaciones de valor donde cadaaparece como máximo una vez. También se llama contexto. Esto se puede considerar como una función que asigna variables en el DCOP a sus valores actuales:
f
puede considerarse como el conjunto de todos los contextos posibles para el DCOP. Por lo tanto, en el resto de este artículo podemos utilizar la noción de contexto (es decir, el función) como una entrada a la función. Una tarea completa es una tarea en la que cadaaparece exactamente una vez, es decir, se asignan todas las variables. También se le llama una solución al DCOP.
Una solución óptima es una asignación completa en la que la función objetivo está optimizado (es decir, maximizado o minimizado, según el tipo de problema).
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 juego de colores , asigne cada vértice ,, un color, , de manera que se minimiza el número de vértices adyacentes con el mismo color.
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:
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 modo que se minimice la cantidad de desbordamiento. Dejar ser el conjunto de elementos, sea el conjunto de mochilas, ser una función mapeando elementos a su volumen, y ser una función que mapee las mochilas a sus capacidades.
Para codificar este problema como un DCOP, para cada crea una variable con dominio asociado . Entonces para todos los contextos posibles:
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 para 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 todos los artículos deben asignarse, agregue una restricción n -ary 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:
- coordinar sensores móviles;
- programación de reuniones y tareas.
Algoritmos
Los algoritmos DCOP se pueden clasificar de varias formas: [3]
- Integridad : algoritmos de búsqueda completos que encuentran la solución óptima, versus algoritmos de búsqueda locales que encuentran un óptimo local .
- Estrategia de búsqueda : la mejor búsqueda primero o la búsqueda en profundidad primero en ramificaciones y límites;
- Sincronización entre agentes: sincrónica o asincrónica;
- Comunicación entre agentes: punto a punto con vecinos en el gráfico de restricción o difusión;
- Topología de comunicación : cadena o árbol.
ADOPT, por ejemplo, utiliza la mejor búsqueda 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.
Nombre del algoritmo | Año introducido | Complejidad de la memoria | Numero de mensajes | Corrección (informática) / Completitud (lógica) | Implementaciones |
---|---|---|---|---|---|
ABT [ cita requerida ] Retroceso asincrónico | 1992 | [ cita requerida ] | [ cita requerida ] | Nota: pedido estático, completo | [ cita requerida ] |
AWC [ cita requerida ] Compromiso débil asincrónico | 1994 | [ cita requerida ] | [ cita requerida ] | Nota: reordenamiento, rápido, completo (solo con espacio exponencial) | [ cita requerida ] |
Algoritmo de ruptura distribuida de DBA | 1995 | [ cita requerida ] | [ cita requerida ] | Nota: incompleto pero rápido | FRODO versión 1 [ enlace muerto permanente ] |
SyncBB [4] Rama sincrónica y enlazada | 1997 | [ cita requerida ] | [ cita requerida ] | Completo pero lento | |
BID Ruptura distribuida iterativa | 1997 | [ cita requerida ] | [ cita requerida ] | Nota: incompleto pero rápido | |
AAS [ cita requerida ] Búsqueda de agregación asincrónica | 2000 | [ cita requerida ] | [ cita requerida ] | agregación de valores en ABT | [ cita requerida ] |
DFC [ cita requerida ] Encadenamiento directo distribuido | 2000 | [ cita requerida ] | [ cita requerida ] | Nota: baja, comparable a ABT | [ cita requerida ] |
ABTR [ cita requerida ] Retroceso asincrónico con reordenación | 2001 | [ cita requerida ] | [ cita requerida ] | Nota: ordenar en ABT con nogoods delimitados | [ cita requerida ] |
DMAC [ cita requerida ] Mantenimiento de coherencias asincrónicas | 2001 | [ cita requerida ] | [ cita requerida ] | Nota: el algoritmo más rápido | [ cita requerida ] |
Computación segura con servidores semi-confiables [ cita requerida ] | 2002 | [ cita requerida ] | [ cita requerida ] | Nota: la seguridad aumenta con la cantidad de servidores confiables | [ cita requerida ] |
Cálculo seguro de varias partes para resolver DisCSPs (MPC-DisCSP1-MPC-DisCSP4) [ cita requerida ] | 2003 | [ cita requerida ] | [ cita requerida ] | Nota: seguro si la mitad de los participantes son dignos de confianza | [ cita requerida ] |
Adopte el retroceso asincrónico [5] | 2003 | Polinomio (o cualquier espacio [6] ) | Exponencial | Probado | Implementación de referencia: Adoptar DCOPolis ( GNU LGPL ) |
Superposición parcial asíncrona OptAPO [7] | 2004 | Polinomio | Exponencial | Demostrado, pero se ha impugnado la prueba de integridad [8] | Implementación de referencia: "OptAPO" . Centro de Inteligencia Artificial . SRI Internacional . Archivado desde el original el 15 de julio de 2007. |
Procedimiento de optimización de pseudotárboles distribuidos de DPOP [9] | 2005 | Exponencial | Lineal | Probado | Implementación de referencia: FRODO ( GNU Affero GPL ) |
Subdivisión de NCBB sin compromiso y consolidada [10] | 2006 | Polinomio (o cualquier espacio [11] ) | Exponencial | Probado | Implementación de referencia: no divulgada públicamente |
Aprendizaje sin comunicación CFL [12] | 2013 | Lineal | Ninguno Nota: no se envían mensajes, pero se asume conocimiento sobre la satisfacción de la restricción local | Incompleto |
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 en profundidad primero de bifurcación y límite.
DCOP asimétrico
Un DCOP asimétrico es una extensión de DCOP en la 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 a un mismo evento pueden derivar valores diferentes de él.
- Red inteligente : el aumento del precio de la electricidad en horas cargadas puede ser de diferentes agentes.
Una forma de representar un ADCOP es representar las restricciones como funciones:
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 es 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 se desea debido a consideraciones de privacidad. [14] [15] [16]
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 restricción. 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 es 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 teoría de juegos de un juego simultáneo . 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 resulta en una recompensa 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 costo). Por lo tanto, el mejor resultado que se puede buscar en tal escenario 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 de acuerdo con el protocolo incluso si 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
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 solo 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 firma. Por lo tanto, están dispuestos a ayudar a otros o realizar otras tareas que consuman mucho tiempo y que ayuden a la empresa, siempre que no sea demasiado oneroso para ellos. Algunos modelos para agentes que cooperan parcialmente 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 veces su utilidad no cooperativa.
Resolver tales 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
- ^ ""o" × "denota el producto cartesiano .
- ^ Netzer, Arnón; 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 .
- ^ a b Yeoh, William; Felner, Ariel; Koenig, Sven (2008), "BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm" , Actas de la Séptima Conferencia Conjunta Internacional sobre Agentes Autónomos y Sistemas Multiagente , 2 , págs. 591–8, ISBN 9780981738116
- ^ Hirayama, Katsutoshi; Yokoo, Makoto (1997). Smolka, Gert (ed.). "Problema de satisfacción de restricción parcial distribuida" . Principios y práctica de la programación de restricciones-CP97 . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer. 1330 : 222-236. doi : 10.1007 / BFb0017442 . ISBN 978-3-540-69642-1.
- ^ La versión publicada originalmente de Adopt estaba desinformada, ver Modi, Pragnesh Jay; Shen, Wei-Min; Tambe, Milind; Yokoo, Makoto (2003), "Un método completo asincrónico para la optimización de restricciones distribuidas" (PDF) , Actas de la segunda conferencia conjunta internacional sobre agentes autónomos y sistemas multiagente , ACM Press, pp. 161-168. La versión original de Adopt se amplió posteriormente para estar informado, es decir, utilizar estimaciones de los costos de la solución para enfocar su búsqueda y correr más rápido, ver Ali, Syed; Koenig, Sven; Tambe, Milind (2005), "Preprocessing Techniques for Accelerating the DCOP Algorithm 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. Esta extensión de Adopt se utiliza normalmente como implementación de referencia de Adopt.
- ^ 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 inteligencia artificial y aplicaciones , págs. 727–732, CiteSeerX 10.1.1.408.7230
- ^ Mailler, Roger; Lesser, Victor (2004), "Solución de problemas de optimización de restricciones distribuidas mediante la mediación cooperativa" (PDF) , Actas de la Tercera Conferencia Conjunta Internacional sobre Agentes Autónomos y Sistemas Multiagent , IEEE Computer Society , págs. 438–445, ISBN 1581138644
- ^ Grinshpoun, Tal; Zazon, Moshe; 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. 117-124
- ^ Petcu, Adrian; Faltings, Boi (agosto de 2005), "DPOP: A Scalable Method for Multiagent Constraint Optimization" , Actas de la XIX Conferencia Conjunta Internacional sobre Inteligencia Artificial, IJCAI 2005, Edimburgo, Escocia, págs. 266-271
- ^ Chechetka, Anton; 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 Multiagente , págs. 1427–9, doi : 10.1145 / 1160633.1160900 , ISBN 1595933034, S2CID 43918609
- ^ 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 AAAI sobre planificación distribuida y gestión de horarios
- ^ Duffy, KR; Leith, DJ (agosto de 2013), "Descentralized Constraint Satisfaction", IEEE / ACM Transactions on Networking , 21 (4): 1298–1308, arXiv : 1103.3240 , doi : 10.1109 / TNET.2012.2222923 , S2CID 11504393
- ^ a b c 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. doi : 10.1613 / jair.3945 . ISSN 1076-9757 .
- ^ 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 21a Conferencia Nacional sobre Inteligencia Artificial - Volumen 1 . AAAI'06. Boston, Massachusetts: AAAI Press: 647–653. ISBN 978-1-57735-281-5.
- ^ Maheswaran, Rajiv T .; Pearce, Jonathan P .; Inclinándose, Emma; Varakantham, Pradeep; Tambe, Milind (1 de julio de 2006). "Pérdida de privacidad en el razonamiento de restricción distribuida: 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 .
- ^ Yokoo, Makoto; Suzuki, Koutarou; Hirayama, Katsutoshi (2002). Van Hentenryck, Pascal (ed.). "Satisfacción de restricción distribuida segura: llegar a un acuerdo sin revelar información privada" . Principios y práctica de la programación de restricciones - CP 2002 . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer. 2470 : 387–401. doi : 10.1007 / 3-540-46135-3_26 . ISBN 978-3-540-46135-7.
- ^ Rajiv T. Maheswaran, Milind Tambe, Emma Bowring, Jonathan P. Pearce, Pradeep Varakantham (2004). "Llevando DCOP al mundo real: soluciones completas eficientes para la programación distribuida de múltiples eventos" . www.computer.org . Consultado el 12 de abril de 2021 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ a b 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 XI Conferencia Internacional sobre Agentes Autónomos y Sistemas Multiagente - Volumen 3 . AAMAS '12. 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 de restricciones distribuidas" , en Walsh, Toby (ed.), Manual de programación de restricciones , Elsevier , ISBN 978-0-444-52726-4 Un 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-7Consulte 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", Autonomous Agents and Multiagent Systems , 3 (2): 185-207, doi : 10.1023 / A: 1010078712316 , S2CID 2139298