Date post: | 18-Jan-2015 |
Category: |
Documents |
Upload: | pastor-sanchez |
View: | 3 times |
Download: | 0 times |
1
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
CAPITULO 1
1. Problemas de Satisfacción de Restricciones (CSP).
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, aridad de las restricciones, fuertes y débiles, restricciones lineales, disyuntivas, etc.).
2
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
““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)
CSP
3
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
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
Coloreado de Mapas• Variables: x,y,z,w• Dominios: x,y,z,w :{r,v,a}• Restricciones: binarias
x y, yz, z x, ...
x y
zw
Objetivos
• Consistencia
• Soluciones
El Problema de las 8 Reinas…
EJEMPLOS 1
4
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
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?
EJEMPLOS 2
5
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
Existen 3 periódicos (P1, P2, P3) y 4 lectores (L1, L2, L3, L4), que desean leer los periódicos en el mismo orden.
Ready-Time
P1 P2 P3 Due-Time
L1 0 5' 10' 2' 30'L2 0 2' 6' 5' 20'L3 0 10' 15' 15' 60'L4 0 3' 5' 5' 15'
Problemas de Horarios, Asignación de Recursos, Scheduling, etc...
Problemas de Horarios, Asignación de Recursos, Scheduling, etc...
Obtener la asignación óptima (scheduling) de lectura.
EJEMPLOS 3
6
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
"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.
EJEMPLOS 4
7
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
i
j
TparTimpar
i
j
Tpar Timpar
i
j
TparTimpar
i
j
Tpar Timpar
Tiempo de ExpediciónTiempo de Expedición
Tiempo de Recepción(cruce)
Tiempo de Expedición(cruce)
Sucesión no Automática
i
Sucesión Automática
i + 1
Tiempo de Recepción(alcance)
Tiempo de Expedición(alcance)
EJEMPLOS 5
8
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
h (altura de la viga)
Vibraciones
No Vibraciones
Conductos atravesando lasvigas
Conductos por debajo de las vigas
Conexiones de ángulo doble
Conexiones de lámina simple
W (longitud de la viga)
0
1
2
3
4
• Variables: altura de viga, longitud de viga, canto de forjado
• Dominios continuos: altura, longitud : [0, 10]
• Restricciones: vibraciones, refuerzos, conexiones, etc.
Refuerzos
Suelo fexible para evitarvibraciones
-a-
Conductosatravesando las vigas
-b-
Conductos pordebajo de las vigas
-c-
Conexiones deángulo doble
-d-
Conexiones delámina simple
-e-
viga
Canto delforjado
Objetivos
• Consistencia
• Intervalos de tolerancia
• Soluciones
• etc
EJEMPLOS 6
9
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
Problemas de Satisfacción de Restricciones
CSP
Metodología de Resolución de problemas
INTELIGENCIA ARTIFICIAL
CSP
10
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
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: xiDi
• Un Conjunto de Restricciones entre las variables:
C ={c1, c2, ..., cm}
Definición de CSP
11
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
MODELACIÓNCSP
VariablesDominios
Restricciones
(EXPRESIVIDAD)(EXPRESIVIDAD)
1)
RESOLUCIÓNCSP
Técnicas ResoluciónCSP
(EFICICIENCIA)(EFICICIENCIA)2)
Modelización CSP
12
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
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
Modelización 1
13
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
• Variables: s, e, n, d, m, o, r, y• Dominios: s, e, n, d, m, o, r ,y : {0,…,9}• Restricciones:
• se, sn, sd, sm, so, sr, sy, en, ed, em,….. • d+e = y+10c1
• c1+n+r = e+10c2
• c2+e+o = n+10c3
• c3+s+m = 10m+o
Modelización 2
s e n d+ m o r e m o n e y
14
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
Resolución
s e n d+ m o r e m o n e y
MODELACIÓNCSP
RESOLUCIÓNCSP
15
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
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.
16
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
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.
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.
Objetivos
17
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
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 / viD
• 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 x i=v.
• Un CSP es consistente sii tiene al menos una solución.
Conceptos básicos
18
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
• Un CSP discreto es aquel en el que todas las variables sondiscretas, es decir, toman valores en dominios finitos.
• 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 cualquier cualquier número de variables.
Conceptos básicosVariables
19
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
• 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 sólo participan cualquier número de 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.
Conceptos básicosRestricciones
20
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
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 diagonalrel(Rij)= {(a,b)| a b |i -j| |a -b|}Características:• CSP binario, discreto y finito
21
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
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
22
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
Crucigrama
Definición: Dada una rejilla y un diccionario, construirun crucigrama legal.
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)
23
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
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"
24
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
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 donde es preferible que los pilares no toquen el agua, con pilares 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.
25
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
Un CSP binario se suele representar mediante un grafo, donde:
Nodos: VariablesArcos: Relaciones binarias entre las variables.
X1 R12 x2x3 R35 x5x1 R15 x5x4 R42 x2x4 R45 x5x2 R25 x5
X1
X2
X3X5
X4
CSPs binarios & n-ariosBinario
26
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
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
CSPs binarios & n-ariosNo Binario
X1 X2 X3
X5X4
X7
X6C24567
27
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
Consistencia de nodo Consistencia de nodo (1-consistencia)(1-consistencia)
Un nodo (xi) es consistente si al menos un valor en su dominio es consistente con la restricción unaria del nodo:
10xi 15, D(Xi):{0, 10}
Un grafo red es nodo-consistente sii todos sus nodos son consistentes:xiCSP, viD / (xi ci0) se cumple para xi=vi (ie: Dci0{
Consistencia: Niveles1-consistencia
28
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
Consistencia de arco Consistencia de arco (2-consistencia)(2-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:
es consistente, pero no lo sería si cij en vez de fuese
Un grafo es arco-consistente si todos sus arcos son consistentes.
cijCSP,vidi vjdj / (xi cij xj) se cumple para xi=vi, xj=vj
xi xjCij
[3,6] [8,10]
Consistencia: Niveles2-consistencia
29
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
Consistencia: Niveles2-consistencia
Azul, Rojo
Azul
Azul, RojoVerde Azul, Verde
X1
X4
X2
X3
Azul, Rojo
Azul
Azul, RojoVerde Azul, Verde
X1
X4
X2
X3
Grafo Inicial Grafo arco-consistente
30
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
3-Consistencia: 3-Consistencia: Un grafo es 3-consistente sii todas sus 2-sendas son
consistentes: "cij Í CSP, "viÎdi, "vjÎdj / (xi=vi cij xj=vj) Þ $vkÎdk / (xi=vi cik xk=vk) Ù (xj=vj
cjk xk=vk)
Senda-Consistencia (Montanari, Mackworth, 1976): – Una k-senda (x1, x2, ..., xk, xj) es consistente sii para cualquier
valor v1d1 y vjdj, tal que la restriccion (x1=v1 c1j xj=vj) se cumple,
– Entonces existe una secuencia de valores – v2d2, v3d3, ..., vkdk – tal que las restricciones (v1 cl2 v2), (v2 c23 v3),...., (vk ck,j vj)
se cumplen.
Consistencia: Niveles3-consistencia