Actividad de Programación 3: Algoritmo ID3

Medio Ambiente:
Nuestro medio ambiente será como un tipo calabozo con forma de laberinto (el cuál será dinámico), constará de una entrada y una salida Y tres tipos de agentes principales: buscador, guardián y espía. El agente buscador se encargará de buscar un objeto y huir hacia la salida, evitando lo más que pueda al agente guardián. El agente guardián se encargará de hacer rondas en el calabozo en diferentes zonas (mientras las va conociendo y aprendiendo) y en cuanto encuentre al agente buscador, seguirlo para capturarlo. El agente espía se encargará de ayudar al agente buscador para encontrar el objeto verdadero, indicándole dónde hay atajos e interfiriendo en las comunicaciones de los agentes guardianes (solo en el caso que exista más de un agente guardián). Puede que existan más buscadores y de ésta forma los agentes guardianes se confundirán.

En caso de que solo existiera una entrada, se tendría que conseguir el objeto único que podrá convertir la entrada en la salida, para esto, nuestro agente tendría que recordar el camino por el que vino, siempre tratando de evitar al agente guardia.

Existirán agentes guardias, los cuales estarán recorriendo todo el calabozo para conocer el terreno y estar haciendo guardia en algunas de las zonas del mismo. Dentro del calabozo existen diversos objetos, de los cuales hay uno que es el que le abrirá la puerta a la salida, pero hay objetos falsos, copias, que tratarán de confundir al agente buscador.

Actividad que aprende:
En este caso el agente aprenderá a moverse dentro del medio ambiente intentando no ser atrapado por los centinelas. Utilizando el algoritmo de ID3 este aprende en qué dirección moverse de acuerdo a la retroalimentación obtenida.



Patrones:
Los patrones de entrenamiento en este caso, se generan por 30 segundos a partir de que el programa corre. Los patrones cuentan con los siguientes datos:
a) [0, 1] Un valor booleano de si hay o no centinelas en su rango de visión.
b) [1 ,2, 3, 4] El valor de la dirección tomada para el movimiento.
c) [0, 1] Un valor booleano que determina si encontró un callejón sin salida o no en su camino.
d) [0, 1] Una evaluación de si la acción fue buena o mala.
Se escogieron estos valores ya que son los más importantes en este ambiente para poder moverse en el medio y cumplir la meta que se quiere aprender. Además de que son valores fáciles de evaluar para la utilización del algoritmo.

Los patrones se irán almacenando en un arreglo bidimensional.

Solución ID3:
i) Algoritmo utilizado:
a. ID3: Ya que fue interesante la implementación de este en el medio ambiente y porque es sencillo de comprender.
ii)
a. Aprendizaje: El número de patrones realmente no está definido ya que está delimitado por tiempo, en este caso se generan patrones, cada que el agente se mueve y que se repinta la pantalla durante 30 segundos. Terminando el lapso de 30 segundos el movimiento se determina de acuerdo al algoritmo.
b. Validación: En este caso no se utilizan patrones de validación ya que nosotros no tenemos control sobre el movimiento del agente, simplemente al ser movimientos aleatorios, el programa utiliza el árbol generado con los patrones de entrenamiento para ir evaluando paso por paso el movimiento del agente, en el caso de tener una retroalimentación buena sigue el camino, en caso de tener una retroalimentación mala, se mueve en dirección contraria.
c. Ejemplos:
iii) Este programa si funciona en tiempo real, ya que por eso se está corriendo por tiempo, durante un tiempo se entrena y todo lo que resta del tiempo está generando movimientos a partir de lo que aprendió con ID3 cada paso o movimiento que hace.
iv) No cuenta con overfitting ya que el movimiento del agente es aleatorio, entonces puede darse el caso de que muchos casos no estén considerados dentro del lapso de tiempo que se asignó para generar patrones de entrenamiento.
v) Mejorar el funcionamiento podría ser agregando más valores a los patrones de entrenamiento ya que en la forma que está ahorita sería una forma simple, pero en un ambiente más complicado podría llegar a no funcionar bien con tan pocos valores o patrones. También se podría aumentar el tiempo que genera patrones de entrenamiento.

Conclusiones:
Esta actividad nos ayudo a comprender mejor la forma en que se lleva a cabo la relación entre el árbol de decisiones generado por ID3 y el medio ambiente, llegando así a un aprendizaje. A la vez pudimos ver que no es un algoritmo muy complejo de programar, sino su dificultad está en adaptarse a un medio diferente por todas las variables que hay que tomar en cuenta, a la vez de que se deben decidir los patrones.
Probablemente la parte de la decisión de que valores utilizar para los patrones fue el más difícil ya que de esto dependía el funcionamiento completo del algoritmo.

