Bootcamp Inteligencia Artificial

Nivel Explorador

Master Class 2: Python Para Inteligencia Artificial

Principios de Inteligencia Artificial

Agenda
1. Racionalidad y Agentes
2. Algoritmos de búsqueda
3. Búsqueda Informada
1.1 ¿Qué es la Inteligencia Artificial?
1.2 Pensar como humano
• 1960 “Revolución cognitiva” comienza el estudio de la cognición. Estudio científico de la
mente y sus procesos
• Se centra en el estudio de la “inteligencia” centrándose en la forma como los sistemas
nerviosos representan, procesan y transforman
• Considera aspectos como el lenguaje, percepción, memoria, atención razonamiento y
emoción.
• Requiere teorías sobre el comportamiento del cerebro:

• Identificar un nivel de abstracción (Neuronas o circuitos)

• Intenta predecir y verificar el comportamiento humano (Top-down)
• Relaciona el comportamiento con información neurológica (Bootom-up)
1.3 Pensar como humano
• Los seres humanos son muy buenos tomando
decisiones racionales, pero no son perfectos.
• El cerebro no es tan modular como el software, por
lo tanto, hacer ingeniería inversa es difícil
• !Los cerebros son a la inteligencia lo que las alas a
volar!
• Qué hemos aprendido del cerebro: para tomar
buenas decisiones la memoria y la simulación (o
predicción) son factores clave
1.4 Actuar como humano

• Un intento por cuantificar la idea de “inteligencia”

• El juego de la imitación
• Sugiere los mayores componentes de IA: razonamiento, representación,
aprendizaje
• No es reproducible, subjetivo (no es posible analizarlo matemáticamente)
1.5 Agentes
Un agente es una entidad que percibe su
ambiente a través de sensores y actúa mediante
actuadores.
• ¿Los humanos son agentes?
• ¿Los animales son agentes?
• ¿Las plantas son agentes?
• ¿Un cajero automático es un agente?
• ¿Los autos autónomos son agentes?
1.6 Agentes
• La función del agente f asigna a cada percepción (o secuencia de percepciones) una
acción
f : P* → A
• Esta función representa el comportamiento del agente ante cambios en el estado del
ambiente
NEXT NEXT NEXT NEXT
Percept

Action LEFT LEFT DROP RIGHT

1.7 Agentes
El programa del agente l corre en una máquina M que implementa f
• f = Agent(l, M)
• Las máquinas tienen procesamiento y memoria limitados. Esto puede generar
retrasos en la ejecución de las acciones. En consecuencia, f depende de l y de
M.

NEXT NEXT NEXT NEXT

Percept

Action NOOP NOOP NOOP LEFT

1.8 Agentes
• El universo de una aspiradora
A B

• Percepciones: [location, status], e.g., [A,Dirty]

• Acciones: Left, Right, Suck, NoOp
1.9 Agentes
Función del agente Programa

Percept sequence Action function Reflex-Vacuum-Agent([location,status])

returns an action
[A,Clean] Right if status = Dirty then return Suck
[A,Dirty] Suck else if location = A then return Right
else if location = B then return Left
[B,Clean] Left
[B,Dirty] Suck
Podemos preguntarnos:
[A,Clean],[B,Clean] Left
• ¿Cuál es la función correcta para el agente?
[A,Clean],[B,Dirty] Suck • ¿Puede ser implementada por un programa simple?
Etc. Etc. • ¿Cuál es el tipo de programa?

¿Esta función tiene algún problema?

1.10 Agentes Racionalidad
• Comportamiento racional: hacer lo correcto
• Hacer lo correcto: aquello que maximiza mis objetivos (o beneficio) a partir de la
información disponible
• El comportamiento de un agente se evalúa a partir del resultado de sus acciones
• No necesariamente implica procesos de pensamiento complejo
• Las limitaciones de recursos computacionales hacen la idea de racionalidad
perfecta un propósito inviable

“Diseñar el mejor programa, según los recursos y la información

disponible”
 A B

1.11 Agentes Racionalidad

Función del agente
Percept sequence Action
function Reflex-Vacuum-Agent([location,status])
[A,Clean] Right
returns an action
[A,Dirty] Suck
if status = Dirty then return Suck
[B,Clean] Left
else if location = A then return Right
[B,Dirty] Suck
else if location = B then return Left
[A,Clean],[B,Clean] Left
[A,Clean],[B,Dirty] Suck
Etc. Etc.

¿Podemos decir que nuestro programa para la aspiradora es racional?

 A B

1.12 Agentes Racionalidad

