cap nvo 5 r&n (2ª ed.) búsqueda restricta

Cap Nvo 5 r&n (2ª ed.)Cap Nvo 5 r&n (2ª ed.)Búsqueda RestrictaBúsqueda Restricta

Diapositivas de C H von der Becke parcialmente sobre ideas de lStuart Russell, Peter Norvig, Alan Mackworth,

Tralvex Yeap

Inte

lige

nci

a A

rtif

icia

l 1P

arte

II

http://images.google.com/imgres?imgurl=www.biblequizzes.co.uk/crosswords/goodsamaritan_std.gif&imgrefurl=http://www.biblequizzes.co.uk/crosswords/goodsamaritan_std.html&h=262&w=262&prev=/images%3Fq%3Dcrosswords%26svnum%3D10%26hl%3Des%26lr%3D%26ie%3DUTF-8%26sa%3DG

Carlos H. von der Becke - - - - - - -Cap 05 Búsqueda Restricta - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Foundations of Artificial Intelligence

2

Algoritmo general de Búsqueda

FASTA - IA1 - Clase 6 18

3.7-Algoritmo Gral de Búsqueda• Idea básica:

– fuera de línea (no en el mundo real), exploraciónsimulada del espacio de estados

– por generación de sucesores de estados yaexplorados (se llama expandir estados)

function General-Search(problem, strategy) returns a solution, or failureintialize the search tree using the initial state of the problemloop do

if there are no candidates for expansion thenreturn failure

choose a leaf node for expansion according to strategyif the node contains a goal state then

return the corresponding solutionelse expand the node and add the resulting nodes to the search tree

return

function General-Search(problem, strategy) returns a solution, or failureintialize the search tree using the initial state of the problemloop do

if there are no candidates for expansion thenreturn failure

choose a leaf node for expansion according to strategyif the node contains a goal state then

return the corresponding solutionelse expand the node and add the resulting nodes to the search tree

return


3

Repaso Russell y Norvig han definido con elegancia un algoritmo general

para resolver problemas de búsqueda. Este algoritmo puede ser usado para expresar diferentes estrategias específicas de búsquedas.

Un problema se representa como una estructura con componentes: ESTADO NODO PADRE OPERADOR PROFUNDIDAD COSTO DE RUTA.


4

Búsqueda mediante satisfacción de Restricciones

Prueba de meta - ahora hay restricciones en los valores que pueden tener las variables (deben satisfacerse en la meta).

Prueba de meta una serie de restricciones a las variables que hay que satisfacer. Esto es una novedad.

Estrategias

a) Búsqueda Primero en Profundidad sirve bastante bien pues la profundidad coincide con n, el número de variables - pero se pierde tiempo porque como es ciega no aplica inteligencia.


5

b) Búsqueda Primero lo Mejor (BPM) La Idea: expandir el nodo mejor posicionado por la función de

evaluación f(n) Estrategia avara: f(n) = h(n), donde h(n) estima el costo de avanzar

desde el nodo n hasta el nodo meta.

¿Qué puede suceder si siempre tratamos de dar el siguiente paso de manera de movernos en forma de quedar más cerca de la meta?

El típico caso es la “escalada”

En el caso de la derechael algoritmo se equivoca pues sigue el camino más largo al estar comprometido con esa solución

En el caso de la derechael algoritmo se equivoca pues sigue el camino más largo al estar comprometido con esa solución


6

Descripción General

Definición del problema Condiciones de inicio/meta Reglas como conjunto de IF...THEN..... Estrategia - control de la aplicación de las reglas


7

Procedimiento: PRODUCCION

Sistema de PRODUCCION conjunto de reglas contenidas en una base de reglas , con reglas permanentes y reglas efímeras; además hay una estrategia de control del empleo de las reglas Reglas de condición-acción conjunto de IF...THEN..... Estrategia control de la aplicación de las reglas


8

Temas a tratar

Ejemplos de CSP o PSR Búsqueda reversible en CSP o PSR Estructura de problema y descomposición de problema Resolver CSP o PSR

Restricciones propositivas: resolvedor con satisfabilidad

Restricciones relacionales de primer orden: dificultades – más adelante

Aceleración del CSP o PSR: mejora iterativa Optimización por gradiente máximo – escalada

Forjado simulado

