INTELIGENCIA ARTIFICIAL

1.

Presentacin basada en:

Inteligencia Artificial un enfoque moderno. Stuart Rusell & Peter
Norving.

La resolucin de problemas es uno de los

procesos bsicos de razonamiento que la
inteligencia artificial trata de abordar

El objetivo consiste en lograr que la mquina ayude

a un experto humano a encontrar la solucin a un
determinado problema (de forma ms rpida, ms
exacta, ms fiable...)

Pero...

cmo expresar el problema de forma

computacional?
cmo puede resolverlo la mquina de forma
eficiente?

Se tienen dos jarras de agua, una de 4l y otra

de 3l sin escala de medicin.
Se desea tener 2l de agua en la jarra de 4l. Las
siguientes operaciones son vlidas:
ACCIONES
llenar las jarras,
vaciar el agua de las jarras,
pasar agua de una jarra a otra.

El espacio de estados se define como

{ (X,Y) tal que, X son los litros en la jarra de 4l con 0<=X<=4 AND Y son los litros de la
jarra de 3l con 0<=Y<=3 }

El estado inicial es (0,0)

El estado final es (2,0). El estado final podra ser (2, N) en caso de que no
importen los litros de la segunda jarra.
Las reglas que se pueden aplicar son:
1.
2.

Llenar la jarra de 4l: Si (X,Y) AND X<4 => (4,Y)

Llenar la jarra de 3l: Si (X,Y) AND Y<3 => (X,3)

3.
4.

Vaciar la jarra de 4l: Si (X,Y) AND X>0 => (0, Y)

Vaciar la jarra de 3l: Si (X,Y) AND Y>0 => (X, 0)

5.

Pasar agua de la jarra de 4l a la jarra de 3l hasta llenarla:

Si (X,Y) AND X>0 AND X+Y>=3 => (X-(3-Y),3)
Pasar agua de la jarra de 3l a la jarra de 4l hasta llenarla:
Si (X,Y) AND Y>0 AND X+Y>=4 => (4, Y-(4-X))
Pasar toda el agua de la jarra de 4l a la jarra de 3l:
Si (X,Y) AND X>0 AND X+Y<3 => (0, X+Y)
Pasar toda el agua de la jarra de 3l a la jarra de 4l:
Si (X,Y) AND Y>0 AND X+Y<4 => (X+Y,0)

6.

7.
8.

Llenar la jarra de 4l:

Vaciar "un poco" la jarra de 4l:

Pasar agua de la jarra de 4l a la jarra de 3l hasta llenarla: Si

Si (X,Y) AND X<4 => (4,Y)

PREC. contiene la condicin (X<4), especificando que la jarra no se encuentra

llena. Si esta condicin no se incluye, se puede aplicar la regla an cuando la
jarra est llena. Dado que en este caso el estado del problema no cambia la
aplicacin de la regla se considera intil .
EFEC. (4,Y), indicando que ya esta llena X.
Si (X,Y) AND X>0 => (X-Q, Y)

PREC. es decir, tirar agua sin cuantificar, intuitivamente (Q) se concluye que la
aplicacin de esta regla nunca nos acercar a la solucin del problema.
EFECT. X queda con menos Q cantidad de agua y Y queda igual (X-Q, Y).

X>0 AND X+Y>=3 => (X-(3-Y),3)

(X,Y) AND

PREC. X debe tener algo de agua y X+Y debe ser igual o mayor de 3 (si se
desborda no nos preocupa). X>0 AND X+Y>=3
EFECT. La jarra X queda con 3 litros menos lo que tenia previamente Y y Y
queda llena. (X-(3-Y),3)

El programa debera encontrar un pasaje de

estados para ir del estado (0,0) al estado
(2,0). Puede existir ms de un pasaje de
estados hacia la solucin, por ejemplo:
(0,0) => (0,3) => (3,0) => (3,3) => (4,2) => (0,2)
=> (2,0)

en la cual, a partir del estado inicial, se

aplicaron las reglas 2, 8, 2, 6, 3 y 8, hasta
conseguir el estado objetivo.

El programa debera encontrar un pasaje de

estados para ir del estado (0,0) al estado (2,0).
Puede existir ms de un pasaje de estados hacia
la solucin, por ejemplo:
(0,0) => (4,0) => (1,3) => (1,0) => (0,1) => (4,1) =>
(2,3) => (2,0)
en la cual se aplicaron las reglas 1, 5, 4, 7, 1, 5 y 4.

en la cual, a partir del estado inicial, se aplicaron

las reglas 2, 8, 2, 6, 3 y 8, hasta conseguir el
estado objetivo.

INTELIGENCIA ARTIFICIAL

1.

Presentacin basada en:

Inteligencia Artificial un enfoque moderno. Stuart Rusell & Peter
Norving.

Estrategias de Bsqueda Informada

Primero Mejor o Bsqueda avara
A*

Como proponer Heursticas

Caractersticas de la bsqueda informada:

Informacin para auxiliar el proceso de bsqueda
de grafos
Funcin de evaluacin que toma valores en cada
nodo del grafo
Ejemplos: Primero Mejor, A*, Escalada simple
(simple hill climbing), Escalada profunda
(steepest ascent hill climbing), Simulated
Annealing, Algoritmos genticos.

Funcin heurstica
Una heurstica es una funcin que asigna a cada
nodo un valor que corresponde al costo estimado
de llegar a la meta estando en dicho nodo
Se denota por h(n)

Funcin de evaluacin f(n), dado un nodo n

estima la distancia desde ese nodo n a un nodo
objetivo
Un nodo tendr ms calidad cuanto menor sea la
distancia al objetivo
Las bsquedas informadas expanden primero los
nodos que estn ms cerca del objetivo, aquellos
en los que la funcin f(n) asigna un menor valor
Hay distintas formas de definir la funcin de
evaluacin. Bsicamente, se pueden tener en
cuenta dos distancias:
La distancia desde el nodo inicial a n
La distancia desde n hasta un nodo objetivo

Puede tener dos componentes:

Coste del camino g(n): coste del mejor camino
conocido para ir desde el nodo inicial al nodo n
Funcin heurstica h(n): estimacin del camino de
menor coste desde el nodo n a un objetivo
Si n es un objetivo necesariamente h(n)=0
Jugando con g(n) y h(n) podemos definir distintas
funciones de evaluacin f(n):
f(n) = g(n) (Coste uniforme, bsq. no infor.)
f(n) = h(n) (Voraz primero el mejor)
f(n) = g(n)+h(n) (A*)

Avara: Expandir el nodo con menor h(n), esto

es, aquel que parece estar ms cerca de la
meta sin importar a qu profundidad est.
A*: Expandir el nodo con menor f(n), esto es,
aquel con el menor costo estimado para la
solucin f(n) = g(n) + h(n)

Un enfoque general de la bsqueda Informada:

Bsqueda de Primero el Mejor: El nodo es seleccionado
por expansin basado en una funcin de evaluacin
f(n).

Idea: La funcin de evaluacin mide la distancia

al objetivo
Seleccionar el nodo que parece el mejor

Implementacin:
Funciona como una cola de hilos, ordenados en orden
decreciente de conveniencia.

Se expandirn primero los estados con menor

valor de f(n)
Es un caso particular de los algoritmos
generales de bsqueda en rboles o grafos
El nombre primero el mejor es inexacto, si
realmente supiramos cul es el mejor, la
bsqueda sera directa
En realidad escogemos el estado que parece
el mejor
La funcin de evaluacin es un estimador

Las heursticas son criterios para decidir cul

entre varias acciones promete ser la mejor
para alcanzar una meta

Arqumedes (287 212 a.c)

Hiern - Monarca de Siracus

[Diccionario] regla bsica, simplificacin,

o suposicin que reduce o limita la
bsqueda de soluciones en los mbitos
que
son
difciles
y
pobremente
comprendidos
h(n) = costo estimado de la ruta de acceso
ms barata a partir del nodo n al nodo
objetivo.
Si n es el objetivo entonces h(n) = 0.

El tringulo mgico. Utilizando el operador

intercambio(a,b) que cambia de posicin los
nmeros a y b, colocarlos de tal forma que la
suma sobre cada lado sea 20.

Vacaciones en Bucharest
Actualmente en Arad
Formulacin del objetivo:
Estar en Bucharest

Formulacin del problema:

Estados: varias ciudades

Acciones: conducir entre ciudades

Buscar solucin:

Secuencia de ciudades, ej. Arad, Sibiu, Fagaras, Bucharest

Supongamos que queremos utilizar la

bsqueda avara para resolver el problema
de los viajes de Arad a Bucharest.
El estado inicial = Arad

El primer paso de expansin producido:

Sibiu, Timisoara and Zerind

El primero mejor avaro seleccionar a Sibiu

Arad
Sibiu

Arad
(366)

Fagaras
(176)

Oradea
(380)

Rimnicu Vilcea
(193)

Si Sibiu se expande se obtiene:

Arad, Fagaras, Oradea y Rimnicu Vilcea

La bsqueda avara primero mejor

seleccionar: Fagaras

S se expande Faragas, se obtiene:

Objetivo alcanzado!!

Sibiu y Bucarest

Sin embargo, no es ptimo (ver Arad, Sibiu, Rimnicu Vilcea, Pitesti)

Pero ac se trata de obtener una solucin aun que aparente ser la
mejor

Es un algoritmo de bsqueda preferente por lo

mejor (best-first) en el que se utiliza f como
funcin heurstica y una funcin h aceptable.
Es un algoritmo genrico de bsqueda.
Basa su comportamiento en una funcin de
evaluacin.

La forma ms conocida de la bsqueda

del primero mejor
Idea: Evita expandir caminos que son
altamente costosos
Funcin de evaluacin:
f(n)=g(n) + h(n)

g(n) es el costo (actual) para alcanzar el nodo

