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.