Problemas de satisfacción de restricciones en Inteligencia Artificial

Problemas de satisfacción de restricciones en Inteligencia Artificial

Problemas de satisfacción de restricciones (PSRs) Componentes del estado = grafo de restricciones: Variables Dominios (valores posibles para las variables) Restricciones (binarias) entre las variables Objetivo: encontrar un estado (una asignación completa de valores a las variables) que satisface las restricciones. 2 2

Problemas de satisfacción de restricciones (PSRs) Ejemplos: colorear mapas crucigramas n-reinas asignación/distribución/ubicación de recursos: distribución de tareas de fabricación ubicación de gasolineras ubicación de antenas de telefonía 3 3

4 Representación Problema: colorear mapa Ejemplo de estado: Variables (n) = etiquetas de nodos Dominios = contenido de nodos Restricciones = arcos dirigidos y etiquetados entre nodos 4

5 Representación A cada paso hay una asignación de variable. Las soluciones deben ser asignaciones completas y por lo tanto, en el árbol de búsqueda, aparecen a profundidad n. El árbol se extiende sólo a profundidad n. Los algoritmos de búsqueda primero en profundidad son populares para PSRs. El camino que alcanza una solución es irrelevante. La clase más simple de PSR implica variables discretas y dominios finitos: problemas de coloreo de mapas, de n-reinas… 5

6 Dominios finitos Si el tamaño máximo del dominio de cualquier variable es d, entonces el número de posibles asignaciones completas es O(dn), exponencial en el número de variables. Los PSRs con dominio finito incluyen a los PSRs booleanos, cuyas variables pueden ser verdaderas o falsas. En el caso peor, no se pueden resolver los PSRs con dominios finitos en menos de un tiempo exponencial. Evidentemente, los algoritmos para PSR resuelven problemas órdenes de magnitud más grandes que los resolubles con algoritmos de búsqueda no informada. 6

7 Dominios infinitos Las variables discretas pueden tener dominios infinitos (p.e., el conjunto de números enteros o de cadenas). Con dominios infinitos, no es posible describir restricciones enumerando todas las combinaciones permitidas de valores. Se debe usar un lenguaje de restricción:

Comienzo-Trabajo1 + 5 = Comienzo-Trabajo3

Existen algoritmos para restricciones lineales sobre variables enteras. 7

8 Dominios infinitos No existe un algoritmo general para restricciones no lineales sobre variables enteras. En algunos casos, se pueden reducir los problemas de dominio infinito a dominio finito simplemente acotando los valores de todas las variables, p.e.: fijando límites temporales para el comienzo de los trabajos. 8

9 Dominios continuos Los PSRs con dominios continuos son muy comunes en el mundo real. La categoría más conocida son los problemas de programación lineal: las restricciones deben ser desigualdades lineales que forman una región convexa. Los problemas de programación lineal pueden resolverse en tiempo polinomial en el número de variables. 9

Algoritmos Basados en búsqueda complejidad: tiempo: O(exp(n)) espacio: O(n) Basados en programación dinámica complejidad: tiempo: O(exp(w*+1)) espacio: O(exp(w*)) Donde n es el número de variables y w* es la anchura inducida del grafo de restricciones dado un orden. 10 10

11 Algoritmos basados en búsqueda Formulación incremental, como en un problema de búsqueda estándar: Estado inicial: la asignación vacía { }, en que todas las n variables no están asignadas. Función de sucesor: asignación de un valor d a cualquier variable no asignada, a condición de que no suponga conflicto con variables ya asignadas. Test objetivo: la asignación actual es completa. Costo del camino: un costo constante (p.e., 1) para cada paso. 11

12 Algoritmos basados en búsqueda Formulación completa de estados: Cada estado es una asignación completa que satisface o no las restricciones. Los métodos de búsqueda local trabajan bien para esta formulación. 12

13 Algoritmos basados en búsqueda Búsqueda heurística Búsqueda en profundidad con vuelta atrás cronológica

Propagación de restricciones Antes de la búsqueda Durante la búsqueda 13

14 Restricciones El tipo más simple es la restricción unaria, que restringe los valores de una sola variable. Una restricción binaria relaciona dos variables. Las restricciones de orden alto implican tres o más variables. Un ejemplo son los puzzles cripto-aritméticos. 14

15 Puzzles cripto-aritméticos Variables: F T U W R O X1 X2 X3

Dominio: {0,1,2,3,4,5,6,7,8,9}

Restricciones:

TodasDif (F,T,U,W,R,O) O + O = R + 10 · X1 X1 + W + W = U + 10 · X2 X2 + T + T = O + 10 · X3 X3 = F, T ? 0, F ? 0 15

Búsqueda con vuelta atrás para PSR Si los PSRs se formulan como problemas de búsqueda, cualquiera de los algoritmos de búsqueda vistos anteriormente los pueden resolver. Estado inicial: la asignación vacía { }, en que todas las n variables no están asignadas. Función de sucesor: asignación de un valor d a cualquier variable no asignada, a condición de que no suponga conflicto con variables ya asignadas. Si aplicamos la búsqueda primero en anchura, notamos algo terrible: El factor de ramificación en el nivel superior es de nd. 16