**Satisfacción de Restricciones Distribuida (DisCSP)** SVRAI
Fernando Sancho Caparrini --- ## Introducción !!! **DAI**: subcampo de la IA que se ocupa de la interacción (coordinación) entre agentes para resolver problemas evitando la centralización del proceso y recursos. !!!Def **DisCSP**: CSP en el que las variables y las restricciones están distribuidas entre agentes. !!! Tip Sin pérdida de generalidad, hacemos las siguientes suposiciones: - **Cada agente** tiene exactamente **una variable** (identificación agente-variable). - Todas las **restricciones** son **binarias**. - Cada agente **conoce** todos los predicados de las **restricciones** relevantes para su variable. Un algoritmo distribuido hace que cada agente combine el cálculo local con la comunicación con sus vecinos. Un buen algoritmo debe terminar con una solución global (o con la constatación de que no existe) y que lo haga rápidamente. Veremos dos tipos de algoritmos: * **Enfoque de mínimo compromiso**, descartar valores variables imposibles sin perder ninguna solución posible. * **Selección de valores tentativos de variables**, retrocediendo cuando esas elecciones resultan infructuosas. --- ## Algoritmos triviales para DisCSP ### Método centralizado Seleccionar un **agente líder**, reunir toda la información del CSP en él. El líder resuelve el CSP utilizando algoritmos centralizados y distribuye la solución. * Coste de recopilar toda la información puede ser prohibitivo, no deseable o imposible por razones de seguridad/privacidad. ### Backtracking Síncrono (SBT) Se **fija un orden** en los agentes. Cada agente, al recibir una solución parcial (instancias de las variables precedentes) del agente anterior, instancia su variable basándose en las restricciones que conoce. Si encuentra un valor adecuado, lo añade a la solución parcial y lo pasa al siguiente agente. Si no, envía un mensaje de backtracking al agente anterior. * Determinar el orden de instanciación sigue requiriendo ciertos costes de comunicación. * No aprovecha el paralelismo. * En cada momento, sólo un agente está activo, por lo que el problema se está resolviendo de forma secuencial. --- ## Reducción de dominios Los nodos se comunican con sus vecinos para eliminar valores de sus dominios. ### Algoritmo de Filtrado $x_i$ comunica $D_i$ a sus vecinos ($x_j$), elimina de su dominio los valores que no son consistentes con los valores recibidos de los vecinos, y el proceso se repite: ~~~~none Procedimiento Revisa(xi, xj) Para cada v_i ∈ D_i: Si no existe v_j ∈ D_j que es consistente con v_i entonces: Borrar v_i de D_i ~~~~ * El proceso termina cuando no se produce ninguna eliminación más, o cuando uno de los dominios queda vacío (problema sin solución). * Si termina con un valor en cada dominio, ese conjunto de valores constituye una solución. * Si termina con varios valores en cada dominio, el resultado no es concluyente (podría tener o no solución, y el algoritmo no lo determina). El algoritmo **siempre para**, y es **correcto** pero **no es completo**. --- ## Reducción de dominios ### Algoritmo de Filtrado ![](../SVRAI/img/sma2-7.png width="40%" align="left")(a) Al principio sólo los mensajes de $x_1$ producen cambio: cuando $x_2$ o $x_3$ reciben el mensaje de $x_1$ eliminan el rojo de sus dominios, quedando $D_2 = \{azul\}$ y $D_3 = \{azul, verde\}$. Luego, cuando $x_2$ comunica su nuevo dominio a $x_3$, éste reduce su dominio a $D_3=\{verde\}$. Ya no hay más cambios y termina con una solución correcta. (b) El algoritmo comienza igual, pero cuando $x_2$ y $x_3$ reciben el mensaje de $x_1$, reducen sus dominios a $\{azul\}$. Después, cuando se actualizan mutuamente en sus nuevos dominios, cada uno reduce sus dominios a $\emptyset$. Aquí el algoritmo termina y anuncia correctamente que no existe ninguna solución. (c) En este caso, el conjunto inicial de mensajes no produce ninguna reducción en ningún dominio. El algoritmo termina, pero todos los nodos tienen valores múltiples restantes. Por tanto, el algoritmo no es capaz de demostrar que el problema está sobrecondicionado y no tiene solución. (d) El filtrado también puede fallar aunque exista una solución. Por razones similares a las del caso (c), en este caso el algoritmo no es capaz de demostrar que ahora el problema sí tiene solución. --- ## Reducción de dominios ### Algoritmo de Filtrado !!! Note El filtrado es muy débil y se utiliza como paso inicial de otros métodos. Se basa en la noción de **resolución unitaria**: $$ \begin{array}{c} A_1\\ \neg(A_1\wedge A_2\wedge\dots\wedge A_n)\\ \hline \neg(A_2\wedge\dots\wedge A_n) \end{array} $$ Escribir restricciones como combinaciones prohibidas de valores, llamadas **No-goods**. * Restricción $\{\neg(x_1 = rojo \wedge x2 = rojo)\}$, * Anuncio de $x_1$: $\{x_1 = rojo\}$. $$ \begin{array}{c} x_1=rojo\\ \neg(x_1=rojo\wedge x_2=rojo)\\ \hline \neg(x_2=rojo) \end{array} $$ --- ## Reducción de dominios ### Algoritmo de Filtrado !!! Para resolver el problema de la debilidad del filtrado se introduce la regla de **hiperresolución**: $$ \begin{array}{c} A_1\vee A_2\vee\dots A_m\\ \neg(A_1\wedge A_{1,1}\wedge A_{1,2}\wedge \dots)\\ \neg(A_2\wedge A_{2,1}\wedge A_{2,2}\wedge \dots)\\ \dots \neg(A_m\wedge A_{m,1}\wedge A_{m,2}\wedge \dots)\\ \hline \neg(A_{1,1}\wedge \dots\wedge A_{2,1}\wedge\dots\wedge A_{m,1}\wedge \dots)\\ \end{array} $$ La hiperresolución es correcta y completa y da lugar a un algoritmo para DisCSP completo. --- ## Reducción de dominios ### Algoritmo de Filtrado Cada agente genera repetidamente nuevas restricciones para sus vecinos, se las notifica y poda su propio dominio basándose en las restricciones que recibe (correcto y completo): ~~~~ Procedimiento RevisaHR(NG_i, NG^∗_j) Repite NG_i ← NG_i ⋃ NG'_j NG'_i ← HR(NG_i,D_i) Si NG'_i ≠ ∅ entonces: NG_i ← NG_i ⋃ NG'_i envia NG'_i a los vecinos de i Si ∅ ∈ NG'_i entonces Parar hasta que no haya cambios en NG_i ~~~~ $NG_i$: *No-goods* que conoce $x_i$. $NG^*_j$: *No-goods* comunicados por $x_j$ a $x_i$. --- Caso (c) de los ejemplos anteriores: Inicialmente, $x_1$ tiene cuatro *No-goods* que se derivan de las restricciones que le afectan: $\{x_1 = rojo, x_2 = rojo\}$, $\{x_1 = rojo, x_3 = rojo\}$, $\{x_1 = azul, x_2 = azul\}$, $\{x_1 = azul, x_3 = azul\}$, Además, $x_1 = rojo \vee x_1 = azul$. Utilizando la hiperresolución, $x_1$ puede razonar: $$ \begin{array}{c} x_1=rojo \vee x1= azul\\ \neg(x_1=rojo\wedge x_2=rojo)\\ \neg(x_1=azul\wedge x_3=azul)\\ \hline \neg(x_2=rojo\wedge x_3=azul) \end{array} $$ $x_1$ construye los *No-good* $\{x_2 = rojo, x_3 = azul\}$ y $\{x_2 = azul, x_3 = rojo\}$. Los envía a $x_2$ y $x_3$. $x_2$ razona: $$ \begin{array}{c} x_2=rojo \vee x2= azul\\ \neg(x_2=rojo\wedge x_3=azul)\\ \neg(x_2=azul\wedge x_3=azul)\\ \hline \neg(x_3=azul) \end{array} $$ $x_2$ también puede construir el *No-good* $\{x_3 = rojo\}$. Los comunica a $x_3$, que genera el *No-good* vacío. Lo que demuestra que el problema no tiene solución. --- ## Reducción de dominios ### Algoritmo de Filtrado * Mayor potencia de la hiperresolución en relación con la resolución unitaria. * Debilidad: el número de *No-goods* generados puede llegar a ser inmanejablemente grande (el ejemplo sólo muestra el número mínimo de *No-goods* necesarios para derivar el *No-good* vacío). * Fuertes similitudes entre Filtrado+Hiperresolución y el problema SAT de fórmulas proposicionales, que se sabe **NP**-completo. * **Conclusión**: un algoritmo demasiado débil (no completo) y otro poco práctico (**NP**-completo). * **Problema**: la naturaleza de mínimo compromiso (están restringidos a eliminar sólo combinaciones de valores probadamente imposibles). * **Alternativa**: explorar el de soluciones espacio haciendo selecciones tentativas de valores para las variables y retrocediendo cuando sea necesario. * **Resultado**: algoritmo no eficiente en todos los casos, pero no se comporte muy mal en el caso medio. * Pero los algoritmos vistos no son irrelevantes: * el Filtrado (basado en resolución unitaria) es un paso eficaz de preprocesamiento, y * Inspiración de otros algoritmos. --- ## Algoritmos de Búsqueda Heurística Del **BT** al **BT descentralizado**: Cada agente ejecuta el siguiente procedimiento, en paralelo y de forma asíncrona... ~~~~none Repetir Si el valor actual es consistente con los valores de los vecinos, o ninguno de los valores del dominio lo es, entonces: No hacer nada si no: selecciona un valor del dominio consistente con los vecinos y comunícalo a todos los vecinos hasta que no haya cambios en el valor ~~~~ * Puede terminar porque no se ha producido ninguna violación de las restricciones y se ha encontrado una solución. * Puede terminar porque ningún agente puede encontrar un valor consistente con los de sus vecinos, pero podría haber una asignación global consistente. * Y puede que el algoritmo no termine nunca aunque haya una solución: * En (d) anterior: cada agente puede hacer un ciclo secuencial entre *rojo*, *verde* y *azul* que nunca termina pero hay una solución posible. --- # Backtracking Asíncrono --- ## Backtracking Asíncrono ABT elimina los inconvenientes de BT al permitir que los agentes se ejecuten de forma concurrente y asíncrona. Cada agente instanciará su variable y comunicará el valor de la misma a los agentes correspondientes. * ![](../SVRAI/img/sma2-23.png width="20%" align="right")Representación en red: **variables/nodos** y **restricciones binarias/aristas**. * Cada agente tiene exactamente una variable. * Cada arista/restricción es dirigida: **emisor valores $\rightarrow$ evaluador de restricciones**. * Un agente puede actuar como evaluador en algunas relaciones, y como emisor en otras. * Los agentes: 1. Instancian sus valores de forma concurrente y los comunican a sus vecinos salientes. 2. Esperan y responden a los mensajes que reciben (modifican sus valores, y crean/envían mensajes). 3. Manejan múltiples mensajes de forma concurrente: 1) revisan su información del mundo con los mensajes que ha recibido, y 2) comprueban la consistencia. 4. Tipos de Mensajes: * **ok?**: que un evaluador recibe de un emisor preguntando si el valor elegido es aceptable para él, * **nogood**: que un emisor recibe indicando que un evaluador ha encontrado una violación según su visión del mundo. --- ## Backtracking Asíncrono ~~~~none Cuando se reciba ["Ok?", (x_j, d_j)]: añadir (x_j, d_j) a vista_agente Comprobar_vista Cuando se reciba ["Nogood", nogood]: añadir nogood a lista_nogood Para cada (x_k, d_k) ∈ nogood con x_k no vecino de x_i hacer: añadir (x_k, d_k) a vista_agente Pedir a x_k que añada a x_i como vecino Comprobar_vista Procedimiento Comprobar_vista Cuando vista_agente y valor_actual son inconsistentes hacer: Si ningún valor en D_i es consistente con vista_agente entonces: backtracking si no selecciona d ∈ D_i consistente con vista_agente valor_actual ← d enviar ["Ok?", (x_i, d)] a vecinos de menor prioridad Procedimiento backtracking nogood ← algún conjunto inconsistente, usando hiperresolucion o similar Si nogood = ∅ entonces: Transmitir a otros agentes que no hay solución, y Parar si no: selecciona (x_j, d_j) ∈ nogood donde x_j tiene la menor prioridad en nogood enviar ["Nogood", nogood] a x_j eliminar (x_j, d_j) de vista_agente ~~~~ --- ## Evitar bucles infinitos * ¿Bucles infinitos? Por ejemplo, si un cambio en $x_1$ hace que $x_2$ cambie, entonces este cambio en $x_2$ hace que $x_3$ cambie, lo que hace que $x_1$ cambie de nuevo, y así sucesivamente. * En la red, un bucle se refleja mediante un ciclo de enlaces dirigidos. * **Solución**: obligar que la red sea *acíclica dirigida*. Por ejemplo, utilizando una relación de orden total entre los nodos, para cada restricción, el agente de menor prioridad será evaluador, y el de mayor prioridad enviará los mensajes de tipo **ok?** al evaluador. * Para reducir el número de agentes involucrados en el backtracking, si un agente se encuentra una inconsistencia, enviará un mensaje **Nogood** solo al agente de menor prioridad del $nogood$ encontrado. * Requiere menor conocimiento de la red completa por cada agente. --- ## Tratamiento de los cambios asíncronos * Como los agentes cambian sus instancias de forma asíncrona, una $vista\_agente$ puede estar sujeta a cambios sin parar, dando lugar a inconsistencias porque el mensaje **Nogood** puede basarse en información obsoleta. * Para evitar este problema, tras recibir un mensaje, el receptor sólo cambia su valor si el $nogood$ recibido es compatible con su actual $vista\_agente$ y su propia asignación. * Un $nogood$ puede verse como una nueva restricción derivada de las restricciones originales. Al incorporar esta nueva restricción (con las nuevas aristas necesarias), los agentes pueden evitar repetir el mismo error. * Aunque todas las restricciones originales sean binarias, las nuevas restricciones derivadas podrían no serlo. Entoces, solo el agente de menor prioridad de la restricción hará el papel de evaluador y los enlaces se añadirán desde cada uno de los otros agentes a él. --- ## Corrección y Completitud de ABT !!!Def ABT es **correcto** y **completo**: 1. Si existe una solución, ABT alcanza un estado estable donde todos los valores de las variables satisfacen todas las restricciones, y todos los agentes se quedan esperando un mensaje entrante que nunca llega (para detectar que se ha alcanzado un estado estable se necesitan algoritmos distribuidos adicionales de detección de terminación), y 2. Si no existe ninguna solución, ABT descubre este hecho y para. Para que los agentes alcancen un estado estable, todos los valores de sus variables deben satisfacer todas las restricciones. Por tanto, la corrección de ABT es evidente. No existe una solución global cuando el problema está **sobrecargado: exceso de restricciones**. Entonces, ABT genera un $nogood$ correspondiente al conjunto vacío (un conjunto de asignaciones que conduce a una contradicción). --- ## Algunas consideraciones adicionales de ABT El problema de satisfacción de restricciones es **NP**-completo, por lo que la complejidad temporal en el peor de los casos del ABT se vuelve exponencial en el número de variables. ABT es la columna vertebral de los enfoques modernos de DisCSP, pero admite muchas extensiones y modificaciones: 1. En la primera versión de ABT, se usa como $nogood$ la vista completa. Se puede reducir y ganar eficiencia en los saltos atrás. 2. La solución a esta ineficiencia no es sencilla: **encontrar un $Nogood$ mínimo** es, en general, un **problema intratable** (**NP**-duro). Por lo que se necesitan varias heurísticas para reducir el tamaño del $Nogood$ sin sacrificar la corrección. 3. Una cuestión relacionada es el **número de $Nogoods$ almacenados** por cada agente. Una propuesta es que los agentes mantengan sólo los $Nogoods$ consistentes con su vista. Una mejora adicional es almacenar sólo los $Nogoods$ que son consistentes tanto con la vista del agente como con su asignación actual. Este enfoque, que es considerado por algunos como la mejor implementación del algoritmo ABT, garantiza que el número de $Nogoods$ almacenados por cualquier agente no es mayor que el tamaño del dominio. 4. Por último, hay enfoques para la satisfacción de restricciones distribuidas que no siguen el esquema ABT, incluyendo la comprobación asíncrona hacia adelante y el backtracking dinámico concurrente. No los veremos. --- # Búsqueda Asíncrona de Compromiso Débil (AWCS) --- ## AWCS !!! Metodología General: 1. Todas las variables comienzan con **valores iniciales tentativos**. 2. Se construye una solución parcial consistente para un subconjunto de variables, y esta solución parcial se intenta ampliar añadiendo variables una a una hasta encontrar una solución completa. 3. Cuando se añade una variable a una solución parcial, su valor inicial provisional se revisa de forma que el nuevo valor satisfaga todas las restricciones entre las variables incluidas en la solución parcial, y satisfaga el mayor número posible de restricciones entre las variables que no están incluidas en la solución parcial (que también tienen un valor inicial, pero que se considera que pesan menos para la verificación parcial): **heurística de mínimo conflicto**. 4. Cuando no existe ningún valor para una variable que satisfaga todas las restricciones entre las variables incluidas en la solución parcial, este algoritmo abandona toda la solución parcial construida hasta el momento, y se comienza a construir una nueva solución parcial desde cero, utilizando la asignación de valores actuales como nuevos valores iniciales tentativos. El último paso no es sencillo, ya que los agentes actúan de forma concurrente y asíncrona, y ningún agente tiene información exacta sobre la solución parcial que está siendo construida. Además, podría darse el caso de que varios agentes intentaran reiniciar el proceso de búsqueda simultáneamente. --- ## AWCS AWCS se compromete con la solución parcial de forma débil y puede construirse cambiando el orden de prioridad de forma dinámica. La forma de establecer el orden de prioridad es introduciendo valores de prioridad, que cambian mediante las siguientes reglas: - Para cada variable/agente, su **valor de prioridad** es un entero que representa su orden de prioridad. - A mayor valor, mayor prioridad. - En caso de igualdad, el orden se determina por su numeración **natural**. - Para cada variable/agente, el valor de prioridad inicial es 0. - Si no existe un valor consistente para un agente, su valor de prioridad cambia a $k + 1$, donde $k$ es el mayor valor de prioridad de los agentes relacionados. --- ## AWCS ~~~~none Cuando se reciba ["Ok?", (x_j, d_j, p_j)]: añadir (x_j, d_j, p_j) a mi vista Comprobar_vista Cuando se reciba ["Nogood", x_j, nogood]: añadir nogood a lista_nogood Para cada (x_k, d_k, p_k) ∈ nogood con x_k no vecino mío: añadir (x_k, d_k, p_k) a mi vista, y añadir x_k como vecino Comprobar_vista Procedimiento Comprobar_vista Cuando mi vista y mi valor_actual son inconsistentes hacer: Si ningún valor en D_i es consistente con mi vista entonces: backtracking si no selecciona d ∈ D_i consistente con mi vista y que minimiza el nº de restricciones con agentes de menor prioridad valor_actual ← d enviar ["Ok?", (x_i, d, prioridad_actual)] a vecinos Procedimiento backtracking nogoods ← algún conjunto inconsistente, usando hiperresolucion o similar Si ∅ ∈ nogoods entonces: Transmitir a otros agentes que no hay solución y Parar si ningún elemento de nogoods ha sido enviado hacer: Para cada V ∈ nogoods hacer: añadir V a nogoods_enviados Para cada (x_j, d_j, p_j) ∈ V hacer: enviar ["Nogood", x_i, V] a x_j prioridad_actual ← 1 + max_{(x_j,d_j,p_j)∈ vista} p_j Selecciona d ∈ D_i que minimiza las restricciones violadas con agentes de menor prioridad valor_actual ← d enviar ["ok", (x_i, d, prioridad_actual)] a vecinos ~~~~ --- ## Diferencias con ABT - En ABT, cada agente envía su valor sólo a los agentes relacionados de menor prioridad, mientras que en AWCS cada agente envía su valor tanto a los agentes de menor como de mayor prioridad conectados por restricciones: sus **vecinos**. - Prioridad y valor se comunican a través del mensaje **ok?**. - La prioridad se determina utilizando los valores de prioridad comunicados. Si el valor actual no es consistente con su vista (alguna restricción con agentes de mayor prioridad no se satisface), el agente cambia su valor para: ganar consistencia, y minimizar el número de violaciones de restricciones con agentes de menor prioridad. - Cuando un agente no puede encontrar un valor consistente con su vista, envía mensajes **nogood** a otros agentes, e incrementa su valor de prioridad (comprueba envíos repetidos). !!!def: Teorema AWCS es correcto y completo. --- ## Seguridad/privacidad de los agentes ¿Porqué CSP de forma distribuida? los agentes pueden no querer comunicar toda la información a un agente líder centralizado. En este sentido, una pregunta interesante: ¿cuánta información revelan los agentes utilizando el algoritmo AWCS? !!!Tip Los agentes comunican las asignaciones actuales y los $nogoods$. Al observar las asignaciones de un agente, otros agentes pueden acumular gradualmente información, pero no pueden saber si la información obtenida sobre él es completa o no (por ejemplo, puede haber valores que no se seleccionan porque violan restricciones con agentes de mayor prioridad que ellos desconocen). Además, el agente nunca revela directamente información sobre sus restricciones: un mensaje **nogood** es una información muy resumida sobre sus restricciones y los $nogoods$ enviados por otros agentes. Por tanto, podemos ver que la cantidad de información revelada por estos algoritmos es mucho menor que la de los métodos centralizados, en los que los agentes deben declarar información precisa sobre sus dominios, restricciones y variables. --- ## Comparativa: ABT vs. ABT-MC vs. AWCS !!! Tip Experimentalmente: - AWCS resuelve problemas que no pueden ser resueltos en un tiempo de cálculo razonable por ABT. La heurística de mínimo conflicto mejora, pero no consigue resolver muchos de los casos. - **Orden de prioridad es estático**: la eficiencia depende de la selección de los valores iniciales. Cuando los valores iniciales de los agentes de mayor prioridad son buenos, la solución puede encontrarse fácilmente. Caso contrario, se requiere una búsqueda exhaustiva para revisar estos valores. - **En AWCS**, los valores iniciales son menos críticos, y se puede encontrar una solución incluso si los valores iniciales están lejos de la solución final, ya que los valores de las variables se acercan gradualmente a la solución final. - **Orden de prioridad como jerarquía de autoridad entre agentes**, es decir, el orden de prioridad de la toma de decisiones. Si la jerarquía es estática, los juicios erróneos de los agentes con mayor prioridad son fatales para todos los agentes. En cambio, si se cambia el orden de prioridad de forma dinámica, los errores de determinados agentes no tienen efectos fatales. - Estos resultados son intuitivamente naturales, ya que implican que una organización de agentes flexible funciona mejor que una organización estática y rígida. --- # Sistemas basados en Hill-climbing --- ## Mínimos Locales **Hill-climbing**: Se comienza asignando al azar, y luego los valores se van cambiando para minimizar las violaciones de las restricciones. Este proceso se repite hasta que no se pueda mejorar la solución actual. En una versión distribuida de *hill-climbing* cada agente se identifica con una variable y todos los agentes cambian su valor en paralelo, enviando mensajes a sus vecinos que indican su nuevo valor. Sufren el problema de los **mínimos locales**: ningún agente puede reducir el número total de violaciones de las restricciones cambiando su valor, pero ese número podría reducirse haciendo que dos o más agentes cambien su valor simultáneamente. Identificar que el sistema está en un mínimo local requiere que todos los agentes transmitan el hecho de que están en un mínimo local y estas transmisiones deben ser anotadas para asegurar que los puntos de vista locales de los agentes son coherentes entre sí - todos ellos estaban en el mismo estado global cuando enviaron sus transmisiones... da lugar a un algoritmo complejo con gran cantidad de comunicaciones y, posiblemente, largos tiempos de ejecución. --- ## Breakout Distribuido: Cuasi-mínimos locales **Breakout Distribuido** (DBA) intenta evitar este problema reconociendo lo que se denomina un **cuasi-mínimo local**, en lugar de un mínimo local estándar. La ventaja de los cuasi-mínimos locales es que pueden ser reconocidos por los agentes individuales. !!!def: Definición Un agente se encuentra en un *cuasi-mínimo local* si está violando alguna restricción y ni él ni ninguno de sus vecinos puede hacer un cambio que resulte en un menor costo total para el sistema. Que un agente se encuentre en un cuasi-mínimo local no implica que esté en un mínimo local (algunos agentes no vecinos puedan realizar cambios que reduzcan el coste total). Pero si el sistema está en un mínimo local, al menos un agente se encontrará en un cuasi-mínimo local. --- ## Breakout Distribuido 1. Para escapar de los mínimos locales, el algoritmo identifica los cuasi-mínimos locales y aumenta el coste de las violaciones de las restricciones. 2. DBA mantiene un peso asociado a cada restricción (inicialmente, $1$) y cada vez que un agente se encuentra en un cuasi-mínimo local, aumenta los pesos de las restricciones que se violan. 3. Los pesos se utilizan para calcular el coste de la violación de una restricción: DBA utiliza la suma ponderada de las restricciones violadas. 4. Una restricción violada aumenta su peso, por lo que es más importante satisfacer esa restricción en pasos posteriores que otras que no han sido violadas en asignaciones anteriores. !!! Note Ideas básicas: - Para garantizar la mejora del valor de evaluación, los agentes vecinos intercambian los valores de las posibles mejoras, y sólo el agente que puede mejorar al máximo el valor de evaluación tiene derecho a cambiar su valor (esta comprobación es local, si dos agentes no son vecinos, es posible que cambien sus valores simultáneamente). - Como detectar un mínimo local requiere comunicación global, cada agente detecta cuasi-mínimo local, que es más débil y precisa solo comunicación local. - 2 tipos de mensajes: **ok?** y **improve** (para comunicar la posible mejora del valor de la evaluación). --- ## Breakout Distribuido ~~~~none Modo wait_ok? Si se recibe ("Ok?", x_j, d_j) hacer: añadir (x_j, d_j) a agent_view Si se han recibido mensajes "Ok?" de todos los vecinos, hacer: enviar_improve y entrar en Modo wait_improve entrar en Modo wait_ok? enviar_improve eval_actual ← evaluar valor de valor_actual mi_mejora ← posible máxima mejora nuevo_valor ← valor que da la máxima mejora enviar("improve", x_i, mi_mejora, eval_actual) a vecinos Modo wait_improve si se recibe ("improve", x_j, mejora, eval) hacer: grabar el mensaje Si se han recibido mensajes improve de todos los vecinos, hacer: enviar_ok limpiar agent_view y entrar en Modo wait_ok entrar en Modo wait_improve enviar_ok Si su mejora es la mayor de los vecinos, hacer: valor_actual ← nuevo_valor Si es un cuasi-mínimo local, hacer: incrementa el pero de las restricciones violadas enviar ("Ok?", x_i, valor_actual) a los vecinos ~~~~ --- ## Breakout Distribuido Cuando un agente recibe mensajes **ok?** de todos sus vecinos, calcula su nuevo coste y su posible mejora y envía un mensaje **improve** a todos sus vecinos. Si recibe mensajes **improve** de todos sus vecinos, entonces determina si está en un cuasi-mínimo local. Si es así, aumenta los pesos de las violaciones de las restricciones y envía un mensaje **ok?** a sus vecinos. El rendimiento del DBA es, en promedio, superior a AWCS (que a su vez es superior a ABT). Sin embargo, tiene el problema de que **no es completo**, ya que podría quedarse atascado en un mínimo local. Tampoco será capaz de identificar que un problema concreto carece de solución, y podría quedarse en una ejecución infinita o atascarse en un mínimo local cuando reciba un problema que no tiene solución. Experimentalmente: 1. la distribución de la carga de este algoritmo es bastante desigual (algunos agentes acaban manejando muchos más mensajes que otros). 2. DBA encuentra, en la práctica, los óptimos locales un gran porcentaje de las veces, y hay variaciones que funcionan mejor ($Multi-DB^{++}$ encuentra siempre la solución para los problemas 3SAT).