Actividad Programación 2 Algoritmo LMS

Nuestro medio ambiente es Planet Wars, un juego basado en Galcon. El juego tiene lugar en el espacio exterior en un mapa que contiene varios planetas, cada uno con un escuadrón de naves. Los planetas pueden pertenecer a uno de tres propietarios diferentes: al jugador 1, al enemigo o neutral. El juego tiene un cierto número máximo de vueltas, de tal manera que al final del juego el jugador con la mayor cantidad de naves gana. El juego puede terminar antes si uno de los jugadores pierde todas sus naves, en cuyo caso el jugador restante gana al instante. Si ambos jugadores tiene el mismo número de naves cuando el juego termina, es un empate.

Debido al contexto en el cual se desarrollara (el juego planet wars); el agente aprenderá a derrotar a su oponente (el jugador rojo) de una forma cada vez más eficiente; ya sea por medio de la conquista de planetas (neutrales o enemigos) o por la eliminación sistemática de las tropas enemigas y la capacidad de producción de las mismas (i.e. atacando aquellos planetas enemigos que producen más tropas en menos tiempo). El algoritmo usado fue lms.

Conclusiones

Se invirtió una gran cantidad de tiempo a la definición de las x y los pesos iniciales de la función; esto consumió una gran cantidad de tiempo ya que no es un cambio inmediato. También influyo el hecho de que cambiamos de ambiente, pasando de tron a planet wars; aunque este cambio nos beneficiara a futuro, si nos afectó al corto plazo. Por último, se nos dificulto la implementación de la representación de las x de la función objetivo y los pesos debido al sistema de turnos que emplea el juego.

La función elegida para el algoritmo fue la siguiente:

Z =w0+ w1X1 + w2X2 + w3X3 + w4X4 + w5X5 + w6X6 + w7X7 + w8X8 + w9X9 + w10X10 + w11X11 + w12X12 + w13X13

El significado de las variables de la función objetivo se ´presenta a continuación:

X1 = número de planetas del agente con un índice de crecimiento de 0 o 1

X2 = número de planetas del agente con un índice de crecimiento de 2 o 3

X3 = número de planetas del agente con un índice de crecimiento de 4 o 5

X4 = número de planetas bajo control enemigo

X5= número de flotas del agente en vuelo

X6 = número de flotas enemigas en vuelo

X7 = número total de naves del agente

X8 = número total de naves del enemigo

X9 = número de naves en planeta origen

X10 = tasa de crecimiento de planeta origen

X11 = turnos para llegar al destino

X12 = naves en el destino

X13 = tasa de crecimiento del destino

Actividad Programación 2 Algoritmo LMS

1-Descripción del medio ambiente

El medio ambiente hasta este momento cuenta con zombies que te siguen de forma inmediata ni bien el programa se inicia. dentro del ambiente también tenemos edificios que sirven para dar una mejor idea del movimiento del jugador. El jugador tiene una cantidad de vida limitada la cual podemos alterar tanto programaticamente como manualmente mediante el engine de Unity 3D.

El jugador tiene la opción de disparar, rotar en 8 direcciones, moverse e invertir su movimiento sin rotar.

2-Descripción detallada de la actividad o acción que va a aprender tu agente.

El agente aprenderá a desplazarse por el medio ambiente esquivando a los zombies.

3-Solución planteada al problema utilizando el algoritmo LMS.

a. Selección de la experiencia de aprendizaje

i.Se optó por usar feedback indirecto para poder hacer un análisis de los estados que eligió durante su toma de decisiones.

b. Selección de la función objetivo

i.La función objetivo quedó de la siguiente forma:

W0*P+W1*D+W2*R+W3*Z

Donde :

P=Número de enemigos en la dirección elegida.

D=Distancia al zombie más cercano.

R=Que tan rodeado estás.

Z=Si ves zombies.

c.Selección de la representación de la función objetivo.

La función objetivo devuelve un número real. Se optará por el mayor a la hora de decidir la acción.

d.Selección del algoritmo de aproximación.

i.Selección de los patrones utilizados para el aprendizaje

1. Cuando el agente esta rodeado por zombies.

2. Cuando hay muchos zombies en una sola dirección.

3. Cuando no hay ningún zombie a la vista.

ii.Los pesos elegidos dentro de la función objetivo buscaban

1. w0 = -1

2. w1 = -10

3. w2 = -3

4. w3 = 1

4-Conclusiones después de la programación.

Luego de finalizar la actividad de programación 2 nos pudimos dar cuenta de certas cosas.

