Optimización de restricciones distribuidas

Los ingredientes principales de un problema DCOP son los agentes y las variables . Es importante destacar que cada variable pertenece a un agente; esto es lo que hace que el problema sea distribuido. Formalmente, un DCOP es una tupla.${\displaystyle \langle A,V,{\mathfrak {D}},f,\alpha ,\eta \rangle }$, dónde:

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

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

Una asignación parcial es un conjunto de asignaciones de valor donde cada${\displaystyle v_{j}}$Aparece como máximo una vez. También se le llama contexto. Esto puede entenderse como una función que asigna variables en el DCOP a sus valores actuales:$${\displaystyle t:V\to (D\in {\mathfrak {D}})\cup \{\emptyset \}.}$$ 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,${\displaystyle t(v_{i})\mapsto \emptyset }$implica que el agente${\displaystyle \alpha (v_{i})}$aún no se ha asignado un valor a la variable${\displaystyle v_{i}}$. Dada esta representación, el " dominio " (es decir, el conjunto de valores de entrada) de la función fpuede pensarse 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, el${\displaystyle t}$función) como entrada para la${\displaystyle f}$función.

Una tarea completa es una tarea en la que cada${\displaystyle v_{j}}$Aparece exactamente una vez, es decir, todas las variables están asignadas. También se le denomina solución al DCOP.

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

El problema de coloración de grafos es el siguiente: dado un grafo${\displaystyle G=\langle N,E\rangle }$y un conjunto de colores${\displaystyle C}$, asignar cada vértice ,${\displaystyle n\subset N}$, un color,${\displaystyle c\leq C}$, de manera que se minimice el número de vértices adyacentes del mismo color.

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

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, asignar cada artículo a una mochila de tal manera que se minimice la cantidad de desbordamiento.${\displaystyle I}$ser el conjunto de elementos,${\displaystyle K}$ser el conjunto de mochilas,${\displaystyle s:I\to \mathbb {N} }$ser una función que asigna elementos a su volumen, y${\displaystyle c:K\to \mathbb {N} }$ser una función que relaciona las mochilas con sus capacidades.

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

El problema de asignación de artículos es el siguiente: Hay varios artículos 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 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 pertenece al agente i .
• Para expresar la restricción de que cada artículo se entrega a un máximo de un agente, agregue restricciones binarias para cada par de 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 ser asignados, 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".

DCOP se aplicó a otros problemas, como por ejemplo:

• Coordinación de sensores móviles;
• Planificación de reuniones y tareas.

Una forma sencilla de resolver un ADCOP es reemplazar cada restricción.${\displaystyle f_{C}:D_{1}\times \cdots \times D_{k}\to \mathbb {R} ^{k}}$con una restricción${\displaystyle f_{C}':D_{1}\times \cdots \times D_{k}\to \mathbb {R} }$, que es igual a la suma de las funciones${\displaystyle f_{C}^{1}+\cdots +f_{C}^{k}}$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 ]}

Otro enfoque se denomina 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 que poseen sus vecinos en la red de restricciones. Existen restricciones adicionales (con un coste 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 conlleva 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 ]}

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 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 busca maximizar su propia utilidad (o minimizar su propio coste). Por lo tanto, el mejor resultado posible en este contexto es un equilibrio , una situación en la que ningún agente puede aumentar unilateralmente su propio beneficio.
• En un problema 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 complejo: 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 nosotros buscamos un óptimo global.

Existen algunos modelos intermedios en los que los agentes son parcialmente cooperativos : están dispuestos a disminuir su utilidad para contribuir al objetivo global, pero solo si su propio costo no es demasiado elevado. Un ejemplo de agentes parcialmente cooperativos son los empleados de una empresa. Por un lado, cada empleado busca maximizar su propia utilidad; por otro lado, también desean contribuir al éxito de la empresa. Por lo tanto, están dispuestos a ayudar a otros o realizar otras tareas que consumen tiempo y que benefician a la empresa, siempre que no les suponga una carga excesiva. Algunos modelos para agentes parcialmente cooperativos son: ^{[ 18 ]}

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

La resolución de este tipo de ADCOP de cooperación parcial requiere adaptaciones de los algoritmos ADCOP. ^{[ 18 ]}