Q-Learning, Aprendizaje por Refuerzo

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 dos tipos de agentes principales: buscador (agente verde) y guardián (agente rojo). También dentro del calabozo se encuentra un objeto que el buscador debe obtener (cuadro azul obscuro).

El objetivo del buscador será evitar a los guardias el mayor tiempo posible y a la vez, donde los callejones sin salida influirán a veces si es atrapado o no. El buscador debe encontrar el objetivo para de esta manera “ganar”.
En cuanto el agente buscador es atrapado por alguno de los guardianes, este regresa al inicio. También al encontrar el objetivo el buscador regresara a la entrada.

Actividad que aprende:
En este caso el agente aprenderá a moverse dentro del medio ambiente intentando acercarse lo más posible al objetivo.

Experiencia de Aprendizaje:
En este caso se utilizó el algoritmo de Q-Learning para que el agente buscador aprenda a encontrar su camino al objetivo (cuadro azul obscuro). El calabozo está situado en un cuadro de 40x40 donde el agente y los guardianes solo se mueven en los números impares, esto es coordenadas impares. Dado al tamaño el aprendizaje puede ser muy lento de acuerdo a los episodios seleccionados. Para esto se utiliza una variable entera, si esta es 1 quiere decir que el buscador obtuvo el objetivo, si es 2, significa que el buscador fue atrapado por uno de los guardias. Esto marca los episodios del aprendizaje.




Recompensas:
Las recompensas elegidas fueron las siguientes:
Si el movimiento elegido deja al buscador en la posición del objetivo, su recompensa es 100.
Si el movimiento elegido deja al buscador en la posición de un guardia, su recompensa es de -100.
Si no es ninguno de los casos anteriores se utiliza la fórmula para el cálculo de las recompensas:
Q‘(s,a) <- r + gamma*max(Q (delta(s,a), a’))

Posibles acciones:
Las acciones están decididas de acuerdo a la posición actual del buscador. Para esto se creó una función que toma como argumento la posición (x, y) actual y determina de acuerdo a los choques que pueda tener las posibles direcciones que puede tomar el buscador. Estas acciones son almacenadas como números del 1 al 4, donde cada número representa una de las 4 direcciones que puede tomar para moverse, restringido por las paredes.

Estados:
Los estados están definidos por la posición actual del personaje, (x, y). Por lo que cada coordenada posible es un estado diferente. Cada par de coordenadas (x, y) están asignadas a un identificador, para facilitar la búsqueda de este estado.

Exploración:
A la constante gamma se le dio un valor de 0.6 para los cálculos, por lo que se lleva una exploración, sin embargo el espacio de estados es tan grande que muchas veces simplemente se la pasa explorando si no ha llegado al objetivo varias veces, o si el objetivo está muy lejos.

Ejemplos de estados:
Estado: 0 (21,21) (El estado inicial): En este caso hay paredes tanto arriba como abajo por lo que su acción es moverse a la izquierda o derecha.
Acción: 3, esto indica que se va a mover a la derecha.

Estado 10: (35, 15) Suponiendo que en este caso no hay paredes alrededor, puede decidir cualquier dirección.
Acciones posibles: [1, 2, 3, 4]
Acción tomada = 4, moverse a la izquierda.

Evaluación:
Para que el buscador se acerque al objetivo la mayoría de las veces, al asignar una recompensa de 100 al movimiento que lo llevo a tal estado, se utiliza una función para elegir un nuevo movimiento de acuerdo a las recompensas conocidas.
Si todas las recompensas son 0 para ese estado, entonces se toma una dirección aleatoria.
Si existe alguna que no es 0, entonces se toma la primera mayor recompensa (en caso de que haya múltiples con el mismo valor), es decir:
Acciones posibles: [1, 2. 3]
Recompensas:
1 -> 20
2-> 0
3-> 20

Movimiento/Acción tomada = 1.

Acciones posibles: [1, 2. 3]
Recompensas:
1 -> 0
2-> 0
3-> 0

Movimiento/Acción tomada = Movimiento aleatorio entre 1 y 3.

Acciones posibles: [1, 2. 3]
Recompensas:
1 -> -100
2-> 0
3-> 0

Movimiento/Acción tomada = 2.

Corridas:




Conclusiones:
Existen algunos pequeños errores, que más que nada se deben al medio ambiente y la velocidad con la que se actualiza. A veces interfiriendo por completo en el programa ya que le da una evaluación al encontrar el objetivo y el buscador deja de moverse, o arrojando números completamente exagerados, por cuestiones de la velocidad a la que se actualizan los datos.
En cuanto a la programación del algoritmo se puede observar en la segunda imagen, que al actualizar las recompensas se puede ver que si va aprendiendo que acción es la que debe tomar en ese caso. Sin embargo fue un problema el tener que tratar con un espacio de estados tan grande y a la vez con las restricciones de las paredes. Aunque si es un poco tedioso toda la exploración que hace a veces, sin embargo fue un algoritmo interesante de implementar en este ambiente.

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 dos tipos de agentes principales: buscador y guardián

El objetivo del buscador será evitar a los guardias el mayor tiempo posible y a la vez, donde los callejones sin salida influirán a veces si es atrapado o no.
En cuanto el agente buscador es atrapado por alguno de los guardianes, este regresa al inicio.