Para empezar nos topamos con ciertos problemas con unity, su función arctan. Los ángulos que nos devolvía no concordaban con los angulos de nuestros cuadrantes por lo cual debimos adaptar nuestra lógica al engine para que todo saliera bien. Luego fue muy interesante el hecho de que el algoritmo pudiera balancear los pesos de niuestra función objetivo en cada corrida. Determinar cada cuanto tiempo se hace el LMS fue algo un poco dificil y esto implicó que pensaramos que tanto una persona piensa lo que hace. Nos dimos cuenta de que la decisión se toma en un primer instante y por lo general luego actuas inmediatamente. Esto nos ayudó a determinar que el algoritmo debía de balancear los pesos luego de cada muerte. El algoritmo para tomar decisiones se corre cada medio segundo y cada decisión es almacenada en una lista para poder realizar el balanceo de pesos posteriormente.

Finalmente es muy interesante ver como el personaje esquiva a los zombies y aparentemente aprende con base a nuestra función objetivo. Lo más impresionante es que lo hace solo sin necesidad de estar manipulando los pesos manualmente.

Actividad Programación 2 Algoritmo LMS

Breve descripción del medio ambiente:

Nuestro medio ambiente es un patio de una escuela simulada, en donde nuestro agente principal será un niño de esa escuela. En ese ambiente se transmiten mensajes o chismes entre los alumnos. El problema es que estos chismes no siempre son transmitidos de manera fiel por lo que es necesario aprender a rastrearlos para saber quien ha dicho el chisme.

Descripción detallada de la actividad o acción que va a aprender el agente:
En esta actividad nuestro objetivo es que el agente, utilizando el algoritmo LMS, aprenda a rastrear el chisme que se ha propagado entre todos los alumnos. En primer lugar aparecen los niños en posición aleatoria, nuestro agente y finalmente hay uno solo que tiene un chisme. Ese niño chismoso comienza a caminar por el paisaje y conforme se va encontrando niños les transmite el chisme. Estos niños portadores del chisme, a su vez, lo transmiten a los niños que se encuentran en su camino, el problema es que el chisme ya ha sido modificado por cada uno de los transmisores. El objetivo de la primera etapa es que todos los niños posean información, ya sea falsa o verdadera, del chisme La siguiente etapa comienza con nuestro agente investigando sobre ese chisme que fue propagado, y es en esta etapa donde utilizamos el LMS.

Solución planteada al problema utilizando el Algoritmos LMS:

i. Selección de la experiencia de aprendizaje:
Las instancias del problema se generarán de manera aleatoria por la computadora.
ii. Selección de la función objetivo:
Es una función que recibe un estado en el que las variables a evaluar son el chisme, el rango de visión, la fuente del chisme, la posición de la misma (esto puede o no ser verdad) y el número de personas a las que les ha preguntado.
iii. Selección de la representación de la función objetivo:

La representación se dará en forma de un polinomio de la forma

V = W0 + W1X1 + W2X2 + W3X3 + W4X4 + W5X5

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

Decidimos utilizar tres constantes de aprendizaje diferentes que afectarán a nuestro algoritmo.:

X1:El inverso de la distancia en X entre el agente y la fuente “inmediata” del chisme.
X2: El inverso de la distancia en Y entre el agente y la fuente “inmediata” del chisme.
X3: El número de personas en el rango de visión del agente y que no les ha preguntado.
X4: El número de personas a las que se les ha preguntado.
X5: El número de personas que se encuentran en su rango de visión y que están repetidas (ya les preguntó)

v. Los pesos comienzan en 1 y utilizamos los 4 correspondientes a w0, w1, w2, w3, w4 y w5.

2. Describir los patrones utilizados para el aprendizaje (al menos 3 ejemplos).

Para nuestro ambiente no se utilizan patrones ya que se genera de manera aleatoria la posición de cada niño y las decisiones que ellos toman para moverse también son generadas sin un orden específico. Sin embargo las corridas se inician con un chisme que por ahora se inicia en {1,1,1} pero que en un futuro podría generarse al azar.

Conclusiones:

Al estar programando nuestro proyecto notamos que lo más difícil para lograr un aprendizaje óptimo es crear una función objetivo adecuada. Esto se debe a que de ella dependen los pasos siguientes, y si está mal diseñada aunque el agente tenga una buena experiencia de entrenamiento no aprenderá con facilidad.
A demás, el valor que nos regresa la función determina qué tanto le dejamos aprender a nuestro agente; en este caso nuestra retroalimentación fue excesivamente negativa desviando el aprendizaje hasta llevarlo a pesos negativos, alejándolo de aprender algo.
Por esta razón es necesario tomar en consideración las variables para darle una pista de que el camino no era tan malo.