• Debemos definir una métrica de desempeño para nuestra aspiradora
• Un punto por cada cuadro limpiado en el tiempo T
• Un punto por cada cuadrado limpio en el tiempo T, menos uno por cada movimiento
• Penalizar, por tener más de k cuadrados sucios
• Un agente racional selecciona las acciones que maximizan el valor esperado de la
medida de desempeño basado en la secuencia de percepciones hasta el momento
• La métrica de desempeño debe ser definida en términos de los estados del
ambiente y no del agente
 A B

1.13 Agentes Racionalidad

• La racionalidad en cualquier instante de tiempo depende de cuatro factores:

• La métrica de desempeño que define el criterio de éxito

• El conocimiento previo del agente sobre el ambiente
• Las acciones que el agente puede realizar
• La secuencia de percepciones percibidas por el agente hasta el momento
 A B

1.14 Agentes Racionalidad

A partir de esto podemos construir la siguiente definición de agente racional:

Para cada posible secuencia de percepciones, un agente racional debe

seleccionar la acción que permite maximizar el valor esperado de sus
medias de desempeño, dada la información que proporciona la secuencia de
percepciones y el conocimiento incorporado previamente en el agente
1.15 Agentes Racionalidad
• Vale la pena hace algunas aclaraciones sobre la idea de racionalidad

• Racional ≠ Omnisciente
• Racional ≠ Clarividente
• Racional ≠ Exitoso
• Racional → Explorar, aprender, autonomía
• ¿un agente cometen errores?
1.16 Ambientes
Para diseñar un agente racional debemos especificar el “Problema” para el cual
el agente será la solución.

Performance: ?
Environment: ?
Actuators: ?
Sensors: ?

Jugador humano
1.18 Ambientes
Consideremos un taxi autónomo:

Performance: ?
Environment: ?
Actuators: ?
Sensors: ?
1.19 Ambientes
Consideremos un sistema de diagnóstico automático:

Performance: ?
Environment: ?
Actuators: ?
Sensors: ?
1.20 Ambientes
Consideremos un bot de compras:

Performance: ?
Environment: ?
Actuators: ?
Sensors: ?
1.21 Tipos de Ambientes
Pacman Taxi Diagnóstico Bot Parqués

Observable o parcialmente
observable
Determinístico o estocástico

Estático o dinámico
Discreto o continuo

Episódico o secuencial
Multi-agente

Métrica de desempeño conocida

1.22 Tipos de Agentes
Inicialmente podemos clasificar los agentes en cuatro tipos:
• Agente reflejo
• Agente reflejo con memoria
• Agente basado en objetivos
• Agente basado en utilidad

¡Todos ellos pueden ser transformados en agentes de aprendizaje!

1.23 Agentes Reflejo

Agent Sensors

What the world

is like now

Environment
Condition-action rules What action I
should do now

Actuators
1.24 Agentes Reflejo con estado

Sensors
State
How the world evolves What the world
is like now

Environment
What my actions do

What action I
Condition-action rules
should do now

Agent Actuators
1.25 Agentes basados en Objetivos
Sensors

State
What the world
How the world evolves is like now

Environment
What it will be like
What my actions do if I do action A

What action I
Goals should do now

Agent Actuators
1.26 Agentes basados en Utilidad
Sensors
State
What the world
How the world evolves is like now

Environment
What it will be like
What my actions do if I do action A

Utility How happy I will be

in such a state

What action I
should do now

Agent Actuators
1.26 Agentes de aprendizaje
2.1 Problemas de Búsqueda
Buscar la Ejecutar la
Formular el
Entradas problema
secuencia de secuencia de Salidas
acciones acciones
2.2 Problemas de Búsqueda
Podemos especificar formalmente un problema de búsqueda definiendo los siguientes
aspectos:

• Espacio de estados: conjunto de estados alcanzables desde el estado inicial a partir de una
secuencia de acciones
• Un estado inicial: so es el estado donde inicia el agente.
• Acciones por estado: A(s), dado un estado s se debe conocer que acciones podría realizar el
agente en el dicho estado.
• Modelo de transición: result s, a , especifica cuál es el estado resultante de aplicar la acción a
en un estado s
• Función de evaluación: Goal(s), determina si el estado actual es el estado objetivo
• Función de costo: c s, a, s′ , función que asigna a cada acción un valor numérico
2.3 Problemas de Búsqueda • Estados
• S=
{Ciudades en el mapa}
• Estado inicial
• so = Arad
• Acciones:
• Moverme a las ciudades
adyacentes
• Modelo de transición
• Alcanzar una ciudad
adyacente
• Función de evaluación:
• s = Bucharest?
• Función de costo
• Distancia entre s y s′
• ¿Solución?
2.4 Problemas de Búsqueda
A B • Estados
• Combinan la posición del agente
y la posición de la suciedad
• Estado inicial
• so = ?
• Acciones:
• Derecha, Izquierda, Aspirar
• Modelo de transición
• Ver imagen
• Función de evaluación:
• s =¿Todos los cuadros están
limpios?
• Función de costo
• 1 por cada movimiento
Espacio de estados
• ¿Solución?
2.5 Representación de estados
• Grafo del espacio de estados: representación
matemática de un problema de búsqueda a G
• Nodos: representaciones (abstractas) de la b c
configuración del mundo e
• Arcos: representan transiciones asociadas a las d f
acciones S h
• Cada estado ocurre una sola vez p r
q
• Generalmente es imposible representarlo en memoria
(demasiado grande), sin embargo, es una idea útil
2.6 Representación de estados
E E E
S S

