**Problemas de Satisfacción de Restricciones** SVRAI
Fernando Sancho Caparrini --- !!! **Objetivo**: representar problemas mediante la declaración de restricciones sobre el espacio de posibles soluciones y encontrar aquellas que satisfagan todas. !!!Tip:Problema de coloración de mapas ![](..\SVRAI\img\screen-shot-2013-05-20-at-3.57.27-pm.png width="40%" align="right") Dado un conjunto de colores y un mapa dividido en regiones, colorear cada región del mapa de manera que regiones adyacentes tengan distintos colores. **Modelado CSP**: Variables :: regiones, Dominio :: colores, Restricciones :: adyacencia $\rightarrow$ colores distintos. **Representación Grafo**: Nodos :: regiones, Aristas :: adyacencia (restricción). --- ## Metodología La resolución de un CSP consta de dos fases: 1. **Modelar/Representar el problema como un CSP**. Decidir variables, dominios y explicitar restricciones. 2. **Procesar las restricciones**: - **Técnicas de consistencia/filtrado**: eliminación de valores inconsistentes de los dominios de las variables. Se pueden aplicar técnicas derivadas de la Lógica. - **Algoritmos de búsqueda**: exploración sistemática del espacio de soluciones hasta encontrar una solución que verifica todas las restricciones del problema. Combinación: las técnicas de consistencia permiten deducir información del problema y reducir el espacio de soluciones para poder explorarlo usando algoritmos de búsqueda. --- ## Formalización CSP Un **CSP** es una terna $(X,D,C)$ donde: 1. $X$ es un conjunto de $n$ variables $\{x_1 ,...,x_n \}$. 2. $D =\langle D_1 ,...,D_n \rangle$ es un vector de dominios ($D_i$ son los posibles valores de $x_i$). 3. $C$ es un conjunto finito de restricciones. Por ejemplo, un predicado asociado a $k$ de las variables de $X$. **Asignación**: $((x_1 ,a_1),...,(x_i ,a_i))$ **Localmente consistente**: si satisface todas las restricciones formadas por variables de la tupla. **Solución**: si es completa y consistente. --- ## Representaciones: Problema de las N reinas Disponer en un tablero de ajedrez de tamaño $N\times N$, $N$ reinas de forma que no haya amenazas entre ningún par de ellas (recordemos que una reina amenaza a toda la fila, columna y diagonales de la casilla en la que se sitúa).  Vamos a ver varias representaciones. --- ### Representación 1: Problema de las N reinas 1. $X=\{R_1,\dots,R_N\}=\{R_i :\ 1 \leq i \leq N\}$ 2. $D=\{(x,y):\ 1\leq x,y \leq N\}$, donde $R_i=(x_i,y_i)$ 3. Las restricciones: - No hay amenaza horizontal: $x_i \neq x_j$, para todo $i\neq j$. - No hay amenaza vertical: $y_i \neq y_j$, para todo $i\neq j$. - No hay amenaza en la diagonal principal: $x_i - x_j \neq y_i - y_j$, para todo $i \neq j$. - No hay amenaza en la diagonal secundaria: $x_i - x_j \neq y_j - y_i$, para todo $i \neq j$. (Las dos diagonales se pueden tratar conjuntamente con: $|x_i - x_j| \neq |y_i - y_j|$, para todo $i \neq j$) Para $N=8$ hay $64^8$ posibles asignaciones y $126$ restricciones. --- ### Representación 2: Problema de las N reinas 1. $X=\{R_{i,j}:\ 1\leq x,y \leq N\}$ (una por cada casilla). 2. $D=\{0,1\}$ 3. Las restricciones: - $\displaystyle{\sum_i R_{i,j} \leq 1}$, para todo $1\leq j\leq N$. - $\displaystyle{\sum_j R_{i,j} \leq 1}$, para todo $1\leq i\leq N$. - $\displaystyle{\sum_{(i,j)\in D} R_{i,j} \leq 1}$, para toda $D$ diagonal. Para $N=8$ hay $64^2$ posibles asignaciones y unas $300$ restricciones. --- ### Representación 3: Problema de las N reinas Similar a la anterior, pero por medio de predicados lógicos: 1. $X=\{R_{i,j}:\ 1\leq x,y \leq N\}$ (una por cada casilla). 2. $D=\{0,1\}$ 3. Las restricciones: - $(R_{i,j} \rightarrow \neg R_{i,j'})$, para todo $j' \neq j$. - $(R_{i,j} \rightarrow \neg R_{i',j})$, para todo $i' \neq i$. - $(R_{i,j} \rightarrow \neg R_{i+k,j+k})$, para todo $1\leq i+k, j+k \leq N$. - $(R_{i,j} \rightarrow \neg R_{i+k,j-k})$, para todo $1\leq i+k, j-k \leq N$. --- ### Representación 4: Problema de las N reinas Uso de conocimiento implícito del problema (hay una, y solo una, reina en cada columna): 1. $X=\{R_i :\ 1\leq i \leq N\}$ 2. $D=\{1,\dots,N\}$ 3. Las restricciones: - $R_i \neq R_j$, para todo $i\neq j$. - $|R_i - R_j| \neq |i - j|$, para todo $i\neq j$. Para $N=8$ hay $8^8$ posibles asignaciones y unas $80$ restricciones. --- ## Consistencia en un CSP Al igual que con los algoritmos de búsqueda generales, la búsqueda sistemática para CSP tiene como base **backtracking**. Pero es normal la explosión combinatoria en el espacio de búsqueda y, por tanto, no es suficientemente eficiente. Problema: inconsistencias locales que aparecen continuamente (combinación de valores de variables que no satisfacen alguna restricción). Se han propuesto varias técnicas de consistencia local para mejorar la eficiencia de la búsqueda: borran valores inconsistentes de las variables o inducen restricciones implícitas que ayudan a podar el espacio de búsqueda. --- ## Consistencia en un CSP 1. **Consistencia de Nodo ($1$-consistencia)**: Las restricciones unarias de cada variable se pueden satisfacer. 2. **Consistencia de Arco ($2$-consistencia)**: para cualquier par de variables $x_i$ y $x_j$, para cada valor $a$ en $D_i$ hay al menos un valor $b$ en $D_j$ tal que las asignaciones $(x_i ,a)$ y $(x_j ,b)$ satisfacen las restricciones binarias entre $x_i$ y $x_j$. 3. **Consistencia de caminos ($3$-consistencia)**: Para cada asignación $((x_i,a), (x_j,b))$ que satisfaga la restricción entre $x_i$ y $x_j$, además existe un valor para cada variable a lo largo del camino entre $x_i$ y $x_j$ de forma que todas las restricciones a lo largo del camino se satisfagan. 4. **Consistencia Global**: Para cada variable $x_i$ y cada $a \in D_i$, la asignación $(x_i, a)$ forma parte de una solución del CSP. --- ## Árbol de Búsqueda ![](..\SVRAI\img\psr-tree.png align="left")Las asignaciones en un CSP con una estructura específica para ser visto como un **árbol de búsqueda**. La búsqueda mediante **backtracking** es la base de la mayoría de algoritmos para CSP, corresponde a la exploración en **profundidad DFS** en el árbol de búsqueda. **Estático**: el orden de las variables no cambia durante la búsqueda, y un nodo en el nivel $k$ representa una asignación de $x_1 ,...,x_k$ y $x_{k+1} ,...,x_n$ no están asignadas. La raíz del árbol representa la asignación vacía. --- ## Backtracking Cronológico (BT) Para árboles estáticos: $X=\{x_1,\dots,x_n\}$, $D_i=\{a^i_1,\dots,a^i_{m_i}\}$ finitos. 1. $i=1$, $j_1=1$. 1. Si $i>n$, entonces: **Éxito**. Fin. 2. Comprobar $(x_i,a^i_{j_i})$ en todas las restricciones en las intervienen $x_1,\dots,x_i$: * Si todas las restricciones se han satisfecho: $i\leftarrow i+1$, $j_i\leftarrow 1$, ir al punto 2. * Si no: $j_i\leftarrow j_i+1$. * Si $j_i > m_i$, entonces: $i\leftarrow i-1$, $j_i\leftarrow j_i+1$. * Si $i>0$, ir al punto 2. * Si no, entonces: **Fracaso**. Fin. * Si no: ir al punto 2. --- ## Backtracking Cronológico (BT) Si una restricción involucra a la variable actual y al menos una variable futura, entonces esta restricción no se comprobará hasta que se hayan asignado todas las variables futuras de la restricción. BT es un algoritmo muy simple pero muy ineficiente: tiene una visión local del problema, ignora el futuro y las restricciones entre otras variables pasadas, no *recuerda* las acciones previas y puede repetir la misma acción varias veces innecesariamente. Para ayudar a combatir este problema: algoritmos **look-back** y algoritmos **look-ahead**. --- ### Algoritmos Look-Back **Backjumping (BJ)** es parecido a BT excepto que: en vez de retroceder a la variable anteriormente instanciada, salta a la variable más profunda (más cerca de la variable actual) $x_j$ anterior que está en conflicto con la variable actual. Una variante, **conflict-directed Backjumping (CBJ)** tiene un comportamiento de salto hacia atrás más sofisticado: almacena para cada variable un conjunto de conflictos mutuos que permite no repetir conflictos existentes a la vez que saltar a variables anteriores como hace BJ. --- ### Algoritmos look-Ahead: Forward checking (FC) 1. Seleccionar $x_i$. 2. Instanciar $(x_i , a_i) : a_i \in D_i$. 3. Check-forward: Eliminar de las variables futuras los valores inconsistentes con $(x_i, a_i)$. 4. Si quedan valores posibles en los dominios futuros, entonces: - Si $i < n$, incrementar $i$, e ir al paso 1. - Si $i = n$, parar devolviendo la solución. 5. Si hay una variable futura sin valores posibles entonces retractar $(x_i, a_i)$: - Si quedan valores por intentar en $D_i$, ir al paso 2. - Si no quedan valores: - Si $i > 1$, decrementar $i$ y volver al paso 2. - Si $i = 1$, salir sin solución. Otro: **FC-CBJ**, combina FC con CBJ. --- # Heurísticas --- ## Ordenación de Variables Resultados experimentales muestran que el orden en el cual las variables son asignadas durante la búsqueda tiene una impacto significativo en el tamaño del espacio de búsqueda explorado. Las heurísticas de ordenación de variables tratan de seleccionar lo antes posible las variables que más restringen a las demás: la intuición indica que es mejor tratar de asignar lo antes posible las variables más restringidas y de esa manera identificar las situaciones sin salida lo antes posible y así reducir el número de vueltas atrás. --- ### Heurísticas de ordenación de variables estáticas Se basan en la topología del grafo de restricciones original que representa el CSP: 1. **Minimum Width (MW)**: $anchura(x)$ = número de variables que están antes de $x$, de acuerdo a un orden dado, y que son adyacentes a $x$ (en el grafo de restricciones). Las variables se ordenan desde la última hasta la primera en anchura decreciente. Las primeras son las más restringidas. 2. **Maximun Degree (MD)**: ordena las variables en un orden decreciente de su grado en el grafo de restricciones. 3. **Maximun Cardinality (MC)**: selecciona la primera variable arbitrariamente y después en cada paso, selecciona la variable que es adyacente al conjunto más grande de las variables ya seleccionadas. --- ### Heurísticas de ordenación de variables dinámicas **Principio del primer fallo** (**FF**): intentar primero donde sea más probable que falle. Así, las situaciones sin salida pueden identificarse antes y se ahorra espacio de búsqueda. **Heurística Minimum Remaining Values (MRV)**: selecciona la variable con el dominio más pequeño. Menos valores, más difícil encontrar un valor consistente. * **MRV+Look-Back** = heurística estática que ordena las variables de forma ascendente con el tamaño del dominio antes de llevar a cabo la búsqueda. * **MRV+Look-Ahead** = heurística dinámica, los valores de las futuras variables se pueden podar después de cada asignación de variables. En cada etapa, la próxima variable a asignar es la variable con el dominio más pequeño. Resultados experimentales: las heurísticas de ordenación de variables estáticas son peores que **MRV**. --- ## Ordenación de Valores Poco trabajado. Idea básica: seleccionar el valor de la variable actual que más probabilidad tenga de llevarnos a una solución. Habitualmente, seleccionar el valor menos restrictivo de la variable actual, es decir, el valor que menos reduce el número de valores útiles para las futuras variables. * **Heurística de mínimo-conflicto**: ordena los valores de acuerdo a los conflictos en los que éstos están involucrados con las variables no instanciadas.