También aprendimos sobre la importancia que tienen los pesos en el algoritmo, ya que al irse modificando toman importancia las diferentes características a las que éstos modifican, y también es importante su correcta configuración inicial para que el algoritmo funcione más rápido.

En el video podemos observar diversas iteraciones del algoritmo, al principio se enfoca en preguntar, sin embargo conforme va avanzando el programa vemos que se desvía un poco de lo que queríamos que aprendiera ya que la retroalimentación de la función objetivo no era la adecuada.

 

Actividad de programación 2- ML - Q-Learning

Diego García M. 1162205
Joaquín León M. 1162101
Enrique Peña A. 1162110

Actividad de programación 3 –Q-Learning

a. Breve descripción del medio ambiente.
Es una pista de velocidad donde se simula una carrera de 100 metros. El agente puede controlar los movimientos del corredor de la cintura para abajo. Al coordinar de manera correcta los movimientos de los muslos y las pantorrillas se realiza un desplazamiento similar al de una persona mientras corre.
Ambiente desarrollado en C++ utilizando la librería de física Box2D.

b. Descripción detallada de la actividad o acción que va a aprender tu agente.
El agente va a aprender a correr sobre la pista. Al realizar los movimientos correctos que tiene a su disposición debe de lograr un movimiento similar a correr o al menos debe de aprender a desplazarse hacia adelante utilizando sus movimientos.

c. Solución planteada al problema utilizando el Algoritmos Q-learning. Describe con detalle cada elemento del planteamiento:

I. Selección de la experiencia de aprendizaje
Feedback: Indirecto, al realizar una acción, el agente recibe una recompensa con base en la distancia avanzada.
La selección de acciones la realiza el agente basándose en su tabla Q.
Todos los entrenamientos siguen la misma distribución que los ejemplos futuros.

II. Selección de la recompensa
Cada que el agente realiza una acción es recompensado inmediatamente con un número que representa la distancia que avanzó al realizar dicha acción.

III. Posibles acciones
Mover sus muslos alternado con el hombro del otro lado del cuerpo.

Esperar.

IV. Estados posibles que puede sensar tu agente en el medio (descripción de los estados).
Nuestro agente no puede sensar muchas cosas de su ambiente mas que la posición en la que se encuentra.
Los estados posibles se refieren mas a las teclas que apretaría o no apretaría un usuario en el juego de QWOP. Esto es: Q apretada, W apretada, nada apretado.

V. Descripción de la estrategia de exploración/explotación para el aprendizaje.
La estrategia que usamos para balancear la exploración y la explotación del ambiente es una variable llamada temperatura (tomado del algoritmo “Simulated Annealing”). Ésta empieza con un valor alto lo cual hace poco probable que el algoritmo se vaya por la mejor opción. Conforme pasa el tiempo, la temperatura va bajando, obligando al algoritmo a elegir las mejores acciones.

VI. Ejemplo de tres estados distintos del medio ambiente, con las respectivas acciones que pueden ser realizadas desde dicho estado y las recompensas que se le otorgan al agente al tomar las acciones.
Estado 1: S (sleep) Posibles acciones: continuar en S, apretar Q, apretar W. La recompensa es igual a la cantidad avanzada por el agente al realizar la acción.
Estado 2: Q. Posibles acciones: continuar en Q, pasar a S, apretar W. La recompensa es igual a la cantidad avanzada por el agente al realizar la acción.
Estado 3: W. Posibles acciones: continuar en W, apretar Q, pasar a S. La recompensa es igual a la cantidad avanzada por el agente al realizar la acción.

VII. Explicar cuándo es que tu agente va aprendiendo y cuándo utiliza lo aprendido para tomar decisiones en el medio.
El agente empieza a aprender de una manera más eficaz en cuanto encuentra (random) una combinación de acciones que lo llevan a avanzar una distancia considerable. Esto hace que se de cuenta que esta combinación es favorable y la siga aplicando.

d. Conclusiones después de la programación.
En nuestro caso, la gran mayoría del tiempo lo invertimos en programar y adptar el medio ambiente. Debido a que ninguno de nosotros estaba familizarizado con Box2D, nos costó tiempo y esfuerzo hacerlo. Una vez programado el medio ambiente procedimos a simular una elección de acciones para ver si se llevaban a cabo. La última parte fue implementar QLearning.