Problemas de Satisfacción de Restricciones

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


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


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 >


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


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}


Ejemplo 1: Coloreado de mapas


Ejemplo 2: problemas criptoaritmticos

En un acertijo criptoaritmtico, cada letra

representa a un dgito distinto (0-9)

RUOF

OWT

OWT


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


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)


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


Hipergrafo de restricciones

F T U W R O

C1000 C100 C10Los recuadros

representan las

restricciones

globales


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


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


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


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


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.

Documents

Problemas de Satisfacción de Restricciones