**SVRAI**
Satisfacción de Restricciones Distribuida (DisCSP)
Definiciones y Algoritmos
# Introducción
!!!
La **Inteligencia Artificial Distribuida** (DAI, por sus siglas en inglés) es un subcampo de la Inteligencia Artificial (IA) que se ocupa de la interacción, especialmente de la coordinación, entre agentes artificiales automatizados para resolver problemas evitando la centralización del proceso y recursos.
Debido a los avances en las tecnologías de hardware y de redes, los entornos informáticos distribuidos se han extendiendo muy rápidamente y como consecuencia han surgido necesidades apremiantes de técnicas distribuidas para mejorar el rendimiento de estos sistemas. Por ello, la DAI se ha convertido en un área vital de investigación en IA.
En este capítulo, y como puerta de entrada a la DAI, presentaremos formalmente los **Problemas de Satisfacción de Restricciones Distribuidos** (DisCSP, por sus siglas en inglés), que no son más que Problemas de Satisfacción de Restricciones (CSP) en los que las variables y las restricciones están distribuidas entre múltiples agentes automatizados (de tal forma que ninguno de ellos conoce la totalidad de las condiciones del problema).
Recordemos que un CSP es un problema que, tras formalizarlo, tiene como objetivo encontrar una asignación consistente (con un conjunto de restricciones conocido) de valores a un conjunto de variables. Aunque la definición de un CSP es muy sencilla, es uno de los mecanismos más universales de representación de problemas, pues existe una variedad sorprendentemente amplia de problemas de IA que pueden formalizarse en su marco. De igual forma, muchos problemas de aplicación de la DAI que se ocupan de encontrar una combinación consistente de acciones/estados de agentes pueden formalizarse como DisCSP.
Por ejemplo, en los *problemas de asignación de recursos distribuidos en una red de comunicación*, cada agente tiene un conjunto de tareas propias, y hay varias formas (planes) de realizar cada tarea. Dado que los recursos (finitos) se comparten entre los agentes, existen restricciones entre los planes (ya que un uso excesivo de recursos por parte de un agente reduce el acceso a recursos del resto). El objetivo del problema es encontrar la combinación de planes que permita la ejecución simultánea de todas las tareas. Este problema puede formalizarse como un DisCSP representando cada tarea como una variable, y los posibles planes como valores variables.
Hay que señalar que, aunque los algoritmos para resolver DisCSPs parecen ser similares a los métodos de procesamiento paralelo/distribuido para resolver CSPs, las motivaciones de la investigación son fundamentalmente diferentes. La principal preocupación en el procesamiento paralelo/distribuido es la eficiencia, y podemos elegir cualquier tipo de arquitectura informática paralela/distribuida para resolver un problema determinado de forma eficiente. En cambio, en un DisCSP la situación en la que el conocimiento sobre el problema (es decir, las variables y las restricciones) está distribuido entre los agentes está prefijada, y el principal problema será cómo llegar a una solución a partir de esta situación dada. Si todo el conocimiento sobre el problema puede reunirse en un solo agente, éste puede resolver el problema por sí solo utilizando algoritmos normales de CSP centralizados. Sin embargo, la recopilación de toda la información sobre un problema requiere no sólo costes de comunicación, sino también los costes de traducción de los conocimientos propios de cada agente a un formato intercambiable entre ellos (una dificultad añadida en sistemas heterogéneos, donde puede haber agentes que implementas arquitecturas informáticas diferentes). Estos costes de centralizar toda la información en un agente podrían ser prohibitivos. Además, en algunas aplicaciones, reunir toda la información en un solo agente no es deseable o es imposible por razones de seguridad/privacidad. En estos casos, varios agentes tienen que resolver el problema sin centralizar toda la información.
A lo largo de este tema presentaremos varios algoritmos básico para resolver DisCSPs, desde el llamado **Backtracking Asíncrono** (**ABT**), en el que los agentes actúan de forma asíncrona y concurrente basándose en su conocimiento local sin ningún tipo de control global, hasta una variante llamada **Búsqueda Asíncrona de Compromiso Débil** (**AWCS**), inspirada en el algoritmo de búsqueda de compromiso débil secuencial que existe para resolver CSPs, y en el que los agentes pueden revisar una mala decisión sin necesidad de realizar una búsqueda exhaustiva, sino cambiando el orden de prioridad de los agentes de forma dinámica.
En ABT se determina el orden de prioridad de los agentes, y cada agente intenta encontrar un valor que satisfaga las restricciones con las variables de los agentes de mayor prioridad. Cuando un agente establece el valor de una variable, el agente se *compromete* fuertemente con el valor seleccionado, es decir, el valor seleccionado no se cambiará a menos que los agentes de menor prioridad realicen una búsqueda exhaustiva y lo indiquen como obligatorio. Por lo tanto, en los problemas a gran escala, un solo error en la selección de valores se convierte en algo fatal, ya que en ese caso la búsqueda exhaustiva es prácticamente imposible. Este inconveniente es común a todos los algoritmos de backtracking. En AWCS, cuando un agente no puede encontrar un valor consistente con los agentes de mayor prioridad, el orden de prioridad se cambia para que el agente que hace el cambio tenga la mayor prioridad. Como resultado, cuando un agente se equivoca al seleccionar un valor, la prioridad de otro agente pasa a ser más alta; así, el agente que cometió el error no se compromete con la mala decisión, y el valor seleccionado se cambia sin consecuencias globales.
Justificaremos cómo AWCS puede resolver varios problemas para los que ABT no consigue resolver en un tiempo razonable. Estos resultados son interesantes, ya que implican que una organización de agentes flexible, en la que el orden jerárquico se cambia dinámicamente, funciona mejor que una organización en la que el orden jerárquico es estático y rígido.
# CSP y DisCSP
## CSP
!!!
Un **Problema de Satisfacción de Restricciones** (**CSP**) está definido por un conjunto de *variables*, *dominios* para cada una de las variables y *restricciones* sobre los valores que las variables pueden tomar simultáneamente. La función de los algoritmos CSP es asignar valores a las variables de forma que sean consistentes con todas las restricciones, o determinar que no existe tal asignación.
Las técnicas de satisfacción de restricciones se han aplicado en diversos ámbitos, desde la *Visión Artificial*, hasta el *Procesamiento de Lenguaje Natural*, pasando por la *Demostración de Teoremas* y la *Planificación* y *Programación*. La esencia de este tipo de problemas queda claramente reflejada en el **Problema de Coloreado de Grafos**, cuyo objetivo es elegir un color para cada nodo de manera que no haya dos nodos adyacentes con el mismo color.
![Figura [graphcoloring]: Un problema de coloreado de grafos](img/graphcoloring.png width="50%")
**Definición: (CSP)**
Formalmente, un CSP consiste en un conjunto finito de variables $X = \{X_1, \ldots, X_n\}$, un dominio $D_i$ para cada variable $X_i$, y un conjunto de restricciones $\{C_1,\ldots , C_m\}$. Aunque en general los CSP permiten dominios infinitos, supondremos que todos los dominios son finitos. (En el ejemplo de coloreado de grafos anterior hay tantas variables como nodos, todas ellas con el mismo dominio de colores disponibles).
Cada restricción es un predicado sobre algún subconjunto de las variables disponibles, $\{X_{i1}, \ldots , X_{ij}\}$. Por tanto, el predicado define una relación que se puede interpretar como un subconjunto del producto cartesiano $D_{i1} \times \cdots \times D_{ij}$, concretamente, el de aquellas tuplas de valores que verifican el predicado. Cada restricción de este tipo restringe los valores que pueden asignarse simultáneamente a las variables que participan en la restricción. En nuestra aproximación restringimos la discusión a las restricciones binarias, en cada una de las cuales intervienen exactamente dos variables. (Por ejemplo, en el caso de la coloración del mapa, cada restricción "*distinto color*" se aplica solo a dos nodos.)
Dado un subconjunto $S$ de las variables, una instanciación de $S$ es una asignación de un valor del dominio para cada variable en $S$; se dice **legal** si no viola ninguna restricción que mencione sólo las variables en $S$. Una **solución global** es una instanciación legal de todas las ($n$) variables del problema.
Las tareas típicas asociadas a los problemas de restricciones son determinar si existe una solución, encontrar una o todas las soluciones, determinar si una instanciación legal de algunas de las variables puede extenderse a una solución global, etc. Nos concentraremos en la tarea más común, que es encontrar una solución global a un CSP, o demostrar que no existe ninguna.
## DisCSP
Un **CSP distribuido** (**DisCSP**) es un CSP en el que las variables y las restricciones están distribuidas entre agentes automatizados.
El objetivo sigue siendo encontrar una asignación global de variables que cumpla las restricciones, pero cada agente decide el valor de su propia variable con relativa autonomía. Aunque no tiene una visión global, cada agente puede comunicarse con sus vecinos en el grafo de restricciones (no confundir con el grafo de comunicaciones, que pueden ser distintos). Asumimos el siguiente modelo de comunicación:
- Los agentes se comunican mediante el envío de mensajes. Un agente puede enviar mensajes a otros agentes si conoce las direcciones de los mismos.
- El retraso en la entrega de un mensaje es finito, aunque aleatorio. Para la transmisión entre cualquier par de agentes, los mensajes se reciben en el orden en que fueron enviados y no se pierden.
Hay que señalar que este modelo no significa necesariamente que la red de comunicación física deba estar totalmente conectada (es decir, un grafo completo). A diferencia de la mayoría de los estudios de algoritmos paralelos/distribuidos, en los que la topología de la red de comunicación física juega un papel importante, nosotros asumimos la existencia de una estructura de comunicación subyacente fiable entre los agentes y no nos preocupamos por la implementación de la red de comunicación física. Esto se debe a que nuestra principal preocupación es la cooperación entre agentes inteligentes, más que la resolución de CSPs mediante determinadas arquitecturas multiprocesador.
!!! Tip
Sin pérdida de generalidad, hacemos las siguientes suposiciones al describir nuestros algoritmos. Relajar estos supuestos a casos generales es relativamente sencillo:
- Cada agente tiene exactamente una variable.
- Todas las restricciones son binarias.
- Cada agente conoce todos los predicados de las restricciones relevantes para su variable.
Por tanto, en lo que sigue utilizamos el mismo identificador $x_i$ para representar a un agente y su variable, que sirve de identificador único.
Un algoritmo distribuido para resolver un CSP hace que cada agente participe en algún protocolo que combina el cálculo local con la comunicación con sus vecinos. Un buen algoritmo garantiza que dicho proceso termina con una solución global (o con la constatación de que no existe ninguna solución global) y que lo haga rápidamente.
Nos centraremos en dos tipos de algoritmos:
* Los algoritmos del primer tipo incorporan un enfoque de mínimo compromiso e intentan descartar valores variables imposibles sin perder ninguna solución posible.
* Los algoritmos del segundo tipo encarnan un espíritu más aventurero y seleccionan valores de variables tentativos, retrocediendo cuando esas elecciones resultan infructuosas.
# Algoritmos para CSPs
Los algoritmos para resolver CSPs pueden dividirse, esencialmente, en dos grupos: *algoritmos de búsqueda* y *algoritmos de consistencia*. Los algoritmos de búsqueda para resolver CSPs se pueden dividir a su vez en dos grandes grupos: *algoritmos de backtracking* y *algoritmos de mejora iterativa*.
## Backtracking
Un *algoritmo de backtracking* es un algoritmo básico de búsqueda sistemática para resolver CSPs. En este tipo de algoritmos se construye una asignación de valores para un subconjunto de variables que satisface todas las restricciones dentro del subconjunto. Esta asignación de valores se denomina *solución parcial*. Una solución parcial se amplía añadiendo nuevas variables una a una, hasta que se convierte en una solución completa. Cuando para una variable, ningún valor satisface todas las restricciones con la solución parcial, se cambia el valor de la última variable añadida a la solución parcial. Esta operación se denomina **backtracking**.
Aunque el backtracking es un simple algoritmo de búsqueda en profundidad en árbol, hay que tener en cuenta muchas cuestiones para mejorar su eficiencia. Por ejemplo, el orden de selección de las variables y los valores afecta en gran medida a la eficiencia del algoritmo. Se han desarrollado varias heurísticas durante la larga historia de los estudios de CSP.
Una heurística de ordenación de valores llamada **heurística de mínimo-conflicto** es una de las más exitosas. En esta heurística, cada variable tiene un valor inicial tentativo, que se revisa cuando la variable se añade a la solución parcial. Como es un algoritmo de backtracking, el valor revisado debe satisfacer todas las restricciones con las variables en la solución parcial. Si existen varios valores que satisfacen todas las restricciones con la solución parcial, se elige el que satisface el mayor número posible de restricciones con valores iniciales provisionales.
## Mejora iterativa
En los *algoritmos de mejora iterativa*, al igual que ocurría en el backtracking de mínimo conflicto, todas las variables tienen valores iniciales tentativos. Sin embargo, no se construye una solución parcial consistente. Una solución defectuosa que contiene todas las variables se revisa utilizando la *búsqueda de ascenso de la colina*. La heurística de mínimo conflicto puede utilizarse para guiar el proceso de búsqueda, es decir, se cambia el valor de una variable de forma que se minimice el número de violaciones de las restricciones.
Como estos algoritmos son algoritmos de búsqueda de ascenso de la colina, ocasionalmente pueden quedar atrapados en mínimos locales. Los mínimos locales son estados que violan algunas restricciones, pero en los que el número de violaciones de las restricciones no puede reducirse cambiando el valor de una sola variable. Se han propuesto varios métodos para escapar de los mínimos locales. Por ejemplo, en el **algoritmo Breakout** se define un peso para cada restricción (el peso inicial es 1), y la suma de los pesos de las restricciones violadas se utiliza como valor de evaluación. Cuando está atrapado en un mínimo local, el algoritmo aumenta los pesos de las restricciones violadas en el estado actual en 1, de modo que el valor de evaluación del estado actual sea mayor que el de los estados vecinos.
En los algoritmos de mejora iterativa, se puede revisar un error sin realizar una búsqueda exhaustiva, es decir, se puede revisar la misma variable una y otra vez. Por tanto, estos algoritmos pueden ser eficientes, pero no se puede garantizar su exhaustividad.
Existen varios *algoritmos híbridos* que mezclan ideas de backtracking y de mejora iterativa. Por ejemplo, el *algoritmo de búsqueda de compromiso débil* se basa en el backtracking de mínimo conflicto. Sin embargo, en este algoritmo, cuando para una variable ningún valor satisface todas las restricciones con la solución parcial, en lugar de cambiar el valor de una variable, se abandona toda la solución parcial. El proceso de búsqueda se reinicia utilizando las asignaciones de valores actuales como nuevos valores iniciales tentativos. Este algoritmo es similar a los algoritmos de tipo de mejora iterativa, ya que los nuevos valores iniciales tentativos suelen ser mejores que los valores iniciales de la iteración anterior.
## Algoritmos de consistencia
Los algoritmos de consistencia son algoritmos de preprocesamiento que reducen el backtracking inútil. Se pueden clasificar según la noción de $k$-consistencia que presentaremos con más detalle más adelante (un CSP es $k$-consistente si dada cualquier instanciación de cualesquiera $k - 1$ variables que satisfagan todas las restricciones entre esas variables, es posible encontrar una instanciación de cualquier $k$-ésima variable tal que los $k$ valores satisfagan todas las restricciones entre ellas). Si hay $n$ variables en un CSP y el CSP es $k$-consistente para todo $k \leq n$, entonces se puede obtener una solución inmediatamente sin ningún backtracking. Sin embargo, conseguir un grado tan alto de consistencia requiere un coste computacional muy elevado, por lo que debemos encontrar una combinación adecuada de algoritmos de consistencia y backtracking para que los costes totales de búsqueda se minimicen.
# Algoritmos triviales para DisCSP
Entre los algoritmos de búsqueda para DisCSPs podemos destacar dos que son triviales:
## Método centralizado
El algoritmo más trivial para resolver un DisCSP es seleccionar un agente líder entre todos los agentes, y reunir toda la información sobre las variables, sus dominios, y sus restricciones en el agente líder. A continuación, el líder resuelve el CSP utilizando algoritmos de CSP centralizados habituales y distribuye, si fuera necesario, la solución.
Sin embargo, como hemos comentado, el coste de recopilar toda la información sobre un problema puede ser prohibitivo. Además, en algunas aplicaciones, como los agentes de software en los que cada agente actúa como secretario de un individuo, reunir toda la información a un agente no es deseable o es imposible por razones de seguridad/privacidad.
## Backtracking Síncrono
El algoritmo de backtracking estándar para CSP puede modificarse para obtener el **algoritmo de Backtracking Síncrono** (SBT) para DisCSPs. Supongamos que los agentes acuerdan un orden de instanciación para sus variables (por ejemplo, el agente $x_1$ va primero, luego el agente $x_2$, y así sucesivamente). Cada agente, al recibir una solución parcial (las instancias de las variables precedentes) del agente anterior, instanciará 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 ninguna instanciación de su variable puede satisfacer las restricciones, entonces envía un mensaje de backtracking al agente anterior.
Aunque este algoritmo no sufre la misma sobrecarga de comunicación que el método centralizado, determinar el orden de instanciación sigue requiriendo ciertos costes de comunicación. Además, este algoritmo no puede aprovechar el paralelismo (hay ligeras variantes que sí admiten cierta concurrencia construyendo un árbol de jerarquía, en vez de una jerarquía lineal). Dado que, en un momento dado, sólo un agente recibe la solución parcial y actúa sobre ella, el problema se está resolviendo, de hecho, de forma secuencial.
# Reducción de dominios
En los métodos de reducción de dominios, los nodos se comunican con sus vecinos para eliminar valores de sus dominios. Consideraremos dos algoritmos que hacen uso de estos métodos. En el primero, el **algoritmo de Filtrado**, cada nodo comunica su dominio a sus vecinos, elimina de su dominio los valores que no son consistentes con los valores recibidos de los vecinos, y el proceso se repite. En concreto, cada nodo $x_i$ con dominio $D_i$ ejecuta repetidamente el procedimiento $Revisa(x_i, x_j)$ para cada vecino $x_j$.
~~~~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, conocido también bajo el término general de **consistencia de arco** o **2-consistencia**, termina cuando no se produce ninguna eliminación más, o cuando uno de los dominios queda vacío (en cuyo caso el problema no tiene solución). Si el proceso 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; el problema podría tener o no solución, y el algoritmo no lo determina.
Está claro que el algoritmo **siempre para**, y además es **correcto** (en el sentido de que si anuncia una solución, o anuncia que no existe solución, la respuesta es correcta), pero **no es completo** (es decir, hay casos en los que puede no pronunciar un veredicto). Consideremos, por ejemplo, la familia de pequeños problemas de coloreado de grafos que se muestra en la siguiente figura:
![Figura [familiacolgraph]: Una familia de problemas de coloreado de grafos](img/sma2-7.png width="75%")
Todos los problemas comparten la estructura del grafo subyacente y de las restricciones entre los nodos, lo que cambia son los dominios de las variables. Vamos a analizar qué ocurre en cada uno de esos casos:
* (a) Inicialmente, cuando los nodos se comunican entre sí, sólo los mensajes de $x_1$ producen algún cambio. En concreto, 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 aún más su dominio a $D_3=\{verde\}$. En este punto no se producen más cambios y el algoritmo termina con una solución correcta.
* (b) El algoritmo comienza como antes, pero una vez que $x_2$ y $x_3$ reciben el mensaje de $x_1$, cada uno reduce sus dominios a $\{azul\}$. Ahora, cuando se actualizan mutuamente en sus nuevos dominios, cada uno reduce sus dominios a $\emptyset$, el conjunto vacío. En este punto 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.
!!! Note
En general, el filtrado es un método muy débil y, en el mejor de los casos, se utiliza como paso previo a métodos más sofisticados. El algoritmo se basa directamente en la noción de **resolución unitaria** de la Lógica Proposicional, que se corresponde con la siguiente regla de inferencia:
$$
\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}
$$
Para ver cómo el algoritmo de filtrado se corresponde con la resolución de unidades, primero debemos escribir las restricciones como combinaciones prohibidas de valores, llamadas *No-goods*. Por ejemplo, la restricción de que $x_1$ y $x_2$ no pueden tomar ambos el valor $rojo$ daría lugar a la sentencia proposicional $\neg(x_1 = rojo \wedge x2 = rojo)$. En el caso (b) de la figura anterior, el agente $x_2$ actualizó su dominio basándose en el anuncio del agente $x_1$ de que $x_1 = rojo$ y en el No-good $\{x_1 = rojo, x_2 = rojo\}$.
$$
\begin{array}{c}
x_1=rojo\\
\neg(x_1=rojo\wedge x_2=rojo)\\ \hline
\neg(x_2=rojo)
\end{array}
$$
!!!
La resolución unitaria es una regla de inferencia muy débil, por lo que no es de extrañar que el algoritmo de filtrado también lo sea si es todo lo que usa. Para resolver el problema de su debilidad (que se basa en que no es capaz de ver combinaciones prohibidas que afecten a más variables simultáneamente) podemos introducir una versión más potente de la regla de resolución por medio de la **hiperresolución**, que es una generalización de la resolución unitaria con la siguiente forma:
$$
\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 para la Lógica Proposicional, y de hecho da lugar a un algoritmo para DisCSP completo. En este algoritmo, cada agente genera repetidamente nuevas restricciones para sus vecinos, les notifica estas nuevas restricciones y poda su propio dominio basándose en las nuevas restricciones que le pasan sus vecinos. En concreto, podemos expresarlo de la siguiente forma, donde $NG_i$ es el conjunto de todos los *No-goods* de los que el agente $i$ tiene conocimiento y $NG^∗_j$ es un conjunto de nuevos *No-goods* comunicados por el agente $j$ al agente $i$:
~~~~
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
~~~~
Se garantiza que el algoritmo para porque solo hay una combinación finita de posibilidades, así que solo se enviarán y recibirán una cantidad finita de mensajes, y llega un momento en que cada agente dejará de enviar mensajes y de generar *No-goods*. Además, el algoritmo es completo: el problema tiene solución si, al finalizar, ningún agente ha generado el *No-good* vacío, y no tiene solución en caso contrario.
Consideremos de nuevo el caso (c) de los ejemplos anteriores. A diferencia del algoritmo del filtrado básico (basado en resolución unitaria), el algoritmo basado en hiperresolución procede como sigue:
Inicialmente, $x_1$ mantiene cuatro *No-goods*:
$\{x_1 = rojo, x_2 = rojo\}$,
$\{x_1 = rojo, x_3 = rojo\}$,
$\{x_1 = azul, x_2 = azul\}$,
$\{x_1 = azul, x_3 = azul\}$,
que se derivan directamente de las restricciones que afectan a $x_1$. Además, $x_1$ debe adoptar uno de los valores de su dominio, por lo que $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}
$$
Así, $x_1$ construye el nuevo *No-good* $\{x_2 = rojo, x_3 = azul\}$; de forma similar también puede construir el *No-good* $\{x_2 = azul, x_3 = rojo\}$, y a continuación envía ambos *No-goods* a sus vecinos $x_2$ y $x_3$. Usando su dominio, un *No-good* existente y uno de estos nuevos *No-goods*, $x_2$ puede razonar:
$$
\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}
$$
Utilizando el otro *No-good* de $x_1$ ($\{x_2 = azul, x_3 = rojo\}$), $x_2$ también puede construir el *No-good* $\{x_3 = rojo\}$. Estos dos *No-goods* únicos se comunican a $x_3$ y le permiten generar el *No-good* vacío. Lo que demuestra que el problema no tiene solución.
Este ejemplo, aunque demuestra la mayor potencia del algoritmo basado en hiperresolución en relación con el algoritmo basado en resolución unitaria, también expone su debilidad: el número de *No-goods* generados puede llegar a ser inmanejablemente grande (de hecho, en el ejemplo sólo hemos descrito el número mínimo de *No-goods* necesarios para derivar el *No-good* vacío, pero se crearían muchos otros a medida que todos los agentes procesaran los mensajes de los demás en paralelo).
De hecho, en un curso básico de Lógica Proposicional se pueden encontrar fuertes similitudes entre la aproximación que hemos visto en estos ejemplos y el problema SAT de fórmulas proposicionales por medio de resolución, un problema que se sabe **NP**-completo y para el que no podemos esperar construir un algoritmo eficiente.
Así, la situación en la que nos encontramos es que tenemos un algoritmo demasiado débil (no completo) y otro poco práctico (**NP**-completo). El problema de ambos radica en la naturaleza de mínimo compromiso de estos algoritmos; están restringidos a eliminar sólo combinaciones de valores probadamente imposibles. La alternativa a estos procedimientos *seguros* es explorar un subconjunto del espacio, haciendo selecciones tentativas de valores para las variables y retrocediendo cuando sea necesario. El resultado no será un algoritmo eficiente en todos los casos, pero esperamos obtener uno que no se comporte muy mal en el caso medio.
Sin embargo, los algoritmos que acabamos de describir no son irrelevantes; el algoritmo de filtrado (basado en resolución unitaria) es un paso eficaz de preprocesamiento, y en realidad el algoritmo que presentamos a continuación se basa en el algoritmo basado en hiperresolución.
## Algoritmos de Búsqueda Heurística
Una solución centralizada de prueba y error para un CSP consiste en ordenar primero las variables (por ejemplo, alfabéticamente, aunque existen estrategias más prometedoras), para luego, a partir de esa jerarquía $x_1, x_2,\dots , x_n$, llamar al procedimiento $SeleccionaValor(x_1, \{\})$. Este procedimiento se define recursivamente como sigue, donde $\{v_1, v_2,\dots , v_{i-1}\}$ es el conjunto de valores asignados a las variables $x_1,\dots , x_{i-1}$:
~~~~none
Procedimiento SeleccionaValor(x_i, {v_1, v_2, ... , v_{i−1}})
v_i ← d, donde d ∈ D_i consistente con {v_1, v_2, ... , v_{i−1}}
Si no existe d, entonces:
backtrack
si existe e i = n, entonces:
Parar
si no, entonces:
SeleccionaValor(x_{i+1}, {v_1, v_2, ... , v_i})
~~~~
Hay varias formas de implementar el backtracking en este procedimiento. La forma más sencilla es deshacer las elecciones realizadas hasta el momento en orden cronológico inverso, un procedimiento conocido como **backtracking cronológico**, aunque se sabe que hay procedimientos de backtracking más sofisticados que pueden ser más eficientes.
Esta búsqueda exhaustiva del espacio de asignaciones tiene la ventaja de ser completa. Pero está muy *pobremente distribuida*, ya que los diferentes agentes se ejecutan secuencialmente, imitando la ejecución de un algoritmo centralizado.
Una nueva aproximación buscará mejorarlo: permitirá que los agentes se ejecuten en paralelo y de forma asíncrona, será también correcta,... pero no será completa. Consideremos el siguiente procedimiento, ejecutado por todos los agentes 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
~~~~
Evidentemente, cuando el algoritmo termina porque no se ha producido ninguna violación de las restricciones, se ha encontrado una solución. Pero en el resto de los casos, todo está perdido. Si el algoritmo termina porque ningún agente puede encontrar un valor consistente con los de sus vecinos, todavía podría haber una asignación global consistente. Y puede que el algoritmo no termine nunca aunque haya una solución. Por ejemplo, consideremos el ejemplo (d) anterior: si cada agente hace un ciclo secuencial entre el rojo, el verde y el azul, el algoritmo nunca terminará, a pesar de que hay una solución posible.
Hemos dado estas dos aproximaciones por dos razones:
1. La primera es mostrar que reconciliar el verdadero paralelismo y la asincronía con la corrección y completitud probablemente necesite algoritmos más elaborados.
2. Y en segundo lugar, mostrar que el algoritmo heurístico fundamental para los CSP distribuidos, el **algoritmo de backtracking asíncrono** (o ABT), comparte mucho con estos dos algoritmos introductorios. De la primera aproximación, ABT toma prestada la noción de un ordenamiento total de los agentes. De la segunda, toma prestado un protocolo de paso de mensajes, de comunicación, aunque algo más compleja que la anterior, que se basa en este ordenamiento global. Describiremos el ABT en su forma más simple. Después de demostrarlo en un ejemplo ampliado, señalaremos las formas en que puede mejorarse.
# Backtracking Asíncrono
## Visión general
El ABT elimina los inconvenientes del backtracking síncrono 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.
Recordemos que representamos un DisCSP en el que todas las restricciones son binarias como una red en la que las variables son nodos y las restricciones (que son binarias) son enlaces entre nodos (esta red de restricciones no tiene nada que ver con la red de comunicación física, los enlaces de la red de restricciones no son enlaces de comunicación físicas, sino relaciones lógicas entre agentes). Al igual que en los casos anteriores, como cada agente tiene exactamente una variable, un nodo también representa a un agente, por lo que utilizamos el mismo identificador para representar un agente y su variable. También asumiremos que cada enlace de restricción es dirigido, concretamente, un enlace está dirigido desde el agente que envía los valores hasta el agente que evalúa la restricción. Por ejemplo, en la siguiente figura hay tres agentes, $x_1$, $x_2$, $x_3$, con dominios variables $\{1, 2\}$, $\{2\}$, $\{1, 2\}$, respectivamente, y restricciones $x1 \neq x3$ y $x2\neq x3$.
![Figura [RedRestricciones]: Ejemplo de red con restricciones](img/sma2-23.png width="50%")
Cada agente instancia su variable de forma concurrente y envía el valor a los agentes que están conectados por enlaces salientes. A continuación, los agentes esperan y responden a los mensajes que reciben (con acciones que modifican sus asignaciones, y la creación y envío de nuevos mensajes). En el código del algoritmo se describen los procedimientos ejecutados por el agente $x_i$ al recibir dos tipos de mensajes (aunque se da una descripción secuencial, es solo por nuestro sistema habitual de describirlo y, de hecho, un agente puede manejar múltiples mensajes de forma concurrente, es decir, el agente primero revisa $vista$ y $lista\_nogood$ de acuerdo con los mensajes que ha recibido, y realiza **comprobar_vista** sólo una vez cuando acaba de procesar los mensajes):
* un mensaje de tipo **ok?**, que un agente evaluador de restricciones recibe de un agente emisor de valores preguntando si el valor elegido es aceptable para él,
* y un mensaje de tipo **nogood** que recibe un agente emisor de valores, indicando que el agente evaluador de restricciones ha encontrado una violación de las mismas según su visión del mundo.
~~~~none
Cuando se reciba ["Ok?", (x_j, d_j)]:
añadir (x_j, d_j) a mi vista
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 mío hacer:
añadir (x_k, d_k) a mi vista
Pedir a x_k que me añada 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
valor_actual ← d
enviar ["Ok?", (x_i, d)] a mis 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
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 mi vista
~~~~
!!! Tip
Observa que un agente puede actuar como evaluador en algunas relaciones, y como emisor en otras.
Cada agente lleva control en una variable propia, llamada $vista$, del conjunto de valores asignados por los agentes que le pueden enviar valores (aquellos que tienen aristas salientes que llegan hasta él). Concretamente, lo almacena como una lista de pares de la forma $(x,d)$ donde $d$ es el valor que el agente considera asignado al agente $x$. Si se recibe uno de estos pares en un mensaje **ok?** por medio de un enlace entrante, el agente evaluador añadirá el par a su $vista$ (si ya tenía ese valor asignado, lo cambiará) y posteriormente comprobará la consistencia de su nueva $vista$ con el valor de su variable (representada como $(x_i, valor\_actual)$). Si su propia asignación no es consistente con su $vista$, el agente $x_i$ intenta cambiar su $valor\_actual$ para obtener la consistencia con su $vista$ (un agente solo puede cambiar el valor de su propia variable, el de ninguno más, por eso se usan mensajes para intentar que los implicados en restricciones tengan el conocimiento necesario acerca de la satisfactibilidad de las restricciones). Más adelante veremos cómo se comprueba la consistencia...
Un subconjunto de una $vista$ se llama $nogood$ si el agente no es capaz de encontrar ningún valor de su variable consistente con ese subconjunto. Por ejemplo, en el ejemplo anterior, si los agentes $x_1$ y $x_2$ instancian sus variables a 1 y 2, respectivamente, la $vista$ de $x_3$ será $\{(x_1, 1), (x_2, 2)\}$, como no hay ningún valor posible para $x_3$ que sea consistente con $vista$, esta $vista$ es un $nogood$. Si un agente encuentra que un subconjunto de su $vista$ es un $nogood$ la única solución para encontrar una solución pasa por que otros agentes cambien sus asignaciones (en este sentido, lo ideal es que los nogoods detectados sean **minimales**, para que afecten al menor número posible de agentes, pero se puede probar que en general este problema es intratable, así que una solución puede ser intentar trabajar con **nogoods no minimales**, por ejemplo, usar el conjunto entero $vista$ como nogood). Ante esta situación, la solución es que el agente provoque un backtracking, y para comunicarlo a los agentes que están involucrados envía un mensaje **Nogood** a uno de los otros agentes (no a todos, para no activar demasiados cambios, pero a cuál, será algo que decidiremos también más adelante).
Considerando las restricciones y los $nogoods$ ya podemos ver cómo determinar la consistencia de una $vista$ con su valor: una $vista$ es consistente con el valor del agente si:
* se verifican todas las restricciones que el agente puede evaluar (las correspondientes a las aristas que entran en él) y
* no es compatible con los $nogoods$ que almacena (recordemos que los $nogoods$ son precisamente trozos de combinaciones que impiden formar soluciones).
## Evitar bucles infinitos
Si no controlamos la forma en que los agentes cambian sus valores, podríamos entrar en un bucle infinito en el que una y otra vez cambian los valores y nunca alcanzan un estado estable. Un bucle así puede ocurrir si existe un bucle de cambio de valores de los agentes, como 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 representación de la red, este bucle se reflejaría mediante un ciclo de enlaces dirigidos.
Así pues, una forma de evitar estos ciclos en un grafo es obligar que la red sea *acíclica dirigida*, por ejemplo, utilizando una relación de orden total entre los nodos. Si cada nodo tiene un identificador único, podemos definir un orden de prioridad entre los agentes utilizando el orden alfabético de estos identificadores (el agente anterior en el orden alfabético tiene mayor prioridad). Si los enlaces se dirigen utilizando este orden de prioridad (del agente de mayor prioridad al de menor prioridad) la red resultante será acíclica. Esto significa que, para cada restricción, el agente de menor prioridad será evaluador, y el de mayor prioridad enviará los mensajes de tipo **ok?** al evaluador.
Además, 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.
El conocimiento que cada agente requiere para este método es mucho más local que el necesario para el backtracking síncrono anterior. En el SBT, los agentes deben actuar en un orden secuencial predefinido. Este orden secuencial no puede obtenerse fácilmente dando un identificador único a cada agente. Cada agente debe conocer al anterior y al siguiente, lo que implica sondear a todos los demás agentes para encontrar los identificadores más cercanos por encima y por debajo de él. Por otro lado, en el método del identificador único para el backtracking asíncrono, cada agente tiene que conocer sólo los identificadores de un agente con el que debe establecer una restricción para dirigirla.
## Tratamiento de los cambios asíncronos
Como los agentes cambian sus instancias de forma asíncrona, una $vista$ puede estar sujeta a cambios sin parar. Esto puede llevar a potenciales inconsistencias, porque un agente evaluador de restricciones podría enviar un mensaje $nogood$ a un agente que ya ha cambiado el valor de su variable como resultado de otras restricciones. En esencia, debido a la asincronía, el mensaje **Nogood** puede basarse en información obsoleta y, en ese caso, el agente que recibe el mensaje no tendría que volver a cambiar su valor.
Para evitar este problema, después de recibir este mensaje, el receptor sólo cambia su valor si el $nogood$ recibido es compatible con su actual $vista$ y su propia asignación (por eso en la definición de consistencia se habla de los $nogoods$ en el segundo punto).
En realidad, un $nogood$ puede verse como una nueva restricción derivada de las restricciones originales. Al incorporar esta nueva restricción, los agentes pueden evitar repetir el mismo error. Por ejemplo, en el ejemplo anterior, el $nogood$ $\{(x_1, 1), (x_2, 2)\}$ representa una restricción adicional entre $x_1$ y $x_2$. Como originalmente no hay ningún enlace/restricción entre $x_1$ y $x_2$, hay que añadir un nuevo enlace entre ellos cuando se *descubre* esta nueva restricción (en forma de $nogood$) para evitar tener que pasar por el procesamiento continuo de $x_3$ para poder detectarla. Por tanto, tras recibir el mensaje **Nogood**, el agente $x_2$ (que es el de menor prioridad) le pediría a $x_1$ que añada un enlace entre ellos ($x_1\rightarrow x_2$).
En general, aunque todas las restricciones originales sean binarias, las nuevas restricciones derivadas podrían hacer intervenir más de dos variables. En tal caso, solo uno de los agentes, el que tiene la menor prioridad entre los que intervienen en la nueva restricción, hará el papel de evaluador y los enlaces se añadirán desde cada uno de los otros agentes a él.
## Ejemplo
Primero veremos como ejemplo el caso sencillo del coloreado simple que hemos venido analizando:
Consideremos de nuevo la instancia (c) de la colección de ejemplos anterior, y supongamos que los agentes están ordenados alfabéticamente: $x_1$, $x_2$, $x_3$.
Inicialmente, cada uno selecciona un valor posible se su variable aleatoriamente. Supongamos que todos seleccionan el valor $azul$. Tras esa elección, cada uno notifica a los de rango inferior su valor: $x_1$ se la notifica a $x_2$ y a $x_3$, y $x_2$ se la notifica a $x_3$ (recuerda que los inferiores no molestan a los superiores con su visión del mundo). Así pues, la visión local de $x_2$ es $\{x_1 = azul\}$, y la de $x_3$ es $\{x_1 = azul, x_2 = azul\}$. Lo primero que han de hacer $x_2$ y $x_3$ es comprobar la coherencia de sus visiones locales con sus propios valores.
En paralelo (o asíncronamente):
* $x_2$ detecta un conflicto, que se produce con $x_1$, de rango superior, por lo que cambia su propio valor a $rojo$ y lo notifica a $x_3$ (su inferior).
* Simultáneamente, $x_3$ también comprueba su consistencia, detecta el conflicto y cambia igualmente su valor a $rojo$, que le permite mantener la coherencia con su visión del mundo; sin embargo, no lo notifica a nadie, porque no tiene inferiores a él.
En este proceso $x_3$ tiene en su pila un mensaje de tipo **ok?** de $x_2$ por procesar, que le hace actualizar su vista local a $\{x_1 = azul, x_2 = rojo\}$, y su valor es $rojo$. En este punto no puede encontrar un valor de su dominio que sea consistente con su visión local y, utilizando la hiperresolución, genera el nogood $\{x_1 = azul, x_2 = rojo\}$ y se lo comunica a $x_2$, el agente de menor rango que participa en ese nogood.
Al procesar el mensaje **Nogood** recibido de $x_3$, $x_2$ no puede encontrar un valor consistente con su visión local, genera el nogood $\{x_1 = azul\}$, y lo comunica a $x_1$.
Al procesar el mensaje **Nogood** recibido de $x_2$, $x_1$ detecta la inconsistencia con su valor actual, cambia su valor a $rojo$, y comunica el nuevo valor a $x_2$ y $x_3$. El proceso continúa ahora como antes; $x_2$ cambia su valor de nuevo a $azul$, $x_3$ no encuentra ningún valor consistente y genera el nogood $\{x_1 = rojo, x_2 = azul\}$, y entonces $x_2$ genera el nogood $\{x_1 = rojo\}$.
En este punto $x_1$ tiene el nogood $\{x_1 = azul\}$ así como el nogood $\{x_1 = rojo\}$, y usando la hiperresolución genera el nogood $\{\}$, y el algoritmo termina habiendo determinado que el problema no tiene solución.
Veamos a continuación un ejemplo en el que se comprueba la necesidad de añadir nuevas aristas de restricción a partir de $nogoods$:
![Figura [cadena]: Cadena de mensajes y operaciones desencadenadas en la ejecución de un ABT donde se crea una arista nueva](img/sma2-8.png width="50%")
En la figura anterior (a), al recibir mensajes **ok?** de $x_1$ y $x_2$, la $vista$ de $x_3$ será $\{(x_1, 1), (x_2, 2)\}$. Como no hay ningún valor posible para $x_3$ que sea consistente con esta vista, el contenido de $vista$ se convierte en $nogood$. El agente $x_3$ elige el agente de menor prioridad en la vista, es decir, el agente $x_2$, y envía un mensaje **nogood** con este $nogood$ como contenido.
Al recibir este mensaje **nogood**, el agente $x_2$ lo almacena en su $lista\_nogoods$, y como contiene al agente $x_1$, que no está conectado con $x_2$ por un enlace, le solicita a $x_1$ que se conecte con él, lo que también provoca que se envíe el valor de $x_1$ a $x_2$, y éste añada $(x_1, 1)$ a su $vista$ (figura (b)). Entonces, el agente $x_2$ comprueba si su valor es coherente con su vista. Como el $nogood$ recibido del agente $x_3$ no es compatible con su propio valor, $(x_2, 2)$, y su vista $\{(x_1, 1)\}$, ésta se convierte en $nogood$ porque $x_2$ no tiene otros valores posibles. Sólo hay un agente en este nuevo $nogood$, el agente $x_1$ (con el que ya está conectado), por lo que el agente $x_2$ envía un mensaje **nogood** al agente $x_1$ (figura (c)).
### El Problema de las 4 Reinas
Para que el algoritmo ABT se aprecie mejor que el ejemplo didáctico anterior, que es demasiado pequeño, veamos uno de los problemas CSP canónicos: el problema de las $N$ reinas. Más concretamente, consideraremos el problema de las 4 reinas, que plantea cómo colocar 4 reinas en un tablero de ajedrez de $4 \times 4$ de forma que ninguna reina amenace a ninguna otra. Describiremos el comportamiento de ABT en términos de ciclos del algoritmo, que definimos de forma un tanto artificial como el bloque de ejecuciones que contiene la recepción de mensajes, los cálculos desencadenados por los mensajes recibidos, y el envío de nuevos mensajes debido a esos cálculos.
![Figura [ciclo1]: Ciclo 1 de ABT para 4 reinas. Todos los agentes están activos](img/sma2-9.png)
En el ciclo 1 todos los agentes seleccionan valores para sus variables, que representan las posiciones de sus reinas a lo largo de sus respectivas filas. Arbitrariamente, suponemos que cada uno comienza colocando su reina en la primera casilla de su fila. Cada uno de los agentes 1, 2 y 3 envía mensajes de **ok?** a los agentes ordenados después de él: $x_1$ envía tres mensajes, $x_2$ envía dos y el agente $x_3$ envía un solo mensaje. El agente $x_4$ no tiene ningún agente detrás de él, por lo que no envía ningún mensaje. Todos los agentes están activos en este primer ciclo de la ejecución del algoritmo.
![Figura [ciclo2]: Ciclo 2 de ABT para 4 reinas](img/sma2-10.png)
En el Ciclo 2 los agentes $x_2$, $x_3$ y $x_4$ reciben los mensajes **ok?** que se les enviaron y proceden a asignar valores coherentes a sus variables. El agente $x_3$ asigna, por ejemplo, el valor 4, que es consistente con las asignaciones de $x_1$ y $x_2$ que recibe. El agente $x_4$ no tiene ningún valor consistente con las asignaciones de $x_1$, $x_2$ y $x_3$ que ha recibido, por lo que envía un **Nogood** que contiene estas tres asignaciones a $x_3$ y elimina la asignación de $x_3$ de su visión del agente ($x_1 = 1 \wedge x_2 = 1 \rightarrow x_3 \neq 1$). Luego, asigna el valor 2 que es consistente con las asignaciones que recibió de $x_1$ y $x_2$ (habiendo borrado la asignación de $x_3$, asumiendo que será reemplazada por el mensaje **Nogood**). Los agentes activos en este ciclo son $x_2$, $x_3$ y $x_4$. El agente $x_2$ actúa según su información sobre la posición de $x_1$ y se mueve a la casilla 3, enviando dos mensajes **ok?** para informar a sus sucesores sobre su valor. Como puede verse en la figura anterior, $x_3$ se ha movido a la casilla 4 tras recibir los mensajes **ok?** de los agentes $x_1$ y $x_2$. Nótese que el agente $x_3$ piensa que estos agentes siguen en la primera columna de sus respectivas filas. Esta es una manifestación de la concurrencia que hace que cada agente actúe en todo momento de una forma que se basa únicamente en su vista. La vista del agente $x_3$ incluye los mensajes de **ok?** que ha recibido.
![Figura [ciclo3]: Ciclo 3 de ABT para 4 reinas](img/sma2-11.png)
En el ciclo 3 sólo $x_3$ está activo. Tras recibir la asignación del agente $x_2$, $x_3$ devuelve un mensaje **Nogood** al agente $x_2$ ($x_1 = 1 \rightarrow x_2\neq 3$). A continuación, borra la asignación del agente $x_2$ de su vista y valida que su asignación actual (el valor 4) es consistente con la asignación del agente $x_1$. Los agentes $x_1$ y $x_2$ siguen estando inactivos, ya que no han recibido ningún mensaje que se haya enviado en el paso anterior. Lo mismo ocurre con el agente $x_4$. El agente $x_3$ también recibe el $Nogood$ enviado por $x_4$ en el paso anterior, pero lo ignora porque incluye una asignación no válida para $x_2$ según su visión del mundo.
![Figura [ciclo45]: Ciclos 4 y 5 de ABT para 4 reinas](img/sma2-12.png)
La Figura [ciclo45] anterior representa los pasos 4 y 5. En el paso 4, el agente $x_2$ se mueve a la casilla 4 debido al mensaje **Nogood** que recibió. Su valor anterior fue descartado y el nuevo valor es el siguiente válido. Informa a sus sucesores $x_3$ y $x_4$ de su nueva posición enviando dos mensajes **ok?**. En el ciclo 5, el agente $x_3$ recibe la nueva posición del agente $x_2$ y selecciona el único valor compatible con las posiciones de sus dos predecesores, la casilla 2. Envía un mensaje a su sucesor informándole de este nuevo valor. El agente $x_4$ se queda ahora sin ningún valor válido que asignar y envía un mensaje **Nogood** a $x_3$ que incluye todos sus conflictos ($x_1 = 1 \wedge x_2 = 4 \rightarrow x_3 \neq 4$). Obsérvese que el mensaje **Nogood** ya no es válido. El agente $x_4$, sin embargo, asume que $x_3$ cambiará su posición y se mueve a su única posición válida (dado el movimiento anticipado de $x_3$): la columna 3.
![Figura [ciclo6]: Ciclo 6 de ABT para 4 reinas](img/sma2-13.png)
Consideremos ahora el ciclo 6. El agente $x_4$ recibe la nueva asignación del agente $x_3$ y le envía un mensaje **Nogood** ($x_1 = 1\wedge x_2 =4 \rightarrow x_3 \neq 2$). Tras borrar la asignación de $x_3$ después de enviar el mensaje **Nogood**, decide quedarse en su asignación actual (columna 3), ya que es compatible con las posiciones de los agentes $x_1$ y $x_2$. El agente $x_3$ está inactivo en el paso 6, ya que no recibe mensajes del agente $x_1$ ni del agente $x_2$ (que también están inactivos). Por tanto, $x_4$ es el único agente activo en el paso 6.
![Figura [ciclo78]: Ciclos 7 y 8 de ABT para 4 reinas](img/sma2-14.png)
En cada uno de los ciclos 7 y 8 se envía un $nogood$ ($x_1 = 1 \rightarrow x_2\neq 4$ y $x_1\neq 1$). En primer lugar, el agente $x_3$, tras recibir el mensaje **Nogood** de $x_4$, comprueba que no le quedan valores válidos y envía un **Nogood** a $x_2$. A continuación, en el paso 8, el agente $x_2$ también descubre que su dominio de valores se ha agotado y envía un mensaje **Nogood** a $x_1$. Ambos agentes emisores borran los valores de sus sucesores (a los que se enviaron los mensajes **Nogood**) de sus vistas y, por tanto, permanecen en sus posiciones, que ahora están libres de conflicto.
![Figura [ciclo9]: Ciclo 9 de ABT para 4 reinas](img/sma2-15.png)
En el ciclo 9 sólo interviene el agente $x_1$, que recibe el mensaje **Nogood** de $x_2$ y, por tanto, se desplaza a su siguiente valor, la casilla 2. A continuación, envía mensajes **ok?** a sus tres sucesores.
![Figura [ciclo10]: Ciclo 10 de ABT para 4 reinas](img/sma2-16.png)
El último ciclo es el 10. El agente $x_3$ recibe el mensaje **ok?** de $x_1$ y se desplaza a la casilla de valor 1 de su fila. Los agentes $x_2$ y $x_4$ comprueban sus vistas después de recibir los mismos mensajes **ok?** del agente $x_1$ y encuentran que sus valores actuales son consistentes con la nueva posición de $x_1$. El agente $x_3$ envía un mensaje **ok?** a su sucesor $x_4$, informando de su movimiento, pero $x_4$ no encuentra ninguna razón para moverse. Su valor es coherente con todas las asignaciones de valor de todos sus predecesores.
Después de este paso, todos los agentes permanecen inactivos, sin violaciones de las restricciones con asignaciones en sus vistas. Por lo tanto, este es un estado final del algoritmo ABT en el que encuentra una solución.
## Corrección y Completitud del Algoritmo
Vamos a justificar que el algoritmo 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 (la forma de determinar que los agentes en su conjunto han alcanzado un estado estable no está contenida en el algoritmo, para detectar el 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 forzosamente todas las restricciones. Por tanto, la corrección del algoritmo es evidente. Además, el algoritmo es completo, ya que encuentra una solución si existe, y termina con un fallo cuando no hay solución global.
No existe una solución global cuando el problema está sobrecargado. En una situación de exceso de restricciones, el algoritmo acaba generando un $nogood$ correspondiente al conjunto vacío. Como un $nogood$ representa un conjunto de asignaciones que conduce a una contradicción, un $nogood$ vacío significa que cualquier conjunto de asignaciones conduce a una contradicción. Por tanto, no hay solución posible. Lo que significa que el algoritmo termina con un fallo si y sólo si se construye un $nogood$ vacío.
Lo que queda es justificar que el algoritmo llega a una de estas conclusiones en un tiempo finito. La única manera de que el algoritmo no llegue a una conclusión es cuando al menos un agente entra en un bucle infinito que intercambia continuamente entre sus posibles valores. Se puede ver que esto no ocurre por inducción:
1. En el caso base, supongamos que el agente con mayor prioridad, $x_1$, está en un bucle infinito. Como tiene la máxima prioridad, $x_1$ sólo recibe mensajes **Nogood**, no mensajes **ok?**. Cuando propone un valor posible, $x_1$ recibe un mensaje **Nogood** o no recibe ningún mensaje. Si recibe mensajes **Nogood** para todos los valores posibles de su variable, entonces generará un $nogood$ vacío (ya que almacena todos los $nogoods$ que va recibiendo, que juntos general el $nogood$ vacío), y cualquier elección conduce a una violación de esta restricción, por lo que el algoritmo terminará. Si no recibe un mensaje **Nogood** para un valor propuesto, entonces no cambiará ese valor. En cualquier caso, no puede quedarse en un bucle infinito.
2. Ahora, supongamos que los agentes $x_1$ a $x_{k-1}$ ($k > 2$) están en un estado estable, y razonando por reducción al absurdo, supongamos que el agente $x_k$ está en un bucle infinito. En este caso, los únicos mensajes que recibe el agente $x_k$ son mensajes **Nogood** de agentes cuyas prioridades son menores que $k$, y estos mensajes **Nogood** sólo contienen a los agentes $x_1$ a $x_k$. Como los agentes $x_1$ a $x_{k-1}$ están en un estado estable, los mensajes **Nogood** que recibe el agente $x_k$ deben ser compatibles con sus vistas, por lo que $x_k$ cambiará la instanciación de su variable con un valor diferente. Dado que el dominio de su variable es finito, $x_k$ acabará generando un valor que no le haga recibir un $nogood$ (lo que contradice la suposición de que $x_k$ está en un bucle infinito), o bien agotará los valores posibles y enviará un $nogood$ a uno de los agentes $x_1,\dots, x_{k-1}$. Sin embargo, este $nogood$ haría que un agente, que suponíamos que estaba en un estado estable, no lo estuviera. Así, por contradicción, $x_k$ no puede entrar en un bucle infinito.
## Algunas consideraciones adicionales
Como el problema de satisfacción de restricciones es **NP**-completo en general (y todavía no hemos resuelto el problema de si **P** y **NP** son iguales o no) la complejidad temporal en el peor de los casos del ABT se vuelve exponencial en el número de variables.
Una nota acerca de la complejidad espacial: en el peor de los casos del algoritmo, la complejidad espacial viene determinada por el número de $nogoods$ almacenados. En el algoritmo estándar, un agente puede olvidar los $nogoods$ antiguos después de crear un nuevo $nogood$ a partir de ellos. Además, un agente no necesita guardar los $nogoods$ que no son compatibles con su vista. Por tanto, cada agente $x_i$ necesita registrar, como máximo, $|D_i|$ $nogoods$, donde $|D_i|$ es el tamaño de su dominio.
El algoritmo ABT es la columna vertebral de los enfoques modernos de DisCSP, pero admite muchas extensiones y modificaciones.
Una de las principales modificaciones tiene que ver con la asignación parcial inconsistente (es decir, $nogood$) que se envía en el mensaje de backtracking. En la versión que hemos visto, que es la primera versión de ABT, se envía la vista completa. Sin embargo, esta vista completa no es en muchos casos un $Nogood$ mínimo porque un subconjunto estrictamente más pequeño que él también puede ser inconsistente. En general, los $Nogoods$ más cortos pueden conducir a un proceso de búsqueda más eficiente, ya que permiten saltar hacia atrás en el árbol de búsqueda sin producir cambios innecesarios.
Veamos un ejemplo. Consideremos un agente $x_6$ que tiene una vista inconsistente con las asignaciones de los agentes $x_1$, $x_2$, $x_3$, $x_4$ y $x_5$. Si suponemos que $x_6$ sólo está limitado por las asignaciones actuales de $x_1$ y $x_3$, enviar un mensaje **Nogood** a $x_5$ que contenga todas las asignaciones de la vista parece un desperdicio. Después de enviar el **Nogood** a $x_5$, $x_6$ eliminará su asignación de la vista y hará otro intento de asignar su variable, al que seguirá un **Nogood** adicional enviado a $x_4$ y la eliminación de la asignación de $x_4$ de la vista. Estos intentos continuarán hasta que se envíe un subconjunto mínimo como $Nogood$. En este ejemplo, es el **Nogood** enviado a $x_3$. La asignación con la menor prioridad en el subconjunto mínimo inconsistente se elimina de la vista del agente y ahora se puede encontrar una asignación consistente. En este ejemplo, el cálculo terminó enviando un **Nogood** al agente culpable, que habría sido el resultado si el agente calculara un subconjunto mínimo.
La solución a esta ineficiencia, sin embargo, no es sencilla, ya que encontrar un $Nogood$ mínimo es, en general, un problema intratable (concretamente, es **NP**-duro). Por ello, se necesitan varias heurísticas para reducir el tamaño del $Nogood$ sin sacrificar la corrección.
Una cuestión relacionada es el número de $Nogoods$ almacenados por cada agente. En la versión que hemos visto de ABT, cada $Nogood$ es registrado por el agente receptor. Dado que el número de subconjuntos inconsistentes puede ser exponencial, se crearán listas de restricciones con un tamaño exponencial, y una búsqueda a través de dichas listas requiere un tiempo exponencial en el peor de los casos. Se han hecho varias propuestas para reducir este número y preservar la corrección. Una propuesta es que los agentes mantengan sólo los $Nogoods$ consistentes con su vista. Aunque esto elimina algunos de los $Nogoods$, en el peor de los casos sigue dejando un número de $Nogoods$ que es exponencial en el tamaño de la 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.
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. La discusión de estos enfoques está fuera de nuestro alcance.
# Búsqueda Asíncrona de Compromiso Débil
A continuación vamos a describir brevemente el Algoritmo de Búsqueda de Compromiso Débil para resolver CSPs y cómo utilizarlo para construir el Algoritmo de **Búsqueda Asíncrono de Compromiso Débil** (**AWCS**) modificando el ABT.
## Algoritmo de Búsqueda de Compromiso Débil
!!!
En el **Algoritmo de Búsqueda de Compromiso Débil** todas las variables comienzan con valores iniciales tentativos. 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. 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). Esta heurística de ordenación de valores se denomina **heurística de mínimo conflicto**. 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.
Además, este algoritmo registra las soluciones parciales abandonadas como nuevas restricciones (ya que se comportan como los *nogoods* anteriores), y evita crear la misma solución parcial que ha sido creada y abandonada anteriormente. Por tanto, la completitud del algoritmo (siempre encuentra una solución si existe, y termina si no existe ninguna solución) está garantizada. Los resultados experimentales en varios problemas de ejemplo ilustran que este algoritmo es de 3 a 10 veces más eficiente que otros algoritmos similares, como el **backtracking de mínimo conflicto** o el **algoritmo breakout**.
## Ideas básicas
!!!
Las principales características del algoritmo AWCS descrito en la subsección anterior son las siguientes:
1. El algoritmo utiliza la heurística de mínimo conflicto como heurística de ordenación de valores.
2. Abandona la solución parcial y reinicia el proceso de búsqueda si no existe ningún valor consistente con la solución parcial.
Introducir la primera característica en el algoritmo ABT es relativamente sencillo. Al seleccionar un valor de la variable, si existen múltiples valores consistentes con la visión del agente (los que satisfacen las restricciones con variables de agentes de mayor prioridad), el agente prefiere el valor que minimiza el número de violaciones de las restricciones con variables de agentes de menor prioridad.
En cambio, introducir la segunda característica en el ABT ya 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.
El algoritmo distribuido que mostraremos a continuación se compromete con la solución parcial de forma débil y puede construirse cambiando el orden de prioridad de forma dinámica. Definimos la forma de establecer el orden de prioridad introduciendo valores de prioridad, y cambiamos los valores de prioridad mediante las siguientes reglas:
- Para cada variable/agente, se define un valor entero no negativo (**valor de prioridad**) que representa su orden de prioridad.
- El orden se define de forma que cualquier variable/agente con un valor de prioridad mayor tiene una prioridad mayor.
- Si los valores de prioridad de varios agentes son iguales, el orden se determina por el orden alfabético de los identificadores (es decir, su numeración **natural**).
- Para cada variable/agente, el valor de prioridad inicial es 0.
- Si no existe un valor consistente para $x_i$, su valor de prioridad se cambia a $k + 1$, donde $k$ es el mayor valor de prioridad de los agentes relacionados.
Conviene resaltar las diferencias entre este algoritmo AWCS y otros algoritmos de backtracking con ordenación dinámica de variables (por ejemplo, el backtracking dinámico, o el backtracking dirigido por dependencias). En los algoritmos de backtracking habituales, una solución parcial nunca se modifica a menos que se esté seguro de que la solución parcial no puede formar parte de ninguna solución completa (el backtracking dinámico o el backtracking dirigido por dependencias es una forma de averiguar la verdadera causa del fallo). En el algoritmo AWCS, una solución parcial no se modifica sino que se abandona completamente después de un fallo/backtracking.
Además, en el algoritmo ABT, los agentes intentan evitar las situaciones que previamente se han considerado *nogood*. Sin embargo, debido al retardo de los mensajes, una vista de un agente puede ser ocasionalmente idéntica a un $nogood$ encontrado previamente. Para evitar reaccionar ante estas situaciones inestables y realizar cambios innecesarios en los valores de prioridad, cada agente realiza el siguiente procedimiento:
- Cada agente registra los $nogoods$ que ha enviado. Cuando su vista es idéntica a un $nogood$ que ya ha enviado, el agente no cambia el valor de prioridad y espera el siguiente mensaje.
~~~~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 hacer:
añadir (x_k, d_k, p_k) a mi vista
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
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
~~~~
## Detalles del algoritmo
En AWCS, al igual que en ABT, cada agente asigna concurrentemente un valor a su variable, y envía el valor de la variable a otros agentes. Después, los agentes esperan y responden a los mensajes entrantes (al igual que en ABT, aunque el algoritmo se describe de forma que un agente reacciona a los mensajes de forma secuencial, en realidad puede manejar múltiples mensajes de forma concurrente, es decir, que primero revisa su vista y la lista de $nogoods$ que tiene almacenada de acuerdo con los mensajes, y posteriormente realiza la comprobación de consistencia una sola vez). Los procedimientos mostrados son los que se ejecutan en el agente $x_i$ al recibir un mensaje **ok?** y un mensaje **nogood** (como en ABT, no se refleja la forma de determinar que los agentes en su conjunto han alcanzado un estado estable).
!!!
Las diferencias entre estos procedimientos y los de ABT son las siguientes:
- 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 variable tanto a los agentes de menor como de mayor prioridad conectados por restricciones. A estos agentes relacionados los llamamos *vecinos*.
- El valor de prioridad, así como la asignación de valor actual, se comunica a través del mensaje **ok?**.
- El orden de prioridad se determina utilizando los valores de prioridad comunicados. Si el valor actual no es consistente con su vista, es decir, alguna restricción con variables de agentes de mayor prioridad no se satisface, el agente cambia su valor para que el valor sea consistente con su vista y además minimice el número de violaciones de restricciones con variables de agentes de menor prioridad.
- Cuando $x_i$ no puede encontrar un valor consistente con su vista, $x_i$ envía mensajes **nogood** a otros agentes, e incrementa su valor de prioridad. Si $x_i$ ya ha enviado un **nogood** idéntico, $x_i$ no cambiará su valor de prioridad, sino que esperará al siguiente mensaje.
## Ejemplo
Ilustremos la ejecución del algoritmo utilizando el problema de 4 reinas.
![Figura [ACWSReinas]: Ejecución del ACWS en una instancia del problema de 4 reinas](img\sma2-24.png width="50%")
Los valores iniciales se muestran en el paso (a). Los agentes se comunican estos valores entre sí. Los valores entre paréntesis representan los valores de prioridad (inicialmente 0).
Como los valores de prioridad son iguales, el orden de prioridad se determina por el orden alfabético de los identificadores. Por tanto, sólo el valor de $x_4$ no es consistente con su vista. Como no hay ningún valor consistente, el agente $x_4$ envía mensajes **nogood** e incrementa su valor de prioridad. En este caso, el valor que minimiza el número de violaciones de la restricción es 3, ya que sólo entra en conflicto con $x_3$. Por tanto, $x_4$ selecciona 3 y envía mensajes **ok?** a los demás agentes. Entonces, $x_3$ intenta cambiar su valor. Como no hay un valor consistente, el agente $x_3$ envía mensajes **nogood**, e incrementa su valor de prioridad. En este caso, el valor que minimiza el número de violaciones de la restricción es 1 o 2. En el ejemplo, $x_3$ selecciona 1 y envía mensajes **ok?** a los demás agentes. Después, $x_1$ cambia su valor a 2, y se obtiene una solución.
En el problema de 4 reinas, no existe solución si se fija el valor de $x_1$ a 1. Podemos ver que la mala decisión de $x_1$ (poner su valor en 1) puede ser revisada sin una búsqueda exhaustiva en AWCS.
## Completitud del algoritmo
Los valores de prioridad se cambian si y sólo si se encuentra un nuevo $nogood$. Como el número de posibles $nogoods$ es finito (es exponencial en el número de variables), los valores de prioridad no pueden ser cambiados infinitamente. Por lo tanto, a partir de un determinado momento, los valores de prioridad serán estables. Entonces, demostremos que las situaciones descritas a continuación no se producirán cuando los valores de prioridad sean estables:
1. Existen agentes que no satisfacen algunas restricciones, y todos los agentes están esperando mensajes entrantes.
2. Los mensajes se envían/reciben repetidamente, y el algoritmo no alcanzará un estado estable (bucle infinito).
Si se da la situación (1), existen al menos dos agentes que no satisfacen la restricción entre ellos. Supongamos que el agente $k$ en el orden de prioridad no satisface la restricción con el agente $j$ (donde $j \lt k$), y que todos los agentes de rango superior a $k$ satisfacen todas las restricciones entre ellos. El único caso en el que el agente $k$ espera los mensajes entrantes aunque no satisfaga la restricción con el agente $j$ es que el agente $k$ haya enviado mensajes no válidos a agentes de mayor prioridad. Este hecho contradice la suposición de que los agentes de mayor prioridad satisfacen las restricciones en su interior. Por tanto, la situación (1) no se puede producir.
Además, si los valores de prioridad son estables, el AWCS es básicamente idéntico a ABT. Como ABT está garantizado para no caer en un bucle infinito, la situación (2) tampoco se puede producir.
Del hecho de que ni la situación (1) ni la (2) ocurrirán, podemos garantizar que el algoritmo AWCS siempre parará, y encontrará una solución global, o encontrará el hecho de que no existe ninguna solución global.
De nuevo, como la satisfacción de restricciones es **NP**-completa en general, la complejidad temporal de AWCS en el peor de los casos se vuelve exponencial en el número de variables. Además, su complejidad espacial en el peor de los casos también es exponencial en el número de variables. Este resultado parece inevitable, ya que este algoritmo cambia el orden de búsqueda de forma flexible mientras garantiza su completitud. Podemos restringir el número de $nogoods$ registrados en el algoritmo AWCS, es decir, hacer que cada agente registre sólo un número fijo de los $nogoods$ encontrados más recientemente. Pero en este caso no se puede garantizar la exhaustividad teórica (el algoritmo puede caer en un bucle infinito en el que los agentes encuentran repetidamente $nogoods$ idénticos pero ya olvidados). Sin embargo, cuando el número de $nogoods$ registrados es razonablemente grande, este bucle infinito rara vez se produce. De hecho, en el artículo fundacional se probó que AWCS encontraba soluciones para todos los problemas de ejemplo incluso cuando el número de $nogoods$ registrados se limitaba a 10.
## Seguridad/privacidad de los agentes
Una de las razones para resolver un CSP de forma distribuida es que los agentes pueden no querer comunicar toda la información a un agente líder centralizado. En este sentido, una pregunta interesante sería: ¿cuánta información revelan los agentes utilizando el algoritmo AWCS?
En los algoritmos presentados, los agentes comunican las asignaciones de valores actuales y los $nogoods$ que encuentran. Al observar las asignaciones de valor del agente $x_i$, otros agentes pueden acumular gradualmente información sobre el dominio de $x_i$. Sin embargo, los demás agentes no pueden saber si la información obtenida sobre el dominio de $x_i$ es completa o no. Puede haber otros valores de $x_i$ que no se seleccionan porque violan algunas restricciones con agentes de mayor prioridad que ellos desconocen.
Además, el agente $x_i$ nunca revela directamente información sobre sus restricciones. Un mensaje **nogood** enviado por $x_i$ 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.
# Evaluaciones
Es interesante evaluar y comparar la eficiencia de los algoritmos vistos mediante una simulación en la que cada agente mantiene su propio reloj simulado. El tiempo de un agente se incrementa en una unidad de tiempo simulado cada vez que realiza un ciclo de cálculo, que consiste en leer todos los mensajes entrantes, realizar cálculos locales y, a continuación, enviar mensajes. Suponemos que un mensaje emitido en el tiempo $t$ está disponible para el destinatario en el tiempo $t + 1$. Analizaremos el rendimiento en términos del número de ciclos necesarios para resolver el problema. Por supuesto, un inconveniente de esta aproximación es que no tiene en cuenta los costes de comunicación, pero introducir los costes de comunicación en el modelo es difícil, ya que no disponemos de ninguna forma estándar para comparar los costes de comunicación y los costes de cálculo.
Desde un punto de vista intuitivo, un ciclo corresponde a una serie de acciones de los agentes, en las que un agente reconoce el estado del mundo (las asignaciones de valor de otros agentes), luego decide su respuesta a ese estado (su propia asignación de valor) y por último comunica sus decisiones.
## SBT vs. ABT
En primer lugar, vamos a comparar el algoritmo de Backtracking Síncrono (SBT) y el algoritmo de Backtracking Asíncrono (ABT).
Como los agentes pueden actuar concurrentemente en el algoritmo ABT, podemos esperar que ABT sea más eficiente que SBT. Sin embargo, el grado de aceleración se ve afectado por la fuerza de las restricciones entre los agentes. Si las restricciones entre los agentes son débiles, podemos esperar que los agentes puedan alcanzar fácilmente una solución, incluso si establecen sus valores de forma concurrente. Por otro lado, si las restricciones entre los agentes son fuertes, podemos suponer que hasta que los agentes de mayor prioridad no fijen sus valores adecuadamente, los agentes de menor prioridad no podrán elegir valores consistentes; por ello, el rendimiento global de ABT se acerca al de SBT.
Para verificar estas expectativas, realizamos evaluaciones experimentales en el problema de las $N$ reinas con el que ya hemos jugado. Como sabemos, cada agente corresponde a cada reina de cada fila, por lo que el problema distribuido de $N$ reinas es resuelto por $N$ agentes.
En este problema, las restricciones entre los agentes se vuelven débiles a medida que $N$ aumenta. Los resultados se resumen en la siguiente figura. Para que las comparaciones sean justas, incluimos el backtracking dirigido por dependencias en SBT: cada agente selecciona aleatoriamente un valor entre los valores consistentes con los agentes de mayor prioridad. El gráfico muestra la media de 100 pruebas (no incluimos el coste de determinar el orden secuencial en SBT, ni el coste de la detección de la terminación en el ABT).
![Figura [ABT-SBT]: Comparación ABT - SBT para las $N$ reinas](img/sma2-18.png width="50%")
En el problema de $N$ reinas existen restricciones entre cualquier par de agentes. Por tanto, SBT es básicamente equivalente al Protocolo de Consistencia de Red [7]. Como es esperable, el paralelismo obtenido de ABT se hace mayor a medida que $N$ aumenta. Cuando $N > 18$, ABT es aproximadamente 2x más rápido que SBT (como ABT requiere más mensajes que SBT para cada ciclo, SBT podría ser tan eficiente como ABT debido a la sobrecarga de comunicación, aunque requiera más ciclos). Tradicionalmente, las aplicaciones de DAI implican que los agentes trabajen en subproblemas casi independientes y poco acoplados. Estos resultados confirman que, si los subproblemas locales están poco acoplados, la resolución del problema de forma asíncrona por parte de varios agentes merece la pena.
## ABT vs. AWCS
Vamos a comparar los siguientes tres tipos de algoritmos:
1) ABT, en el que el valor de una variable se selecciona aleatoriamente de entre los valores consistentes, y el orden de prioridad se determina por orden alfabético,
2) ABT con heurística de mínimo conflicto, en el que se introduce la heurística de mínimo conflicto, pero el orden de prioridad se determina estáticamente por orden alfabético, y
3) AWCS.
La sobrecarga de comunicación de estos algoritmos es casi equivalente. Las cantidades de cálculo local realizadas en cada ciclo para (2) y (3) son equivalentes. La cantidad de cálculo local de (1) puede ser menor ya que no utiliza la heurística de mínimo conflicto, pero para el agente de menor prioridad, las cantidades de cálculo local de estos algoritmos son equivalentes.
Primero aplicamos estos tres algoritmos al problema de $N$ reinas, variando $N$ de 10 a 1.000. Los resultados se resumen en la Tabla 1 (como la heurística de mínimo conflicto es muy eficaz cuando $N$ es muy grande, no incluimos los resultados para $N > 1.000$). Para cada $N$ se generan 100 problemas, cada uno con diferentes valores iniciales generados aleatoriamente, y se promedian los resultados de estos problemas. Para cada problema, a fin de realizar los experimentos en un tiempo razonable, se fija el límite del número de ciclos en 1.000, y se termina el algoritmo si se supera este límite. En la Tabla 1 se muestra la media de los problemas realizados con éxito y la relación entre los problemas completados con éxito y el número total de problemas.
![](img/sma2-19.png width="50%")
El segundo caso de estudio será el problema distribuido de coloreado de grafos (cada nodo corresponde a un agente). Se genera aleatoriamente un problema con $N$ nodos/agentes y $M$ aristas por el método descrito en [17], de forma que se asegura que el grafo es conexo y el problema tiene solución. Se evalúa el problema para $N = 60, 90$ y $120$, donde $M = 2N$ y $k = 3$. Esta configuración de parámetros corresponde a los problemas "dispersos" para los que [17] informó de un pobre rendimiento de la heurística de mínimo conflicto. Se generan 10 problemas diferentes, y para cada problema se realizan 10 ensayos con diferentes valores iniciales (100 ensayos en total). Al igual que en el problema de las $N$ reinas, los valores iniciales se establecieron de forma aleatoria. Los resultados se resumen en la Tabla 2.
![](img/sma2-20.png width="50%")
A continuación, para examinar la aplicabilidad de AWCS a problemas de la vida real y no a problemas aleatorios artificiales, se aplican los mismos algoritmos al problema de asignación de recursos distribuidos en una red de comunicaciones de NTT en Japón. En este problema, existen solicitudes de asignación de circuitos entre nodos de conmutación de la red.
![Figura [RedNTT]: Red de Comunicación de NTT en Japón](img/sma2-22.png width="50%")
Para cada solicitud, existe un agente asignado para atenderla, y se dan los candidatos para los circuitos. El objetivo es encontrar un conjunto de circuitos que satisfaga las restricciones de recursos. Este problema puede formalizarse como un DisCSP representando cada petición como una variable y cada candidato como un posible valor para la variable. SE generan problemas basados en los datos de una red troncal de 400 Mbps extraídos de la base de datos de gestión de la configuración de la red desarrollada en NTT Optical Network Systems Laboratories [20]. En cada problema, existen 10 solicitudes de asignación de circuitos generadas aleatoriamente, y para cada solicitud, se dan 50 candidatos. Estos candidatos representan circuitos razonablemente cortos para satisfacer la solicitud, y se supone que estos candidatos están calculados de antemano. Las restricciones entre las solicitudes son que no asignen los mismos circuitos. Se generan 10 conjuntos diferentes de valores iniciales generados aleatoriamente para 10 problemas diferentes (100 ensayos en total), y se promedian los resultados. Al igual que en los problemas anteriores, el límite del número de ciclos requerido se fijó en 1.000. Los resultados se resumen en la Tabla 3.
![](img/sma2-21.png width="50%")
!!! Tip
De estos resultados se desprenden los siguientes hechos:
- AWCS puede resolver problemas que no pueden ser resueltos en un tiempo de cálculo razonable por los algoritmos ABT. Utilizando sólo la heurística de mínimo conflicto, aunque se puede obtener un cierto aumento de velocidad, el algoritmo no consigue resolver muchos de los casos de los problemas planteados experimentalmente.
- Cuando el orden de prioridad es estático, la eficiencia del algoritmo depende en gran medida de la selección de los valores iniciales, y la distribución de los ciclos necesarios es bastante grande. Por ejemplo, en el problema de asignación de recursos de red, cuando sólo se utiliza la heurística de mínimo conflicto, el número medio de ciclos necesarios para 63 ensayos completados con éxito es de sólo 92,8. Sin embargo, el número de ciclos necesarios para 37 ensayos (fallidos) es superior a 1.000. Cuando los valores iniciales de los agentes de mayor prioridad son buenos, la solución puede encontrarse fácilmente. Sin embargo, si algunos de estos valores son malos, se requiere una búsqueda exhaustiva para revisar estos valores; esto tiende a hacer que el número de ciclos requeridos supere el límite prefijado. Por otro lado, 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.
- Podemos suponer que el orden de prioridad representa una jerarquía de autoridad de los agentes, es decir, el orden de prioridad de la toma de decisiones. Si esta jerarquía es estática, los juicios erróneos (malas selecciones de valores) 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 y se seleccionan los valores de forma cooperativa, los errores de apreciación de determinados agentes no tienen efectos fatales, ya que las malas decisiones se eliminan y sólo sobreviven las buenas. 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.
# Breakout Distribuido
Otra forma de enfocar el problema DisCSP, diferente de la idea de **backtracking**, es utilizar un método de **escalada** (**hill-climbing**, o **ascenso de la colina**). En este método se comienza asignando a todas las variables valores elegidos al azar, y luego estos 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. Como en los métodos anteriores, 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.
Todos los algoritmos de escalada sufren el problema de los mínimos locales. Es decir, es posible que el sistema llegue a un estado en el que ningún agente pueda encontrar un valor mejor para su variable y que, sin embargo, no sea la mejor asignación de valores para el sistema completo. Es decir, un mínimo local puede reconocerse por el hecho de que 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. Por lo tanto, 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 (recuerda que estos mecanismos, habituales en los problemas con sincronización, no son sencillos de abordar en los no sincronizados). La aplicación de todas estas técnicas daría lugar a un algoritmo complejo con gran cantidad de comunicaciones y, posiblemente, largos tiempos de ejecución.
El algoritmo **Breakout Distribuido** (DBA) intenta evitar este problema reconociendo lo que se denomina un **cuasi-mínimo local**, en lugar de un mínimo local completo. La ventaja de los cuasi-mínimo local es que pueden ser reconocidos por los agentes individuales.
!!!def: Definición
Un agente $x_i$ 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.
Por desgracia, el hecho de que un agente se encuentre en un cuasi-mínimo local no implica necesariamente que esté en un mínimo local, ya que es posible que algunos agentes no vecinos puedan realizar cambios que reduzcan el coste total. Por otro lado, si el sistema está en un mínimo local, al menos un agente se encontrará en un cuasi-mínimo local. Así, 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.
Para ello, el algoritmo Breakout mantiene un peso asociado a cada restricción. Estos pesos se fijan inicialmente en $1$. Cada vez que un agente se encuentra en un cuasi-mínimo local, aumenta los pesos de las restricciones que se violan. A su vez, los pesos se utilizan para calcular el coste de la violación de una restricción. Es decir, en lugar de contar simplemente el número de restricciones violadas, Breakout Distribuido utiliza la suma ponderada de las restricciones violadas. De este modo, 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.
!!!
Las ideas básicas para implementar la versión distribuida del algoritmo Breakout son las siguientes:
- 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. Debe tenerse en cuenta que esta comprobación es local, por lo que si dos agentes no son vecinos, es posible que cambien sus valores simultáneamente.
- En lugar de detectar el hecho de que los agentes en su conjunto están atrapados en un mínimo local (lo que requiere una comunicación global entre los agentes), cada agente detecta el hecho de que está en un cuasi-mínimo local, que es una condición más débil que un mínimo local y puede ser detectado a través de las comunicaciones locales.
En este algoritmo, se comunican dos tipos de mensajes (**ok?** y **improve**) entre vecinos. Los procedimientos ejecutados por el agente $x_i$ al recibir estos mensajes se muestran a continuación. El agente alterna entre el modo de espera de un mensaje **ok?** y el modo de espera de un mensaje **improve**. Este último se utiliza para comunicar la posible mejora del valor de la evaluación.
~~~~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
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
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
~~~~
Esencialmente, 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.
La figura siguiente muestra un ejemplo de aplicación del DBA. Comenzamos con una coloración aleatoria de los nodos en (paso a). Cada agente comunica este valor inicial a través de mensajes **ok?**. Después de recibir los mensajes **ok?** de todos sus vecinos, cada agente calcula su *eval_actual* y *mi_mejora*, y envía mensajes **improve**. Inicialmente, todos los pesos son iguales a 1. En el estado inicial, las mejoras de todos los agentes son iguales a $0$. Por lo tanto, los pesos de las restricciones (nogoods): $\{(x_1, b), (x_6, b)\}$, $\{(x_2, n), (x_5, n)\}$, y $\{(x_3, b), (x_4, b)\}$, se incrementan en $1$ (paso b).
En este punto, las mejoras de $x_1, x_3, x_4$ y $x_6$ son $1$, y las mejoras de $x_2$ y $x_5$ son $0$. Los agentes que tienen derecho a cambiar sus valores son $x_1$ y $x_3$ (cada uno de los cuales precede en orden alfabético dentro de su propio entorno). Estos agentes cambian su valor de blanco a negro (paso c). Entonces, la mejora de $x_2$ es 4, mientras que las mejoras de los otros agentes son $0$. Por lo tanto, $x_2$ cambia su valor a blanco, y todas las restricciones se satisfacen (paso d).
![Figura [DBA]: Ejemplo de Breakout distribuido sobre coloración de un grafo con dos colores (blanco y negro). En las aristas se representan los pesos que cada agente da a la restricción](img/sma2-17.png width="75%")
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.
Diferentes pruebas experimentales también han demostrado que la distribución de la carga de este algoritmo es bastante desigual. Es decir, algunos agentes acaban manejando muchos más mensajes que otros. Es probable que exista una correlación entre el número de aristas que tiene un agente y el número de mensajes que debe procesar. Aun así, se ha demostrado que DBA encuentra, en la práctica, los óptimos locales un gran porcentaje de las veces, y hay variaciones del algoritmo básico que aquí hemos visto que funcionan incluso mejor. En concreto, se ha demostrado que, en la práctica, el algoritmo $Multi-DB^{++}$ encuentra siempre la solución para los problemas 3SAT.
# Extensiones de la formalización del problema
## Manejo de múltiples variables locales
Hasta ahora, hemos asumido que cada agente tiene una sola variable local. Aunque los algoritmos desarrollados pueden aplicarse a la situación en la que un agente tiene múltiples variables locales mediante los siguientes métodos, ambos no son eficientes ni escalables a problemas grandes.
* **Método 1**: cada agente encuentra primero todas las soluciones a su problema local. Al encontrar todas las soluciones, el problema dado puede reformularse como un CSP distribuido, en el que cada agente tiene una variable local cuyo dominio es un conjunto de soluciones locales obtenidas. A continuación, los agentes pueden aplicar algoritmos para el caso de una única variable local. El inconveniente de este método es que cuando un problema local se hace grande y complejo, encontrar todas las soluciones de un problema local se hace prácticamente imposible.
* **Método 2**: un agente crea múltiples agentes virtuales, cada uno de los cuales corresponde a una variable local, y simula las actividades de estos agentes virtuales. Por ejemplo, si el agente $k$ tiene dos variables locales $x_i$, $x_j$, suponemos que existen dos agentes virtuales, cada uno de los cuales corresponde a cada una de estas variables. Entonces, el agente $k$ simula las actividades concurrentes de estos dos agentes virtuales. En este caso, cada agente no tiene que predeterminar todas las soluciones locales. Sin embargo, como la comunicación con otros agentes suele ser más cara que la realización de cálculos locales, es un desperdicio simular las actividades de múltiples agentes virtuales sin distinguir las comunicaciones entre agentes virtuales dentro de un mismo agente real y las comunicaciones entre agentes reales.
En [#Armstrong97] se introdujo la priorización entre agentes para manejar múltiples variables locales. En este algoritmo, cada agente intenta encontrar una solución local que sea consistente con las soluciones locales de los agentes de mayor prioridad. Si no existe tal solución local, se produce un backtracking o una modificación de la priorización. En ese mismo trabajo se examinaron varias heurísticas para determinar un buen ordenamiento entre los agentes. Este enfoque es similar al método 1, salvo que cada agente busca sus soluciones locales sólo cuando es necesario, en lugar de encontrar todas las soluciones por adelantado.
En [#Yokoo98] se desarrolló una extensión del AWCS que puede manejar múltiples variables locales. Aunque este algoritmo es similar al método 2, tiene algunas características particulares:
- Un agente cambia secuencialmente los valores de sus variables locales. Más concretamente, selecciona una variable $x_k$ que tiene la mayor prioridad entre las variables que están violando las restricciones con variables de mayor prioridad, y modifica el valor de $x_k$ para que se satisfagan las restricciones con variables de mayor prioridad.
- Si no existe ningún valor que satisfaga todas las restricciones con variables de mayor prioridad, el agente aumenta el valor de prioridad de $x_k$.
- Al iterar los procedimientos anteriores, cuando todas las variables locales satisfacen las restricciones con variables de mayor prioridad, el agente envía los cambios a los agentes relacionados.
Cada variable debe satisfacer las restricciones con variables de mayor prioridad. Por lo que cambiar el valor de una variable de menor prioridad antes de fijar el valor de una variable de mayor prioridad suele ser un desperdicio. En consecuencia, un agente cambia primero el valor de la variable de mayor prioridad. Además, al enviar mensajes a otros agentes sólo cuando encuentra una solución local consistente, los agentes pueden reducir el número de interacciones entre ellos. Al utilizar este algoritmo, si la solución local seleccionada por un agente de mayor prioridad es mala, un agente de menor prioridad no tiene que buscar exhaustivamente su problema local. Simplemente aumenta los valores de prioridad de ciertas variables que violan las restricciones con la mala solución local.
## Satisfacción parcial de restricciones distribuidas
Muchos problemas de aplicación en los Sistemas Multiagente que pueden formalizarse como DisCSPs pueden estar sobrecondicionados, es decir, una instancia del problema tiene demasiadas restricciones y no existe ninguna solución que satisfaga todas las restricciones por completo. En ese caso, los algoritmos distribuidos descritos no proporcionan ninguna información útil, es decir, si el algoritmo es completo, simplemente informa de que el problema no tiene solución, y si no es completo, nunca termina.
Sin embargo, en muchos problemas de aplicación, preferimos tener una solución incompleta que satisfaga tantas restricciones como sea posible. Por ejemplo, en un *problema de asignación de recursos distribuidos*, los agentes intentan encontrar la combinación de planes que permita la ejecución de todas las tareas de los agentes bajo las restricciones de recursos. Si los agentes necesitan realizar sus tareas con recursos escasos, la instancia del problema se puede mapear en un DisCSP con demasiadas restricciones. Para esta instancia de problema, queremos saber cómo debe modificarse la instancia para que sea resoluble.
Como colofón de esta entrada, solo queremos indicar que también se han definido marcos generales para tratar con DisCSPs sobre-restringidos, llamados **DisCSPs parciales**, de los que destacan dos subclases: **DisCSPs máximos**, donde cada agente trata de encontrar los valores de las variables que minimizan el número máximo de restricciones violadas sobre los agentes, y **DisCSPs jerárquicos**, donde cada agente trata de encontrar los valores de las variables que minimizan el grado máximo de importancia de las restricciones violadas sobre los agentes.
Intuitivamente, en un DisCSP parcial, los agentes tratan de encontrar un DisCSP solucionable y su solución relajando un DisCSP original con demasiadas restricciones. El grado de relajación del problema original se mide mediante una función definida globalmente (función de distancia global). Los agentes prefieren que el problema se acerque más al problema original, y en algunos casos quieren que la relajación sea mínima.
# Referencias
[#Armstrong97]: A. Armstrong, and E. H. Durfee, “Dynamic prioritization of complex agents in distributed constraint satisfaction problems,” in Proc. 15th Int. Joint Conf. Artif. Intell., 1997, pp. 620–625.
[#Yokoo98]: M. Yokoo and K. Hirayama, “Distributed constraint satisfaction algorithm for complex local problems,” in Proc. 3rd Int. Conf. on Multi-Agent Syst., 1998.