PDF de programación - Satisfacción de Restricciones - Inteligencia Artificial

Satisfacción de Restricciones

Inteligencia Artificial

CS-GEI-FIB c b e a

Curso 2018/2019

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

1 / 19

Índice

1

Introducción

2 Backtracking Cronológico

3 Propagación de restricciones

4 Forward Checking

5 Otras heurísticas

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

2 / 19

Satisfacción de Restricciones

Introducción

Componentes del estado:

Variables
Dominios (valores posibles para las variables)
Restricciones binarias entre las variables

Objetivo: Encontrar un estado que satisface las restricciones
(Asignación de valores a las variables, que satisfaga las restricciones)
Ejemplos:

Colorear mapas, crucigramas, 8-reinas, sudoku, ...
Asignación/distribución/ubicación de recursos (distribución de tareas
de fabricación, ubicación de gasolineras, antenas de telefonía, ...)

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

3 / 19

Representación

Introducción

Estado = Grafo de restricciones
Variables = etiquetas de nodos
Dominios = contenido de nodos
Restricciones = arcos dirigidos y etiquetados entre nodos

Ejemplo: colorear un mapa

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

4 / 19

123456789Dominios={Rojo,Verde,Azul,Amarillo}Restricción := DesigualdadAlgoritmos

Introducción

Generación y prueba: enormemente ineficiente
Búsqueda ciega

Búsqueda en profundidad con backtracking cronológico

Propagación de restricciones

Antes de la búsqueda
Durante la búsqueda

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

5 / 19

Backtracking Cronológico

Búsqueda en profundidad con backtracking cronológico

Búsqueda en profundidad sobre las variables
Asignar valor por estrategia exhaustiva

Comprobar restricciones tras cada posible asignación
Si no se satisfacen para ningún valor, backtracking sobre la última
asignación válida

La búsqueda se realiza en el espacio de soluciones parciales
Backtracking cronológico: tipos de variables (pasadas, actual, futuras)

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

6 / 19

Backtracking Cronológico

Algoritmo Backtracking Cronológico

Función: backtracking_cronologico(vfuturas, solucion)
si vfuturas.es_vacio?() entonces

sino

retorna solucion
vactual ← vfuturas.primero()
vfuturas.borrar_primero()
para cada v ∈ vactual.valores() hacer

vactual.asignar(v)
solucion.anadir(vactual)
si solucion.valida() entonces

solucion ← backtracking_cronologico(vfuturas,solucion)
si no solucion.es_fallo?() entonces

retorna solucion

sino

solucion.borrar(vactual)

sino

solucion.borrar(vactual)

retorna solucion.fallo()

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

7 / 19

Backtracking Cronológico

Ejemplo: 4-reinas

Colocar 4 reinas, 1 en cada fila de un tablero 4x4, sin que se maten

Variables: R1, ... , R4 (reinas)
Dominios: [1 .. 4] para cada Ri (columna)
Restricciones: Ri no-mata Rj

Grafo de restricciones:

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

8 / 19

R3R1R2R4Backtracking Cronológico

4-reinas mediante backtracking cronológico

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

9 / 19

R1=1R1=2R2=3R2=1 NOR2=2 NOR3=1 NOR3=2 NOR3=3 NOR3=4 NOBacktracking a R2R2=4R3=1 NOR4=1 NOR4=2 NOR4=3 NOR4=4 NOR3=2NOR3=3 NOR3=4 NOR2=1 NOR2=2 NOR2=3 NOR2=4R3=1R4=1 NOR4=2 NOR4=3Solucion (R1=2,R2=4,R3=1,R4=3)Backtracking a R3Propagación de restricciones

Propagación de restricciones

Un conjunto de restricciones puede inducir otras que estaban implícitas. La
propagación de restricciones es el proceso de hacerlas explícitas

El papel de la PR es disminuir el espacio de búsqueda. Debemos realizar la
propagación:

1 preproceso (eliminar zonas del espacio donde no hay soluciones)
2 durante el proceso: podar el espacio a medida que la búsqueda

progresa (Forward Checking)

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

10 / 19

{Azul}{Axul, Rojo}{Azul, Verde}{Azul, Rojo, Verde}X1X2X3X4{Azul}X1X2X3X4{Rojo}{Verde}{Rojo}Propagación de restricciones

Propagación de restricciones

Cada ciclo tiene dos partes:

1 Se propagan las restricciones

Se podrían utilizar de reglas de inferencia.
Tener en cuenta que las restricciones no tienen por qué ser
independientes (Muchas restricciones implican a varias variables, una
variable participa en muchas restricciones)

2 Se analiza el resultado:
1 Solución encontrada
2 Solución imposible
3 Seguir buscando: proceso heurístico de búsqueda

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

11 / 19

Propagación de restricciones

Propiedades sobre grafos de restricciones

Se pueden definir propiedades sobre los grafos de restricciones que
permiten reducir el espacio de búsqueda

k-consistencia: Poda de valores que no sean posibles para un grupo de
k variables
Arco consistencia (2-consistencia): Eliminamos valores imposibles para
parejas de variables
Camino consistencia (3-consistencia): Eliminamos valores imposibles
para ternas de variables
...

Comenzar con un grafo k-consistente (2, 3, ...) reduce el número de
backtrackings

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

12 / 19

Propagación de restricciones

Preproceso de arco-consistencia

