1FCT - UNCA Ing. Héctor Estigarribia
PROBLEMAS DE SATISFACCIÓN DE RESTRICCIONES
10/04/2014
INTELIGENCIA ARTIFICIAL - UNIDAD 5:
Problemas de satisfacción de restricciones
Búsqueda con vuelta atrás (Backtracking) para PSR
FCT - UNCA Ing. Héctor Estigarribia 2
INTRODUCCIÓN• Hasta Ahora hemos tratado a los estados como si
fueran una caja negra sin una estructura perceptible interna.
• Los representamos por una estructura de datos arbitraria a la que se puede acceder solo son funciones específicas (función sucesor, heurística, test objetivo).
• Al tratar los estados como más que solo pequeñas cajas negras encontraremos nuevos poderosos métodos de búsqueda y entender mejor la estructura y complejidad del problema
10/04/2014
FCT - UNCA Ing. Héctor Estigarribia 3
Problemas de Satisfacción de restricciones
• Un problema de satisfacción de restricciones (PSR) viene definido formalmente por los siguientes elementos:
• Un conjunto finito de variables X1, . . . , Xn
• Cada variable tiene un conjunto no vacío D de valores posibles.
• Un conjunto finito de restricciones C1, . . . , Cm
• Cada restricción implica un subconjunto de variables
10/04/2014
PSR: variables con restricciones sobre ellas
FCT - UNCA Ing. Héctor Estigarribia 4
Problemas de Satisfacción de restricciones
• Un estado del problema está definido por una asignación de valores a una o todas las variables {Xi = vi… Xj = Vj}.
• Una asignación que no viola ninguna restricción Ci se le llama consistente o legal.
• Una asignación completa es una asignación en la que se menciona cada variable.
• Una solución de un PSR es una asignación completa que satisface todas las restricciones.
10/04/2014
FCT - UNCA Ing. Héctor Estigarribia 5
Ejemplo
10/04/2014
Colorear cada región de rojo, verde o azul de modo que ninguna de las regiones vecinas tenga el mismo color.
Variables Regiones:{AO, TN, Q, NGS, V,AS, T}.Dominio de cada variable conjunto de colores: {rojo, verde, azul}Restricciones: que las
regiones vecinas tengan colores distintos
FCT - UNCA Ing. Héctor Estigarribia 6
• Es bueno visualizar un PSR como un grafo de restricciones:
10/04/2014
Problemas de Satisfacción de restricciones
Nodos variablesArcos restricciones
FCT - UNCA Ing. Héctor Estigarribia 7
• Formulación incremental de un PSR
10/04/2014
Problemas de Satisfacción de restricciones
Estado inicial ninguna variable asignada
Función de sucesor asignar un valor a una variable
Test objetivo asignación completa
Costo del camino constante, por ejemplo 1 para cada paso
FCT - UNCA Ing. Héctor Estigarribia 8
Búsqueda con vuelta atrás (Backtracking)
para PSR• Con la formulación anterior, cualquier algoritmo
de búsqueda de los anteriores capítulos puede resolver la PSR.
• El término búsqueda con vuelta atrás se utiliza para la búsqueda primero en profundidad que elige valores para una variable a la vez y vuelve atrás cuando una variable no tiene ningún valor legal para asignarle.
10/04/2014
FCT - UNCA Ing. Héctor Estigarribia 9
Búsqueda con vuelta atrás (Backtracking)
para PSR
10/04/2014
Parte del árbol de búsqueda generado por vuelta atrás para el problema de colorear el mapa de Australia
FCT - UNCA Ing. Héctor Estigarribia 10
Búsqueda con vuelta atrás (Backtracking)
para PSR
10/04/2014
Parte del árbol de búsqueda generado por vuelta atrás para el problema de colorear el mapa de Australia
FCT - UNCA Ing. Héctor Estigarribia 11
Búsqueda con vuelta atrás (Backtracking)
para PSR
10/04/2014
Parte del árbol de búsqueda generado por vuelta atrás para el problema de colorear el mapa de Australia
FCT - UNCA Ing. Héctor Estigarribia 12
Búsqueda con vuelta atrás (Backtracking)
para PSR
10/04/2014
• ¿Que variable debe asignarse después?• ¿Cuáles son las implicaciones de las
asignaciones de las variables actuales para las otras variables no asignadas?
• Cuando un camino falla, ¿puede la búsqueda evitar repetir este fracaso en los caminos siguientes?
FCT - UNCA Ing. Héctor Estigarribia 13
Búsqueda con vuelta atrás (Backtracking) para
PSR.
Variable y ordenamiento de valor
10/04/2014
• El algoritmo back tracking simplemente selecciona la siguiente variable no asignada en el orden dado por la lista de variables.
• Una vez asignada, ayuda a hacer más eficiente la búsqueda, pues las siguientes variables a asignar ya tienen más restricciones.
FCT - UNCA Ing. Héctor Estigarribia 14
Búsqueda con vuelta atrás (Backtracking) para
PSR.
Variable y ordenamiento de valor
10/04/2014
Ejemplo: Ao rojo, TN verde, solo queda AS azul.Entonces es mejor asignar azul a AS que azul o rojo a Q .Luego de asignar AS, las opciones para Q, NGS y V están forzadas. Esta idea intuitiva (escoger la variable con menos valores “legales” se llama heurística de mínimos valores restantes (MVR).
FCT - UNCA Ing. Héctor Estigarribia 15
Búsqueda con vuelta atrás (Backtracking) para
PSR.
Variable y ordenamiento de valor
10/04/2014
La heurística MVR no ayuda en la elección de la primera región a colorear en Australia, por que al principio cada región tiene 3 colores “legales”En este caso, el grado heurístico es más práctico. Intenta seleccionar la variable que esté implicada en el mayor número de restricciones.
2
2
3
3
3
5
0
La heurística MVR normalmente es más poderosa pero la heurística del grado puede usarse para romper empates
FCT - UNCA Ing. Héctor Estigarribia 1610/04/2014
Búsqueda con vuelta atrás (Backtracking) para
PSR.
Variable y ordenamiento de valorLa heurística del valor menos restringido puede ser eficaz en algunos casos
Supongamos AO=rojo, TN=verde y que debemos continuar con Q
FCT - UNCA Ing. Héctor Estigarribia 1710/04/2014
Búsqueda con vuelta atrás (Backtracking) para
PSR.
Variable y ordenamiento de valorLa heurística del valor menos restringido puede ser eficaz en algunos casos
Azul sería una opción mala, pues elimina el último valor legal de AS
FCT - UNCA Ing. Héctor Estigarribia 1810/04/2014
Búsqueda con vuelta atrás (Backtracking) para
PSR.
Variable y ordenamiento de valorLa heurística del valor menos restringido puede ser eficaz en algunos casos
La heurística del valor menos restringido, prefiere rojo a azul para Q
En general, esta heurística trata de dejar la flexibilidad máxima de las asignaciones a las variables siguientes
FCT - UNCA Ing. Héctor Estigarribia 19
PROPAGACIÓN DE LA
INFORMACIÓN A TRAVÉS DE LAS
RESTRICCIONES • Hasta ahora el algoritmo de
búsqueda considera las restricciones sobre una variable sólo cuando la variable es elegida.
• Mirando algunas restricciones antes en la búsqueda, o incluso antes de que haya comenzado la misma, podemos reducir drásticamente el espacio de ésta.
10/04/2014
FCT - UNCA Ing. Héctor Estigarribia 20
COMPROBACIÓN HACIA ADELANTE
10/04/2014
Cuando se asigna una variable X , el proceso mira cada variable no asignada Y relacionada con X por una restricción
Entonces suprime del dominio de Y cualquier valor que sea inconsistente con el valor elegido para X
FCT - UNCA Ing. Héctor Estigarribia 21
COMPROBACIÓN HACIA ADELANTE
10/04/2014
AO TN Q NGS V AS T
R V A
R V A
R V A
R V A
R V A
R V A
R V A
1- AO = ROJO
FCT - UNCA Ing. Héctor Estigarribia 22
COMPROBACIÓN HACIA ADELANTE
10/04/2014
AO TN Q NGS V AS T
R V A
R V A
R V A
R V A
R V A
R V A
R V A
R V A
R V A R V A R V A V A
R V A
R R V A
R R V A
Despues de AO=rojo
* La Comprobación hacia adelante suprime rojo de los dominios de TN y AS
1- AO = ROJO
FCT - UNCA Ing. Héctor Estigarribia 23
COMPROBACIÓN HACIA ADELANTE
10/04/2014
AO TN Q NGS V AS T
R V A
R V A
R V A
R V A
R V A
R V A
R V A
R V A
R V A R V A R V A V A
R V A
R A V R A
R V A A R V A
R V R V A
Despues de ao=rojo
* La Comprobación hacia adelante suprime rojo de los dominios de TN y AS
1- AO = ROJO
* La Comprobación hacia adelante suprime verde de los dominios de TN, AS y NGS
2- Q = VERDE
Despues de q=verde
* Los dominios de TN y AS se reducen a un solo valor
FCT - UNCA Ing. Héctor Estigarribia 24
COMPROBACIÓN HACIA ADELANTE
10/04/2014
AO TN Q NGS V AS T
R V A
R V A
R V A
R V A
R V A
R V A
R V A
R V A
R V A R V A R V A V A
R V A
R A V R A
R V A A R V A
R A V R A R V A
Despues de ao=rojo
* La Comprobación hacia adelante suprime rojo de los dominios de RN y AS
1- AO = ROJO
* La Comprobación hacia adelante suprime verde de los dominios de TN, AS y NGS
2- Q = VERDE
Despues de q=verde
* La Comprobación hacia adelante suprime azul del dominio de NGS y AS, se obtiene AS sin valores legales
3- V = AZUL
Despues de v=azul
* La comprobacion hacia adelante descubre que AO, Q, V es inconsistente y el algoritmo volverá atrás
FCT - UNCA Ing. Héctor Estigarribia 25
Propagación de restricciones
• La comprobación hacia adelante descubre inconsistencias, pero no todas.
• En este punto tanto TN como AS están obligadas a ser azules.
• Pero son adyacentes y eso no puede ocurrir.• La CHA no la descubre como inconsistencia, pues
no mira lo suficientemente lejos.
10/04/2014
AO TN Q NGS V AS T
R V A
R V A
R V A
R V A
R V A
R V A
R V A
R V A
R V A R V A R V A V A
R V A
R A V R A
R V A A R V A
R V R V A
Despues de ao=rojo
Despues de q=verde
FCT - UNCA Ing. Héctor Estigarribia 26
Arco consistente
10/04/2014
• Proporciona un método rápido de propagación de restricciones que es más potente que la CHA.
• El “arco” se refiere a un arco dirigido en el grafo de restricciones, como el arco de AS a NGS.
• Considerando los valores actuales de AS y NGS, el arco es consistente si, para todo valor x de AS, hay algún valor y de NGS que es consistente con x.
FCT - UNCA Ing. Héctor Estigarribia 27
Arco consistente
10/04/2014
• En la figura los dominios actuales de AS y NGS son {azul} y {rojo, azul}.
• Para AS=azul hay una asignación consistente para NGS (NGS=roja).
• Por tanto, el arco de AS a NGS es consistente.• Para la asignación NGS=azul no hay ninguna
asignación consistente para AS.• Por tanto, el arco de NGS a AS no es consistente.• El arco puede hacerse consistente suprimiendo el
valor azul del dominio de NGS
AO TN Q NGS V AS T
R V A R V A R V A R V A R V A R V A R V A
R V A R V A R V A R V A V A R V A
R A V R A R V A A R V A
R V R V A
FCT - UNCA Ing. Héctor Estigarribia 28
Arco consistente
10/04/2014
• Podemos aplicar el arco consistente al arco de AS a TN:
• Ambas variables tienen el dominio {azul}.• El resultado es que azul debe suprimirse del
dominio de AS, dejando el dominio vacío.• Así, la aplicación del arco consistente ha causado la
detección temprana de una inconsistencia no descubierta por la CHA pura.
AO TN Q NGS V AS T
R V A R V A R V A R V A R V A R V A R V A
R V A R V A R V A R V A V A R V A
R A V R A R V A A R V A
R V R V A
FCT - UNCA Ing. Héctor Estigarribia 29
Arco consistente
10/04/2014
• La comprobación de la consistencia del arco puede aplicarse como un pre proceso antes de comenzar el proceso de búsqueda o como un paso de propagación (como la CHA).
• En todo caso el proceso debe aplicarse repetidamente hasta que no permanezcan más inconsistencias.
• Siempre que un valor se suprime del dominio de alguna variable para quitar la inconsistencia de un arco, podría surgir una nueva inconsistencia de arco en arcos que señalan a aquella variable.
• Aunque sea considerablemente más costosa que la CHA, el coste suplementario por lo general vale la pena.
FCT - UNCA Ing. Héctor Estigarribia 30
Vuelta atrás inteligente• El algoritmo backtracking tiene una
política muy simple para saber que hacer cuando falla una rama: hacia atrás hasta la variable anterior e intentar un valor diferente para ella.
• Esto se llama vuelta atrás cronológica(visita el punto de decisión mas reciente).
• Veamos que ocurre cuando aplicamos backtrack simple con una variable fija que ordena Q, NGS, V, T, AS, AO, TN.
10/04/2014
FCT - UNCA Ing. Héctor Estigarribia 31
Vuelta atrás inteligente
10/04/2014
• Supongamos que hemos generado la asignación parcial Q – NGS – V – T.
• Cuando intentamos la siguiente variable AS vemos que cada valor viola una restricción.
• Volvemos hacia atrás hasta T e intentamos un nuevo color para Tasmania (Obviamente esto es inútil)
1
23
4
5
FCT - UNCA Ing. Héctor Estigarribia 32
Vuelta atrás inteligente
10/04/2014
• Una aproximación más inteligente es ir hacia atrás hasta el conjunto de variables que causaron el fracaso.
• Este conjunto se llama conjunto conflicto: en el ejemplo el conjunto conflicto para AS es (Q, NGS, V).
• En general el conjunto conflicto para la variable X es el conjunto de variables previamente asignadas que están relacionadas con X por las restricciones.
• En este caso, el backtrack debería saltar sobre Tasmania e intentar un nuevo valor para V.
• Esto se implementa modificando el algoritmo de modo que acumule el conjunto conflicto mientras comprueba un valor legal para asignar.
FCT - UNCA Ing. Héctor Estigarribia 33
Ejercicio• Coloree el mapa con 3 colores usando Vuelta
atrás, grado heurístico, MVR, CHA:
10/04/2014
FCT - UNCA Ing. Héctor Estigarribia 34
BIBLIOGRAFÍA• INTELIGENCIA ARTIFICIAL: UN ENFOQUE
MODERNO. o STUART RUSSELL Y PETER NORVIG. o PEARSON EDUCATIONo 2da Edición, 2004.o 1240 páginas
• Capitulo 5, Paginas 155 a 180• http://es.wikipedia.org/wiki/Problema_de_satisfacci%C3%B3n_de_restricciones• http://users.dsic.upv.es/~msalido/papers/capitulo.pdf• http://www.cs.us.es/cursos/ia1/temas/tema-05.pdf• http://gpd.sip.ucm.es/rafa/docencia/pr/tema1.html#tema1primerprograma
10/04/2014