Actividad que aprende:
En este caso el agente aprenderá a moverse dentro del medio ambiente intentando no ser atrapado por los guardianes. Para esto se utiliza una red neuronal que se entrena.

Patrones de Entrada:
Los patrones de entrada en este caso, se generan mediante iteraciones.
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.



Patrones de Salida:
La salida que se genera es un arreglo de 4 atributos cuyo valor es 0 o 1, de tal forma que el siguiente movimiento del buscador será decidido por el índice o “bandera” que este prendida en el patrón de salida.
Ejemplo de patrón de salida:
[0, 0, 1, 0] -> El cual indicaría que el movimiento deberá tomar un valor de 3 (“Muévete a la derecha”)

Red Neuronal:
En este caso, dado que lo que se quiere evaluar es algo complejo, se decidió utilizar una red neuronal multicapas utilizando un algoritmo de Backpropagation.

La red cuenta con 3 capas
• Entrada: Esta capa cuenta con 4 neuronas, de las cuales cada una toma uno de los atributos de los patrones de entrada.
• Secreta: Esta capa consta de 2 neuronas, se decidió de esta forma para facilitar un poco la implementación y reducir un poco los cálculos.
• Salida: Esta capa cuenta con 4 neuronas, para las cuales cada una sirve como bandera para elegir el siguiente movimiento, dependiendo de que neurona se active es el movimiento elegido.
En la red se utiliza un factor de aprendizaje de 0.3 ya que es un valor pequeño y un tanto “estándar”: ya que queremos que el aprendizaje sea preciso en cuanto a las salidas.
En este caso no se utilizo momento.
El número de iteraciones elegido para entrenar a la red fue de 1500 ya que al ser movimientos aleatorios al principio, es de interés que tenga una exploración del ambiente bastante grande para poder hacer la red neuronal más precisa


Ejemplos de corridas:


En la imagen se puede observar del lado izquierdo las entradas que va generando, y del lado derecho la salida que se debería dar, pero dado a que solo se está entrenando apenas la red, los valores de salida no son realmente acertados. Si se ven por ejemplo la primera línea:
Patrón de entrada: [0, 0, 4, 1]
Salida: [0, 0, 1, 0] Mientras que la salida esperada sería [0, 0, 0, 1]




Después de que ha terminado las iteraciones de entrenamiento podemos ver, que de acuerdo al patrón de entrada, ahora si nos envía la salida esperada:
Ejemplo de la primera línea:
Entrada: [0, 0, 4, 1]
Valor esperado: [0, 0, 0, 1]

Como se observa en la imagen, el valor obtenido es igual al esperado, por lo que la red aprendió efectivamente.

Conclusiones:
Las redes neuronales son bastante útiles para problemas como el presentado ya que sus cálculos y división en las salidas nos permite una evaluación y un aprendizaje más preciso asignando una dirección a cada salida. También es importante notar que la velocidad de los cálculos es importante, y en este caso es lo suficientemente rápida para un programa que se actualiza en tiempo real, lo que hace una red neuronal muy viable para este tipo de problemas.
La parte más difícil para este proyecto se podría considerar la codificación de entradas y salidas del medio ambiente, ya que todos los cálculos internos son automáticos del algoritmo.

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.

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:

Seleccion de Medio Ambiente

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.

Plataforma y lenguaje de programación

El ambiente se desarrollará sobre Dev C++, utilización C++ con el API grafico de GLUT que usa OpenGL pera su operación

Actividades que puede aprender el agente

Identificar objeto. La actividad de identificar objeto será llevada a cabo por el agente buscador. Consistirá en recorrer el calabozo y buscar objetos, aplicando el reconocimiento de patrones, para diferenciar los objetos entre sí y las copias falsas del original. Lo que es necesario para elegir el verdadero objeto y continuar con su camino hacia la salida. Como se mencionaba en la descripción del medio ambiente, se puede llegar a contar con solo una salida y una entrada, por lo que deberá recordar el camino que siguió(o si aprendió un camino mejor) para llegar a la salida. Si llegase a identificar un objeto falso como verdadero los agentes guardianes irían inmediatamente por él y el agente buscador perdería. Sin embargo si logra alcanzar el objeto verdadero, los agentes guardianes empezarían la persecución.

Conocer calabozo. Ésta actividad puede ser realizada por los 3 agentes que se encontrarían en el medio ambiente (buscador, guardián y espía). Consiste simplemente en ir reconociendo el calabozo y guardar dicha información. El agente buscador usará esta información para conocer donde se encuentra la salida y dirigirse a ella una vez que encuentre el objeto verdadero y a su vez saber donde se encuentran algunos atajos (aprendidos gracias al agente espía). El agente guardia deberá conocer el terreno para que cuando el agente buscador encuentre y agarre el objeto verdadero o agarre un objeto falso algún comience a perseguirlo. Finalmente el agente espía se encargará de buscar o encontrar atajos para ayudar al agente buscador en la tarea de encontrar el objeto verdadero y evadir al agente guardia cuando sea necesario.

Si el agente buscador encuentra y agarra un objeto falso, (si hay más de un agente guardián) se comunicarán entre ellos para rodear al agente buscador, sin embargo el agente espía hará su aparición y se interpondrá en dicha negociación para dar datos falsos y darle tiempo al agente buscador de buscar un lugar seguro.