Búsqueda local para CSP o PSR


9

CSS (Constrained Satisfaction Search)

A Constrained Satisfaction Problem (CSP) is composed of:

1. States correspond to the values of a set of variables.

2. The goal test specifies a set of constraints that the values must obey.

CSP Examples:

Coloreado de mapas

Crucigrama 1

Calendario de actividades

Reserva de pasajes

Crucigrama 2

n-reinas,

Ciptoaritmética

VLSI layout,

Alocación de recursos


10

CSP del mundo real Floorplanning is the

process of identifying structures that should be placed close together, and allocating space for them in such a manner as to meet the sometimes conflicting goals of available space (cost of the chip), required performance, and the desire to have everything close to everything else.


11

Caso estándar

a)


12

Casos estándar y CSP Caso estándar Estado es una caja negra – es

cualquier estructura clásica que soporta UNA PRUEBA DE META, FUNCION EVALUACIÓN Y FUNCION SUCESORES (recién

definida)

Caso CSP Estado definido por variable Xi

con valores en el dominio Di La prueba de meta (recién

detallada) es un conjunto de restricciones especificando las combinaciones permitidas de valores para los subconjuntos de variables

Uso de lenguaje formal de representación (CSP es un ejemplo simple de ese lenguaje)

Permite el empleo de algoritmos de uso general con buen desempeño.


13

Satisfacción de restricciones o CSP Introducimos la teoría de los problemas de satisfacción de restricciones, CSP o

PSR. El razonamiento basado en restricciones es un paradigma en la inteligencia

artificial que consigue que muchos expertos profundicen en esta especialidad porque resulta ser una valiosa forma de solucionar muchos problemas.

Muchas aplicaciones informáticas importantes, tales como la configuración de racks, la planificación, la alocación de recursos, la programación restricta y el diseño se pueden modelar como problemas discretos usando satisfacción de restricciones.

Un problema finito discreto binario de satisfacción de restricciones se define como un sistema de variables, un dominio de los valores permitidos para cada una de las variables del sistema y un sistema de restricciones entre cada par de variables.

Una solución de un CSP o PSR es una asignación final permitida por las restricciones de los valores. Un CSP o PSR puede tener una o muchas soluciones y también resultar insoluble (cero soluciones).


14

Crucigrama

El rompecabezas denominado crucigrama es un ejemplo simple para ilustrar el proceso de formalización de un problema clásico en un CSP o PSR. El problema es poner palabras de un diccionario en una estructura dada que satisface ciertas restricciones.

Las variables son las filas y las columnas en el crucigrama, y sus valores son las palabras en un diccionario. En este CSP o PSR tenemos restricciones unarias y restricciones binarias. Las restricciones unarias garantizan que las palabras tienen el tamaño apropiado para ubicarse en la grilla y las binarias se cercioran que las letras de posiciones entrecruzadas sean iguales.

Solucionar un CSP o PSR discreto es equivalente a efectuar las asignaciones de algún valor a las variables sujetas a restricciones. Ya existe un conjunto grande de técnicas para solucionar CSP o PSR eficientemente.

Se puede utilizar Java, llamándose JCL la colección específica de programas que encaran a los CSP o PSR

La L significa librería. Ella provee servicios para: Crear, gestionar y representar redes Aplicar algoritmos a las redes Gestionar resultados temporarios y finales

NOTA: Ninguno de estos servicios necesita el ingreso de gráficos o el egreso de la información como gráficos – pueden así ser incorporados a cualquier aplicación.


15

Un ejemplo muy simple Diccionario = {FANTASTIC,

JAVA, INTERNET, HELLO, INSOLUBLE},


16

Restricciones unarias - binarias

Las restricciones además de ser unarias y binarias pueden ser ternarias y de órdenes superiores (en criptaritmética, etc.). Pueden ser ‘blandas’ (prefiero rojo a verde)


17

Calendario de actividades Un problema de satisfacción de restricciones –CSP o PSR – presenta:

Un conjunto de variables Cada variable tiene asociado un dominio de valores posibles Relaciones de restricción o “restricciones” en varios subconjuntos de

las variables que autorizan combinaciones legales de valores de dichas variables

Una solución en el caso de un PSR será una n-tupla de valores para las variables que satisfacen la totalidad de las relaciones de restricción.