Gato 3D con LMS

Gato 3D

Descripción del medio ambiente.

Hay tres tableros de gato formando un cubo. Cada panel vertical y horizontal es un gato de modo que hay más formas de ganar. Existen 27 espacios donde se puede tirar. El ambiente es accesible, no determinista, no episódico, estático y discreto.

Actividades que aprende el agente.

El objetivo del agente ganar a su oponente. El agente es autónomo y reacciona según los tiros del otro jugador, va aprendiendo a jugar hasta ser capaz de ganar.

El agente aprenderá a bloquear tiros y a tirar de manera que tenga oportunidad de ganar.

1. Bloquear tiros. A partir de la estrategia del usuario el agente aprenderá que posición del tablero utilizar para su siguiente jugada para así impedir que el otro jugador gane.

2. Tirar. De acuerdo al desempeño del jugador el agente elige la mejor jugada posible.

Solución utilizando el Algoritmo LMS

· Experiencia de aprendizaje

El agente juega contra un agente reactivo. La retroalimentación es indirecta ya que depende del resultado final de la partida. La selección de estados la hace el agente y al final se infiere el resultado a través del medio ambiente. La distribución de ejemplos es muy similar a los reales.

· Función objetivo

Tirar: Tablero →ℜ

V: T→ℜ

V (b) = 10 cuando ganó

V (b) = -10 cuando perdió

V (b) = V (mejor estado alcanzable)

· Representación de la función objetivo

X1 = número de espacios peligrosos (si el oponente tira ahí gana)

X2 = número de espacios beneficiosos (si el agente tira ahí junta 2 en línea y tiene posibilidades de ganar)

X3 = número de espacios ganadores (si el agente tira ahí gana)

V (b) = w0 + w1x1 + w2x2 + w3x3

W0, W1, W2, W3 son pesos a aprender.

· Selección del algoritmo de aproximación

Se usará LMS.

Los valores iniciales de pesos W0, W1, W2, W3 son elegidos al azar y van de 0 a 1 y la constante de aprendizaje η fue elegida al azar entre 0.4 y 0.9.

Los patrones utilizados para el aprendizaje son la representación de los espacios que existen en el tablero. Los primeros nueve representan la cara superior del cubo, los siguientes nueve el gato horizontal en la mitad del cubo y los últimos nueve el gato en la cara inferior.

Conclusiones después de la programación

Implementar LMS tuvo ciertas complicaciones ya que hay que ser cuidadosos en las variables que obtienen información del sistema, de hacer falta una o de no calcularlas correctamente, puede llegar a no aprender correctamente. También, es necesario hacer que el programa sea entrenado contra muchos y diferentes escenarios para que sepa qué hacer bajo diferentes situaciones

BogoTron

Aprendizaje Automático

Grupo 1

Alejandro Morales A01161376

Jonathan Valle A01161110

Rafael Santos A01161734

24 de febrero de 2010

Equipo 1: ./42

Actividad 2

Ambiente: BogoTron.

Breve descripción del medio ambiente

Tron es un juego de video basado en la película "Tron" (1982) muy parecido al juego "Snake". En Tron, se tiene un mapa y dos jugadores. Mientras los jugadores se mueven en el mapa, van dejando "estelas" que se convierten en paredes por lo que un jugador no puede volver a pasar por ningún lugar que cualquiera de los dos haya pasado con anterioridad. Conforme avanza el juego, el espacio de movilidad se reduce hasta que inevitablemente algún jugador choca con una pared.

El juego termina cuando uno o ambos jugadores chocan con alguna pared o los jugadores colisionan entre sí.

Para nuestro caso el ambiente es un mapa que puede variar de tamaño, las motos son representadas por un 1 (el otro jugador) y un 2 (nuestro bot), y las paredes y rastros de los jugadores se representan por un #.

Acción que va a aprender el agente

El agente debe aprender a jugar Tron y a generar estrategias que le permitan vencer a su oponente o que le permitan vivir por el mayor número de turnos posibles, por ejemplo, si hay dos caminos, debe aprender a elegir el que le dé un mayor espacio de movilidad para tener una mejor probabilidad de vivir.

Solución planteada al problema utilizando LMS

Selección de la experiencia de aprendizaje
La experiencia de aprendizaje que tenemos es que nuesto bot jugará contra los bots que vienen de ejemplo en el starter pack más un bot similar a él denominado dummy, también se le pondrá a jugar en los diversos mapas que vienen por default con el paquete, de esta forma recuperará datos valiosos de la forma de jugar de los diversos bots y de los diferentes mapas. Desafortunadamente no tenemos mas bots enemigos par ponerlo a jugar contra ellos y obtener una mucho mejor retroalimentación, ya que, dicho sea de paso, los bots de ejemplo son bastante tontos.

