Problemas de satisfacción de restricciones en Inteligencia Artificial (página 2)

Búsqueda con vuelta atrás para PSR ¿Por qué terrible?: En el siguiente nivel, el factor de ramificación es (n-1)·d, etcétera para los n niveles. ¡Generamos un árbol con n!·dn hojas, aunque haya sólo dn asignaciones completas! La formulación del problema, aparentemente razonable pero ingenua, no ha considerado una propiedad crucial común en todos los PSRs: la conmutatividad 17

Conmutatividad Un problema es conmutativo si el orden de aplicación de las acciones no tiene ningún efecto sobre el resultado. Éste es el caso de los PSRs, donde las acciones son asignaciones de valores a variables. Por lo tanto, todos los algoritmos de búsqueda para PSR generan los sucesores considerando asignaciones posibles para sólo una variable en cada nodo del árbol de búsqueda. 18

Conmutatividad Por ejemplo, en el nodo raíz de un árbol de búsqueda para colorear este mapa: podríamos tener una opción entre C3 = azul, C3 = rojo y C3 = verde pero nunca elegiríamos entre C3 = rojo y C1 = azul. Con esta restricción, el número de hojas es de dn., como era de esperar. 19

Búsqueda con vuelta atrás El término búsqueda con vuelta atrás se utiliza para la búsqueda 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. El algoritmo genera los sucesores incrementalmente, uno a la vez extiende la asignación actual para generar un sucesor, más que volver a copiarlo 20

Búsqueda con vuelta atrás: algoritmo 21

Búsqueda con vuelta atrás: algoritmo función Búsqueda-Con-Vuelta-Atrás(psr) devuelve una solución, o fallo devolver Vuelta-Atrás-Recursiva({}, psr)

función Vuelta-Atrás-Recursiva(asignación, psr) devuelve una solución, o un fallo si asignación es completa entonces devolver asignación var ? Selecciona-Variable-Noasignada(Variables[psr], asignación, psr) para cada valor en Orden-Valores-Dominio(var, asignación, psr) hacer si valor es consistente con asignación de acuerdo a las Restricciones[psr] entonces añadir {var = valor} a asignación resultado ? Vuelta-Atrás-Recursiva(asignación, psr) si resultado ? fallo entonces devolver resultado borrar {var = valor} de asignación devolver fallo 22

23 Ejemplo: 4-reinas Colocar 4 reinas, una en cada fila de un tablero 4×4, sin que se maten.

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

Grafo: 23

24 Ejemplo: 4-reinas

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

El papel de la PR es disminuir el espacio de búsqueda. Se puede realizar la propagación: 1) como pre-proceso: eliminar zonas del espacio donde no hay soluciones (arc consistency); 2) durante el proceso: podar el espacio a medida que la búsqueda progresa (forward checking). 25

Propagación de restricciones Cada ciclo tiene dos partes: Se propagan las restricciones: Posible utilización de reglas de inferencia Las restricciones no tienen por qué ser independientes: Restricciones que implican a varias variables Variables que participan en varias restricciones Se analiza el resultado: Solución encontrada Solución imposible Seguir buscando 26 26

Propiedades sobre grafos de restricciones Se pueden definir propiedades sobre los grafos de restricciones que permiten reducir el espacio de búsqueda. k-consistency: poda de valores que no sean posibles para un grupo de k variables: Arc consistency (2-consistency): Eliminamos valores imposibles para parejas de variables. Path consistency (3-consistency): Eliminamos valores imposibles para ternas de variables. … Comenzar con un grafo k-consistent (2, 3…) reduce el número de vueltas atrás.

Preproceso 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. Se pretende que todas las variables sean arco consistentes para todos los arcos que inciden en ellas. Los dominios actuales de cada variable tienen que ser consistentes con todas las restricciones.

Preproceso Si un PSR no es arco-consistente se le puede convertir mediante el siguiente algoritmo:

(Se vuelve a analizar la consistencia de arcos cuyo destino ha podido cambiar.)

Ejemplo de arco-consistencia: colorear mapa 30

Ejemplo de arco-consistencia: colorear mapa 31

Ejemplo de arco-consistencia: colorear mapa 32

Ejemplo de arco-consistencia: colorear mapa 33

Ejemplo de arco-consistencia: colorear mapa 34

Ejemplo de arco-consistencia: colorear mapa 35

Ejemplo de arco-consistencia: colorear mapa 36

Ejemplo de arco-consistencia: colorear mapa 37

Ejemplo de arco-consistencia: colorear mapa 38

Ejemplo de arco-consistencia: colorear mapa 39

Propagación durante la búsqueda(forward checking) Modificación del algoritmo de búsqueda en profundidad con vuelta atrás cronológica Anticipación: detectar cuanto antes caminos sin solución y podarlos. Asignar un valor y consultar las restricciones sobre las variables futuras con arco desde la actual Se eliminan valores no compatibles de los dominios correspondientes a dichas variables futuras Equivale a hacer arco-consistente la variable actual con las futuras en cada paso. La eficiencia dependerá del problema. Se incrementa el coste de cada iteración.

Algoritmo forward checking

Ejemplo: 4-reinas mediante forward checking

Ejemplo: 4-reinas mediante forward checking R1=1? Propagamos: R2=3,4; R3=2,4; R4=2,3 ? R1=1 R2=3? Propagamos: R3= Ø R2=4? Propagamos: R3=2; R4=3 ? R2=4 R3=2? Propagamos: R4= Ø Ningún otro valor para R3. Backtracking a R2 Ningún otro valor para R2. Backtracking a R1 R1=2? Propagamos: R2=4; R3=1,3; R4=1,3,4 ? R1=2 R2=4? Propagamos: R3=1; R4=1,3 ? R2=4 R3=1? Propagamos: R4=3 ? R3=1 R4=3? No hay propagaciones ? R4=3

44 PSR: ejemplo

45 PSR: ejemplo

46 PSR: ejemplo

Forward checking Idea: Keep track of remaining legal values for unassigned variables Terminate search when any variable has no legal values 47 47

48 Forward checking Idea: Keep track of remaining legal values for unassigned variables Terminate search when any variable has no legal values 48

49 Forward checking Idea: Keep track of remaining legal values for unassigned variables Terminate search when any variable has no legal values 49

50 Forward checking Idea: Keep track of remaining legal values for unassigned variables Terminate search when any variable has no legal values 50

51 Forward checking Forward checking propagates information from assigned to unassigned variables, but doesn't provide early detection for all failures:

NT and SA cannot both be blue!

Constraint propagation repeatedly enforces constraints locally. 51

52 Arc consistency Simplest form of propagation makes each arc consistent . (X Y) is consistent iff: for every value x of X there is some allowed y 52

53 Arc consistency Simplest form of propagation makes each arc consistent . (X Y) is consistent iff: for every value x of X there is some allowed y 53

54 Arc consistency Simplest form of propagation makes each arc consistent . (X Y) is consistent iff: for every value x of X there is some allowed y

If X loses a value, neighbors of X need to be rechecked. 54

55 Arc consistency Simplest form of propagation makes each arc consistent . (X Y) is consistent iff: for every value x of X there is some allowed y

Arc consistency detects failure earlier than forward checking. Can be run as a preprocessor or after each assignment. 55

Heurísticas adicionales La búsqueda con vuelta atrás puede mejorarse reordenando las variables: Antes de la búsqueda (primero las mas restrictivas) Durante la búsqueda: Variable con mas restricciones Variable con menos valores La reordenación de variables puede reducir el tiempo de búsqueda varios ordenes de magnitud en ciertos problemas.