1 Problemas de Satisfacción de Restricciones (CSP)
Contenidos:Definición del problema de satisfacción de restricciones (CSP). Áreas de aplicación. Especificación de un problema CSP: variables, dominios y restricciones. Tipología de restricciones (discretas y continuas, fuertes y débiles, restricciones lineales, disyuntivas, etc.).
2 CSP
““Constraint Satisfaction is a Constraint Satisfaction is a simple but powerful idea”simple but powerful idea”
Rina Dechter,
In 'Constraint Processing'Morgan Kaufmann Pub. (2003)
3 EJEMPLOS 1
s e n d+ m o r em o n e y
• Variables: s,e,n,d,m,o,r,y• Dominios: s,e,n,d,m,o,r,y∈{0,…,9}• Restricciones
103(s+m)+102(e+o)+10(n+r)+d+e=104m+103o+102n+y
Objetivos
• Consistencia• Soluciones
El Problema de las 8 Reinas…
Coloreado de Mapas• Variables: x,y,z,w• Dominios: x,y,z,w :{r,v,a}• Restricciones: binarias
x ≠ y, y≠z, z ≠ w, ...
x y
zw
4 EJEMPLOS 2
Juan, Pepe y Paco nacieron y viven en ciudades diferentes (Málaga, Madrid y Valencia). Además, ninguno vive en la ciudad donde nació.
Juan es más alto que el que vive en Madrid. Paco es cuñado del que vive en Valencia. El que vive en Madrid y el que nació en Málaga tienen nombres que comienzan por distinta letra. El que nació en Málaga y el que vive ahora en Valencia tienen nombres que comienzan por la misma letra.
Donde nació y vive cada uno?Donde nació y vive cada uno?
5 EJEMPLOS 3
"Juan va de su casa al trabajo en coche (30-40 minutos) o en tren (al menos una hora). Luis va en coche (20-30 minutos) o en metro (40-50 minutos).Hoy Juan parte de casa entre las 8:10 y las 8:20 y Luis llega al trabajo entre las 9:00 y las 9:10. Además, sabemos que Juan llegó al trabajo entre 10 y 20 minutos después de que Luis saliera de casa“
Cuestiones:– ¿Esta información es consistente?– ¿Es posible que Juan haya usado el tren y Luis haya usado el
Metro?– ¿Cuales son los posibles tiempos en los que Luis pudo haber
salido de casa?, etc.
6 EJEMPLOS 4
• Variables: altura de viga, longitud de viga, canto de forjado• Dominios continuos: altura, longitud : [0, 10]• Restricciones: vibraciones, refuerzos, conexiones, etc.
• Consistencia• Intervalos de tolerancia• Soluciones• etc
Objetivos
7 CSP
Problemas de Satisfacción de Restricciones
CSP
Metodología de Resolución de problemas
INTELIGENCIA ARTIFICIAL
8 Definición de CSP
Un Problema de Satisfacción de Restricciones (CSP)se puede representar como:
• Un Conjunto de Variables: X={x1, x2, ..., xn}• Dominios de Interpretación (D = <D1,…,Dn> ) para las variables: xi∈Di
• Un Conjunto de Restricciones entre las variables: C ={c1, c2, ..., cm}
9 Modelización CSP
MODELACIÓNCSP
VariablesDominios
Restricciones
(EXPRESIVIDAD)(EXPRESIVIDAD)
1)
RESOLUCIÓNCSP
Técnicas ResoluciónCSP
(EFICICIENCIA)(EFICICIENCIA)2)
10 Modelización 1
s e n d+ m o r em o n e y
• Variables: s,e,n,d,m,o,r,y• Dominios: s,e,n,d,m,o,r,y:{0,…,9}• Restricciones
• Variables: s, e, n, d, m, o, r, y• Dominios: s, e, n, d, m, o, r ,y : {0,…,9}• Restricciones:
• Todas Diferentes, • 103(s+m) + 102(e+o) + 10(n+r) + d + e= 104m + 103o + 102n + 10e+y
Especificación CSP
11 Modelización 2
• Variables: s, e, n, d, m, o, r, y• Dominios: s, e, n, d, m, o, r ,y : {0,…,9}• Restricciones:
• s≠e, s≠n, s≠d, s≠m, s≠o, s≠r, s≠y, e≠n, e≠d, e≠m,…..• d+e = y+10c1• c1+n+r = e+10c2
• c2+e+o = n+10c3
• c3+s+m = 10m+o
s e n d+ m o r em o n e y
12 Resolución
s e n d+ m o r e
m o n e y
MODELACIÓNCSP
RESOLUCIÓNCSP
13 Objetivos
ConsistenciaConsistencia del problema (existe solución).
Obtener una o todas las solucionessoluciones del problema.
Obtener los dominios mínimos.
La solución que optimizaoptimiza una función objetivo o multi-objetivo.
14 Objetivos
Objetivo de un CSP:• Tiene solución? ⇒ Consistencia.
• Obtener una solución. Obtener todas las soluciones.
• Obtener una solución óptima, o al menos una buena solución, medida por alguna función objetivo (función de evaluación).
Algoritmos para CSP:• Técnicas de Búsqueda (Algoritmos CSP): Obtienen una solución,
guiados por heurísticas.
• Técnicas Inferenciales (Algoritmos de propagación): Obtienen las consecuencias de las restricciones explícitamente conocidas del problema.
15 Conceptos básicos
Dado un CSP (X, Di, C),
• Una instanciación (o asignación) de las variables X es una asignación de valores a las variables en sus dominios:
x1=v1, x2=v2, ..., xn=vn / vi∈D
• Una solución del CSP es una instanciación consistente de las variables, de forma que se satisfacen todas las restricciones del problema.
• Un valor v es un valor consistente (o posible) para xi si existe una solución del CSP en la cual participa la asignación xi=v.
• Un CSP es consistente sii tiene al menos una solución.
16 Conceptos básicosVariables
• Un CSP discreto es aquel en el que todas las variables sondiscretas, es decir, toman valores en dominios discretos.
• Un CSP continuo es un CSP en el que todas las variables son continuas, es decir, tienen dominios continuos.
• Un CSP mixto consta de variables continuas y discretas.
• Un CSP binario es aquel en el que todas las restricciones tienen a los sumo dos variables respectivamente.
• Un CSP no binario o n-ario es aquel en el que las restriccionestienen más de dos variables.
17 Conceptos básicosRestricciones
• Discretas: las variables participantes están acotadas en dominios discretos.
• Continuas: las variables participantes están acotadas en dominios continuos.
• Binarias: son restricciones en las que sólo participan dos variables.
• N-arias: son restricciones en las que participan N variables (N>2).
• Fuertes (hard): son restricciones cuya satisfabilidad es imprescindible.
• Débiles (soft): son restricciones cuya satisfabilidad no es imprescindible.
• Difusas (fuzzy): son restricciones definidas sobre niveles de preferencia.
• Disyuntivas: son restricciones compuestas por un conjunto disjunto de restricciones.
18 N-reinas
Definición: posicionar n reinas en un tablero deajedrez n x n, de forma que no se ataquen.
Formulación: 1 reina por fila• variables: reinas, Xi reina en la fila i-ésima• dominios: columnas posibles {1, 2, . . . , n}• restricciones: no colocar dos reinas en– la misma columna– la misma diagonal
Características:• CSP binario, discreto y finito
19 Coloreado de Grafos
Definición: Dado un grafo,• n nodos• m colores,asignar un color a cada nodo de forma que no hayados nodos adyacentes con el mismo color.Formulación:• variables: nodos• dominios: colores posibles• restricciones: ≠ nodos adyacentes
Características:• CSP binario, discreto y finito
20 Crucigrama
Definición: Dada una rejilla y un diccionario, construirun crucigrama compatible.
Formulación:• variables: grupo de casillas para una palabra (slots)• dominios: palabras del diccionario con la longitud adecuada• restricciones: misma letra en la intersección de dos palabras
Características:• CSP binario, discreto y finito (dominios grandes)
21 Restricciones Temporales
Definición: dado un conjunto de sucesos que ocurrenen intervalos temporales con ciertas relaciones, encontrar una asignación temporal
consistente.
Formulación:• variables: sucesos• dominios: intervalo temporal para cada suceso• restricciones: distancia temporal permitida entresucesos; relaciones temporales antes, después, solapado, etc.
Características:• CSP binario, continuo, con restricciones disyuntivas
T0
T1 T2
T3 T4
{[10, 20]}
{[30, 40], [60, ∞]}
{[10, 20]}
{[20, 30], [40, 50]}
T0: Tiempo inicial (en este caso, 8:00 h.)T1 / T2: Tiempo en que Juan sale de casa / llega al trabajo.T3/T4: Tiempo en que Luis sale de casa / llega al trabajo.
{[60, 70]}
"Juan va de su casa al trabajo en coche (30-40 minutos) o en tren (al menos una hora). Luis va en coche (20-30
minutos) o en metro (40-50 minutos).
Hoy Juan parte de casa entre las 8:10 y las 8:20 y Luis llega al trabajo entre las 9:00 y las 9:10. Además,
sabemos que Juan llegó al trabajo entre 10 y 20 minutos después de que Luis saliera de casa"
"Juan va de su casa al trabajo en coche (30-40 minutos) o en tren (al menos una hora). Luis va en coche (20-30
minutos) o en metro (40-50 minutos).
Hoy Juan parte de casa entre las 8:10 y las 8:20 y Luis llega al trabajo entre las 9:00 y las 9:10. Además,
sabemos que Juan llegó al trabajo entre 10 y 20 minutos después de que Luis saliera de casa"
22 Problema de diseño
a) Solución por defecto para los arcos dados:
b) Versión teniendo en cuenta aspectos estéticosy geotecnológicos:
c) Bases para diseñar los detalles de los pilares:
e) Diseño final:
d2) Pilaressobre elperalte
d3) Pilaresen el agua
Backtracking sobrelos detalles dediseño de los pilares
d1) Pilaresdemasiadocerca
? ?
Definición: el problema consiste en llevar a cabo el diseño de un puente que debe constar de pocos arcos siendo preferible que los pilares no toquen el agua y los pilares sean lo más bajos posibles.
Formulación:• variables: partes y elementos del diseño• dominios: valores permitidos para cada parte y elemento• restricciones: propiedades que las partes deben satisfacer.
Características:• CSP no binario, mixto, con restricciones hard, soft y difusas.
23 CSPs binarios & n-ariosBinario
Un CSP binario se suele representar mediante un grafo, donde:
Nodos: VariablesArcos: Relaciones binarias entre las variables.
X1
X2
X3X5
X4X1 R12 x2x3 R35 x5x1 R15 x5x4 R42 x2x4 R45 x5x2 R25 x5
24 CSPs binarios & n-ariosNo Binario
Un CSP no binario no se suele representar mediante un grafo, sino como un hiper-grafo perdiendo toda la funcionalidad existente sobre la teoría de grafos. donde:Nodos: VariablesArcos: Relaciones binarias entre las variables.
C123 X1 X2 X3
X5X4
X7
X6C24567
25 Consistencia: Niveles1-consistencia
Consistencia de nodo Consistencia de nodo (1(1--consistencia)consistencia)
Un nodo (xi) es consistente si al menos un valor en su dominio es consistente con la restricción unaria del nodo:
10≤xi≤ 15, D(Xi):{0, 10}
Un grafo red es nodo-consistente sii todos sus nodos son consistentes:∀xi∈CSP, ∃vi∈D / (xi ci0) se cumple para xi=vi (ie: D∩ci0≠{∅})
26 Consistencia: Niveles2-consistencia
Consistencia de arco Consistencia de arco (2(2--consistencia)consistencia): :
Un arco (xi {cij} xj) es consistente si y solo si para cada asignación de xi en su dominio, existe una asignación para xi, tal que la restricción {cij} se satisface.
Por ejemplo el arco:
xi xjCij≤
[3,6] [8,10]
es consistente, pero no lo sería si cij en vez de ≤ fuese ≥Un grafo es arco-consistente si todos sus arcos son consistentes.
∀cij ⊆CSP, ∀vi∈di ∃vj∈dj / (xi cij xj) se cumple para xi=vi, xj=vj
27 Backtracking: ejemplo
28 Backtracking: ejemplo
29 Backtracking: ejemplo
30 Backtracking: ejemplo