Tema 4: Problemas de
satisfaccin de restricciones
Ezequiel Lpez Rubio y Enrique Domnguez
Departamento de Lenguajes y Ciencias de la Computacin
Universidad de Mlaga
Contenidos
4.1 Introduccin
4.2 Definicin del problema y ejemplos
4.3 Restricciones y consistencia
4.4 Vuelta atrs
4.5 Conclusin
4.1 INTRODUCCIN
4.1 Introduccin
Motivacin
El telescopio espacial Hubble fue lanzado en 1990
Poda observar objetos nunca antes vistos
Muchos astrnomos estaban interesados en usarlo
4.1 Introduccin
Motivacin
Cada ao haba que planificar alrededor de 10.000-30.000 observaciones, cada una con varias restricciones operativas y cientficas
Cientfica: slo se puede observar un eclipse cuando est ocurriendo
Operativa: no puedes observar un objeto cuando est detrs de la Tierra
El algoritmo de planificacin inicial necesitaba 3 semanas para planificar una semana de observaciones (!)
4.1 Introduccin
Representaciones factorizadas
En los temas anteriores exploramos problemas que pueden resolverse buscando en un espacio de estados
Cada estado era atmico, es decir, era una caja negra sin estructura interna
Aqu emplearemos una representacin factorizada para cada estado
Un conjunto de variables, cada una con su valor
Un problema est resuelto cuando cada variable tiene un valor que satisface todas las restricciones sobre dicha variable
4.2 DEFINICIN DEL
PROBLEMA Y EJEMPLOS
4.2 Definicin del problema y ejemplos
Definicin (I)
Un problema de satisfaccin de restricciones (constraint satisfaction problem, CSP) est formado por tres componentes:
Un conjunto de variables, X={X1,,Xn}
Un conjunto de dominios, uno para cada variable: D={D1,, Dn}
Un conjunto de restricciones que especifican combinaciones permitidas de valores, C
Cada dominio Di es el conjunto de valores posibles {v1,, vk} para la variable vi
4.2 Definicin del problema y ejemplos
Definicin (II)
Cada restriccin Ci es un par
donde scope es la tupla de variables que
intervienen en la restriccin y rel es una
relacin que define los valores que dichas
variables pueden tomar
Por ejemplo, si las variables X3 y X5 deben
tener valores distintos, podemos escribir esta
restriccin como < (X3,X5), X3 X5 >
4.2 Definicin del problema y ejemplos
Definicin (III)
Cada estado de un CSP se define como una asignacin de valores a algunas o a todas las variables, {Xi=vi, Xj=vj,}
Una asignacin que no viola ninguna restriccin se llama asignacin consistente o legal
Si tenemos una asignacin en la cual todas las variables estn asignadas, la llamamos asignacin completa. En otro caso, la llamamos asignacin parcial
Una solucin de un CSP es una asignacin consistente y completa
4.2 Definicin del problema y ejemplos
Ejemplo 1: Coloreado de mapas
La tarea consiste en colorear cada regin de un mapa de tal manera que no haya regiones adyacentes que tengan el mismo color
Para el mapa de Australia (siguiente transparencia), definimos las variables como X={WA, NT, Q, NSW, V, SA, T}
El dominio de cada variable es Di={red, green, blue}
Hay nueve restricciones: C={SA WA, SA NT, SAQ, SA NSW, SA V , SA V, WA NT , NT Q, QNSW, NSW V}
4.2 Definicin del problema y ejemplos
Ejemplo 1: Coloreado de mapas
4.2 Definicin del problema y ejemplos
Ejemplo 2: problemas criptoaritmticos
En un acertijo criptoaritmtico, cada letra
representa a un dgito distinto (0-9)
RUOF
OWT
OWT
4.2 Definicin del problema y ejemplos
Ejemplo 2: problemas criptoaritmticos
El requisito de que todas las variables han de tomar diferentes valores se corresponde con la restriccin AllDiff(F,T,U,W,R,O)
Introducimos tres variables auxiliares C10, C100 y C1000, que representan los dgitos acarreados a las columnas de las decenas, las centenas y los millares, respectivamente
De esta manera el resto de las restricciones son:
O+O=R+10C10 C10+W+W=U+10C100 C100+T+T=O+10C1000 C1000=F
4.3 RESTRICCIONES Y
CONSISTENCIA
4.3 Restricciones y consistencia
Tipos de restricciones
Una restriccin unaria restringe el valor de una sola
variable
Por ejemplo, para imponer que South Australia no se
coloree de verde escribimos
Una restriccin binaria relaciona dos variables
Por ejemplo, SANSW
Una restriccin en la que participa un nmero
arbitrario de variables se llama restriccin global
Por ejemplo, AllDiff(F,T,U,W,R,O)
4.3 Restricciones y consistencia
Grafo de restricciones
WA
NT
Q
SANSW
V
T
Cada variable se
representa mediante un
nodo, y cada restriccin
binaria se representa con
un arco
4.3 Restricciones y consistencia
Hipergrafo de restricciones
F T U W R O
C1000 C100 C10Los recuadros
representan las
restricciones
globales
4.3 Restricciones y consistencia
Consistencia de nodos
Una variable es nodo-consistente si todos los valores
del dominio de la variable satisfacen las restricciones
unarias sobre dicha variable
Por ejemplo, si tenemos la restriccin unaria
, podemos hacer SA nodo-consistente
quitando green de su dominio, lo que deja a SA con el
dominio reducido {red, blue}
Siempre es posible eliminar todas las restricciones
unarias de un CSP ejecutando la consistencia de
nodos
4.3 Restricciones y consistencia
Consistencia de arcos
Una variable Xi es arco-consistente si, para cada valor del dominio de Xi y cada restriccin binaria (Xi,Xj), podemos encontrar al menos un valor en el dominio de Xj que satisface la restriccin
Una red es arco-consistente si toda variable es arco-consistente con las dems variables
El siguiente algoritmo asegura la arco-consistencia de la variable Xi con respecto a otra variable Xj ; devuelve true si y slo si se ha revisado el dominio de Xi
4.3 Restricciones y consistencia
Algoritmo de revisin de dominios
function Revise(csp, Xi, Xj)
revised false
for each x in Di do
if ningn valor y en Dj hace que (x,y)
satisfaga la restriccin entre Xi y Xj then
borrar x de Di
revisedtrue
return revised
4.3 Restricciones y consistencia
Algoritmo AC-3 (I)
El algoritmo ms popular para asegurar la arco-consistencia en una red se llama AC-3
Mantiene un conjunto de arcos que considerar
Inicialmente el conjunto contiene todos los arcos del CSP
A continuacin extrae un arco cualquiera (Xi,Xj) del conjunto y hace Xi arco-consistente con respecto a Xj Si esto reduce el dominio Di, entonces aadimos al conjunto todos los
arcos (Xk,Xi), tales que Xk es vecino de Xi
Si un dominio se reduce a nada, entonces el CSP original no tena solucin, y devolvemos false. En otro caso obtenemos un CSP en el que es ms fcil buscar
4.3 Restricciones y consistencia
Algoritmo AC-3 (II)
function AC-3(csp)
setAllArcs(csp)
while set no est vaco do
(Xi,Xj)Extract(set)
if Revise(csp, Xi, Xj) then
if size(Di)=0 then return false
for each Xk in Xi.Neighbors-{Xj} do
aadir (Xk,Xi) a set
return true
4.4 VUELTA ATRS
4.4 Vuelta atrs
Algoritmo bsico (I)
Muchos CSPs no se pueden resolver solamente por inferenciasobre las restricciones; llega un momento en el que hay que buscar una solucin
La bsqueda por vuelta atrs es una bsqueda primero en profundidad que en cada momento elige un valor para una sola variable, y vuelve atrs cuando una variable no tiene ningn valor legal que quede por probar
Debemos considerar las siguientes preguntas:
Qu variable debera ser asignada a continuacin?
En qu orden deberamos probar sus valores?
Qu inferencias deberan realizarse en cada paso?
4.4 Vuelta atrs
Algoritmo bsico (II)function Backtracking-search(csp)
return Backtrack({},csp)
function Backtrack(assignment,csp)
if assignment es completo then return assignment
varSelectUnassignedVariable(csp)
for each value in OrderDomainValues(var,assignment,csp) do
if value es consistente con assignment then
aadir {var=value} a assignment
inferencesInference(csp,var,value)
if inferencesfailure then
aadir inferences a assignment
resultBacktrack(assignment,csp)
if resultfailure then
return result
quitar {var=value} e inferences de assignment
return failure
4.4 Vuelta atrs
Ordenacin de las variables
Habitualmente se elige la variable que tenga el menor nmero de valores legales. Esto es lo que se llama el heurstico del mnimo nmero de valores restantes (minimum remaining values heuristic, MRV)
A fin de romper los empates se puede emplear el heurstico del grado (degree heuristic, DEG), que elige la variable que interviene en el mayor nmero de restricciones con otras variables no asignadas
Esta manera de elegir las variables intenta obtener un fallo tan pronto como sea posible para podar secciones ms grandes del rbol de bsqueda rpidamente
4.4 Vuelta atrs
Ordenacin de los valores
En algunos casos el heurstico del valor menos restrictivo (least constraining value, LCV) puede resultar til
Prefiere el valor que elimina el menor nmero de opciones para las variables vecinas en el grafo de restricciones
Este heurstico intenta obtener una solucin tan pronto como sea posible eligiendo primero los valores ms verosmiles
4.4 Vuelta atrs
Intercalando bsqueda e inferencia
Cada vez que hacemos una eleccin de un valor para una variable, intentamos inferir nuevas reducciones de dominio en las variables vecinas
Una de las estrategias ms sencillas es la comprobacin hacia delante (forward checking) Cada vez que se asigna una variable X, para cada variable
no asignada Y que est conectada a X mediante una restriccin, borramos del dominio de Y los valores que son inconsistentes con el valor elegido para X
La comprobacin hacia delante es intil si ya hemos ejecutado la consistencia de arcos como procesamiento previo
4.5 CONCLUSIN
4.5 Conclusin
Sumario
Los problemas de satisfaccin de restricciones
representan un estado mediante un conjunto de pares
variable/valor y representan las condiciones que
debe cumplir la solucin mediante un conjunto de
restricciones sobre las variables
Las tcnicas de inferencia usan las restricciones para
inferir qu pares variable/valor son consistentes
Habitualmente se emplea la bsqueda por vuelta
atrs para encontrar una solucin
4.5 Conclusin
Eplogo
Empleando tcnicas similares a las estudiadas en este tema, el tiempo de planificacin semanal se redujo de tres semanas a 10 minutos (AIMA, p. 221)
Nebulosa planetaria
NGC 2818, vista
por el telescopio
espacial Hubble.
Rojo = nitrgeno,
verde = hidrgeno,
azul = oxgeno.