h(n) costo estimado para obtener el objetivo
desde el nodo actual
f(n) costo total estimado del camino a travs

de n hacia el objetivo

inicio

fin
f(n) = costo estimado de la solucin mas barata,
pasando por n.

Esta funcion viene de dos principios:

Lo ms corto es lo mas rpido (g).

Para asegurarnos que es la mejor opcin
hay que agregar subestimaciones (h).

Lista abierta: contiene los nodos que podran

formar parte del camino.
Lista cerrada: contiene los nodos que ya han
sido examinados y que no hace falta volver a
examinar.

hSLD= Distancia en lnea

recta heurstica.
hSLD= NO puede ser
calculada, desde la
descripcin del problema
en s.
En este ejemplo:
f(n) = h(n)
Expande el nodo ms
cercano al objetivo

Bsqueda avara del

primero mejor

Buscar Bucharest empezando en Arad

f(Arad) = c(??,Arad)+h(Arad)=0+366=366
g

Expandir Arad y determinar f(n) para cada nodo

f(Sibiu)=c(Arad,Sibiu)+h(Sibiu)=140+253=393
f(Timisoara)=c(Arad,Timisoara)+h(Timisoara)=118+329=447
f(Zerind)=c(Arad,Zerind)+h(Zerind)=75+374=449
La mejor seleccin es SIBIU

Expandir Sibiu y determinar f(n) para cada nodo

f(Arad)=c(Sibiu,Arad)+h(Arad)=280+366=646
f(Fagaras)=c(Sibiu,Fagaras)+h(Fagaras)=239+179=415
f(Oradea)=c(Sibiu,Oradea)+h(Oradea)=291+380=671
f(Rimnicu Vilcea)=c(Sibiu,Rimnicu Vilcea)+
h(Rimnicu Vilcea)=220+192=413

Mejor seleccin es Rimnicu Vilcea

Expandir Rimnicu Vilcea y determinar f(n)

para cada nodo

f(Craiova)=c(Rimnicu Vilcea,
Craiova)+h(Craiova)=360+160=526
f(Pitesti)=c(Rimnicu Vilcea, Pitesti)+h(Pitesti)=317+100=417
f(Sibiu)=c(Rimnicu Vilcea,Sibiu)+h(Sibiu)=300+253=553

Mejor seleccin es Fagaras

Expandir Fagaras y determinar f(n) para cada

nodo
f(Sibiu)=c(Fagaras, Sibiu)+h(Sibiu)=338+253=591
f(Bucharest)=c(Fagaras,Bucharest)+h(Bucharest)=450+0=450

Mejor seleccin es Pitesti !!!

Expandir Pitesti y determinar f(n) para cada nodo

f(Bucharest)=c(Pitesti,Bucharest)+h(Bucharest)=418+0=418

Mejor seleccin es Bucharest !!!

Solucin ptima (solo si h(n) es admisible)

Note los valores a lo largo del camino ptimo !!

En el diseo, se puede pasar desde una casilla a otra

de las posibles adyacentes (arriba, abajo, izquierda,
derecha), salvo si existe una barrera entre ellas (ver
color gris).

En el siguiente laberinto, se puede pasar desde una

casilla a otra de las posibles adyacentes (arriba,
abajo, izquierda, derecha), salvo si existe una barrera
entre ellas

Objetivo: ir de I a F

Como ejercicio final, resolveremos el problema aplicando

las bsquedas en profundidad, primero el mejor y A*

Estados: A, B, C, D, E, G, I, W, K, M, N, P, Q, R, T y F
Estado inicial: I
Estado final: F
Operadores: arriba, abajo, izquierda, derecha
Aplicabilidad y resultado de la aplicacin
Arriba es aplicable a un estado si existe una casilla arriba y no est
separada por barrera; el resultado de aplicarlo es la casilla de arriba y
su coste es 1
El resto de operadores, anlogamente
Consideraremos que los sucesores estn ordenados alfabticamente

Heurstica (admisible): distancia del estado a la

casilla F
Durante la bsqueda, y con igual valoracin, elegir
por orden alfabtico

Solucin encontrada: I-Q-R-T-K-M-F

No es ptima
Nodos analizados: 13

Solucin encontrada: I-Q-R-T-K-M-F

No es ptima
Nodos analizados: 7
La heurstica ha servido para reducir el espacio
de bsqueda

Solucin encontrada: I-W-K-M-F

ptima (heurstica admisible)
Nodos analizados: 8
Aunque en este caso se analizan ms nodos (se ha explorado
parcialmente un camino equivocado), la solucin ptima est
asegurada
Ntese que se generan dos nodos distintos con el mismo
estado K (pero distinto camino)

A es el nodo inicial y
Z el nico nodo meta.
Cada arco lleva asociado su
coste y en cada nodo
aparece la estimacin de la
menor distancia desde ese
nodo a la zeta.
Aplicar:
bsqueda por amplitud
Bsqueda por profundidad
Bsqueda por el primero
mejor