1
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.).
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
CSP
2
“Constraint Satisfaction is a
simple but powerful idea”
Rina Dechter,
In 'Constraint Processing'
Morgan Kaufmann Pub. (2003)
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
3
EJEMPLOS 1
• Variables: s,e,n,d,m,o,r,y
• Dominios: s,e,n,d,m,o,r,y{0,…,9}
• Restricciones
Objetivos
• Consistencia
send
+more
money
• Soluciones
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, yz, z  x, ...
x
y
w
z
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
El Problema de
las 8 Reinas…
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?
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
EJEMPLOS 3
5
Existen 3 periódicos (P1, P2, P3) y 4 lectores (L1, L2,
L3, L4), que desean leer los periódicos en el mismo
orden.
L1
L2
L3
L4
R e a d yT im e
P1
P2
P3
D ueT im e
0
0
0
0
5'
2'
10'
3'
10'
6'
15'
5'
2'
5'
15'
5'
30'
20'
60'
15'
Obtener la asignación óptima (scheduling) de lectura.
Problemas de Horarios,
Asignación de Recursos, Scheduling, etc...
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
EJEMPLOS 4
6

"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.
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
EJEMPLOS 5
7
T iem p o d e R ecep ció n
(a lca nce)
i
i
T im p ar
j
T par
T par
T im p ar
j
T iem p o d e E x ped ició n
(a lca nce)
T iem p o d e E xped ición
T iem p o d e R ecep ción
(cru ce)
T iem p o d e E xped ición
(cru ce)
S u c e sió n n o A utom á tica
S u c e sió n A utom á tica
i
i + 1
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
EJEMPLOS 6
8
h (altura de la viga)
viga
Vibraciones
Canto del
forjado
No Vibraciones
Conductos atravesando las
vigas
4
Conductos por debajo de las vigas
3
Refuerzos
Conexiones de
ángulo doble
2
Conexiones de lámina simple
1
0
Conductos por Conexiones de Conexiones de
Conductos
Suelo fexible para evitar
atravesando las vigas debajo de las vigas ángulo doble lámina simple
vibraciones
-c-d-b-e-a-
W (longitud de la viga)
• Variables: altura de viga, longitud de viga, canto de forjado
• Dominios continuos: altura, longitud : [0, 10]
• Restricciones: vibraciones, refuerzos, conexiones, etc.
• Consistencia
Objetivos
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
• Intervalos de tolerancia
• Soluciones
• etc
9
CSP
Problemas de Satisfacción de Restricciones
CSP
Metodología de Resolución de problemas
INTELIGENCIA ARTIFICIAL
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
10
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}
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
Modelización CSP
11
1)
MODELACIÓN
CSP
Variables
Dominios
Restricciones
(EXPRESIVIDAD)
2)
RESOLUCIÓN
CSP
Técnicas Resolución
CSP
(EFICICIENCIA)
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
12
Modelización 1
• Variables: s,e,n,d,m,o,r,y
• Dominios: s,e,n,d,m,o,r,y:{0,…,9}
send
• Restricciones
+more
money
Especificación
CSP
• 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
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
13
Modelización 2
• Variables: s, e, n, d, m, o, r, y
• Dominios: s, e, n, d, m, o, r ,y : {0,…,9}
• Restricciones:
send
+ more
money
• 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
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
14
Resolución
MODELACIÓN
CSP
s end
+ more
money
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
RESOLUCIÓN
CSP
Objetivos
15

Consistencia del problema (existe solución).

Obtener una o todas las soluciones del
problema.

Obtener los dominios mínimos.

La solución que optimiza una función objetivo
o multi-objetivo.
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
Objetivos
16
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.
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
17
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.
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
18
Conceptos básicos
Variables
• Un CSP discreto es aquel en el que todas las variables son
discretas, 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 restricciones
tienen cualquier cualquier número de variables.
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
19
Conceptos básicos
Restricciones
• 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.
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
20
N-reinas
Definición: posicionar n reinas en un tablero de
ajedrez 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
rel(Rij)= {(a,b)| a  b  |i -j|  |a -b|}
Características:
• CSP binario, discreto y finito
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
21
Coloreado de Grafos
Definición: Dado un grafo,
• n nodos
• m colores,
asignar un color a cada nodo de forma que no haya
dos nodos adyacentes con el mismo color.
Formulación:
• variables: nodos
• dominios: colores posibles
• restricciones:  nodos adyacentes
Características:
• CSP binario, discreto y finito
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
22
Crucigrama
Definición: Dada una rejilla y un diccionario, construir
un 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)
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
23
Restricciones Temporales
Definición: dado un conjunto de sucesos que ocurren
en intervalos temporales con ciertas relaciones, encontrar una asignación temporal
consistente.
"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"
Formulación:
• variables: sucesos
• dominios: intervalo temporal para cada suceso
• restricciones: distancia temporal permitida entre
sucesos; relaciones temporales antes, después, solapado, etc.
Características:
• CSP binario, continuo, con restricciones disyuntivas
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
24
Problema de diseño
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.
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
a) Solución por defecto para los arcos dados:
b) Versión teniendo en cuenta aspectos estéticos
y geotecnológicos:
c) Bases para diseñar los detalles de los pilares:
?
?
Backtracking sobre
los detalles de
diseño de los pilares
d1) Pilares
demasiado
cerca
e) Diseño final:
d2) Pilares
sobre el
peralte
d3) Pilares
en el agua
25
CSPs binarios & n-arios
Binario
Un CSP binario se suele representar mediante un grafo,
donde:
Nodos: Variables
Arcos: Relaciones binarias entre las variables.
X4
X2
X1 R12
x3 R35
x1 R15
x4 R42
x4 R45
x2 R25
x2
x5
x5
x2
x5
x5
X1
X5
X3
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
26
CSPs binarios & n-arios
No 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: Variables
Arcos: Relaciones binarias entre las variables.
C123
X1
X2
X3
C24567
X4
X5
X6
X7
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
27
Consistencia: Niveles
1-consistencia
Consistencia de nodo (1-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{
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
28
Consistencia: Niveles
2-consistencia
Consistencia de arco (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:
xi
[3,6]
Cij

xj
[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
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
Consistencia: Niveles
2-consistencia
29
X1
X1
Azul, Rojo
X2
Azul, Rojo

X2
Azul


Azul


X4
X3
X3
Azul, Rojo 
Azul, Verde
Verde
Grafo Inicial
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04

X4
Azul, Rojo 
Azul, Verde
Verde
Grafo arco-consistente
Consistencia: Niveles
3-consistencia
30
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 v1d1 y vjdj, tal que la restriccion (x1=v1 c1j xj=vj) se
cumple,
– Entonces existe una secuencia de valores
– v2d2, v3d3, ..., vkdk
– tal que las restricciones (v1 cl2 v2), (v2 c23 v3),...., (vk ck,j vj)
se cumplen.
Departamento Ciencia de la Computación e Inteligencia Artificial. Curso 2003-04
Descargar

(CSP).