Actividad 3, Q-Learning y Sarsa

Medio Ambiente

Planet Wars, juego basado en Galcon. El juego tiene 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 y el juego puede terminar antes si uno de los jugadores pierde todas sus naves. Si ambos jugadores tiene el mismo número de naves cuando el juego termina, es un empate.

Actividad que el Agente Aprenderá: Maximizar su eficiencia de juego por medio de la creación de una estrategia de juego.

Algoritmo Q-leaning

Experiencia de Aprendizaje: Como experiencia de aprendizaje se eligió que el agente jugara contra un bot o si mismo.

Selección de Recompensas: La recompensa de una acción es dada por la siguiente función que regresa un valor evaluando el número de naves que tiene el agente, la distancia al objetivo, el número de enemigos en el objetivo, la tasa de crecimiento del objetivo y el tamaño del objetivo.

Acciones Posibles del Agente: Mover tropas a planeta pequeño, lejos y denso; mover tropas a planeta pequeño, largo y no denso; mover tropas a planeta pequeño, cerca y denso; mover tropas a planeta pequeño, cerca y no denso; mover tropas a planeta grande, lejos y denso; mover tropas a planeta grande, lejos y no denso; mover tropas a planeta grande, cerca y denso; mover tropas a planeta grande, cerca y no denso; Esperar.

Estados Posibles del Agente: El agente tiene los siguientes estados: Atacar y Expandir.

Estrategia de Exploración/explotación: Al inicio el agente se dedica únicamente a la exploración del medio, la cual consiste en recorrer todos sus estados y las acciones posibles que puede tomar en cada estado; una vez llena la tabla, se tomara la acción apropiada dependiendo de la recompensa de la misma.

Ejemplos del Estados

· Estado: Atacar

§ Acciones Posibles: Mover tropas a planeta pequeño, lejos y denso; mover tropas a planeta pequeño, largo y no denso; mover tropas a planeta pequeño, cerca y denso; mover tropas a planeta pequeño, cerca y no denso; mover tropas a planeta grande, lejos y denso; mover tropas a planeta grande, lejos y no denso; mover tropas a planeta grande, cerca y denso; mover tropas a planeta grande, cerca y no denso: Esperar

§ Nota: Las acciones del estado “Atacar” aplican solo para planetas ocupados por el enemigo

· Estado: Expandir

§ Acciones Posibles: Mover tropas a planeta pequeño, lejos y denso; mover tropas a planeta pequeño, largo y no denso; mover tropas a planeta pequeño, cerca y denso; mover tropas a planeta pequeño, cerca y no denso; mover tropas a planeta grande, lejos y denso; mover tropas a planeta grande, lejos y no denso; mover tropas a planeta grande, cerca y denso; mover tropas a planeta grande, cerca y no denso; Esperar

§ Nota: Las acciones del estado “Expandir” aplican solo para planetas neutrales.

Aprendizaje del Agente: Se aprende después de cada turno, utiliza los valores generados por la función para generar nuevas recompensas y por ende nuevas estrategias.

Algoritmo SARSA

La información relacionada con el algoritmo SARSA es la misma, lo único que cambia es la forma en la que el agente va aprendiendo.

Aprendizaje del Agente: A diferencia de Q.Learning normal, la implementación de SARSA aprende al final de cada partida, una vez que se cumple el ciclo de exploración y de explotación.

Conclusiones

Después de trabajar en la implementación de Q-Learning y Sarsa hemos llegado a la conclusión de que ninguno de los dos es adecuado a nuestro medio debido a que el medio cambia muy rápidamente, ya que cada partida será distinta por lo que el algoritmo no podría adaptarse de forma adecuada; los dos algoritmos serian adecuados si el medio fuera constante en todas las partidas, y los oponentes siguieran siempre el mismo patrón de ataque expansión.

Actividad Programación 3 Algoritmo Q-Learning Sarsa

Breve descripción del medio ambiente.

El medio ambiente es un campo de batalla limitado y de forma hexagonal con dos jugadores que pueden disparar y cuyo objetivo es matar al contrincante.

Descripción detallada de la actividad o acción que va a aprender tu agente.
Aprende a matar al contrincante

Solución planteada al problema utilizando el Algoritmo Q-Learning y el Algoritmo Sarsa.

Describe con detalle cada elemento del planteamiento:

Selección de la experiencia de aprendizaje

Se iba a premiar al agente por cada vez que este dañara o matara al enemigo, cuando lo detectaba y castigar cuando moría.

Selección de las recompensas.

Cuando la acción es quedarse en el ángulo en el que se encuentran la recompensa es 1.

Cuando cambian de ángulo la recompensa es -0.5 y cuando disparan la recompensa depende de si matan al contrincante, lo hieren, son heridos o mueren, obteniendo respectivamente 2,0.5,-0.5,-2.

Posibles acciones de tu agente en el medio.

Girar, disparar, moverse.

Estados posibles que puede sensar tu agente en el medio (descripción de los estados).

Cada uno de los 8 cuadrantes que puede ver más un estado sin actividad.

Descripción de la estrategia de exploración/explotación para el aprendizaje.

Lo ideal sería que se seleccionara de forma aleatoria algún estado del agente para poder poblar la tabla q y luego se pasara a explotación. Aquí fue donde surgió uno de los problemas, en lo que se le iba a enseñar era muy difícil definir un estado de terminación. Podría estar explorando varios caminos pero realmente no iba a funcionar uno del todo ya que el contrincante no se iba a mover de la misma forma siempre. Por lo cual la exploración realmente no acababa y tenía que darse siempre en cada iteración.

Al principio hay bastante exploración pero conforme aumenta el tiempo la explotación aumenta.

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.

Moviéndose a la derecha:

Puede: detenerse, disparar, moverse en ocho direcciones (8 acciones)

La recompensa depende del estado al que llega y algunas dependen de que hizo. Si dispara, se le debe de premiar solo si hiere, si gasta una bala y no le da a nadie se le castiga.

Quieto

Puede: disparar en 8 direcciones, disparar y moverse. La recompensa depende de si hiere o no a alguien, si se mueve se le premia con una pequeña cantidad

Moverse arriba del mismo

Explicar cuándo es que tu agente va aprendiendo y cuándo utiliza lo aprendido para tomar decisiones en el medio.

No llega a aprender ya que el ambiente siempre está cambiando.

Conclusiones después de la programación. Aquí debes de hacer una comparación e
interpretación de las corridas utilizando Q-Learning y Sarsa.

Q-learning es una técnica muy útil cuando se trata de ambientes no tan cambiantes, ya que las decisiones que tomas son repetir algo. Si el ambiente cambia hay que correr el q-learning de nuevo para cuando hay cosas nuevas y que las detecte. En nuestro caso q-learning no sirvió ya que ambos agentes lo trataron de usar y a aprender algo. El problema de que los estados "finales" dependían de otros agentes y no de ellos no permitió que se estableciera una buena representación en fsm y que cada cosa aprendida en la tala tenga que borrarse ya que solo serviría si el enemigo hacia lo mismo siempre. Por ejemplo si mataba a alguien mientras iba por la derecha quería siempre disparar a la derecha pro el enemigo podría aparecer ahora por la izquierda y cuando eso pasara luego diría que ala izquierda. El problema es que convergiría ej algo probablemente no serviría más.

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.