Repositorio Institucional de Documentos

Control de un agente inteligente mediante Redes Neuronales en el entorno del videojuego UT2004 PROYECTO DE FIN DE CARRERA Autor: Sergio Moreno Ruiz Director: Manuel Gonz´alez Bedia Codirector: Francisco Ser´on Arbeloa Ingenier´ıa en Inform´atica Curso 2011-2012 Departamento de Inform´atica e Ingenier´ıa de Sistemas Centro Polit´ecnico Superior Universidad de Zaragoza Febrero de 2012 Control de un agente inteligente mediante Redes Neuronales en el entorno de simulaci´on UT2004 RESUMEN En este proyecto se pretende obtener agentes sint´eticos (bots) para videojuegos de acci´on en primera persona, de forma que su comportamiento no sea definido directamente por el programador, sino que estos sean capaces de adquirirlo mediante aprendizaje autom´atico. Para ello, se ha optado por una estrategia de aprendizaje basada en Redes Neuronales Recurrentes de Tiempo Continuo (CTRNN) (Beer, 1995a). Las CTRNNs permiten al agente iniciar una acci´on independientemente de su situaci´on inmediata y organizar su comportamiento anticip´andose a eventos futuros (Beer, 1995b). Parte fundamental de este proyecto es que las CTRNNs sean capaces de aprender por s´ı mismas, para lo cual deben de ser capaces de adaptarse a un comportamiento dado mediante algoritmos gen´eticos y, si se requiere, de aprender y adaptarse a las circunstancias a lo largo del tiempo de ejecuci´on del bot al que controlan. El objetivo principal de este proyecto es el de estudiar y aprovechar las capacidades de las CTRNNs para obtener comportamientos para los bots de un videojuego de acci´on en primera persona que ser´ıan imposibles utilizando redes neuronales feed-forward (con comportamiento p´uramente reactivo). Para ello, se realizar´an cuatro experimentos orientados a la obtenci´on de cuatro bots controlados por CTRNNs: 1. En primer lugar se buscar´a obtener dos bots con diferentes comportamientos de navegaci´on que requieran memoria a corto plazo: (a) un primer bot con comportamiento de navegaci´on y evitaci´on de obst´aculos y (b) un segundo bot con capacidad de seguir la trayectoria de movimiento de un bot enemigo, incluso cuando lo pierde moment´aneamente de vista al desaparecer ´este tras un muro, para lo cual tendr´a que poder “predecir” su reaparici´on. 2. En segundo lugar se buscar´a obtener un tercer bot con el que estudiar la capacidad de las CTRNN de aprender durante el tiempo de vida del bot sin variar ninguno de sus par´ametros. 3. Por ´ultimo, una vez estudiadas las propiedades de las CTRNNs para diferentes bots, se buscar´a obtener un cuarto bot cuyo comportamiento sea combinaci´on de los obtenidos para el primer y el tercer bot. El videojuego para el cual se programar´an los bots es Unreal Tournament 2004 (UT2004) el cual cuenta con la plataforma Pogamut 3, la cual permite programar el control de los bots en el lenguaje de programaci´on Java. Al tratarse de un trabajo pionero, el objetivo previo a la realizaci´on de este proyecto consistir´a en estudiar dicha plataforma (sus ventajas y limitaciones), as´ı como realizar un manual adecuado para programadores (dado que Pogamut, al principio de este proyecto, no contaba con uno). Con ello se pretende asentar las bases para futuros proyectos en el ´area de IA en videojuegos utilizando Pogamut. i ´ Indice general I Memoria XI 1. Introducci´on 1 1.1. Objetivo y alcance del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Contexto en el que se realiza el proyecto . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3. Metodolog´ıa: CTRNNs que aprenden . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4. Trabajo a realizar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.5. Herramientas utilizadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.6. Estructura del documento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.7. Planificaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. T´ecnicas para la evoluci´on de redes neuronales din´amicas en el entorno de simulaci´on UT2004 7 2.1. El entorno de simulaci´on UT2004 y Pogamut 3 . . . . . . . . . . . . . . . . . . . . 7 2.2. Redes Neuronales Recurrentes de Tiempo Continuo . . . . . . . . . . . . . . . . . . 8 2.3. Evoluci´on Diferencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4. Dise˜no de los experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3. Aprendizaje evolutivo para la obtenci´on de CTRNNs con comportamientos de navegaci´on 13 3.1. Configuraci´on general de los experimentos . . . . . . . . . . . . . . . . . . . . . . 13 3.1.1. Dise˜no del bot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.1.2. Configuraci´on de las CTRNNs . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.1.3. Configuraci´on del algoritmo de Evoluci´on Diferencial . . . . . . . . . . . . . 15 3.2. Experimento 1: Navegaci´on y evitaci´on de obst´aculos en un entorno no estructurado 16 3.2.1. Descripci´on del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2.2. Dise˜no del experimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.3. Resultados del experimento . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2.4. An´alisis del comportamiento del bot . . . . . . . . . . . . . . . . . . . . . . 19 3.3. Experimento 2: Seguimiento de trayectorias . . . . . . . . . . . . . . . . . . . . . . 20 3.3.1. Descripci´on del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3.2. Dise˜no del experimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3.3. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.4. Conclusiones: memoria a corto plazo en CTRNNs con recurrencias entre sus nodos 23 4. Aprendizaje en CTRNNs sin plasticidad sin´aptica durante el tiempo de vida del bot 25 4.1. Descripci´on del experimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2. Aprendizaje evolutivo para la obtenci´on de la CTRNN . . . . . . . . . . . . . . . 26 4.3. An´alisis del comportamiento de aprendizaje del bot . . . . . . . . . . . . . . . . . 28 4.4. An´alisis de las din´amicas del sistema CTRNN-entorno . . . . . . . . . . . . . . . . 30 iii 4.5. Conclusiones: capacidad de memorizaci´on en CTRNNs con tiempos de activaci´on multiescala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5. Combinaci´on de CTRNNs para la obtenci´on de un sistema escalable 35 5.1. M´etodo utilizado y el problema de la escalabilidad . . . . . . . . . . . . . . . . . . 35 5.2. Dise˜no del experimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.3. Resultados del experimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.4. Conclusiones: combinaci´on de comportamientos de CTRNNs . . . . . . . . . . . . 38 6. Conclusiones 41 6.1. Resultados obtenidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.2. Recurrencias entre los nodos de la red para comportamientos con necesidad memoria a corto plazo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.3. Activaci´on multiescalada en el tiempo para un comportamiento de aprendizaje en tiempo de ejecuci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.4. Combinaci´on de CTRNNs para comportamientos complejos . . . . . . . . . . . . . 43 6.5. Algoritmos Gen´eticos y CTRNNs en UT2004 utilizando Pogamut . . . . . . . . . . 43 6.6. Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 6.7. Valoraci´on personal y problemas encontrados . . . . . . . . . . . . . . . . . . . . . 44 II Anexos 45 A. Inteligencia Artificial y Videojuegos 47 B. Redes neuronales 49 B.1. Introducci´on a las Redes Neuronales . . . . . . . . . . . . . . . . . . . . . . . . . . 49 B.2. Descripci´on matem´atica de las CTRNN . . . . . . . . . . . . . . . . . . . . . . . . 50 B.3. An´alisis de las din´amicas de un agente controlado por CTRNN con su entorno . . 51 B.4. Redes de Elman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 C. Algoritmos Gen´eticos 55 C.1. Introducci´on a los Algoritmos Gen´eticos . . . . . . . . . . . . . . . . . . . . . . . . 55 C.2. Descripci´on de la t´ecnica de Evoluci´on Diferencial . . . . . . . . . . . . . . . . . . 56 C.3. Espacio “Fitness” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 D. Manual Pogamut 3 61 D.1. Instalaci´on y Servidor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 D.1.1. Instalaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 D.1.2. Ejecuci´on del bot en UT2004 . . . . . . . . . . . . . . . . . . . . . . . . . . 62 D.2. Modos de movimiento del bot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 D.2.1. Bot de Navegaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 D.2.2. Bot con raycasting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 D.3. Implementaci´on del bot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 D.3.1. Clases principales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 D.3.2. Clase ModuleController . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 D.3.3. Otros comandos interesantes . . . . . . . . . . . . . . . . . . . . . . . . . . 83 D.4. Eventos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 D.4.1. Interacci´on con el mundo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 D.4.2. Descripci´on de los eventos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 D.4.3. Eventos clasificados por grupos . . . . . . . . . . . . . . . . . . . . . . . . . 91 iv ´ Indice de figuras 1.1. Arquitectura de Pogamut, donde “IDE” es NetBeans 6.9.1 y “Local Parser” se trata de un middleware entre GameBots2004 y el cliente, cuyo prop´osito es simplificar el env´ıo y recepci´on de mensajes de GameBots2004 y minimizar la utilizaci´on del ancho de banda transmitiendo ´unicamente la informaci´on que ha cambiado. . . . . 4 1.2. Diagrama de Gantt de las actividades realizadas. . . . . . . . . . . . . . . . . . . . 5 2.1. Valor de salida en una CTRNN. Izquierda: Un nodo autoconectado. Derecha: Funci´on sigmoidea aplicada para calcular la salida de una neurona. . . . . . . . . . 9 3.1. Veh´ıculo de Braitenberg y su versi´on real y simulada. [A] Representaci´on esquem´atica del un Veh´ıculo de Braitenberg. [B] Robot Khepera, cuya arquitectura es similar a un Veh´ıculo de Braitenberg. [C] Bot de UT2004 con arquitectura similar a un Veh´ıculo de Braitenberg. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2. Comparaci´on entre una arquitectura feed-forward y otra con conexiones recursivas. Izquierda: Un sistema de control basado en un veh´ıculo de Braitenberg con conexiones feedforward sim´etricas se mueve hasta la esquina inferior izquierda, donde se detiene al encontrar las mismas intensidades en los sensores de ambos lados (las peque˜nas oscilaciones se deben al ruido sensorial). Derecha: El controlador evolucionado hace uso de la recursividad para evitar el punto muerto. . . . . . . . . . . 16 3.3. Mapa para el experimento para la obtenci´on de un bot controlado por una CTRNN con capacidad de navegaci´on y evitaci´on de obst´aculos. . . . . . . . . . . . . . . . . 17 3.4. Gr´afica con los resultados de la funci´on “fitness” obtenidos durante el proceso de evoluci´on para la obtenci´on de una CTRNN con capacidad de navegaci´on y evitaci´on de obst´aculos. La l´ınea azul muestra el valor obtenido por el mejor individuo de cada generaci´on. La l´ınea discontinua roja muestra la media de todos los individuos de cada generaci´on. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.5. CTRNN con comportamiento de navegaci´on y evitaci´on de obst´aculos en un entorno no estructurado para un bot con estructura de robot Khepera adaptada. . . . . . . 19 3.6. Ejemplo gr´afico del comportamiento de un bot controlado por la CTRNN resultado del experimento 1 para el modelo 1. [A] El bot localiza un obst´aculo. [B] El bot reacciona y evita el obst´aculo. [C] El bot ha evitado correctamente el obst´aculo sin colisionar contra ´el. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.7. Mapa para la comprobaci´on del correcto funcionamiento de un bot controlado por una CTRNN con capacidad de navegaci´on y evitaci´on de obst´aculos, el cual adem´as sea capaz de evitar puntos muertos. . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.8. Mapa para el segundo experimento. . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.9. Gr´afica con los resultados de la funci´on “fitness” obtenidos tras el proceso de evoluci´on para la obtenci´on de una CTRNN con capacidad de seguimiento de las trayectorias de movimiento de otros bots. La l´ınea azul muestra el valor obtenido por el mejor individuo de cada generaci´on. La l´ınea discontinua roja muestra la media de todos los individuos de cada generaci´on. La l´ınea discontinua vertical muestra la transici´on de la primera fase (fase de localizaci´on) a la segunda (fase de seguimiento). 23 v 3.10. Ejemplo gr´afico del comportamiento de dos bots controlados por la CTRNN resultado de la primera fase del experimento 2. . . . . . . . . . . . . . . . . . . . . . . . 23 3.11. CTRNN con comportamiento de seguimiento de trayectorias de movimiento de otros bots para un bot con estructura de robot Khepera adaptada. . . . . . . . . . . . . 24 3.12. Ejemplo gr´afico del comportamiento de un bot controlado por la CTRNN resultado del experimento 2. [A] El bot sigue la trayectoria de su objetivo. [B] El objetivo se oculta tras un muro. [C] El objetivo reaparece y el bot ha sido capaz de seguir su trayectoria. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.1. Entorno de simulaci´on para el experimento. (A) Entorno de simulaci´on te´orico bidimensional, con un gradiente de alturas, en el que la base “enemiga” puede ser localizada en una de las dos franjas representadas por regiones a puntos. (B) Entorno de simulaci´on en UT2004, en el que el gradiente es la altura a la que se encuentra el bot, y las franjas roja y azul representan d´onde se encuentran las bases “alta” y “baja” respectivamente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.2. Gr´afica con los resultados de la funci´on “fitness” obtenidos tras el proceso de evoluci´on para la obtenci´on de una CTRNN con capacidad de aprendizaje en tiempo de ejecuci´on del bot. La l´ınea azul muestra el valor obtenido por el mejor individuo de cada generaci´on. La l´ınea discontinua roja muestra la media de todos los individuos de cada generaci´on. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.3. Par´ametros para la mejor CTRNN con 4 neuronas totalmente interconectadas y autoconectadas. Los nodos est´an sombreados seg´un sus bias. El grosor de las conexiones excitatorias (negras) e inhibitorias (grises) es proporcional al peso de las mismas. Las constantes de tiempo est´an representados por el tama˜no del nodo, siendo las neuronas m´as lentas las m´as grandes. . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.4. Actividad de la CTRNN para una secuencia de ejecuci´on. De arriba a abajo las trazas corresponden a la se˜nal de base (B), la se˜nal de altura (A), y las salidas de las neuronas (oi). Las dos ´ultimas neuronas controlan el motor de la derecha (rm) e izquierda (lm). Las barras horizontales de color gris oscuro en la traza de altura determinan donde puede encontrarse la base enemiga seg´un el entorno A-ent o B-ent. Las l´ıneas discontinuas verticales finas marcan las diferentes ejecuciones (cuando el bot se vuelve a ejecutar desde el centro del mapa). Las l´ıneas discontinuas verticales gruesas marcan la transici´on entre entornos. . . . . . . . . . . . . . . . . . . . . . . 30 4.5. Diagrama de bifurcaci´on en ausencia de bases. Cuatro proyecciones bidimensionales del diagrama 5-dimensional, una por cada una de las neuronas de la CTRNN. Las l´ıneas s´olidas representan puntos estables de equilibrio, mientras que las l´ıneas discont´ınuas representan puntos de equilibrio inestables. . . . . . . . . . . . . . . . 31 4.6. Diagrama de bifurcaci´on en presencia de la base enemiga. Cuatro proyecciones bidimensionales del diagrama 5-dimensional, una por cada una de las neuronas de la CTRNN. Las l´ıneas s´olidas representan puntos estables de equilibrio, mientras que las l´ıneas discont´ınuas representan puntos de equilibrio inestables. Las l´ıneas grises verticales muestran los rangos de altura donde puede encontrarse la base enemiga. 32 5.1. CTRNN compuesta por las obtenidas en los experimentos del experimento 1 del cap´ıtulo 3 y el del cap´ıtulo 4. La neurona 1 est´a autoconectada, recibe los valores de los sensores base de la CTRNN de la derecha y los valores de los sensores si proporcionados por los rayos del sistema “raytracing” de la CTRNN de la izquierda, y se encarga de seleccionar una de las dos CTRNNs para ejecutar las acci´on del bot. 36 5.2. Mapas para el experimento de obtenci´on de una CTRNN como combinaci´on de otras CTRNNs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 vi 5.3. Gr´afica con los resultados de la funci´on “fitness” obtenidos tras el proceso de evoluci´on para la obtenci´on de una CTRNN capaz de elegir entre el comportamiento de una de las CTRNNs que la componen para con capacidad de navegaci´on y evitaci´on de obst´aculos. La l´ınea azul muestra el valor obtenido por el mejor individuo de cada generaci´on. La l´ınea discontinua roja muestra la media de todos los individuos de cada generaci´on. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 B.1. CTRNN formada por un nodo autoconectado. . . . . . . . . . . . . . . . . . . . . 51 B.2. Gr´aficas para el an´alisis de las din´amicas del sistema agente-entorno de una CTRNN formada por una ´unica neurona autoconectada. [A1] An´alisis de la convergencia del valor de activaci´on a un ´unico punto fijo estable para los par´ametros θ=0, w=- 20 y un valor de entrada constante I=-10. [A2] Diagrama de bifurcaci´on para los par´ametros θ=0, w=-20. [B1] An´alisis de la convergencia del valor de activaci´on a tres puntos fijos (dos estables y uno inestable) para los par´ametros θ=0, w=20 y un valor de entrada constante I=-10. [B2] Diagrama de bifurcaci´on para los par´ametros θ=0, w=20. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 B.3. CTRNN totalmente interconectada y recurrente en la capa intermedia . . . . . . . 53 B.4. Codificaci´on del genotipo de una CTRNN totalmente interconectada y recurrente en la capa intermedia con 6 neuronas de entrada, 4 intermedias y 2 de salida. . . . 54 C.1. Evoluci´on Diferencial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 C.2. Espacio “Fitness” . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 D.1. Modos de juego GameBots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 D.2. Configuraci´on del servidor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 D.3. C´odigo en NetBeans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 D.4. A˜nadir servidor UT2004 a NetBeans . . . . . . . . . . . . . . . . . . . . . . . . . . 65 D.5. Host del servidor UT2004 en NetBeans . . . . . . . . . . . . . . . . . . . . . . . . . 65 D.6. Modo espectador en UT2004 desde NetBeans . . . . . . . . . . . . . . . . . . . . . 66 D.7. Consola del comandos con opciones propias de Pogamut 3 para UT2004 . . . . . . 66 vii persona que ser´ıan imposibles utilizando redes neuronales feed-forward. Debido a la necesidad de procesamiento de la informaci´on lo m´as r´apidamente posible ya comentada, y dado que podr´ıa considerarse la posibilidad de combinar las redes obtenidas en un mismo bot, se buscar´a obtener las CTRNNs m´as peque˜nas posibles que satisfagan los comportamientos deseados. El videojuego para el cual se programar´an los bots es Unreal Tournament 2004 (UT2004). Dicha elecci´on se debe a que es el videojuego utilizado en el concurso a nivel mundial denominado 2K BotPrize, que consiste b´asicamente en una adaptaci´on del test de Turing al dominio de los videojuegos. Adem´as, UT2004 cuenta con la plataforma Pogamut 3, la cual permite programar el control de los bots en el lenguaje de programaci´on Java. Al tratarse de un trabajo pionero, el objetivo previo a la realizaci´on de este proyecto consistir´a en estudiar dicha plataforma (sus ventajas y limitaciones), as´ı como realizar un manual adecuado para programadores (dado que Pogamut, al principio de este proyecto, no contaba con uno). Con ello se pretende asentar las bases para futuros proyectos en el ´area de IA en videojuegos utilizando Pogamut. Dicho manual puede consultarse en el Anexo D. 1.2. Contexto en el que se realiza el proyecto A pesar de que, como se ha comentado anteriormente, en la industria del videojuego hay cierta reticencia a cambiar las t´ecnicas de IA utilizadas tradicionalmente, en el mundo de la investigaci´on acad´emica ya se han dado los primeros pasos para la obtenci´on de bots controlados por redes neuronales feed-forward. Algunos ejemplos de ello son los siguientes: NeuralBot (Chapman, 1999)), el primer bot en utilizar redes neuronales, dise˜nado para el videojuego Quake II; NERO (Stanley el al., 2005), un bot capaz de aprender en tiempo de ejecuci´on cambiando los par´ametros de la red neuronal, para lo que utiliza el algoritmo rNEAT (real-time NeuroEvolution of Augmenting Topologies) que permite cambiar adem´as la topolog´ıa de la red, y DodgingBot (Kadlec, 2008), primer bot programado utilizando Pogamut y que utiliza redes neuronales, siendo capaz de esquivar misiles en el videojuego UT2004. Por otro lado, en los ´ultimos a˜nos, entre la comunidad que estudia los agentes aut´onomos se ha manifestado un inter´es creciente en el uso de las CTRNNs (Beer, 1995a) para controlar el comportamiento de agentes (Beer, 1990) y en la evoluci´on de las mismas como t´ecnica de aprendizaje (Yamauchi y Beer, 1994; Floreano y Mondada, 1994). Estos trabajos, entre otros, han mostrado que la combinaci´on de algoritmos gen´eticos y redes neuronales es una t´ecnica muy interesante para desarrollar estructuras de control en agentes aut´onomos. En concreto, su uso de ha destacado en un ´area que se ha denominado Rob´otica Evolutiva (Harvey et al., 2005), la cual consiste b´asicamente en la aplicaci´on de t´ecnicas evolutivas a redes neuronales para obtener agentes aut´onomos en los que “emerjan” los comportamientos deseados. Aunque es cierto que inicialmente en los proyectos emprendidos se utilizaban agentes f´ısicos, en los ´ultimos a˜nos ha predominado la tendencia a implementar modelos adaptados al dise˜no de agentes sint´eticos en entornos virtuales de simulaci´on (Jakobi, 1998). La obtenci´on de agentes aut´onomos mediante entrenamiento de CTRNNs utilizando algoritmos gen´eticos, se inspira en los trabajos pioneros de Floreano y Mondada (1994) sobre comportamientos de navegaci´on de robots m´oviles Khepera (Floreano y Mondada, 1994) en entornos no estructurados, y de Beer (1996), sobre la capacidad de las CTRNNs para diferentes comportamientos cognitivos sencillos (denominados “modelos m´ınimos de cognici´on”). Tambi´en se han tenido en cuenta los estudios realizados por Izquierdo (2008), en los que demuestra que el comportamiento de una CTRNN est´a ´ıntimamente ligado al modelado del bot y a su situaci´on en el entorno, as´ı como la capacidad de aprendizaje durante el tiempo de ejecuci´on del agente por parte de CTRNNs sin plasticidad sin´aptica. Por ´ultimo, para el an´alisis de las din´amicas de una CTRNN con su entorno, se han seguido las t´ecnicas estudiadas y demostradas por Beer (1995a). 2 1.3. Metodolog´ıa: CTRNNs que aprenden Parte fundamental de este proyecto es que las CTRNNs sean capaces de aprender por s´ı mismas, para lo cual deben de ser capaces de adaptarse a un comportamiento dado y, si se requiere, de aprender y adaptarse a las circunstancias a lo largo del tiempo de ejecuci´on del bot al que controlan. En la naturaleza, la evoluci´on por un lado, y el aprendizaje durante el tiempo de vida por otro, son las dos formas m´as importantes de adaptaci´on biol´ogica. Como es evidente, ´estas operan en diferentes escalas de tiempo: mientas que la evoluci´on permite a las poblaciones de individuos adaptarse lentamente a las necesidades y cambios del entorno, a su vez cada individuo necesita adaptarse a los cambios que ocurren durante su tiempo de vida. a) El aprendizaje evolutivo como aprendizaje del comportamiento para el bot A la hora de dise˜nar una red neuronal, podemos definir dicha red en funci´on del n´umero de nodos que la componen y las conexiones entre los mismos. No obstante, resulta inviable determinar los par´ametros de la red (tales como el valor de los pesos las conexiones, de las bias, etc.) que definen un determinado comportamiento seg´un crece la dificultad del problema y, con ello, el n´umero de variables que determinan el sistema. Debido a ello, se utiliza el aprendizaje mediante t´ecnicas como las Estrategias Evolutivas y Algoritmos Gen´eticos. ´ Estas permiten solucionar un problema de la siguiente manera: 1. Se crea una poblaci´on de redes neuronales en la que a los par´ametros de cada red se asignan valores aleatorios. 2. Se eval´uan las posibles soluciones y se combinan las mejores para crear una nueva generaci´on. 3. Para cada generaci´on se repite el proceso de selecci´on de las mejores soluciones y se repite el proceso de mezcla durante el n´umero de generaciones deseado o hasta obtener un individuo que se comporte satisfactoriamente seg´un los criterios del programador. Este planteamiento se puede interpretar como un sistema de b´usqueda de soluciones que intenta utilizar las mismas t´ecnicas que la naturaleza ha encontrado ante problemas semejantes. Debe tenerse en cuenta que el comportamiento que se obtiene no depende ´unicamente de la red, sino que es producto de la interacci´on entre las din´amicas internas del agente, su cuerpo y su entorno. En este proyecto, se utilizar´a el aprendizaje evolutivo para obtener las CTRNNs con los comportamientos deseados para el control de los bots. Concretamente, el algoritmo gen´etico utilizado el de Evoluci´on Diferencial (Prize, 1999), el cual se explica en profundidad en el Anexo C. b) El aprendizaje durante el tiempo de vida del agente como comportamiento del bot Una vez sintetizada la CTRNN para un comportamiento dado mediante aprendizaje evolutivo, puede ser deseable que la red neuronal obtenida siga siendo capaz de aprender durante el tiempo de vida del bot. Tradicionalmente, el aprendizaje ha sido asociado a la modificaci´on de los par´ametros de una red neuronal, especialmente los que involucran cambios en las conexiones sin´apticas o los pesos de las conexiones de la red. No obstante, este tipo de asunciones no son necesarias y es posible sintetizar CTRNNs sin plasticidad sin´aptica (es decir, cuyos par´ametros permanecen invariables) con capacidad de aprendizaje durante el tiempo de vida del bot (Izquierdo 2008). En estas circunstancias, se considera el aprendizaje como el comportamiento para el cual ha sido evolucionada la CTRNN. Este comportamiento de aprendizaje por parte de las CTRNNs se estudia en el cap´ıtulo 4. 1.4. Trabajo a realizar Para la realizaci´on de este proyecto, se realizar´an cuatro experimentos orientados a la obtenci´on de cuatro bots controlados por CTRNNs, con el objetivo de estudiar las capacidades de este tipo 3 de redes como controladores de agentes sint´eticos en el videojuego UT2004: 1. En primer lugar se buscar´a obtener dos bots con diferentes comportamientos de navegaci´on que requieran memoria a corto plazo, para lo que deber´an hacer uso de las recurrencias entre los nodos de la red. a) Para el primer bot se buscar´a comportamiento de navegaci´on y evitaci´on de obst´aculos en el entorno no estructurado de UT2004 (se entiende como entorno no estructurado a un entorno en el que no es viable que un agente pueda disponer de un mapa por lo complejo o lo cambiante del mismo (Arkin, 1998)). b) En cuanto al segundo bot, se desea que sea capaz de seguir la trayectoria de movimiento de un bot enemigo, incluso cuando lo pierde moment´aneamente de vista al desaparecer ´este tras un muro, para lo cual tendr´a que poder “predecir” su reaparici´on. 2. En segundo lugar se buscar´a obtener un tercer bot con el que estudiar la capacidad de las CTRNN sin plasticidad sin´aptica de aprender durante el tiempo de vida del bot sin variar ninguno de sus par´ametros. 3. Por ´ultimo, una vez estudiadas las propiedades de las CTRNNs para diferentes bots, se buscar´a obtener un cuarto bot cuyo comportamiento sea combinaci´on de los obtenidos para el primer y el tercer bot. Para ello, la CTRNN resultante deber´a ser capaz de alternar entre entre el comportamiento de uno y otro seg´un la situaci´on en la que se encuentre. 1.5. Herramientas utilizadas Para la implementaci´on de los bots se ha utilizado el videojuego Unreal Tournament 2004 junto con la ampliaci´on GameBots2004 (que permite ejecutar bots en el videojuego) y la plataforma Pogamut 3 (http://diana.ms.mff.cuni.cz/main/tiki-index.php) (que permite programar al agente virtual en el lenguaje de programaci´on Java (utiliza JDK 6) y conectarlo y recibir informaci´on del videojuego mediante un plugin para Netbeans 6.9.1), cuya arquitectura puede verse en la Figura 1.1. El programa UnrealED, incluido en la instalaci´on del videojuego, fue utilizado para el dise˜no de mapas adecuados para cada experimento. Figura 1.1: Arquitectura de Pogamut, donde “IDE” es NetBeans 6.9.1 y “Local Parser” se trata de un middleware entre GameBots2004 y el cliente, cuyo prop´osito es simplificar el env´ıo y recepci´on de mensajes de GameBots2004 y minimizar la utilizaci´on del ancho de banda transmitiendo ´unicamente la informaci´on que ha cambiado. Se contempl´o la posibilidad de adaptar la plataforma JGAP (Java Genetic Algorithm Plataform) (http://jgap.sourceforge.net/) para la evoluci´on de las CTRNNs en lenguaje de programaci´on Java. No obstante, su utilizaci´on tuvo que ser desechada, ya que JGAP estaba dise˜nada ´unicamente para evaluaciones r´apidas, es decir, de menos de un segundo, ya que aumentaba enormemente el tama˜no de cada poblaci´on de individuos del algoritmo evolutivo, algo inviable para evaluaciones 4 que pueden durar hasta un minuto en este caso. Se tom´o, por tanto, la decisi´on de dise˜nar m´odulos propios para la evoluci´on de las CTRNNs. Por ´ultimo, para la obtenci´on de las gr´aficas necesarias para el an´alisis de las din´amicas de las CTRNNs, se ha utilizado el m´odulo Dynamica (http://mypage.iu.edu/∼rdbeer/) para el programa Mathematica, desarrollado por Randall Beer (1995a). 1.6. Estructura del documento La estructura de esta memoria est´a dividida en cinco cap´ıtulos, adem´as de este cap´ıtulo introductorio. En el cap´ıtulo 2 se expondr´an y justificar´an las t´ecnicas y herramientas utilizadas para la realizaci´on de este proyecto, tales como el entorno de simulaci´on UT2004, las CTRNNs y el algoritmo gen´etico utilizado, as´ı como sus ventajas y limitaciones. Los cap´ıtulos 3, 4 y 5 estar´an dedicados a los experimentos descritos en los puntos 1, 2 y 3 de la secci´on 1.4 respectivamente. Por ´ultimo, en el cap´ıtulo 6 se recogen las conclusiones extra´ıdas a lo largo de los experimentos que componen el proyecto y se proponen las pautas a seguir para trabajos futuros. 1.7. Planificaci´on Durante los 16 meses de duraci´on del proyecto, se han realizado tareas de documentaci´on, redacci´on del manual de Pogamut, implementaci´on de los m´odulos para los experimentos en Pogamut, ejecuci´on y an´alisis de los experimentos, y la redacci´on de una presentaci´on sobre IA en los videojuegos para su exposici´on en las charlas de la asignatura de Inform´atica Gr´afica. El diagrama de Gantt correspondiente a la realizaci´on del proyecto se muestra a continuaci´on en la figura 1.2. Figura 1.2: Diagrama de Gantt de las actividades realizadas. 5 6 Cap´ıtulo 2 T´ecnicas para la evoluci´on de redes neuronales din´amicas en el entorno de simulaci´on UT2004 En este cap´ıtulo se analizan en profundidad las t´ecnicas y herramientas utilizadas para la realizaci´on de los experimentos de este proyecto. En la secci´on 2.1 se analiza el entorno de simulaci´on del videojuego UT2004, as´ı como la plataforma Pogamut. En la secci´on 2.2 se exponen las Redes Neuronales Recurrentes de Tiempo Continuo como controladores de bots. En la secci´on 2.3 se estudia el algoritmo de Evoluci´on Diferencial (Prize, 1999). Por ´ultimo, en la secci´on 2.4 se muestra el dise˜no a seguir para los experimentos de los siguientes cap´ıtulos. 2.1. El entorno de simulaci´on UT2004 y Pogamut 3 El videojuego UT2004 proporciona todas las herramientas necesarias para la creaci´on de los experimentos. La ejecuci´on de bots en UT2004 se realiza por medio del mod GameBots 2004 (GB or GameBots) y el editor Unreal Editor permite crear mapas personalizados para la simulaci´on de los experimentos. La infraestructura de los bots ha sido programada en Java y conectada a UT2004 a trav´es de la plataforma Pogamut 3, gracias a la cual se simplifica el desarrollo del bot y se reduce el tiempo necesario para depurar su comportamiento. Pese a las ventajas que esta plataforma ofrece a la hora de programar nuestros bots para UT2004, la utilizaci´on de este entorno de simulaci´on supone una serie de limitaciones que deber´an tenerse en cuenta a la hora de dise˜nar nuestros experimentos: UT2004 es un entorno en tiempo real, lo que supone que, a pesar de que el flujo del tiempo puede ajustarse, no existe una opci´on“correr a la m´axima velocidad posible”, lo cual ser´ıa muy ´util para reducir el tiempo necesario para las evaluaciones del algoritmo gen´etico (Kadleck, 2008). Un incremento en la velocidad est´andar del juego provocar´ıa fallos en el comportamiento de los bots, ya que no se terminar´ıan de ejecutar todas las instrucciones que determinan su comportamiento, y se producir´ıan por tanto resultados err´oneos (Kadleck, 2008). Los tiempos de ciclo en UT2004 son irregulares. Pese a que es posible configurar manualmente cada cu´anto tiempo GameBots debe ejecutar sus comandos de acci´on (el cual viene predefinido a 0.25 segundos, es decir, 4 acciones por segundo), la mala gesti´on por parte de Pogamut provoca alternancias entre dos valores (siendo el m´as habitual un tiempo de ciclo 7 irregular entre 0.4 y 0.5 segundos, y el menos habitual es un tiempo de ciclo tambi´en irregular entre 0.2 y 0.25 segundos). Debido a la mala gesti´on de los recursos por parte de Pogamut, en ocasiones no terminan de ejecutarse todas las instrucciones y c´alculos necesarios para obtener las salidas de cada una de las redes neuronales, por lo que el comportamiento de dichos bots es err´oneo e incluso se llegan a producir errores irrecuperables en su ejecuci´on. Pogamut permite ejecutar varios bots en paralelo en la misma computadora mediante una sola instrucci´on. No obstante, una vez ejecutados dichos bots, deberemos esperar a que termine su ejecuci´on para poder lanzar el siguiente “paquete” de bots. Esto impide la ejecuci´on en paralelo de varios“paquetes”de bots, tanto en la misma computadora como en computadoras diferentes. Pogamut 3 se encuentra todav´ıa en versi´on beta y al comienzo de este proyecto no contaba con un manual para programadores, por lo que la primera parte de este proyecto consisti´o en la elaboraci´on del mismo. Dicho manual, el cual puede consultarse en el Anexo D, est´a basado en programas de ejemplo y el Javadoc correspondiente a la plataforma, y en ´el se explican todas las herramientas y funcionalidades que ofrece Pogamut y c´omo utilizarlas. 2.2. Redes Neuronales Recurrentes de Tiempo Continuo En contraste con las redes neuronales feed-forward, las cuales soportan ´unicamente comportamientos reactivos, en las Redes Neuronales Recurrentes de Tiempo Continuo (CTRNN) (Beer, 1995a) pueden existir ciclos en su estructura y la activaci´on de sus neuronas es as´ıncrona y multiescalada en el tiempo. Este tipo de redes neuronales tambi´en facilita describir el agente como un sistema din´amico acoplado al entorno en el que est´a ubicado, ya que est´a demostrado que son el modelo m´as simple de red neuronal din´amica continua no lineal (Funahashi y Nakamura, 1993). Adem´as, la interpretaci´on neurobiol´ogica de las CTRNN ha sido demostrada y puede consultarse en (Beer, 1995a). Descripci´on matem´atica de una CTRNN Las CTRNN est´an formadas por neuronas cuyo comportamiento se describe en la ecuaci´on ˙yi=1 τi∗ −yi+ N X j=1 wji ∗σ(yj+θj) + Ii i= 1,2, . . . , N (2.1) σ(x) = 1 1 + e−x(2.2) donde yies el estado de la neurona, wji es el peso de la conexi´on entre las neuronas iyj, θes el t´ermino bias, Irepresenta una entrada externa y τhace que cada una de las neuronas dependa del tiempo, ya que para diferentes valores la ca´ıda del nivel de activaci´on de la neurona es m´as r´apida o lenta. En la f´ormula 2.1 la velocidad de actualizaci´on de la red neuronal debe ser notablemente mayor (el intervalo entre dos actualizaciones ser´a menor) que el valor de τpara no obtener comportamientos no deseados. En el Anexo B se puede encontrar de manera m´as detallada la descripci´on matem´atica de una CTRNN. 8 Valores de activaci´on y de salida de la neurona de una CTRNN Para poder entender c´omo deben interpretarse la activaci´on y la salida de una CTRNN, se va a utilizar una CTRNN formada por una ´unica neurona autoconectada como la de la figura 2.1-A. El valor de salida ode una neurona ser´a un valor real entre 0 y 1 obtenido al aplicar la funci´on sigmoidea (ecuaci´on 2.2) a la suma del estado actual yde la neurona con su valor bias θ,tal y como puede verse en la figura 2.1-B. Figura 2.1: Valor de salida en una CTRNN. Izquierda: Un nodo autoconectado. Derecha: Funci´on sigmoidea aplicada para calcular la salida de una neurona. En cuanto al valor de activaci´on, a diferencia de una red neuronal feed-forward, la cual realiza un mapeo directo entre entrada y salida de la red, el comportamiento de una CTRNN corresponde al de un sistema din´amico (Beer, 1995a), por lo que el valor de activaci´on de la neurona converger´a a un punto de equilibrio. Para el an´alisis de las din´amicas del sistema formado por el agente controlado por la CTRNN y el entorno, se analizar´an sus diagramas de bifurcaci´on, los cuales muestran todos los puntos de equilibrio para la activaci´on de las neuronas de la red. Para saber m´as acerca de la activaci´on de las neuronas y el an´alisis de las din´amicas de un agente controlado por una CTRNN con su entorno se puede consultar el anexo B.3. Modelos de interconexi´on sin´aptica y simetr´ıa bilateral Para la realizaci´on de los experimentos se utilizar´an CTRNNs en las que todas las neuronas est´en totalmente interconectadas (conexi´on de cada neurona con todas las dem´as en ambas direcciones), autoconectadas (conexi´on recurrente de la neurona a s´ı misma) y conectadas a su vez a todos los sensores (todas las neuronas reciben las entradas de los sensores del bot). Adem´as, se buscar´a obtener redes neuronales lo m´as peque˜nas posibles que proporcionen un comportamiento satisfactorio. Otro tipo de redes neuronales muy utilizadas en trabajos de otros autores (Floreano y Mondada, 1994; Beer,1996) son las llamadas redes de Elman. ´ Estas se explican en el Anexo B, en caso de que puedan ser ´utiles para futuros proyectos en los que se trabaje con CTRNNs. En caso de ser posible, se utilizar´a la t´ecnica de simetr´ıa bilateral, gracias a la cual se puede mantener reducido el n´umero de par´ametros a evolucionar. El motivo por el cual podemos aplicar esta t´ecnica, es que algunos de los comportamientos de navegaci´on en este trabajo son intr´ınsecamente sim´etricos, es decir, en ellos se espera que un patr´on sensorial percibido en el lado izquierdo del bot produzca un activaci´on sim´etricamente id´entica a la misma entrada sensorial percibida en el lado derecho. 2.3. Evoluci´on Diferencial En un problema que admita una soluci´on basada en algoritmos gen´eticos se deben escoger aquellas t´ecnicas evolutivas que mejor se adapten al tipo de controlador utilizado. Recientemente, se han realizado estudios que prueban que la t´ecnica de Evoluci´on Diferencial (Prize, 1999) puede 9 ser el candidato m´as ´optimo cuando se pretende modelar sistemas din´amicos no lineales utilizando CTRNNs (de Falco et al., 2008). Esto se debe a que es un algoritmo evolutivo en el cual las variables del problema a optimizar (en este caso los par´ametros de la CTRNN) est´an codificadas como un vector de n´umeros reales, llamado genotipo, cuya longitud es igual al n´umero de variables del problema. Esta codificaci´on como vector de n´umeros reales es ideal para codificar los par´ametros de la CTRNN. Debido a la t´ecnica de selecci´on utilizada por la Evoluci´on Diferencial, las ventajas que presenta ´este algoritmo respecto a los algoritmos gen´eticos tradicionales son: (1) la siguiente generaci´on siempre tendr´a un comportamiento igual o mejor que su antecesora; (2) su operador de mutaci´on utiliza la distribuci´on actual de los vectores en la poblaci´on, lo que permite adaptar la mutaci´on a la situaci´on de b´usqueda propia que tenga el algoritmo, lo cual parece ser una de sus principales ventajas (Prize, 1999). Para una explicaci´on m´as detallada sobre qu´e son y c´omo funcionan en general los algoritmos gen´eticos puede consultarse el Anexo C.1. En el Anexo C.2 se puede encontrar una descripci´on m´as detallada del algoritmo de Evoluci´on Diferencial. Configuraci´on del algoritmo para los experimentos La versi´on est´andar de la Evoluci´on Diferencial se muestra en el Algoritmo 2.1. Se deben tener en cuenta las siguientes consideraciones en cuanto a los par´ametros del algoritmo: La cantidad m´axima de generaciones Gmax depender´a de la complejidad de cada experimen- to. Para que el algoritmo de Evoluci´on Diferencial pueda asegurar cierto ´exito de convergencia a una soluci´on, el tama˜no de la poblaci´on NP debe ser, al menos, 10 veces el tama˜no del genotipo (Prize, 1999). El par´ametro CR controla la influencia del vector de mutaci´on en la generaci´on del vector hijo. Para cada individuo de la poblaci´on tendr´a un valor en el rango [0.2, 0.9] directamente proporcional al su valor de adaptaci´on (el cual se explica m´as adelante). Valores cercanos a 0.9 implican que el vector hijo ser´a muy parecido al vector de mutaci´on. Por el contrario, valores cercanos a 0.2 indican que el vector hijo sera muy parecido al vector padre. El par´ametro Fpermite escalar las diferencias entre vectores para calcular el vector de mutaci´on. Se ha definido de forma que para cada miembro de la poblaci´on se selecciona un n´umero aleatorio en el rango [0.5, 1.0]. La funci´on randint(min,max) regresa un numero entero entre min y max, mientras que rand[0,1) es una funci´on que devuelve un n´umero real entre 0 y 1. Ambas funciones est´an basadas en una distribuci´on uniforme de n´umeros aleatorios. Debido a que los valores del genotipo son n´umeros reales que se encuentran en el rango [0,1], el resultado de la recombinaci´on del vector padre con el vector mutaci´on para la obtenci´on del vector hijo se expresar´a en m´odulo 1. Espacio “Fitness” La funci´on “fitness” o funci´on de adecuaci´on codifica cu´al de los dos individuos, el padre o el hijo, pasar´a a formar parte de la siguiente generaci´on. Al final de cada experimento, se considerar´a como resultado del mismo a aquel individuo de la ´ultima poblaci´on con mayor valor para la funci´on “fitness”. En el caso concreto de este trabajo, tambi´en determinar´a el valor de CR que debe aplicarse en la mutaci´on de cada individuo para la obtenci´on de su vector hijo. En el Anexo C.3 se expone el Espacio “Fitness” propuesto como estructura para describir, evaluar y comparar funciones de adecuaci´on. 10 Algoritmo 2.1 Algoritmo de Evoluci´on Diferencial. Begin G= 0 Crear aleatoriamente la poblaci´on inicial ¯xG∀i, i = 1, .., NP Evaluar f(¯xG)∀i, i = 1, .., NP For G= 1 to Gmax Do For i= 1 to NP Do Seleccionar aleatoriamente r16=r26=r3 jrand =randInt(1, D) For j= 1 to DDo If ((randj[0,1) < CR)or (j=jrand)) then ui j,G+1 =xr3 j,G +F(xr1 j,G −xr2 j,G) Else ui j,G+1 =ui j,G End if End For If (f(¯ui G+1)≤f(¯xi G)) then ¯xi G+1 = ¯ui G+1 Else ¯xi G+1 = ¯xi G End if End For G=G+ 1 End For End 2.4. Dise˜no de los experimentos Para el dise˜no de cada uno de los experimentos se seguir´an los siguientes pasos: 1. Se dise˜nar´an mapas adecuados para la evaluaci´on del comportamiento de cada uno de los individuos de cada generaci´on del algoritmo gen´etico. 2. Se dise˜nar´an el bot seg´un sus sensores para obtener informaci´on del entorno y sus salidas para realizar sus acciones. 3. Se dise˜nar´a el modelo de CTRNN en funci´on su n´umero de neuronas, las conexiones entre las mismas y la existencia de simetr´ıa bilateral, adem´as de definir valores m´ınimos y m´aximos para cada uno de sus par´ametros. 4. Se definir´an los par´ametros para la ejecuci´on del algoritmo de Evoluci´on Diferencial. Adem´as, se dise˜nar´a una funci´on “fitness” o de adecuaci´on que se ajuste al comportamiento deseado para cada bot. 5. Se generar´a una poblaci´on inicial de CTRNNs, cuyos par´ametros se establecer´an alatoriamente, y se har´an evolucionar dichos par´ametros mediante el algoritmo gen´etico de Evoluci´on Diferencial. 6. Al finalizar la ejecuci´on del algoritmo de Evoluci´on Diferencial, se considerar´a como soluci´on al experimento el bot controlado por la CTRNN que haya obtenido mayor valor “fitness” durante el experimento. 11 CONFIGURACI´ ON EXPERIMENTO 1 CTRNN ALG. GEN´ ETICO RAYTRACING Neuronas 6 Entrada Tama˜no Genotipo 10 Sensor 0 -60 2 Salida Tama˜no Poblaci´on 100 Sensor 1 -30 Simetr´ıa Si Num. Generaciones 75 Sensor 2 -10 BOT Evaluaciones Simult´aneas 4 Sensor 3 10 ´ Angulo de giro m´aximo 45 Evaluaciones por bot 3 Sensor 4 30 Velocidad M´axima 0.5 Tiempo Evaluaci´on 20 seg. Sensor 5 60 Tabla 3.3: Configuraci´on del experimento para el primer bot 3.2.3. Resultados del experimento En la gr´afica de la figura 3.4 se pueden ver los valores devueltos por la funci´on“fitness” durante el proceso de evoluci´on. El bot que mejor se adapta a la tarea lo hace con un valor “fitness” de 58,7 %, y sus par´ametros se muestran en la figura 3.5. El hecho de no haber obtenido un bot con un valor de adaptaci´on cercano al 100 % se debe a que la funci´on “fitness” elegida penaliza situaciones inevitables para el bot, como la de girar o que los sensores detecten alg´un obst´aculo. Figura 3.4: Gr´afica con los resultados de la funci´on “fitness” obtenidos durante el proceso de evoluci´on para la obtenci´on de una CTRNN con capacidad de navegaci´on y evitaci´on de obst´aculos. La l´ınea azul muestra el valor obtenido por el mejor individuo de cada generaci´on. La l´ınea discontinua roja muestra la media de todos los individuos de cada generaci´on. En la Figura 3.6 se muestra un ejemplo gr´afico del comportamiento del bot. El hecho de haber introducido un peque˜no error en las salidas de la red neuronal hace que el bot no camine totalmente en l´ınea recta, sino que le permite dar peque˜nos giros que le proporcionan cierta capacidad de exploraci´on del entorno. 18 Figura 3.5: CTRNN con comportamiento de navegaci´on y evitaci´on de obst´aculos en un entorno no estructurado para un bot con estructura de robot Khepera adaptada. Figura 3.6: Ejemplo gr´afico del comportamiento de un bot controlado por la CTRNN resultado del experimento 1 para el modelo 1. [A] El bot localiza un obst´aculo. [B] El bot reacciona y evita el obst´aculo. [C] El bot ha evitado correctamente el obst´aculo sin colisionar contra ´el. 3.2.4. An´alisis del comportamiento del bot Por ´ultimo, se desea comprobar el correcto funcionamiento del bot. Adem´as se desea comprobar si es capaz de solucionar el problema de evitar bloquearse en puntos muertos descrito en la figura 3.2, a pesar de no haber sido entrenado para ello, para lo cual el bot ser´a capaz de regular su velocidad seg´un el valor de la m´as peque˜na de sus salidas, llegando incluso a detenerse si el valor de ´esta es menor de 0.1 (velocidad m´ınima del bot en Pogamut), comportamiento para el cual cual tampoco ha sido entrenado. Para ello, se ha dise˜nado el mapa de la figura 3.7. Al ejecutar el bot, el primer obst´aculo que ´este encontrar´a ser´a el punto muerto de una de las esquinas. Se considerar´a como ´exito que el bot no colisione con ning´un obst´aculo y sea capaz de evitar todos los obst´aculos utilizando para ello menos de 15 ciclos de ejecuci´on. Tras ejecutar el bot 100 veces, se ha obtenido un ´exito del 100 %. Esto nos demuestra no solo el ´exito del experimento a la hora de obtener un bot con el comportamiento de navegaci´on y evitaci´on de obst´aculos, sino tambi´en la flexibilidad por parte de las CTRNNs de adaptarse a situaciones y comportamientos para los cuales no han sido espec´ıficamente entrenadas. 19 Figura 3.7: Mapa para la comprobaci´on del correcto funcionamiento de un bot controlado por una CTRNN con capacidad de navegaci´on y evitaci´on de obst´aculos, el cual adem´as sea capaz de evitar puntos muertos. 3.3. Experimento 2: Seguimiento de trayectorias 3.3.1. Descripci´on del problema En este segundo experimento se busca obtener una CTRNN como controlador para un bot con capacidad de seguir la trayectoria de movimiento de un bot enemigo. Para ello, el bot deber´a ser capaz de girar sobre s´ı mismo siguiendo la trayectoria de otro bot que gire en c´ırculos alrededor suyo. La ventaja que ofrecen las CTRNNs como controlador del bot para esta tarea, frente a la utilizaci´on de redes neuronales feed-forward, es que, gracias su capacidad de memoria a corto plazo, ser´a posible para el bot seguir la trayectoria de otros bots incluso cuando pierda moment´aneamente el contacto visual con ellos. Un claro ejemplo de esto se producir´ıa en condiciones del juego en que el bot al cual se est´a siguiendo desaparezca tras un muro para reaparecer al otro lado del mismo. El bot controlado por la CTRNN debe ser capaz de, si tal cosa sucede, seguir girando y reencontrar a su objetivo, lo cual no ser´ıa posible para una red totalmente reactiva. 3.3.2. Dise˜no del experimento Evoluci´on incremental En este experimento, la evoluci´on se realizar´a de manera incremental en dos fases: 1. En la primera fase, se buscar´a que la CTRNN sea capaz de controlar un bot con capacidad de enfocar a otro bot “objetivo” que permanecer´a est´atico en todo momento, de forma que ´este quede entre los dos rayos internos de su sistema “raytracing”. Para ello, el bot permanecer´a fijo en su lugar de origen y s´olo ser´a capaz de girar sobre s´ı mismo. Al comienzo de la ejecuci´on del bot, ´este podr´a sentir al bot “objetivo” por uno de sus sensores externos. 2. En la segunda fase se realiza a partir de la poblaci´on obtenida tras la primera. Al principio de la ejecuci´on, el bot tiene localizado al bot “objetivo” entre sus dos sensores internos. La CTRNN debe ser capaz de seguir su trayectoria de movimiento. El bot al que se eval´ua s´olo ser´a capaz de girar sobre s´ı mismo, al igual que en la primera fase, mientras que el bot “objetivo” girar´a en c´ırculos alrededor de ´el, de forma que habr´a momentos en los que se ocultar´a al pasar por detr´as de alg´un muro. El bot debe ser capaz de seguir su trayectoria pese a perder el contacto visual durante algunos ciclos. 20 Dise˜no de mapas para la simulaci´on Para este experimento se ha dise˜nado el mapa que podemos ver en la Figura 3.3, el cual se ha dise˜nado por duplicado para poder as´ı realizar varias evaluaciones en paralelo. En la segunda fase del experimento, el bot “objetivo“ girar´a en c´ırculos alrededor del bot que se desea entrenar, movimiento que le lleva a desaparecer tras los muros dos veces por cada vuelta. Figura 3.8: Mapa para el segundo experimento. Adaptaci´on del sistema “Raytracing” Debido al tama˜no del bot“objetivo”, es muy dif´ıcil que los rayos que componen el sistema “raytracing” del bot controlado por la CTRNN impacten directamente en ´el para localizar su posici´on. Debido a ello, gracias a las ventajas que ofrece trabajar en un sistema virtual de simulaci´on, se simula un agrandamiento del bot “objetivo”. Para ello, se ha adaptado el sistema “raytracing” de forma que el sensor se activa si el bot “objetivo” se encuentra a 3 o menos del ´angulo formado por el bot controlado por la CTRNN como v´ertice, el rayo del “raytracing” y la l´ınea que une ambos bots. Para valores mayores a 3 se considera que el bot se encuentra entre dos rayos, por lo que ambos se activan. Debe tenerse en cuenta que el controlador del bot es una red sim´etrica, por lo que en caso de que todos sus sensores devuelvan 0 (es decir, ning´un bot “objetivo” se encuentre en su campo de visi´on), sus motores realizar´an la misma acci´on en sentidos contrarios, provocando como resultado que el bot no realice acci´on alguna. Para evitar esto, se le a˜nade un peque˜no valor aleatorio a la entrada de cada sensor, lo cual le permite girar en uno u otro sentido en busca de otros bots. Funci´on “Fitness” La funci´on “fitness” elegida para este experimento es la funci´on φ=PnumCiclos n=1 ϕ(n) numCiclos (3.3) siendo ϕ(n) = PN i=1 I′ iri, donde I′ i=(1I′ i>0 0otros casos y donde Nes el n´umero de sensores, I′ ies el valor de activaci´on del sensor i, y ries el valor recompensa del sensor i, definido como [0.1, 0.3, 1.0, 1.0, 0.3, 0.1], donde los valores m´as grandes corresponden a los sensores centrales y los m´as peque˜nos a los exteriores. Para esta funci´on “fitness”, la funci´on ϕ(n) se calcula en cada ciclo, y devuelve un valor proporcional al sensor o sensores que est´an localizando al bot objetivo en ese instante, en t´erminos del vector de recompensas. Una vez terminada la evaluaci´on del individuo, la suma de todas las 21 recompensas se dividir´a por el n´umero de ciclos totales, obteni´endose as´ı el porcentaje de la eficiencia a la hora de seguir la trayectoria del bot manteniendo durante el mayor tiempo posible al bot enemigo en el punto de mira. Configuraci´on del experimento La tabla 3.4 recoge los par´ametros para la configuraci´on del experimento. La longitud de los rayos es 50 veces el ´area de colisi´on del bot (en las unidades de medidas utilizadas por UT2004). Los dos valores para el par´ametro “Evaluaciones Simult´aneas” corresponden a la fase 1 y 2 respectivamente. CONFIGURACI´ ON EXPERIMENTO 1 CTRNN ALG. GEN´ ETICO RAYTRACING Neuronas 6 Entrada Tama˜no Genotipo 10 Sensor 0 -17 ➸ 2 Salida Tama˜no Poblaci´on 100 Sensor 1 -10 ➸ Simetr´ıa Si Num. Generaciones 55 Sensor 2 -3 ➸ BOT Evaluaciones Simult´aneas 4 / 2 Sensor 3 3 ➸ ´ Angulo de giro m´aximo 5 ➸ Evaluaciones por bot 2 Sensor 4 10 ➸ Velocidad Bot Objetivo 0,4 Tiempo Evaluaci´on 30 seg. Sensor 5 17 ➸ Tabla 3.4: Configuraci´on del experimento para el segundo bot 3.3.3. Resultados En la gr´afica de la figura 3.9 se pueden ver los valores devueltos por la funci´on“fitness” durante el proceso de evoluci´on. Tras la ejecuci´on de la primera fase del experimento durante las 10 primeras generaciones, se ha obtenido un bot con un valor de adaptaci´on de 99.61 %. Como se puede apreciar, tan s´olo han sido necesarias dos generaciones para alcanzado dicho valor. En la Figura 3.10 puede verse un ejemplo gr´afico del comportamiento obtenido. Para asegurar el correcto funcionamiento de la CTRNN obtenida, se ejecut´o el bot 100 veces durante 20 segundos cada una, considerando como ´exito que al final de la ejecuci´on del bot, el bot “objetivo” estuviese entre los dos rayos centrales del sistema “raytracing”. El bot tuvo ´exito en la tarea un 100 % de las veces, ´exito tras el cual se decidi´o comenzar la segunda fase del experimento. Tras la ejecuci´on de la segunda fase del experimento hasta llegar a 55 generaciones, se ha obtenido un bot con un valor de adaptaci´on de 78.71 %. La reducci´on de ´este valor se debe a que en esta ocasi´on, el bot “objetivo” se encuentra en movimiento, por lo que habr´a ciclos en los que el bot controlado por la CTRNN lo localizar´a por sus rayos intermedios o incluso externos, o incluso por ninguno en caso de que desaparezca tras un muro. Adem´as, en la gr´afica de la figura 3.9 se aprecia un descenso del valor “fitness” en la transici´on de la fase 1 a la 2, ya que la CTRNN tiene que adaptarse al nuevo comportamiento. La CTRNN obtenida como resultado tras el experimento gen´etico es la mostrada en la Figura 3.11. En la Figura 3.12 podemos ver un ejemplo gr´afico de su capacidad de seguir a un objetivo incluso cuando ´este desaparece tras un muro. Para asegurar el correcto funcionamiento de la CTRNN, se ejecut´o el bot 100 veces durante 30 segundos cada una, considerando como fracaso el hecho de que el bot no perdiese a su objetivo durante m´as de 15 ciclos de ejecuci´on. El bot tuvo ´exito en la tarea en un 92 % de las veces. Tras observar su comportamiento, se lleg´o a la conclusi´on de el 8 % de ejecuciones no exitosas ven´ıa provocado por el hecho de que justo antes de que el bot “objetivo” desaparezca tras el muro, el bot controlado por la CTRNN se adelanta a su trayectoria de movimiento y lo localiza con la parte del “raytracing” que le hace girar en sentido contrario a la trayectoria de movimiento del bot para esperarlo. 22 Figura 3.9: Gr´afica con los resultados de la funci´on “fitness” obtenidos tras el proceso de evoluci´on para la obtenci´on de una CTRNN con capacidad de seguimiento de las trayectorias de movimiento de otros bots. La l´ınea azul muestra el valor obtenido por el mejor individuo de cada generaci´on. La l´ınea discontinua roja muestra la media de todos los individuos de cada generaci´on. La l´ınea discontinua vertical muestra la transici´on de la primera fase (fase de localizaci´on) a la segunda (fase de seguimiento). Figura 3.10: Ejemplo gr´afico del comportamiento de dos bots controlados por la CTRNN resultado de la primera fase del experimento 2. 3.4. Conclusiones: memoria a corto plazo en CTRNNs con recurrencias entre sus nodos Como se ha podido ver, las recurrencias entre los nodos de la CTRNN dotan a ´esta de una memoria a corto plazo que permite realizar tareas que ser´ıan imposibles para una red neuronal feed-forward, incluso cuando se utilizan CTRNNs sim´etricas tan sencillas como las utilizadas en ´este cap´ıtulo, con solo dos neuronas totalmente autoconectadas e interconectadas. En el primer experimento se ha podido comprobar c´omo un bot con estructura de robot Khepera adaptada y controlado por una CTRNN obtenida mediante aprendizaje evolutivo, es capaz de un comportamiento de navegaci´on y evitaci´on de obst´aculos. Adem´as, se ha comprobado que, a pesar de no haber sido entrenado expl´ıcitamente para ello, es capaz de regular su velocidad y evitar puntos 23 Figura 3.11: CTRNN con comportamiento de seguimiento de trayectorias de movimiento de otros bots para un bot con estructura de robot Khepera adaptada. Figura 3.12: Ejemplo gr´afico del comportamiento de un bot controlado por la CTRNN resultado del experimento 2. [A] El bot sigue la trayectoria de su objetivo. [B] El objetivo se oculta tras un muro. [C] El objetivo reaparece y el bot ha sido capaz de seguir su trayectoria. muertos sin quedarse bloqueada, lo cual a su vez muestra la flexibilidad de este tipo de redes para adaptarse a situaciones y comportamientos para los cuales no han sido espec´ıficamente entrenadas. En el segundo experimento se ha obtenido con ´exito mediante aprendizaje evolutivo un bot controlado por una CTRNN, cuyas recurrencias entre sus nodos le permit´ıan seguir la trayectoria del bot “objetivo” incluso cuando ´este desaparec´ıa tras un muro, para lo cual ten´ıa en cuenta su comportamiento anterior. Una vez estudiado el efecto que tienen en el comportamiento de las CTRNNs las recurrencias entre sus nodos, en el siguiente cap´ıtulo se estudiar´a su capacidad de aprendizaje en el tiempo de ejecuci´on del bot cuando se obtienen CTRNNs cuyas neuronas presentan actividad multiescalada en el tiempo. En cuanto al entorno de simulaci´on UT2004, los experimentos realizados muestran la posibilidad de aplicar la b´usqueda de soluciones mediante el aprendizaje evolutivo en el videojuego utilizando Pogamut para la obtenci´on de CTRNNs con pocos par´ametros. 24 Cap´ıtulo 4 Aprendizaje en CTRNNs sin plasticidad sin´aptica durante el tiempo de vida del bot El objetivo de este cap´ıtulo es el de obtener un bot controlado por una CTRNN sin plasticidad sin´aptica con capacidad de aprendizaje en tiempo real, es decir, el bot ser´a capaz de aprender sin realizar cambios en los par´ametros de la red. En la secci´on 4.1 se describe el experimento y el comportamiento deseado para el bot. La secci´on 4.2 est´a dedicada a la obtenci´on mediante evoluci´on de la CTRNN. En la secci´on 4.3 se analiza la capacidad de la CTRNN obtenida de aprender sin plasticidad sin´aptica. En la secci´on 4.4 se realiza un an´alisis de las din´amicas de dicha CTRNN con su entorno para analizar de manera formal y en profundidad el comportamiento del bot a partir de sus diagramas de bifurcaci´on. Por ´ultimo, en la secci´on 4.5 se muestran las conclusiones extra´ıdas del experimento. 4.1. Descripci´on del experimento A la hora de elegir un determinado comportamiento para el bot, en el cual se requiera aprendizaje durante su tiempo de ejecuci´on, se ha optado por adaptar al entorno UT2004 el comportamiento mostrado por el nematodo Caenorhabditis elegans (Hedgecock y Rusell,1975). Dicho comportamiento consiste en asociar dos est´ımulos (aprendizaje asociativo): temperatura y comida. La elecci´on de este modelo se debe a que el C. elegans es una elecci´on muy com´un entre los investigadores en el ´area de la evoluci´on de CTRNNs, ya que muestra comportamientos lo suficientemente sencillos como para poder ser modelados por CTRNNs peque˜nas y suficientemente complejos como para explotar las capacidades de memoria de las mismas (Izquierdo, 2008). A la hora de adaptar este modelo al entorno UT2004 utilizando Pogamut, se utiliza un entorno 2D con un gradiente de altura a lo largo de una de sus dimensiones, el cual se muestra en la figura 4.1-A. En ´el habr´a 2 tipos de base: “enemiga” y “aliada”. Cada base puede encontrarse solo en regiones con un rango particular de alturas: “alta” entre [9,10] y “baja” entre [-10,-9]. La regi´on en la que se encuentra cada base depende del tipo de entorno: en el A-ent la base “enemiga” se encuentra en la regi´on “alta” y la “aliada” en la “baja”, mientras que en el B-ent la base “enemiga” se encuentra en la regi´on “baja” y la “aliada” en la “baja”. El gradiente de altura se extiende por todo el entorno, el cual est´a libre de obst´aculos. Para ello, se ha dise˜nado un entorno como el que se muestra en la figura 4.1-B. Se pretende que el bot sea capaz de asociar durante su ejecuci´on altura y base “enemiga” en cada uno de los entornos descritos y memorizarla para volver a dicha altura en caso de ser reubicado en el centro del mapa. Para ello, el bot aparecer´a en la posici´on 0 del gradiente de altura en una 25 Figura 4.1: Entorno de simulaci´on para el experimento. (A) Entorno de simulaci´on te´orico bidimensional, con un gradiente de alturas, en el que la base “enemiga” puede ser localizada en una de las dos franjas representadas por regiones a puntos. (B) Entorno de simulaci´on en UT2004, en el que el gradiente es la altura a la que se encuentra el bot, y las franjas roja y azul representan d´onde se encuentran las bases “alta” y “baja” respectivamente. orientaci´on aletoria. A partir de ese momento, el bot contar´a con 200 ciclos de ejecuci´on para desplazarse por todo el entorno en busca de la base “enemiga” y permanecer en esa regi´on lo m´as eficientemente posible. Una vez pasados los 200 ciclos, el bot se vuelve a situar en la altura 0 con una orientaci´on aleatoria, y debe ser capaz de subir o bajar en el gradiente de altura dependiendo de si en la ejecuci´on anterior aprendi´o que estaba en un entorno A-ent o B-ent. En caso de que se cambie el tipo de entorno, el bot tiene que ser capaz de reaprender y cambiar su preferencia de altura. El bot, al igual que en los experimentos del cap´ıtulo anterior, se considera como un cuerpo redondo con dos motores diametralmente opuestos, solo que esta vez tiene ´unicamente dos sensores: Los motores permiten al agente moverse hacia adelante y girar. La velocidad de cada uno de ellos depende directamente de la el valor devuelto por una de las neuronas de salida (un valor entre [0,1)). Por ello, la velocidad de movimiento ser´a directamente proporcional a la salida de la neurona con un valor menor (un valor entre 0 y la velocidad m´axima del bot). En cuanto al giro, ´este ser´a proporcional a la diferencia entre el valor del motor derecho y el izquierdo (un valor negativo producir´ıa un giro a la izquierda y un valor positivo a la derecha) y est´a acotado por un valor m´aximo de giro. El sensor de altura puede tener cualquier valor real. El sensor de “base” devuelve un valor 0 a no ser que el bot se encuentre en una de las bases: devolver´a B=1 si se encuentra en la base“enemiga”, y B=-1 si se encuentra en la base“aliada”. 4.2. Aprendizaje evolutivo para la obtenci´on de la CTRNN El modelo utilizado en este experimento es el de una CTRNN con todas sus neuronas totalmente conectadas e interconectadas. As´ı pues, dado que el modelo de la neurona para este experimento est´a basado en la ecuaci´on de la CTRNN 2.1 descrita en la secci´on 2.2, al aplicar la integraci´on de Euler con un tiempo de ciclo Δtpara la activaci´on de los nodos en simulaci´on, se obtiene la ecuaci´on 26 yi(n+ 1) = yi(n) + Δt τi∗ −yi+ N X j=1 wji ∗σ(yj+θj) + siA(x) + giB(x;e) i= 1,2, . . . , N (4.1) donde ies un ´ındice (i= 1,2, ..., N), Nes el n´umero de neuronas, yies el estado de la neurona, Δtes el tiempo de ciclo para la integraci´on, τies la constante temporal de activaci´on de la neurona, wji es el peso de la conexi´on entre las neuronas iyj,θes el t´ermino bias, σv(x) es la funci´on sigmoidal (ecuaci´on 2.2), A(x) es el sensor de altura, sies el peso de de la conexi´on del sensor de altura, B(x;e) es el sensor de base (el cual depende del tipo de entorno), y gies el peso de de la conexi´on del sensor de base. Al igual que para los experimentos del cap´ıtulo anterior, el valor de Δtse ha establecido en 0.4 segundos. Debido a la complejidad del experimento, el proceso de evoluci´on no se realizar´a desde cero utilizando Pogamut, como era el caso de los experimentos del cap´ıtulo anterior. Si se pretendiese realizar tal experimento en Pogamut para una CTRNN similar, la cual estar´ıa descrita por un genotipo seg´un el cromosoma de 32 genes de la tabla 4.1, dado a que ´este no permite paralelizar las evaluaciones de las poblaciones del algoritmo gen´etico (como se ha comentado en la secci´on 2.1), se estima una duraci´on para el experimento de duraci´on =200 ciclos/ejecuci´on ∗9ejecuciones/individuo ∗320 individuos/generaci´on 60 seg/min ∗60 min/hora ∗24 horas/d´ıa ∗365 d´ıas/a˜no ∗ ∗320 generaciones ∗0,4segundos/ciclo 60 seg/min ∗60 min/hora ∗24 horas/d´ıa ∗365 d´ıas/a˜no = 2,33 a˜nos. (4.2) Debido a ello, en este proyecto se propone adaptar la CTRNN ya entrenada para el comportamiento de preferencia de temperatura del C. elegans al entorno UT2004. Se tomar´a como punto de partida el modelo de CTRNN que se ha demostrado obtiene mejores resultados para un comportamiento de preferencia de temperatura por parte del C. elegans. Dicho modelo consiste en una CTRNN de cuatro neuronas totalmente interconectadas y autoconectadas, las neuronas motoras son sim´etricamente inversas y con el par´ametro temporal de una de las neuronas no motoras m´as alto que el de las dem´as (lo que la hace m´as “lenta”). Se crear´a una poblaci´on inicial de 50 individuos, definidos todos ellos por el genotipo que define este modelo CTRNN, a partir de la cual se realizar´a el proceso de evoluci´on durante 45 generaciones. Se ha modificado ligeramente la t´ecnica de mutaci´on (ver algoritmo 2.1) de manera que ui j,G+1 =xr3 j,G +F(xr1 j,G −xr2 j,G) =⇒ui j,G+1 =xr3 j,G +F1∗xr1 j,G −F2∗xr2 j,G), ya que si no, al ser id´enticos todos los individuos de la poblaci´on inicial, la mutaci´on tal y como est´a definida ser´ıa un proceso in´util, ya que el t´ermino F(xr1 j,G −xr2 j,G)siempre devolver´ıa cero. Se estima una duraci´on para el proceso de evoluci´on definido de 5 d´ıas y medio. Cromosoma 4 neuronas τ1θ1A1B1wi1τ2θ2A2B2wi2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 τ3θ3A3B3wi3τ4θ4A4B4wi4 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Tabla 4.1: Codificaci´on del cromosoma de una CTRNN con neuronas totalmente interconectadas y autoconectadas con 4 neuronas y 2 entradas. El hecho de tener que realizar el proceso de evoluci´on a partir de una CTRNN obtenida en otro sistema de simulaci´on diferente a UT2004, y por consiguiente con condiciones diferentes (la 27 34 Cap´ıtulo 5 Combinaci´on de CTRNNs para la obtenci´on de un sistema escalable A la hora de dise˜nar un bot para un videojuego, no es suficiente con que ´este sea capaz de realizar una sola tarea, como es el caso de los bots obtenidos en los cap´ıtulos anteriores, los cuales ten´ıan el objetivo de probar caracter´ısticas concretas de las CTRNNs como controladores de bots. Por tanto, en este cap´ıtulo se buscar´a obtener bots con capacidad de varios comportamientos. En la secci´on 5.1 se describe el m´etodo utilizado para combinar estos comportamientos y el problema de escalabilidad, que surge a la hora de obtener redes cada vez m´as complejas. En la secci´on 5.2 se muestran el dise˜no de la CTRNN y del experimento de evoluci´on. En la secci´on 5.3 se muestran los resultados del experimento. Por ´ultimo, la secci´on 5.4 recoge las conclusiones extra´ıdas de la ejecuci´on del experimento. 5.1. M´etodo utilizado y el problema de la escalabilidad La escalabilidad y, como consecuencia, la posibilidad de abordar problemas cada vez m´as complicados, es el gran muro a la hora de obtener agentes aut´onomos con comportamientos complejos, como afirma Arkin (1998). Los algoritmos gen´eticos trabajan correctamente cuando los datos son pocos, el espacio de estados es peque˜no y es aceptable una b´usqueda. Cuando el espacio de estados es inmenso, la utilizaci´on de algoritmos gen´eticos puede llegar a ser inviable (Jakobi, 1998). Una opci´on ser´ıa la de obtener CTRNNs como controladores de bots que realicen tareas simples, como es el caso de las obtenidas a lo largo de este proyecto, y combinar sus mecanismos para desarrollar ciertas tareas m´as complejas, pero no es tan evidente. A la hora de combinar dos CTRNNs con comportamientos sencillos, Beer (1995a) explica que no es posible montar las salidas de una sobre la entrada de la otra, ya que esto cambiar´ıa las condiciones iniciales en la ejecuci´on de la red que recibiese la salida. En cuanto al juego de guerra de tanques de Bourquin (2004), ´este evoluciona dos CTRNNs, una con comportamiento de navegaci´on en un entorno no estructurado y otra con capacidad para apuntar a tanques enemigos. A la hora de combinar ambos comportamientos, su soluci´on es la de evolucionar la segunda red sobre un tanque con un comportamiento de navegaci´on ya definido. De esta manera, consigue que el segundo comportamiento se adapte al primero, pero no lo contrario. Debido a que no se han demostrado todav´ıa las pautas a seguir a la hora de obtener CTRNNs complejas como combinaci´on de otras CTRNNs con comportamientos simples, para combinar los comportamientos de dos CTRNNs en un mismo bot, en este cap´ıtulo se presenta la siguiente estrategia a seguir: se buscar´a obtener, mediante aprendizaje evolutivo, una CTRNN capaz de elegir en cada ciclo, seg´un la situaci´on en la que se encuentre, la salida de una de dos CTRNNs, cada una de las cuales posee uno de los comportamientos deseados para el bot. 35 En concreto, se buscar´a obtener un bot con los comportamientos proporcionados por las siguientes CTRNNs: (1) la CTRNN con comportamiento de navegaci´on y evitaci´on de obst´aculos en un entorno no estructurado, obtenida tras el primer experimento del cap´ıtulo 3; (2) la CTRNN obtenida tras el experimento 4, con un comportamiento de b´usqueda y memorizaci´on de la base enemiga. Se pretende con ello obtener un bot con capacidad de navegaci´on completa, es decir, que sea capaz de buscar y memorizar la posici´on de la base enemiga durante su ejecuci´on, a la vez que sea capaz de esquivar los obst´aculos que encuentre en el entorno. 5.2. Dise˜no del experimento Modelado de la CTRNN Para la obtenci´on del comportamiento de selecci´on deseado para el bot, se ha dise˜nado una CTRNN como la de la figura 5.1. Como se puede ver lo que se tiene son tres CTRNNs. La de la izquierda tiene un comportamiento de esquivaci´on de los obst´aculos que encuentre en el entorno, aprendido en el cap´ıtulo 3. La de la derecha tiene un comportamiento de b´usqueda y memorizaci´on de la posici´on de la base enemiga, obtenido en el experimento del cap´ıtulo 4. Por ´ultimo, a la CTRNN de en medio, formada por una ´unica neurona autoconectada, se le aplicar´a la t´ecnica de aprendizaje evolutivo para obtener un comportamiento de selecci´on entre las salidas de las otras dos CTRNNs. Para elo, recibe los valores de algunos los sensores de las dos CTRNNS que componen el sistema: los valores de los sensores raytracing de la CTRNN de la izquierda, cuyos pesos son sim´etricos, y el valor base de la CTRNN de la derecha. Para un valor de salida o1<0,5, el bot se comporta seg´un las salidas de la CTRNN de la izquierda, y si o1>0,5 se comporta seg´un las salidas de la CTRNN de la derecha. Figura 5.1: CTRNN compuesta por las obtenidas en los experimentos del experimento 1 del cap´ıtulo 3 y el del cap´ıtulo 4. La neurona 1 est´a autoconectada, recibe los valores de los sensores base de la CTRNN de la derecha y los valores de los sensores si proporcionados por los rayos del sistema “raytracing” de la CTRNN de la izquierda, y se encarga de seleccionar una de las dos CTRNNs para ejecutar las acci´on del bot. 36 Dise˜no del mapa para la simulaci´on El entorno de simulaci´on dise˜nado corresponde al del mapa de la figura 5.2. Como puede apreciarse, se trata de un entorno similar al del experimento del cap´ıtulo 4, pero con obst´aculos en el que el bot deber´a ser capaz de moverse sin colisionar. Figura 5.2: Mapas para el experimento de obtenci´on de una CTRNN como combinaci´on de otras CTRNNs. Funci´on “Fitness” La funci´on “fitness” elegida es φ=PnumEjecuciones i=1 (numCiclos −numColisionesi)∗(baseEnemigaEncontradai) numEjecuciones (5.1) donde numEjecuciones es el n´umero de b´usquedas de la base enemiga, numCiclos es el n´umero de ciclos de vida del bot, numColisionesies el n´umero de ciclos que el bot ha permanecido en colisi´on con un obst´aculo, baseEnemigaEncontradaitiene un valor de 1 si se ha encontrado la base enemiga en la ejecuci´on iy 0 en caso contrario. Como se puede apreciar, la funci´on premia el hecho de que el bot sea capaz de encontrar la base enemiga sin colisionar con los obst´aculos, lo cual es posible, ya que a pesar de que la CTRNN obtenida en el experimento 1 del cap´ıtulo 3 es capaz de regular su velocidad e incluso de detenerse para no colisionar, en caso de que la red elija el otro comportamiento se producir´ıa la colisi´on. En caso de que el bot no encuentre la base enemiga, el valor sumado al total del valor fitness en esa ejecuci´on es 0, lo cual supone una gran penalizaci´on. Configuraci´on de los par´ametros para el experimento La tabla 5.1 recoge los par´ametros para la configuraci´on del experimento. Debe tenerse en cuenta que la longitud de los rayos que componen el sistema de sensores “raytracing” es 10 veces el ´area de colisi´on del bot (en las unidades de medida utilizadas por Unreal). 5.3. Resultados del experimento En la gr´afica de la figura 5.3 se pueden ver los valores devueltos por la funci´on “fitness” para el experimento. El bot que mejor se adapta a la tarea lo hace con un valor“fitness” del 100 %, y sus par´ametros se muestran en la tabla 5.2. Para comprobar el correcto funcionamiento de la CTRNN, se ha 37 CONFIGURACI´ ON EXPERIMENTO 1 CTRNN ALG. GEN´ ETICO RAYTRACING Neuronas 7 Entrada Tama˜no Genotipo 7 Sensor 0 -60 1 Salida Tama˜no Poblaci´on 70 Sensor 1 -30 Simetr´ıa Si Num. Generaciones 100 Sensor 2 -10 τ[e0,e4] Evaluaciones Simult´aneas 4 Sensor 3 10 θ[-2,2] Evaluaciones por bot 1 Sensor 4 30 ω[-5,5] Tiempo Evaluaci´on 300 ciclos Sensor 5 60 Tabla 5.1: Configuraci´on del experimento para el cuarto bot Figura 5.3: Gr´afica con los resultados de la funci´on “fitness” obtenidos tras el proceso de evoluci´on para la obtenci´on de una CTRNN capaz de elegir entre el comportamiento de una de las CTRNNs que la componen para con capacidad de navegaci´on y evitaci´on de obst´aculos. La l´ınea azul muestra el valor obtenido por el mejor individuo de cada generaci´on. La l´ınea discontinua roja muestra la media de todos los individuos de cada generaci´on. ejecutado un bot controlado por la misma 100 veces, en las mismas condiciones, con la misma configuraci´on y la misma funci´on “fitness” utilizadas para el aprendizaje evolutivo. Se ha obtenido un ´exito del 100 %, por lo que consideramos que la CTRNN se adapta satisfactoriamente a la tarea deseada, ya que el bot controlado por ella ha encontrado la base enemiga en todas sus ejecuciones sin colisionar con ning´un obst´aculo. 5.4. Conclusiones: combinaci´on de comportamientos de CTRNNs A la hora de obtener bots con varios comportamientos, cada uno de los cuales es realizado por una CTRNN diferente, en este cap´ıtulo se ha considerado suficiente el intentar obtener un bot con un comportamiento de selecci´on entre dos comportamientos posibles seg´un la situaci´on en la que se encuentre. Se ha comprobado que es posible obtener una CTRNN capaz de seleccionar en cada ciclo de ejecuci´on entre las salidas de dos CTRNNs que ya sean capaces de realizar los comportamientos deseados. Gracias a ello, se ha conseguido obtener un bot con capacidad de navegaci´on compleja, ya que el bot tiene el objetivo de encontrar la base enemiga en cada una de sus ejecuciones y, adem´as, es capaz de evitar obst´aculos en su camino para conseguir dicho objetivo. 38 y1 τ1,0100 θ0,9817 s0 -3,6816 s1 -4,6967 s2 -2,6003 s3 1,0035 s4 4,6429 s5 4,8518 base -2,1309 y1 4,2978 Tabla 5.2: Par´ametros para la mejor CTRNN que permite selecionar entre los comportamientos de navegaci´on y esquivaci´on de obst´aculos por un lado, y de b´usqueda y memorizaci´on de la localizaci´on de la base enemiga por el otro. Se puede asegurar que ´esta capacidad por parte de la CTRNN de selecci´on entre los comportamientos de diferentes CTRNNs es posible para un n´umero de comportamientos reducido. Aunque en este caso se ha probado para dos ´unicos comportamientos, se presume que ´esta capacidad seguir´ıa presente en una CTRNN de dos neuronas totalmente interconectadas y autoconectadas para cuatro comportamientos. No obstante, el uso de la escalabilidad para obtener CTRNNs con comportamientos cada vez m´as complejos a partir de la combinaci´on de CTRNNs con comportamientos simples todav´ıa es un caso de estudio, por lo que no se puede asegurar que ´este sea aplicable seg´un aumenta la complejidad del problema (Jakobi, 1998). 39 40 Cap´ıtulo 6 Conclusiones 6.1. Resultados obtenidos El objetivo de este proyecto era el de obtener bots para el videojuego UT2004 controlados por Redes Neuronales Recurrentes de Tiempo Cont´ınuo (CTRNN), de forma que se estudiasen y aprovechasen las recurrencias entre sus nodos y su actividad multiescalada en el tiempo para obtener bots con comportamientos que ser´ıan imposibles si se utilizasen controladores basados en redes neuronales feed-forward. Para ello, se ha utilizado el aprendizaje evolutivo para obtener cuatro bots controlados por CTRNNs: 1. En el cap´ıtulo 3 se han obtenido dos bots que utilizan las recurrencias entre los nodos de la CTRNN para obtener comportamientos que requer´ıan memoria a corto plazo: a) Un primer bot con un comportamiento de navegaci´on y evitaci´on de obst´aculos en el entorno no estructurado de UT2004. b) Un segundo bot con capacidad para seguir la trayectoria de movimiento de un bot enemigo, incluso cuando lo pierde moment´aneamente de vista al desaparecer ´este tras un muro, para lo cual tendr´a que poder “predecir” su reaparici´on. 2. En el cap´ıtulo 4 se ha obtenido un bot controlado por una CTRNN capaz de aprender durante el tiempo de ejecuci´on del bot, sin variar para ello el valor de sus par´ametros (CTRNN sin plasticidad sin´aptica). Para ello, la CTRNN hace uso de la actividad multiescalada en el tiempo para localizar y memorizar la localizaci´on de la base enemiga seg´un la altura en que ´esta se encuentra. 3. En el cap´ıtulo 5 se ha obtenido un bot controlado por una CTRNN capaz de seleccionar entre los comportamientos obtenidos para la CTRNN obtenida en el primer experimento del cap´ıtulo 3 y la obtenida en el cap´ıtulo 4, seg´un la situaci´on en la que se encuentra. El bot obtenido es capaz de navegar en el entorno con el objetivo de localizar y memorizar la altura a la que se encuentra la base enemiga a la vez que evita los obst´aculos que encuentra en su camino. A continuaci´on, se muestran las conclusiones extra´ıdas tras analizar los resultados de estos experimentos. 6.2. Recurrencias entre los nodos de la red para comportamientos con necesidad memoria a corto plazo Como se ha podido ver en el cap´ıtulo 3, las recurrencias entre los nodos de la CTRNN dotan a ´esta de una memoria a corto plazo que permite realizar tareas que ser´ıan imposibles para una red 41 neuronal feed-forward. En los experimentos dedicados a la obtenci´on de cada bot se han podido observar las siguientes particularidades: 1. Primer bot a) Es capaz de un comportamiento de navegaci´on y evitaci´on de obst´aculos en el entorno no estructurado de UT2004. b) Se ha comprobado su ventaja respecto a las redes neuronales feed-forward al ser capaz de evitar puntos muertos. c) A pesar de no haber sido entrenado expl´ıcitamente para ello, es capaz de regular su velocidad y evitar puntos muertos sin quedarse bloqueado. ´ Esto muestra la flexibilidad de este tipo de las CTRNNs para adaptarse a situaciones y comportamientos para los cuales no han sido espec´ıficamente entrenadas. 2. Segundo bot a) Las recurrencias entre sus nodos lo dotan de una memoria a corto plazo que le permite seguir su trayectoria de movimiento cuando ha perdido de vista al bot “objetivo” al desaparecer ´este tras un muro, lo que le permite“preveer” el momento de su reaparici´on. b)´ Este tipo de comportamiento ser´ıa imposible utilizando redes neuronales feed-forward, ya que al desaparecer el bot “objetivo” tras el muro, el bot controlado por la red no sabr´ıa ni en qu´e direcci´on ni a qu´e velocidad girar para reencontrarlo, al depender su comportamiento ´unicamente de la informaci´on recibida en cada ciclo. Se ha visto como ´esta capacidad de memoria a corto plazo, surge incluso cuando se utilizan CTRNNs sim´etricas tan sencillas como las utilizadas en el cap´ıtulo 3, con solo dos neuronas totalmente autoconectadas e interconectadas, y es suficiente para satisfacer los comportamientos de navegaci´on que se buscaban. 6.3. Activaci´on multiescalada en el tiempo para un comportamiento de aprendizaje en tiempo de ejecuci´on En el cap´ıtulo 4 se ha podido comprobar lo siguiente: 1. Debido a la caracter´ıstica de las CTRNNs de que sus neuronas trabajen con diferentes tiempos de activaci´on, un bot es capaz de aprender durante su tiempo de ejecuci´on sin cambiar ninguno de los par´ametros de la red (CTRNNs sin plasticidad sin´aptica). 2. Se ha comprobado adem´as que el comportamiento por parte de la CTRNN para realizar satisfactoriamente el comportamiento de aprendizaje asociativo para el que se ha entrenado no es siempre tan predecible como a priori pueda parecer. Una vez analizadas las din´amicas del agente con su entorno, se ha visto c´omo el agente ten´ıa un comportamiento en el que ignoraba ideas preconcebidas en su dise˜no: a) En primer lugar, la CTRNN resultante ten´ıa un comportamiento seg´un el cual ignoraba el hecho de estar en la base aliada (indicado por un valor base=-1) y optaba por un comportamiento de ascender y descender en el gradiente de alturas en busca de la base enemiga. b) En segundo lugar, pese a haberse dise˜nado el experimento seg´un un modelo de aprendizaje asociativo con condicionamiento cl´asico (asociando altura y base enemiga), la CTRNN obtenida tambi´en muestra capacidad de aprendizaje asociativo con condicionamiento operativo (asociando est´ımulo con comportamiento). 42 6.4. Combinaci´on de CTRNNs para comportamientos complejos En el cap´ıtulo 5, se ha comprobado la posibilidad de obtener un bot con un comportamiento resultante de la combinaci´on de los comportamientos del primer y el tercer bot. Para ello, se ha conseguido obtener una CTRNN con un comportamiento de selecci´on entre uno de estos dos comportamientos seg´un la situaci´on en la que se encuentre. Del resultado de este experimento, se deduce que es posible obtener una CTRNN capaz de elegir entre las salidas de dos CTRNNs que ya sean capaces de realizar los comportamientos deseados para el bot. Gracias a ello, se ha conseguido obtener un bot con capacidad de navegaci´on compleja, ya que el bot tiene el objetivo de encontrar la base enemiga en cada una de sus ejecuciones y, adem´as, es capaz de evitar obst´aculos en su camino para conseguir dicho objetivo. No obstante, no se puede asegurar que esta t´ecnica de combinaci´on de comportamientos sea aplicable seg´un aumenta la complejidad del problema, ya que el uso de la escalabilidad para obtener CTRNNs con comportamientos cada vez m´as complejos a partir de la combinaci´on de CTRNNs con comportamientos simples todav´ıa es un caso de estudio (Jakobi, 1998). 6.5. Algoritmos Gen´eticos y CTRNNs en UT2004 utilizando Pogamut Mediante la realizaci´on de este proyecto, se pretend´ıa establecer las bases para abrir un nuevo ´area de investigaci´on para futuros proyectos, tal y como es el ´area de la Inteligencia Artificial en videojuegos en general, y la evoluci´on de CTRNNs como controladores de bots en particular: 1. Programaci´on de IA en videojuegos utilizando Pogamut La primera tarea ha consistido en realizar un estudio de la plataforma Pogamut como herramienta de programaci´on de IA para bots en el entorno UT2004. Como primer resultado, desde un punto de vista gen´erico se ha elaborado el manual del Anexo D, el cual pretende funcionar como manual de consulta a la hora de programar bots en el videojuego UT2004. Las conclusiones obtenidas de la utilizaci´on de esta plataforma son las siguiente: Pogamut permite programar en Java, nos abstrae de las tareas de conexi´on al videojuego y nos proporciona herramientas muy ´utiles para la programaci´on de IA en UT2004 no diponibles en el videojuego (como por ejemplo “raytracing”). Aprender a utilizar Pogamut supone poder contar con una herramienta pionera y con futuro en el ´area de investigaci´on de IA en videojuegos, utilizada incluso en el campeonato a nivel mundial 2K BotPrize. A pesar de sus ventajas, cabe destacar que Pogamut todav´ıa est´a en fase de desarrollo, por lo que todav´ıa contiene errores de programaci´on y produce errores en la ejecuci´on de los bots, lo que debe tenerse en cuenta a la hora de trabajar con ´el. 2. Algoritmos gen´eticos para la obtenci´on de CTRNNs en Pogamut Para la obtenci´on de CTRNNs como controladores de bots utilizando el algoritmo de Evoluci´on Diferencial, del trabajo realizado se deduce lo siguiente: Los experimentos realizados en el cap´ıtulo 3 muestran la posibilidad de aplicar la b´usqueda de soluciones mediante el aprendizaje evolutivo en el videojuego utilizando Pogamut para la obtenci´on de CTRNNs con pocos par´ametros. En el experimento realizado en el cap´ıtulo 4 se ha comprobado lo siguiente: ❼ Se ha comprobado la poca utilidad por parte de Pogamut a la hora de evolucionar CTRNNs con muchos par´ametros 43