Un PSR es arco-consistente si para cada par de variables (Xi, Xj) y
para cualquier valor vk de Di existe un valor vl de Dj tal que se
satisfacen las restricciones. Es decir, se busca que los valores posibles
de Xi sean consistentes con la restricción asociada al arco.
Lo que realmente pretendemos es que todas las variables sean arco
consistentes para todos los arcos que inciden en ellas. Es decir, que
los dominios actuales de cada variable sean consistentes con todas las
restricciones.

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

13 / 19

Propagación de restricciones

Algoritmo de arco-consistencia
Si un PSR no es arco-consistente se le puede convertir mediante el siguiente
algoritmo:
Algoritmo: Arco consistencia
R ← conjunto de arcos del problema /* ambos sentidos
mientras se modifiquen los dominios de las variables hacer

*/

*/
*/

r ← extraer_arco(R)
/* ri es la variable del origen del arco
/* rj es la variable del destino del arco
para cada v ∈ en el dominio de ri hacer

si v no tiene ningún valor en el dominio de rj que cumpla r entonces

borrar v del dominio de ri
añadir todos los arcos que tengan como destino ri menos el (rj → ri)

fin

fin

fin

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

14 / 19

Propagación de restricciones

Ejemplo arco-consistencia

X1
{Azul,Rojo}

X2

{Azul}

X3

{Azul,Rojo,Verde}

X4
{Azul,Verde}

Lista de arcos inicial:
(X1,X2), (X2,X1), (X2,X3), (X3,X2),
(X2,X4), (X4,X2), (X3,X4), (X4,X3)

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

15 / 19

1. X1 − X2 → Quitar Azul de X1

Propagación de restricciones

Ejemplo arco-consistencia

×

X1
{Azul,Rojo}

X2

{Azul}

X3

{Azul,Rojo,Verde}

X4
{Azul,Verde}

Lista de arcos inicial:
(X1,X2), (X2,X1), (X2,X3), (X3,X2),
(X2,X4), (X4,X2), (X3,X4), (X4,X3)

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

15 / 19

Propagación de restricciones

Ejemplo arco-consistencia

×

X1
{Azul,Rojo}

1. X1 − X2 → Quitar Azul de X1
2. X2 − X1 → Todo consistente

X2

{Azul}

X3

{Azul,Rojo,Verde}

X4
{Azul,Verde}

Lista de arcos inicial:
(X1,X2), (X2,X1), (X2,X3), (X3,X2),
(X2,X4), (X4,X2), (X3,X4), (X4,X3)

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

15 / 19

Propagación de restricciones

Ejemplo arco-consistencia

×

X1
{Azul,Rojo}

1. X1 − X2 → Quitar Azul de X1
2. X2 − X1 → Todo consistente
3. X2 − X3 → Todo consistente

X2

{Azul}

X3

{Azul,Rojo,Verde}

X4
{Azul,Verde}

Lista de arcos inicial:
(X1,X2), (X2,X1), (X2,X3), (X3,X2),
(X2,X4), (X4,X2), (X3,X4), (X4,X3)

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

15 / 19

Propagación de restricciones

Ejemplo arco-consistencia

1. X1 − X2 → Quitar Azul de X1
2. X2 − X1 → Todo consistente
3. X2 − X3 → Todo consistente
4. X3 − X2 → Quitar Azul de X3,
Tendríamos que añadir X4 − X3
pero ya está

×

X1
{Azul,Rojo}

X4
{Azul,Verde}

X2

{Azul}

X3

×

{Azul,Rojo,Verde}

Lista de arcos inicial:
(X1,X2), (X2,X1), (X2,X3), (X3,X2),
(X2,X4), (X4,X2), (X3,X4), (X4,X3)

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

15 / 19

Propagación de restricciones

Ejemplo arco-consistencia

1. X1 − X2 → Quitar Azul de X1
2. X2 − X1 → Todo consistente
3. X2 − X3 → Todo consistente
4. X3 − X2 → Quitar Azul de X3,
Tendríamos que añadir X4 − X3
pero ya está

5. X2 − X4 → Todo consistente

×

X1
{Azul,Rojo}

X4
{Azul,Verde}

X2

{Azul}

X3

×

{Azul,Rojo,Verde}

Lista de arcos inicial:
(X1,X2), (X2,X1), (X2,X3), (X3,X2),
(X2,X4), (X4,X2), (X3,X4), (X4,X3)

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso 2018/2019

15 / 19

Propagación de restricciones

Ejemplo arco-consistencia

×

X1
{Azul,Rojo}

×

X4
{Azul,Verde}

1. X1 − X2 → Quitar Azul de X1
2. X2 − X1 → Todo consistente
3. X2 − X3 → Todo consistente
4. X3 − X2 → Quitar Azul de X3,
Tendríamos que añadir X4 − X3
pero ya está

5. X2 − X4 → Todo consistente
6. X4 − X2 → Quitar Azul de X4,
Tendríamos que añadir X3 − X4
pero ya está

X2

{Azul}

X3

×

{Azul,Rojo,Verde}

Lista de arcos inicial:
(X1,X2), (X2,X1), (X2,X3), (X3,X2),
(X2,X4), (X4,X2), (X3,X4), (X4,X3)

Inteligencia Artificial (CS-GEI-FIB c b e a)

Satisfacción de Restricciones

Curso