N N
N
E E
W
S
N N N

E N S
W

N E
E
E E

W W
2.7 Representación de estados
Grafo del Árbol de búsqueda
espacio de estados Cada nodo en el
S
árbol representa una
a G ruta desde so e p
d
b c
b c e h r q
e El árbol se genera
d f a a h r p q f
S h cuándo sea
p r necesario, y se p q f q c G
q construye tan q c G a
pequeño como sea
posible a
2.8 Arboles de búsqueda
Nodos
De forma sistemática podemos ver el proceso
de la siguiente forma: Frontera

• Los nodos frontera separan los nodos

inexplorados de los nodos expandidos Inexplorado Expandidos
• Expandir un nodo:
• Lo mueve del conjunto de frontera a los
expandidos
• Agrega nodos inexplorados a los nodos
frontera 𝐴𝑙𝑐𝑎𝑛𝑧𝑎𝑏𝑙𝑒𝑠 = {𝐸𝑥𝑝𝑎𝑛𝑑𝑖𝑑𝑜𝑠 ∪ 𝑓𝑟𝑜𝑛𝑡𝑒𝑟𝑎}
 Arad

2.9 Arboles de búsqueda Sibiu Timisoara Zerind

Arad Fagaras Oradea Rimnicu VilceaArad Arad Lugoj Arad Oradea

Sibiu Timisoara Zerind

Arad
Arad

Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea

Sibiu Timisoara Zerind Sibiu Timisoara Zerind

Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea Arad Fagaras Oradea Rimnicu VilceaArad Arad Lugoj Arad Oradea

Sibiu Timisoara Zerind

Arad Arad

Sibiu Timisoara Zerind Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea
Sibiu Timisoara Zerind

Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea

Arad Fagaras Oradea Rimnicu VilceaArad Arad Lugoj Arad Oradea

Arad Sibiu Timisoara Zerind

Sibiu Timisoara Zerind

Arad Fagaras Oradea Rimnicu Vilcea Arad Lugoj Arad Oradea
2.10 Búsqueda en grafos

• ¿Cuál criterio utilizamos para seleccionar un nodo de la frontera?

• ¿Cuáles estructuras de datos podemos utilizar para modelar este proceso?
2.11 BFS (Búsqueda en Amplitud)
Estrategia: expandir el nodo
menos profundo primero
S
Implementación: la frontera se
representa mediante una cola d e p
(FIFO) Niveles
b c e h r q
búsqueda

a G a a p q f
b c
c G
e
d f
S a
h
p q r

Nota: para este ejemplo los empates se resolverán según el orden alfabético
2.12 BFS (Búsqueda en Amplitud)
• ¿Qué nodos expande BFS?

• Procesa todos los nodos por encima de la solución más

superficial 1 nodo
• Supongamos que la solución menos profunda está en el nivel s b
… b nodos
• Si m es finito, expandirá O(bs) nodos Nivel s
b2 nodos
• ¿Cuánta memoria se necesita para almacenar la frontera?
• Aproximadamente necesitará almacenar la cantidad de nodos
del último del nivel explorado. Por lo tanto, O(bs)

• BFS es completo?
• s debe ser finito para que la solución exista. Luego, es una
estrategia completa

• BFS es óptimo?
• Si todos los costos son iguales (e.g. 1)
2.13 Búsqueda en profundidad
Estrategia: expandir el nodo
más profundo primero
S
Implementación: la frontera se
representa mediante una Pila d e p
(LIFO)
b c e

a G a a h r
b c
e p q f
d f
S h q c G
p q r

Nota: para este ejemplo los empates se resolverán según el orden alfabético
2.14 Búsqueda en profundidad
• ¿Qué nodo expande DFS?

• Proceso todos los nodos a la izquierda de la solución hasta el nivel m

• ¡Podría procesar todo el árbol! 1 nodo
• Si m es finito, expandirá O(bm ) nodos b
… b nodos
• ¿Cuánta memoria se necesita para almacenar la frontera? b2 nodos
Nivel m
• Solo almacenará los nodos vecinos en el camino a la raíz. Por lo
tanto, O(bm)

