Upload
others
View
23
Download
0
Embed Size (px)
Citation preview
Unidad VIBúsqueda.
Estrategias informadas y no informadas.Complejidad computacional.
Planificación.
Inteligencia Computacional
Docente:Dr. Georgina Stegmayer
IC - Métodos de Búsqueda
Inteligencia Artificial
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
Considere el problema de la determinación del camino más corto entre dos puntos, en
el que existe un conjunto de obstáculos. Dicho problema es típicamente estudiado en
robótica para poder lograr que un robot pueda moverse en un ambiente, p.e. para
transporte de mercancías, exploración de un terreno, vehículos inteligentes, entre
otros.
Utilizando búsqueda, encuentre el camino más corto que debe seguir un robot que
desee desplazarse desde el punto A hasta el punto B.
Problema de navegación de robots
IC - Métodos de Búsqueda
sucesor(x): función auxiliar que toma un vértice como entrada y retorna el conjunto
de vértices que pueden ser alcanzados en línea recta a partir de allí.
Ejemplos de la función sucesor:sucesor(A) = {C,G}sucesor(G) = {A,C,F,Q}...
Problema de navegación de robots
Representación del estado: (posiciónAgente)
IA – Modelado de problemas de Búsqueda
Ejercicio 4: Problema de navegación de robots
IC - Métodos de Búsqueda
Problema de navegación de robots
Representación del estado: (posiciónAgente)
Estado inicial: (A)
Estado final: (B)
IA – Modelado de problemas de Búsqueda
Ejercicio 4: Problema de navegación de robots
IC - Métodos de Búsqueda
Problema de navegación de robots
Representación del estado: (posiciónAgente)
Estado inicial: (A)
Estado final: (B)
Prueba de meta:
SI posiciónAgente = B ÉXITO
IA – Modelado de problemas de Búsqueda
Ejercicio 4: Problema de navegación de robots
IC - Métodos de Búsqueda
Problema de navegación de robots
Representación del estado: (posiciónAgente)
Estado inicial: (A)
Estado final: (B)
Prueba de meta:
SI posiciónAgente = B ÉXITO
Operadores:
irA:
SI A sucesor(posiciónAgente) (A)
irB:
SI B sucesor(posiciónAgente) (B)
…
IA – Modelado de problemas de Búsqueda
Ejercicio 4: Problema de navegación de robots
IC - Métodos de Búsqueda
Problema de navegación de robots
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
Estrategias de búsqueda ciega o
no informada
Inteligencia Computacional
Docente:Dr. Georgina Stegmayer
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
Lista de nodos a expandir: cola (los nodos a expandir se
van colocando al final de la lista)
IC - Métodos de Búsqueda
(A)nodo
estado
IC - Métodos de Búsqueda
(A)Contiene unestado objetivo?NO Entonces expandir nodo
Acción de obtener los nodos hijos.Los nodos hijos se obtienen de aplicar todos los operadoresdefinidos al estado representado por el nodo padre.
IC - Métodos de Búsqueda
(A)
(C) (G)
irC irG1
No se muestran en el árbol los operadores que no se pueden aplicar sobre el estado
Posición del nodo en la lista de nodos a expandir
IC - Métodos de Búsqueda
(A)
(C) (G)
irC irG
(D) (G)
irD irG
1
2
Los estados repetidos son eliminados del árbol y no se muestran
(A)
irA
IC - Métodos de Búsqueda
(A)
(C) (G)
irC irG
(D) (G)
irD irG
(C) (F) (Q)
irCirQ
irF
1
2 3
IC - Métodos de Búsqueda
(A)
(C) (G)
irC irG
(D) (G)
irD irG
(C) (F) (Q)
irCirQ
irF
(E) (I)
irE irI
Próximo nodo a expandir …
1
2 3
4 5
IC - Métodos de Búsqueda
(C)
(G) (C) (F) (Q)
(E) (I)
Solución encontrada con la búsqueda en amplitud u horizontal
(D)
(F) (Q) (D) (E) (H) (Q) (F) (P) (B)
1
2 3
4 5 6 7 8
9 10 11 12 13
(A)
14 15 16 17 18 19
(G)
… … … … … … … … … …
irG
irQ
irB
Solución (secuencia de operadores desde el E.I. hasta el E.F.): irG, irQ, irB
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
(A)Contiene unestado objetivo?NO Entonces expandir nodo
IC - Métodos de Búsqueda
(A)
(C) (G)
irC irG1
IC - Métodos de Búsqueda
(A)
(G)
irC irG
(D) (G)
irD irG
(C)
1
2
IC - Métodos de Búsqueda
(A)
(C) (G)
irC irG
(D) (G)
irD irG
(E) (I)
irE irI
1
2
3
IC - Métodos de Búsqueda
(A)
(C) (G)
irC irG
(D) (G)
irD irG
(E) (I)
irE irI
Próximo nodo a expandir …
1
2
3
4
IC - Métodos de Búsqueda
(A)
(C) (G)
(G)
(E) (I)
(D)
(F) (H) (I)
(G) (H) (Q)
(Q)
(B)
1
2
3
4
5
6
7
8
Solución encontrada con la búsqueda en profundidad
irC
Solución: irC, irD, irE, irF, irG, irQ, irB
irD
irE
irF
irG
irQ
irB
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
g(n) = costo del camino
g(n) = costo de ruta = suma de las distancias recorridas desde el nodo inicial?
IC - Métodos de Búsqueda
g(n) = costo del camino
g(n) = costo de ruta = suma de las distancias recorridas desde el nodo inicial?
IC - Métodos de Búsqueda
x
y
A(1,1)
distancia en línea recta entre dos puntos =2
012
01 )()( yyxx
B(10,4)
IC - Métodos de Búsqueda
Lista de nodos a expandir: los nodos a expandir se van
ordenando en la lista según su costo
IC - Métodos de Búsqueda
(A)
(C) (G)
g = 0
g = 1,3g = 1,5
1
irC irG
Próximo nodo a expandir …
IC - Métodos de Búsqueda
(A)
(C) (G)
g = 0
g = 1,3g = 1,5
1
(D) (G)
irD irG
2
irC irG
g =1,3+1=2,3 g = 1,3+1=2,3
IC - Métodos de Búsqueda
(A)
(C) (G)
g = 0
g = 1,3g = 1,5
1
(D) (G)
irD irG
2
irC irG
g =1,3+1=2,3 g = 1,3+1=2,3 Próximo nodo a expandir …
3
IC - Métodos de Búsqueda
(A)
(C) (G)
g = 0
g = 1,3g = 1,5
1
(D) (G)
irD irG
2
irC irG
g =1,3+1=2,3 g = 1,3+1=2,3
(C) (F) (Q)
irCirQ
irF
g =1,5+1=2,5 g = 1,5+1=2,5 g = 1,5+0,5=2
3
IC - Métodos de Búsqueda
(A)
(C) (G)
g = 0
g = 1,3g = 1,5
1
(D) (G)
irD irG
2
irC irG
g =1,3+1=2,3 g = 1,3+1=2,3
(C) (F) (Q)
irCirQ
irF
g =1,5+1=2,5 g = 1,5+1=2,5 g = 1,5+0,5=2
Próximo nodo a expandir …
3
4
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
Estrategias de búsqueda con información
Inteligencia Computacional
Docente:Dr. Georgina Stegmayer
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
(A)h = 9,51
Lista de nodos a expandir: los nodos a expandir se van
ordenando en la lista según el valor de h(n)
IC - Métodos de Búsqueda
(A)h = 9,51Estrategia de búsqueda:
búsqueda avara
Contiene unestado objetivo?NO Entonces expandir nodo
IC - Métodos de Búsqueda
(A)h = 9,51
(C) (G)h = 9,4 h = 8,1
IC - Métodos de Búsqueda
(A)h = 9,51
(C) (G)h = 9,4 h = 8,1
(C) (Q)h = 9,4 h = 7,9
(F)h = 6,1
2
IC - Métodos de Búsqueda
(A)h = 9,5
(C) (G)h = 9,4 h = 8,1
(C) (Q)h = 9,4 h = 7,9
(F)h = 6,1
(I) (H) (Q)h = 3,6 h = 5,0 h = 7,9
1
2
3
(E)h = 5,4
IC - Métodos de Búsqueda
(A)h = 9,5
(C) (G)h = 9,4 h = 8,1
(C) (Q)h = 9,4 h = 7,9
(F)h = 6,1
(I) (H) (Q)h = 3,6 h = 5,0 h = 7,9
1
2
3
(E)h = 5,4
4
(E) (H) (J)h = 5,4 h = 5,0 h = 2,0
(D)h = 6,7
(L)h = 3,2
IC - Métodos de Búsqueda
(A)h = 9,5
(C) (G)h = 9,4 h = 8,1
(C) (Q)h = 9,4 h = 7,9
(F)h = 6,1
(I) (H) (Q)h = 3,6 h = 5,0 h = 7,9
1
2
3
(E)h = 5,4
4
(E) (H) (J)h = 5,4 h = 5,0 h = 2,0
(D)h = 6,7
(L)h = 3,2
5
(L) (B)(K)h = 3,2 h = 1,4 h = 0
6
irG
irF
irI
irJ
irB
Solución encontrada con
búsqueda avara
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
IC - Métodos de Búsqueda
f(n) = función heurística = g(n)+h(n)
g(n) = costo de ruta = suma de las distancias recorridas desde el nodo inicial (A)
h(n) = heurística = distancia en línea recta hasta el nodo objetivo (B)
IC - Métodos de Búsqueda
(A)g = 0 h = 9,5f = g+h = 9,5
1
IC - Métodos de Búsqueda
(A)
(C) (G)
g = 0 h = 9,5f = g+h = 9,5
g = 1,3h = 9,4 f = 10,7
g = 1,5h = 8,1 f = 9,6
1
IC - Métodos de Búsqueda
(A)
(C) (G)
g = 0 h = 9,5f = g+h = 9,5
g = 1,3h = 9,4 f = 10,7
g = 1,5h = 8,1 f = 9,6
(C) (Q)f = 11,9 f = 11,4
(F)f = 9,7
1
2
g = 1+1,5h = 9,4 f = 11,9
IC - Métodos de Búsqueda
(A)
(C) (G)
g = 0 h = 9,5f = g+h = 9,5
g = 1,3h = 9,4 f = 10,7
g = 1,5h = 8,1 f = 9,6
(C) (Q)(F)
(I) (H) (Q)f = 10,5 f = 10,0 f = 13,8
f = 11,9 f = 11,4f = 9,7
1
2
3
(E)f = 10,4
IC - Métodos de Búsqueda
(A)
(C) (G)
g = 0 h = 9,5f = g+h = 9,5
g = 1,3h = 9,4 f = 10,7
g = 1,5h = 8,1 f = 9,6
(C) (Q)(F)
(I) (H) (Q)
(E) (I) (J)
f = 11,8 f = 12,1 f = 10,3
f = 10,5 f = 10,0 f = 13,8
f = 11,9 f = 11,4f = 9,73
4
1
2
(E)f = 10,4
IC - Métodos de Búsqueda
(A)
(C) (G)
g = 0 h = 9,5f = g+h = 9,5
g = 1,3h = 9,4 f = 10,7
g = 1,5h = 8,1 f = 9,6
(C) (Q)(F)
(I) (H) (Q)
(E) (I)
(I) (B)(K)f = 12,4 f = 10,8 f = 10,6
Solución encontrada con A*
(J)
3
4
1
2
f = 11,8 f = 12,1 f = 10,3
f = 10,5 f = 10,0 f = 13,8
f = 11,9 f = 11,4f = 9,7
5
6
(E)f = 10,4
irG
irF
irH
irJ
irB
IC - Métodos de Búsqueda
Método Óptimo? Completo? solución distanciarecorrida
Búsqueda no informada
Amplitud no sí A,irG,irQ,irB 11,2
Profundidad no no A,irC,irD,irE,irF,irG,irQ,irB
16,8
Búsqueda informada
Búsqueda avara
no no A,irG,irF,irI,irJ,irB 11,6
A* sí sí A,irG,irF,irH,irJ,irB 10,6
IC - Métodos de Búsqueda
PROBLEMA: encontrar el camino más corto que debe seguir un robot para ir desde A hasta B
SOLUCIÓN: el camino más corto entre A y B es A,irG,irF,irH,irJ,irB y vale 10,6.
Problema de navegación de robots
Planificación: proceso de búsqueda y articulación de una secuencia de acciones que permiten alcanzar un objetivo
Plan solución: o Ir corredoro Ir hab3o Tomar caja b2o Ir con la caja al corredoro Ir con la caja a hab 1
Problema: llevar la caja b2 desde la hab.3 a la hab. 1
corredor
hab. 1
hab. 2
hab. 3
hab. 4 b1
b2
b3
p1
p2
p3
p4
juan
IC - Planificación
Plantear el problema de búsqueda usualmente exige demasiadas acciones y demasiados estados para analizar.
Recordando conceptos de BÚSQUEDA:Representación de acciones: consisten en funciones que
generan descripciones de estados sucesores
Representación de estados: utiliza representaciones completas de los estados.
Representación de objetivos: solo se tiene un test para verificar el objetivo y una función heurística
IC - Planificación
Planificación
IC - Planificación
El robot Juan debe llevar la caja b1 a la hab. 2
Planificación
corredor
hab. 1
hab. 2
hab. 3
hab. 4 b1
b2
b3
p1
p2
p3
p4
juan
IC - Planificación
El robot Juan debe llevar la caja b1 a la hab. 2
Planificación
corredor
hab. 1
hab. 2
hab. 3
hab. 4 b1
b2
b3
p1
p2
p3
p4
juan
Características:
Representación explícita del objetivo
Descomposición de problemas en sub-problemas.
Las acciones trabajan con expresiones de objetivos explícitos.
Lenguaje expresivo y suficientemente restrictivo que permita ser tratado por algoritmos operativos y eficientes: STRIPS
Suposición de independencia de objetivos.
Entornos: completamente observables, determinísticos, estáticos y discretos
IC - Planificación
Planificación
El algoritmo de búsqueda debería generar un número de nodos demasiado grande, ya que no posee acceso a la estructura del
objetivo.
Abrir la representación de: estados, objetivos y acciones.
Usar un lenguaje formal para describirlos
Permitir realizar conexiones entre estados y acciones.
Por ejemplo,
“Ir(x) se reduce a estar en x”
H2
H3
Objetivo: en(h2)Ir(h2)
Ir(h3)
IC - Planificación
Planificación
Por ejemplo, si tuviéramos como objetivo:En(b1 , hab 2) En(b2 , hab 2)
Se podría obtener un sub-plan que obtenga el primer objetivo y otro sub-plan para el segundo.
Explotar la independencia entre los objetivos a alcanzar.
El planificador puede trabajar sobre las sub-metas independientemente, aunque después necesita trabajo adicional para combinar los sub-planes resultantes
En algunos problemas avanzar sobre una sub-meta puede estar afectando a otra sub-meta.
IC - Planificación
Planificación
Lenguaje Formal:
Representación de estados: conjunto de literales lógicas positivas. Ej: en(caja1, hab1), estado(heladera, sucia)
Deben ser: ground y libre de funciones
IC - Planificación
Planificación
Lenguaje Formal:
Representación de estados: conjunto de literales lógicas positivas. Ej: en(caja1, hab1), estado(heladera, sucia)
Deben ser: ground y libre de funciones
sobre(A,B), sobre(bloque(a), mesa)
IC - Planificación
Planificación
Lenguaje Formal:
Representación de estados: conjunto de literales lógicas positivas. Ej: en(caja1, hab1), estado(heladera, sucia)
Deben ser: ground y libre de funciones
Presunción de Mundo Cerrado
Espacio de estado finito
sobre(A,B), sobre(bloque(a), mesa)
IC - Planificación
No válida
Planificación
Lenguaje Formal:
Representación de estados: conjunto de literales lógicas positivas. Ej: en(caja1, hab1), estado(heladera, sucia)
Deben ser: ground y libre de funciones
Presunción de Mundo Cerrado.
Espacio de estado finito
sobre(A,B), sobre(bloque(a), mesa)
IC - Planificación
No válida
Planificación
Todo lo que no figura explícitamente como un hecho y tampoco se puede deducir,
es falso
Representación de acciones:
Una acción se representa a través de:
precondiciones
efectos
Un operador STRIPS consta de tres partes:
Un conjunto PC de literales denominado precondiciones del operador.
Un conjunto B de literales base denominado lista borrar
Un conjunto A de literales base denominado lista añadir.
IC - Planificación
Planificación
Los operadores STRIPS se definen mediante esquemas de
representación o Reglas STRIPS
Ejemplo:
PutOn(X,Y,Z)
PC: clear(Y) clear(X) on(X,Z)
B: clear(Y), on(X,Z)
A: clear(Z), on(X,Y)
XZ Y
XZ Y
IC - Planificación
Planificación
Los operadores STRIPS se definen mediante esquemas de
representación o Reglas STRIPS
Ejemplo:
PutOn(X,Y,Z)
PC: clear(Y) clear(X) on(X,Z)
B: clear(Y), on(X,Z)
A: clear(Z), on(X,Y)
variables libres
precondición: conjunción de literales. nombre
efecto: Lista borradores + lista adiciones.
XZ Y
XZ Y
clear(Y) on(X,Z)clear(Z),on(X,Z)
otra forma derepresentarlos
IC - Planificación
Planificación
IC - Planificación
PutOn(X,Y,Z)
PC: clear(Y) clear(X) on(X,Z)
B: clear(Y), on(X,Z)
A: clear(Z), on(X,Y)
clear(b) clear(c ) on(c,a) on(b,table) on(a,table).
={Y/b, X/c, Z/a}REGLA
ESTADO
UNIFICADOR
abc
Operador = instancia de una regla.
Una instancia de una regla STRIPS se puede aplicar a la descripción de un estado s si existe una instancia base de PC (considerada como un objetivo) que es satisfecha por la descripción del estado.
Planificación
IC - Planificación
La instancia se obtiene al aplicar a los conjuntos: PC, A y B.
PutOn(X,Y,Z)
PC: clear(Y) clear(X) on(X,Z)
B: clear(Y), on(X,Z)
A: clear(Z), on(X,Y)
={Y/b, X/c, Z/a}
PutOn(c, b, a)
PC: clear(b) clear(c) on(c,a)
B: clear(b), on(c,a)
A: clear(a), on(c,b).
Planificación
IC - Planificación
La instancia se obtiene al aplicar a los conjuntos: PC, A y B.
PutOn(X,Y,Z)
PC: clear(Y) clear(X) on(X,Z)
B: clear(Y), on(X,Z)
A: clear(Z), on(X,Y)
={Y/b, X/c, Z/a}
PutOn(c, b, a)
PC: clear(b) clear(c) on(c,a)
B: clear(b), on(c,a)
A: clear(a), on(c,b).
No pueden aparecer en PC, ni en las listas A y B variables libres que no sean argumentos de la regla.
Planificación
Planificador de orden parcial (POP):
El planificador trabaja sobre sub-metas en forma independiente una de otra.
No se preocupa del orden de los pasos durante la búsqueda.
Estrategia: mínimo compromiso demorar las decisiones durante la búsqueda.
Pueden aparecer dos acciones en un plan sin identificar orden entre ellas.
IC - Planificación
Planificación
Definimos dos acciones: inicio y fin
InicioPC: true.
B:
A: on(B,Table), on(A,Table), on(C,A) cl(A), cl(B).
FinPC: on(A,B), on(B,C), on(C,table), cl(A).B:A:
Estado inicial
meta
IC - Planificación
Planificación
IC - Planificación
Representación de un plan:
Plan(pasos:{S1:op(acción:comenzar); S2: op(acción: ir_a(casa)).....}
orden {S1 S2, comenzar S1, ... }
asociaciones{X/casa; ...} c
links{ S1 S2; ....} )
Planificación
La solución parcial representa dos planes de orden total cada uno de ellos es una linealización del plan de orden parcial.
Planes de orden total:
IC - Planificación
Inicio
ponerMediaIzq
ponerMediaDer
Terminar
Inicio
ponerMediaDer
ponerMediaIzq
Terminar
Planificación
IC - Planificación
Planificación
IC - Planificación
Reglas u operadores “STRIPS”
PC (precondiciones)
B (lista borrar)
A (lista añadir)
PutOn(x,y,z) PutOnTable(x,z)
Planificación
IC - Planificación
S0
S1
Planificación
S0
S1
S2
IC - Planificación
Planificación
Cl(B) On(B,Table) Cl(C)
PutOn(B,C,Table)
Problema “Sussman anomaly”
PutOn(A,B,Table) amenaza Cl(B)
S0
S1
S2
S3PutOn(A,B,Table
)
IC - Planificación
Planificación
Cl(B) On(B,Table) Cl(C)
PutOn(B,C,Table) Cl(A) On(A,Table) Cl(B)
Problema “Sussman anomaly”
PutOn(A,B,Table) amenaza Cl(B)ordenar luego de PutOn(B,C,Table)con un link de ordenamiento
S0
S1
S2
S3
IC - Planificación
Planificación
PutOn(A,B,Table)
Cl(B) On(B,Table) Cl(C)
PutOn(B,C,Table) Cl(A) On(A,Table) Cl(B)
Problema “Sussman anomaly”
PutOn(B,C,Table) amenaza Cl(C)Ordenar luego de PutOnTable(C,A)
S0
S1
S2
S3
S4PutOnTable(C,A)
IC - Planificación
Planificación
PutOn(A,B,Table)
Cl(B) On(B,Table) Cl(C)
PutOn(B,C,Table) Cl(A) On(A,Table) Cl(B)
On(C,A) Cl(C)
Problema “Sussman anomaly”
S0
S1
S2
S3
S4
SoluciónS0 < S4 < S2 < S3 < S1
PutOnTable(C,A)
IC - Planificación
Planificación
PutOn(A,B,Table)
Cl(B) On(B,Table) Cl(C)
PutOn(B,C,Table) Cl(A) On(A,Table) Cl(B)
On(C,A) Cl(C)