Ejemplo de un calendario de actividades Variables – A, B, C, D, E que representan los tiempos iniciales para

varias actividades. Dominios – DA = {1,2,3,4} DB = {1,2,3,4} DC = {1,2,3,4} DD = {1,2,3,4} DE = {1,2,3,4} Restricciones (B ¬= 3) /\ ( C ¬= 2) /\ ….


18

ATP = Reserva de pasajes en aviación

Más adelante estudiaremos el mundo de las reservas de pasajes (DAACS)


19

PSR -Búsqueda especial

Casi todas las búsquedas previas eran irrestrictas (excepción, 8 reinas, búsqueda de repetidos)

Con optimismo, si hay restricciones no hay que buscar en todos los lados que ahora son tabú.

Aparecen nuevas propiedades estructurales. Estado - aplicando el algoritmo de uso general, de entrada

ninguna variable estará asignada. El primer valor asignado lo será por los operadores que elegirán algún valor posible.

Se puede empezar en muchos lugares indistintamente


20

PSR – Más estrategias

c) Búsqueda Reversiva o por Backtracking aplica inteligencia pues verifica a lo largo de la ruta la prueba de meta y apenas hay un error, vuelve atrás y retoma otra bifurcación. Aplica dicha prueba después de cada asignación de una variable, en lugar de sólo hacerlo al final de las asignaciones

d) Verificación para adelante (Forward checking) a medida que los operadores les van asignando valores a las variables, se va llevando una prolija constancia del saldo de los sitios que no están ligados, con vistas a las asignaciones faltantes. Si ese saldo es cero, enseguida se revierte y retoma otra bifurcación.


21

Ejemplo - coloreado de mapa Variables WA,NT,Q,NSW,V,SA,T (Western Au, Territorio del Norte,

Queensland, Nueva Gales del Sur. Victoria, Au del Sur y Tasmania Dominios Di = {rojo, verde, azul} Restricciones: regiones adyacentes necesitan colores distintos, WA ¬= NT (WA,NT) € {(rojo,verde),(rojo,azul),(verde,rojo),(verde,azul),…} Soluciones son asignaciones que satisfacen todas las restricciones WA= rojo NT = verde Q = rojo NSW = verde V= rojo SA= azul T = verde


22

c) Búsqueda reversiva


23

c) Búsqueda reversiva - 2


24

Grafo de restricciones abstracto Cada restricción relaciona aquí

a lo sumo a 2 variables (T subproblema independiente)

Grafo de restricciones; Los nodos son variables X Los arcos muestran restricciones

Esos arcos debieran ser consistentes

Los algoritmos para CSP usan la estructura de grafos para la aceleración de la búsqueda

WA

V NSW

>

Q

NT

SA

T


25

Coloreado de mapas concreto - 1


26

2


27

c) Reversión - 3


28

c) 4


29

c) 5


30

c) 6


31

c) 7 Mejorando el desempeño de la reversión

Los métodos de propósito general ofrecen ganancia en velocidad

1 A cuál variable le toca el turno? 2 En qué orden se deben tratar los valores? 3 Es posible detectar fracaso casi de entrada? 4 Se le puede sacar ventajas a la estructura que muestra el

problema?


32

8-Variable más restricta


33

9-Variable más restricta

La variable más restricta se deduce fácilmente del grafo de diapositiva 23 – es el nodo más ligado a otros.


34

10-valor que causa mínima molestia


35

d) 11-verificación hacia adelante

Mediante la verificación hacia delante se puede reconocer teóricamente si no vale o vale la pena continuar la búsqueda (por ser irresoluble o no)


36

d) 12 - verificación hacia adelante


37

d) 13 - verificación hacia adelante


38

14 – Propagación de restricciones

¿Detección temprana?

Existe la alternativa de entender la propagación de restricciones como corolario del siguiente tema, esto es, la consistencia de arco


39

1


40

2


41

3-Algoritmos de consistencia La idea heurística: Analizar las restricciones de a dos dominios X e Y por vez.

Podar los valores de los dominios tanto como sea posible y luego seccionar o dividir los dominios, salvo que hayan quedado todos vacíos (no hay solución) o todos con 1 valor (solución única). No habrá más búsqueda en esos dos casos.

La búsqueda novedosa es la de valores a podar. La tarea es la de volver consistentes los arcos inconsistentes. En el caso de restricciones binarias, habrá arcos inconsistentes si hay valores

en DX que no pueden formar pares con los valores presentes en DY. (Ausencia de valores correspondientes)

Al detectar un arco inconsistente hay que volverlo consistente por poda de valores inconsistentes en X y en Y.

Esas podas alteran la validez de las tareas previas si Y ha quedado disminuido en número y hay que repetir la secuencia hasta que no haya más disminuciones en número de valores/dominio.

Si ha quedado más de un valor en los dominios, se recomienda partir esos dominios en sub-dominios y aplicar consistencia de arcos a cada sub-dominio (búsqueda novedosa)


42

4 – Mackworth y algoritmos AC UNARIOS - Determine if each element in each domain satisfies

a unary constraint BINARIOS - Definition - An arc (x; y) in the constraint graph of

a CSP is arc consistent (AC) if and only if for every value a in the domain of x which satisfies the constraint on x, there exists a value in the domain of y which is compatible with x; a .

The most naive approaches, AC 1 and AC 2, initiate a queue of all edges and checks for each element in the queue if for each element in domain of variable x there exists a value in domain of variable y, where x and y are subject to the binary constraint C xy , such that C xy holds.

More selective algorithms AC 3 - AC 4 up to AC 7 have been developed.

All of them check for consistency for all values of x; y C x;y .


43

5-Variables, dominios (en inglés) 5 Variables 1 horizontal (3 letras) 3 horizontal (4 letras) 4 horizontal (3 letras) 1 vertical (4 letras) 2 vertical (6 letras) 5 dominios {ant, big, bus, car, has} {book, buys, hold, lane, year} {ant, big, bus, car, has} {book, buys, hold, lane, year} {beast, ginger, search, symbol}

Nótese que beast no satisface una restricción unaria


44

6-Variables, dominios, restricciones 5 Variables (voces) X1=1 horizontal (3 letras) X2=3 horizontal (4 letras) X3=4 horizontal (3 letras) X4=1 vertical (4 letras) X5=2 vertical (6 letras) 5 dominios (únicas voces existentes) D1={dos, has, Job, las, ola} D2={bien, ella, hora, juez, rana} D3={dos, has, Job, las, ola} D4={bien, ella, hora, juez, rana} D5={astros, balada, buscar, sandía} 5 restricciones (entrecruzamientos) R1-Entre X1 y X4 – igual 1ª letra R2-Entre X2 y X5 – igual 3ª letra R3-3ª letra de X1=1ª letra de X5 R4-1ª letra de X3=5ª letra de X5 R5-1ª letra de X2=3ª letra de X4

Número de nodos sin poda alguna:(5)(5)(5)(5)(4) = 2500

No hay restricciones unarias en este ejemplo en español

R1

R2

R3

R4

R5


45

7-Poda con R1 Variables (voces) tomadas como

pares X1=1 horizontal (3 letras) X4=1 vertical (4 letras) dominios (únicas voces existentes) D1={dos, has, Job, las, ola} D4={bien, ella, hora, juez, rana} restricciones (entrecruzamientos) R1-entre X1 y X4 – igual 1ª letra Podables según R1 D1={dos, las, ola} D4={bien, ella, rana} Admisibles según R1 D1={has, Job} D4={hora, juez} Método de consistencia de arco

Número de nodos antes de primera poda: 2500Poda aplicando R1 - (2)(5)(5)(2)(4) = 400

”

’


46

8-Poda con R2 Variables (voces) X2=3 horizontal (4 letras) X5=2 vertical (6 letras) dominios (únicas voces existentes) D2={bien, ella, hora, juez, rana} D5={astros, balada, buscar, sandía} restricciones (entrecruzamientos) R2-Entre X2 y X5 – igual 3ª letra Podables según R2 D2={bien, hora, juez} D5={astros, buscar} Admisibles según R2 D2={ella, rana} D5={balada, sandía}

Número de nodos previos: (2)(5)(5)(2)(4) = 400

Por poda R1 y R2:( ((2)(2)(5)(2)(2) = 80


47

9-Poda (imposible) con R3 5 Variables (voces) X1=1 horizontal (3 letras) X5=2 vertical (6 letras) 5 dominios (únicas voces existentes) D1={has, Job} – ver antes D5={balada, sandía} – ver antes 5 restricciones (entrecruzamientos) R3-3ª letra de X1=1ª letra de X5 Podables según R3 D1={) D5={} Admisibles según R5 D1={has, Job} D5={balada, sandía}

Número de nodos previo: (2)(2)(5)(2)(2) = 80Número de nodos con R3: Sin cambios


48

10-Poda con R4 Variables (voces) X3=4 horizontal (3 letras) X5=2 vertical (6 letras) dominios (únicas voces existentes) D3={dos} – ver antes D5={balada} – ver antes restricciones (entrecruzamientos) R4-1ª letra de X3=5ª letra de X5 Podables según R4 D3={has, Job, las, ola) D5={sandía} Admisibles según R4 D3={dos} D5={balada}

Número de nodos previo: (2)(2)(5)(2)(2) = 80Acumulativo con R4 : (2)(2)(1)(2)(1) = 8

”


49

11-Poda (imposible) con R5 Variables (voces) X2=3 horizontal (4 letras) X4=1 vertical (4 letras) dominios (únicas voces existentes) D2={ella, rana} – ver antes D4={hora, juez} – ver antes restricciones (entrecruzamientos) R5-1ª letra de X2=3ª letra de X4 Podables según R5 D2={-} D4={-} Admisibles según R5 D2={ella, rana} D4={hora, juez}

Número de nodos: (2)(2)(1)(2)(1) = 8Nota: La explicación teórica se aprecia aquí:

”


50

12-Propagación de Restricciones

Consistencia de arcos aplica sistemáticamente un sistema de borrado de sitios o valores que desaparecen para la tarea de asignar un valor a una variable

Propagación de Restricciones consecuencia de la consistencia de arcos - a medida que se van borrando valores, como éstos estaban basados en otros valores, lo que era congruente se volverá incongruente. Esto explica que hecho el primer recorrido, todavía habría que buscar clásicamente el resultado entre 8 nodos. En lugar de hacerlo clásicamente, lo hacemos buscando de nuevo consistencia de arcos. (Otra manera de entender el tema - en diapositiva 35). En ningún momento esta búsqueda revierte a una búsqueda clásica con nodos multiatributos.

Las diapositivas siguientes mostrarán la tarea de propagación de restricciones, una especie de efecto dominó que prolonga la caída de valores y hace que sigan cayendo otros valores relacionados a los ya caídos.


51

13-2ª poda con R1 Variables (voces) X1=1 horizontal (3 letras) X4=1 vertical (4 letras) dominios (únicas voces existentes) D1={has, Job} D4={hora, juez} restricciones (entrecruzamientos) R1-entre X1 y X4 – igual 1ª letra Podables según R1 D1={} D4={} Admisibles según R1 D1={has, Job} D4={hora, juez}

Sin cambiosNúmero de nodos: 8

”

’


52

14-2ª Poda con R2 Variables (voces) X2=3 horizontal (4 letras) X5=2 vertical (6 letras) dominios (únicas voces existentes) D2={ella, rana} D5={ balada} restricciones (entrecruzamientos) R2-Entre X2 y X5 – igual 3ª letra Podables según R2 D2={rana} D5={--} Admisibles según R2 D2={ella} D5={balada}

Número de nodos previos: (2)(2)(1)(2)(1) = 8Por segunda poda R2 (2)(1)(1)(2)(1) = 4


53

15-2ª Poda con R3 5 Variables (voces) X1=1 horizontal (3 letras) X5=2 vertical (6 letras) 5 dominios (únicas voces existentes) D1={has, Job} – ver antes D5={balada} – ver antes 5 restricciones (entrecruzamientos) R3-3ª letra de X1=1ª letra de X5 Podables según R3 D1={has) D5={} Admisibles según R5 D1={ Job} D5={balada}

Número de nodos previo: (2)(1)(1)(2)(1) = 4 Por segundo uso de R3: (1)(1)(1)(2)(1) = 2

”


54

16-2ª Poda (imposible) con R4 Variables (voces) X3=4 horizontal (3 letras) X5=2 vertical (6 letras) dominios (únicas voces existentes) D3={dos} – ver previa D5={balada} – ver previa restricciones (entrecruzamientos) R4-1ª letra de X3=5ª letra de X5 Podables según R4 D3={--} D5={--} Admisibles según R4 D3={dos} D5={balada}

Número de nodos previos: (1)(1)(1)(2)(1) = 2Sin cambios

”


55

17-2ª Poda con R5 - final Variables (voces) X2=3 horizontal (4 letras) X4=1 vertical (4 letras) dominios (únicas voces existentes) D2={ella} – ver antes D4={hora, juez} – ver antes restricciones (entrecruzamientos) R5-1ª letra de X2=3ª letra de X4 Podables según R5 D2={-} D4={hora} Admisibles según R5 D2={ella} D4= {juez}

Número de nodos previos: (1)(1)(1)(2)(1) = 2Resultado definitivo sin árbol alguno: (1)(1)(1)(1)(1)= 1

”


56

Valores que forman pares ANALISIS DE PARES CON LISTAS

SIN PODA ALGUNA RESPETAN LA 1ª RESTRICCIÓN

Has = Hora- Job = Juez

RESPETAN LA 2ª RESTRICCIÓN elLa = baLada - raNa = saNdía

RESPETAN LA 3ª RESTRICCIÓN doS = Sandía haS = Sandía joB = Balada joB = Buscar laS = Sandía olA = Astros

RESPETAN LA 4ª RESTRICCIÓN Dos = balaDa Ola = astrOs

RESPETAN LA 5ª RESTRICCIÓN Ella = biEn Ella = juEz Rana = hoRa

todas las voces que existen aparecen en este listado – hay inconsistencias de arco


57

Inconsistencias de arco ANALISIS MAS DETALLADO DE D5 Valor de D5 que NO forma pares según la

2ª y la 4ª restricción y puede ser eliminada: buScAr que tiene una S y una A inútiles.

De 2500 quedan 1875 nodos a revisar. Valor de D5 que NO forma pares según la

2ª restricción: asTros que tiene una T inútil. Queda una búsqueda con 1250 nodos. Valor de D5 que NO forma pares según la

4ª restricción: sandIa, que tiene una I inútil. Queda una búsqueda con 625 nodos. ANALISIS DE D1 a D4 – valores que dejan

de tener pares y se pueden podar usando propagación de restricciones en D1, todas menos “Job”, en D2, todas menos “ella”, en D3, todas menos “dos”, en D4, todas menos bien y juez

Revisando de nuevo con la restricción R1, se encuentra que el valor “bien” es inconsistente.

Resulta así 1x1x1x1x1 = 1 nodo. El método de una repetida poda de

inconsistencias es apto para una programación iterativa.

¿Sirven o no las heurísticas?


58

Variedades que aparecen en CSP Variables discretas Dominios finitos D tiende a O(d^n) Ej. Calendario de actividades Necesita de un lenguje de

restricciones, p ej Inicio_ tarea1 + 5 =<

Inicio_tarea3 Son resolubles las restricciones

lineales e indecidibles las no-lineales

Variables continuas P.ej. Un observatorio en órbita

como el Hubble Retricciones lineales resolubles

en tiempo polinomial por métodos de programación lineal


59

Variedades que aparecen en CSP

Types of Constraints Discrete (e.g. 8-queens) versus Continuous (e.g. phase I

simplex. Absolute constraints (violation rules out solution candidate) versus

preferential constraints (e.g. goal programming).

Other better search strategies Backtracking search, forward checking, arc consistency checking. constraint propagation.


60

Algoritmo de consistencia de arcos


61

Duraciones


62

Estructura de árbol


63

Algoritmo para estructuras de árbol


64

Estructuras para CSP cuasi-árboles


65

Algoritmos iterativos para CSP


66

n-Reinas


67

Problema de n reinas

Example: 8-Queens Problem

States: <V1, V2, …, V8>, where Vi is the row occupied by the ith queen.

Domains: {1, 2, 3, 4, 5, 6, 7, 8}

Constraints: no-attack constraint { <1,3>, <1,4>, <1,5>, … <2,4>. <2,5>, …}where each element specifies a pair of allowable values for variables Vi and Vj.


68

Desempeño en situaciones de conflicto


69

Alocación de recursos


70

Resumen

cap nvo 5 r&n (2ª ed.) búsqueda restricta

Documents