Selección de la función objetivo
Debido a que también se juega sobre un tablero, la fución objetivo es muy similar a las vistas en clase:
V: B -> R
en donde:
B es el estado del tablero
R los reales

V(b) se define como:
Si b es un estado final y nuestro bot ha ganado (Player Two Wins!): V(b) = 100
Si b es un estado final y nuestro bot ha perdido (Player One Wins!): V(b) = -100
Si b es un estado final y existe algún empate(Players collided. Draw! o Both players crashed. Draw!): V(b) = 0

Selección de la representación de la función objetivo
La retroalimentación que tenemos es indirecta, pues solo es posible determinar si se ha ganado o perdido hasta el final del juego.
Para representar la función objetivo se utilizará una representación polinomial.

evaluation=w0+w1*variables[1]+w2*variables[2]+w3*variables[3]+w4*variables[4]+w5*
variables[5]+w6*variables[6]+w7*variables[7]+w8*variables[8]

Donde wi son los pesos que se tiene asignados y en el arreglos variables se encuentran las variables que se mencionaran en el siguiente punto.

Selección del algoritmo de aproximación – LMS para este caso.

Selección de valores iniciales para los pesos y constante de aprendizaje:

Los valores iniciales para todas las variables fue de 0.5
La constante de aprendizaje propuesta es de 0.06, pues se considera qeu es un equilibrio

Para resolver este problema decidimos utilizar 8 variables, las cuales son las siguientes:

*x1. Es la distancia o que tan lejos se ecuentra el enemigo en mi dirección
*x2. Numero de espacios libres que hay enfrente de donde me estoy dirigiendo
*x3. Numero de espacios libres que hay a los lados del último espacio revisado
*x4. Si el otro jugador esta directamente enfrente de mi
*x5. El enemigo se encuentra en la diagonal izquierda de mi posición
*x6. El enemigo se ecnuentra en la diagonal derecha de mi posición
*x7. El otro jugador se encuentra dos espacios enfrente de mi
*x8. Número de posibles movimientos que puedo hacer sin morir desde mi siguiente movimiento


Describir los patrones utilizados para el aprendizaje (3 ejemplos):

Los patrones utilizados no son muy representativos si es que los escribirmos, aquí. Solo se pegará una parte.