• DFS es completo?
• m podría ser infinito.
• Prevenir ciclos podría ayudar bm nodos

• DFS es óptimo?
• No. Encuentra la solución más a la izquierda sin contemplar
profundidad o costo.
2.15 Búsqueda de Costo Uniforme
g(n) = costo de la raíz a n S 0

Estrategia: expandir el nodo con el d 3 e 9 p 1

menor valor de g(n)
b 4 c 11 e 5 q 16
La frontera es una cola de
prioridad ordenada según g(n) Contorno a 6 h 13 r 7
del costo
f 8

2 a 3 G 11 c G 10
b c 3
1 8 2
2 e
3 d f
9 2
S h 8 1
1 p q r
Nota: para este ejemplo los empates se resolverán según el orden alfabético
15
2.16 Búsqueda de Costo Uniforme
• ¿Qué nodo expande UCS?
• Procesa todos los nodos con un costo menor a la solución
óptima
• Si la solución óptima cuesta C ∗ y suponemos que cada b
g1
acción cuesta mínimo  …
• Si m es finito, expandirá O(bC*/ ) nodos g2
C*/ “Niveles”
g3
• ¿Cuánta memoria se necesita para almacenar la
frontera?
• Almacenará al menos O(bC*/ )
• UCS es completo?
• Sí, asumiendo que  > 0

• UCS es óptimo?
• Sí. (se demostrará más adelante a través de A*)
2.17 Búsqueda. Comparación
Una comparación en términos de eficiencia para los tres algoritmos
 3.1 Búsqueda Informada
• Las estrategias de búsqueda no informada dependen
únicamente del estado inicial, estado objetivo y las
acciones.
• No utilizan ningún tipo de información sobre la
naturaleza del problema que haga la búsqueda más
eficiente
• Si tenemos información sobre en qué dirección
buscar, podemos incluirla como parte de nuestra
estrategia de búsqueda
3.2 Heurística
• Las heurísticas son criterios, métodos o principios para decidir cuál, de entre varias
acciones, promete ser la mejor para alcanzar un objetivo
• El uso de heurísticas nos permite guiar nuestra búsqueda, permitiéndonos obtener una
solución más rápidamente
• Las heurísticas están relacionadas con la naturaleza del problema (Basadas en la
experiencia). Son funciones ad hoc diseñadas para un problema
3.3 Heurística
• Formalmente podemos definir una heurística como una función h ∶ S → ℝ+ que
asigna a cada estado s ∈ S un estimado de la distancia entre s y el estado objetivo.
• Mientras más pequeño el valor de h s , más cercano estará s del estado objetivo. Si s
es el estado objetivo, entonces h s = 0
3.4 Búsqueda Voraz
Heurística: la distancia representada por una línea recta desde una ciudad hasta
Bucharest
h(x)
3.5 Búsqueda Voraz
Expandimos el nodo que siempre parece estar más cerca
3.6 Algoritmo A*
• Expandir el nodo n con más probabilidad de estar en la ruta óptima
• Expandir el nodo n con el menor costo f n = g n + h(n) donde:
• g n es el costo real desde la raíz hasta n
• h(n) es costo estimado desde n hasta la solución más cercana
• A* = utiliza una cola de prioridad ordenada por f n = g n + h(n)

g
h
3.7 Algoritmo A*
Encuentre la solución para el siguiente problema de búsqueda utilizando UCS, búsqueda
voraz y A*
8

e h=1
1
1 3 2
S a d G
h=6 1 h=5
h=2 h=0
1
c b
h=7 h=6
 3.8 Algoritmo A*
Costo uniforme: expande nodos de acuerdo a g(n)
Búsqueda voraz: expande nodos de acuerdo a h n
Algoritmo A*: expande nodos de acuerdo f n = g n + h(n)
8 S g=0
h=6
e h=1 g=1
a
1 h=5
1 3 2 g=2 b g=9
S a d G d g=4 e
h=6 h=5 h=6 h=2 h=1
1 h=2 h=0
1 g=3
c b c G g=6 d g=
h=7 h=0 10
h=7 h=6
h=2
g=
G
12
h=0
3.9 Algoritmo A*
• Combina UCS y búsqueda Voraz
• La búsqueda por costo uniforme solo tiene en
cuenta el costo desde la raíz al nodo actual
para expandir un nodo: g(n)
• La búsqueda voraz solo considera el costo
estimado del nodo actual al nodo objetivo para
expandir un nodo: h(n)
• El algoritmo A* utiliza la suma de ambos
f n = g n + h(n)
Algoritmo A*
3.10 Resumen

Búsqueda Voraz
Preguntas