Ejemplo 1:
Este es el ejemplo de un mapa en el cual los dos inician en el centro.
TrainingData([0,5,10,0,0,0,0,15], , TrainingData([0,5,10,0,0,0,0,15], , TrainingData([0,5,10,0,0,0,0,15], , TrainingData([1,5,9,0,0,0,0,15], , TrainingData([0,5,10,0,0,0,0,15], , TrainingData([0,5,10,0,0,0,0,15],
Cada uno de los valores representa el valor que regresan las x explicadas en el paso anterior, como podemos ver, la última x representada por la cantidad de movimientos posibles se mantiene en 15 porque el mapa está prácticamente vacio,
TrainingData([0,5,7,0,0,0,0,10], , TrainingData([0,5,10,0,0,0,0,9], ,
Los datos anteriores corresponden a los últimos estados, y podemos observar que la cantidad de movimientos posibles se ve reducido y que los espacios libres al lado mio han disminuido.

Conclusiones

Durante la programación de Bogotron nos podemos dar cuenta como funciona el LMS, pues efectivamente hay un cambio entre la primera vez que se corre y las posteriores. Algo muy importante e interesante es notar como se comporta el bot una vez que se le coloca en un mapa completamente nuevo, pues cuando hacemos esto tiende a cometer muchas tonterias, pues efectivamente, al estar en una situación completamente nueva no tiene ni idea de que hacer.

Video:

Actividad de Programación 2: Algoritmo LMS

Medio Ambiente:

Nuestro medio ambiente será como un tipo calabozo con forma de laberinto (el cuál será dinámico), constará de una entrada y una salida Y tres tipos de agentes principales: buscador, guardián y espía. El agente buscador se encargará de buscar un objeto y huir hacia la salida, evitando lo más que pueda al agente guardián. El agente guardián se encargará de hacer rondas en el calabozo en diferentes zonas (mientras las va conociendo y aprendiendo) y en cuanto encuentre al agente buscador, seguirlo para capturarlo. El agente espía se encargará de ayudar al agente buscador para encontrar el objeto verdadero, indicándole dónde hay atajos e interfiriendo en las comunicaciones de los agentes guardianes (solo en el caso que exista más de un agente guardián). Puede que existan más buscadores y de ésta forma los agentes guardianes se confundirán.

En caso de que solo existiera una entrada, se tendría que conseguir el objeto único que podrá convertir la entrada en la salida, para esto, nuestro agente tendría que recordar el camino por el que vino, siempre tratando de evitar al agente guardia.

Existirán agentes guardias, los cuales estarán recorriendo todo el calabozo para conocer el terreno y estar haciendo guardia en algunas de las zonas del mismo. Dentro del calabozo existen diversos objetos, de los cuales hay uno que es el que le abrirá la puerta a la salida, pero hay objetos falsos, copias, que tratarán de confundir al agente buscador.

Actividad que aprende:

El agente buscador (Agente verde) aprende a sobrevivir por lapsos de tiempo establecidos sin ser capturado por los guardias (Agentes rojos). Después de hacer la evaluación con el algoritmo LMS el agente debe ir aprendiendo a cambiar la dirección en la que se mueve, si hay algún guardia cerca en la dirección que se está moviendo, de esta forma evitará ser atrapado por intervalos de tiempo cada vez más grandes. Cada que el agente es capturado este regresa a su punto de origen para empezar de nuevo su camino.

Solución con LMS:

i) Experiencia de aprendizaje:

a. Tarea: No ser atrapado por los guardias.

b. Evaluación: Tiempo sin ser atrapado.

c. Experiencia de aprendizaje:

i. La selección de estados es creada por el agente y el ambiente le da la solución de acuerdo a los diferentes estados.

ii. La distribución de ejemplos en este caso será dada siempre en el mismo programa por lo que se podría considerar una prueba contra si mismo ya que al ser puesto en otro ambiente puede afectar su comportamiento.

ii) Función objetivo

a. V:L -> [1,2,3,4]

En este caso L define el laberinto y un arreglo, en donde se describen las cuatro posibles direcciones en las que se puede mover el agente. [arriba, abajo, derecha, izquierda ].

V (b) = 100 si el agente logró sobrevivir sin ser atrapado.

V (b) = -100 si el agente fue atrapado por un guardia dentro del intervalo de tiempo establecido.

Si b no es un estado final entonces V(b) = V(b’) donde b’ se calcula con el sucesor por medio del algoritmo.

iii) Representación

x₁: Número de guardianes.

x₂: Intervalos de tiempo pasados sin ser capturado.

x₃: Numero de veces capturado en el intervalo.

V(b) = w₁x₁+w₂x₂+w₃x₃

iv) Algoritmo LMS

a. Valores iniciales de los pesos:

i. Para cada w inicial se toma un valor de 0.1 ya que al principio el agente no sabe qué tan importante es cada valor en el arreglo.

b. Valores iniciales de las constantes de aprendizaje

c. Patrones

i. Se utiliza un arreglo de con las variables establecidas en la representación donde los 2 elementos mas importantes son el segundo y tercero, de tal forma que:

[(3,0,1),-100] -> Este patrón representa que el agente fue capturado una vez, por alguno de los 3 guardias, antes de haber sobrevivido un solo intervalo de tiempo.

[(3,2,0), 100] -> Este patrón representa que el agente ha sobrevivido por lo menos 2 intervalos de tiempo sin ser capturado, o en su defecto fue capturado, pero logró sobrevivir sin ser capturado más veces, el contador de las capturas se reinicia una vez que se ha evaluado la función de esta forma, se puede reiniciar la cuenta de las capturas. Para evaluar si el agente, no ha sido capturado en cierto tiempo, al finalizar la evaluación puede ser que si haya sido capturado, pero que también haya sobrevivido intervalos de tiempo sin ser capturado, por lo que si el número de veces que sobrevivió es mayor al de capturas, se evalúa con 100.

[(3,3,5), -100] -> En este patrón se observa el caso de que el agente si llego a sobrevivir intervalos de tiempo algunas veces, pero a final de cuentas fue capturado más veces de las que sobrevivió por lo que se evalúa de una forma negativa.

Conclusiones:

Esta actividad nos permitió observar el comportamiento de un agente utilizando el algoritmo de LMS, de tal forma que en un ambiente el cual es refrescado cada cierto tiempo se puede observar mejoras en el comportamiento, ya que aprende conforme al tiempo y las evaluaciones que se hacen. Partiendo del mismo inicio, después de varias iteraciones el agente debe comportarse de una manera más “inteligente” aprendiendo a mantenerse lejos de sus enemigos.

El algoritmo LMS puede ser de gran utilidad para casos en los que se tiene una retroalimentación inmediata ya que al estar evaluando la función de aprendizaje puede tomar decisiones en los momentos adecuados.

Video: