Repositorio Institucional de Documentos

Proyecto de fin de Carrera Ingenier´ıa en Inform´atica Curso 2011/2012 Dise˜no de estrategias multiagente para el control de equipos de bots en el entorno del videojuego Unreal Tournament 2004 Carlos S´anchez Serrano Director: Manuel Gonz´alez Bedia Co-Director: Francisco Ser´on Arbeloa Departamento de Inform´atica e Ingenier´ıa de Sistemas Centro Polit´ecnico Superior Universidad de Zaragoza Abril de 2012 Dise˜no de estrategias multiagente para el control de equipos de bots en el entorno del videojuego Unreal Tournament 2004 RESUMEN En el presente proyecto se pretende llevar a cabo una serie de simulaciones en el contexto de los videojuegos en primera persona, que demuestre la capacidad de los sistemas multiagente a la hora de resolver problemas de exploraci´on y b´usqueda en entornos. Emplearemos t´ecnicas basadas en algoritmos bioinspirados, tales como el Swarming, y la organizaci´on en roles de nuestros agentes (bots) en sistemas distribuidos, estudiando las posibles interacciones y dependencias entre ellos. Se analizar´a el contexto en el que nos encontramos actualmente, el estado del arte de la inteligencia artificial en el mundo de los videojuegos y las diferentes metodolog´ıas y t´ecnicas empleadas para la realizaci´on de nuestras simulaciones. Nuestros experimentos estar´an enmarcados dentro del dilema “exploration vs exploitation”, una paradoja presente en todos los sistemas que pueden adaptarse y aprender [Holland, 1992], donde se intenta buscar el equilibrio entre dos tipos de comportamiento que afectan directamente a la eficiencia a la hora de resolver una tarea. Estrategias de computaci´on evolutiva por medio de algoritmos gen´eticos, nos ayudar´an a crear nuevas generaciones de agentes que nos permitir´an ajustar y optimizar nuestros sistemas. El videojuego para el cual se programar´an nuestros bots cooperativos ser´a el Unreal tournament 2004 (UT2004). Se trata de un videojuego tipo shooter en primera persona (FPS, Ver glosario) donde los objetivos pueden centrarse en enfrentarse a un enemigo o capturar la bandera enemiga. La implementaci´on la llevaremos acabo a trav´es del conjunto de librer´ıas Pogamut [Gemrot et al., 2009], una plataforma de c´odigo abierto usada para el r´apido desarrollo de comportamientos en agentes virtuales incrustados en un entorno 3D del videojuego Unreal Tournament 2004, que nos permite codificar los agentes mediante el uso de Java. Por otro lado, se pretende abrir una nueva l´ınea de investigaci´on desde la Universidad de Zaragoza, que gire entorno a la programaci´on de agentes inteligentes sobre la plataforma UT2004 y Pogamut. Nuestro marco formal previo a los experimentos y las simulaciones en s´ı mismas, pretenden explorar distintas estrategias multiagente para resolver problemas que puedan ser ´utiles para trabajos futuros. Adem´as, al tratarse de un trabajo pionero, el objetivo previo a la realizaci´on de este proyecto consistir´a en estudiar las plataformas empleadas, analizar 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 sentar las bases para futuros proyectos en el ´area de IA en videojuegos utilizando Pogamut y Unreal Tournament 2004. i Agradecimientos Quiero agradecer a todas las personas que me han apoyado durante el trascurso de la carrera, ya sea de manera directa o indirecta. A mis padres, Carlos y Pilar, que tienen m´as ganas que yo de que esto termine y a mi hermano Pablo, el cual espero que se quede solo con lo bueno de m´ı. Tambi´en para todos los amigos que me han apoyado en muchos aspectos. A mis compa˜neros de PFC, Jol, Sergio y ´ Angel, por su lucha aliada contra Pogamut y su filosof´ıa de compartir conocimientos. A mis tutores de proyecto, Paco y Manolo, por brindarme la oportunidad de investigar sobre lo que me gusta y por haberme ayudado en todo lo posible. No quiero dejarme de nombrar al maestro de la IA acad´emica, al cual no le ha importado ayudarme a altas horas de la madrugada para mejorar mi proyecto. Tambi´en a Germ´an, el gur´u probabil´ıstico, que nos ha ayudado todo lo que ha estado en su mano. Por ´ultimo, se lo quiero agradecer a Claudia por su apoyo constante en todos los ´ambitos, porque sin ella no estar´ıa escribiendo este texto. iii ´ Indice general I Memoria xi 1. Introducci´on 1 1.1. Motivaci´on y objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Contexto ......................................... 2 1.2.1. ¿Pueden pensar las m´aquinas? . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2.2. Inteligencia Artificial y Videojuegos . . . . . . . . . . . . . . . . . . . . . . 3 1.3. Contenido de la Memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4. Planificaci´on ....................................... 5 2. Estado del arte 7 2.1. Sistemas multiagente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1. T´ecnicas cl´asicas empleadas para el modelado de comportamiento colectivo 8 2.1.2. T´ecnicas empleadas para el modelado de comportamiento colectivo en entornosinciertos ................................... 10 2.2. Dilema de exploraci´on-explotaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3. Marco formal y metodolog´ıa 13 3.1. Infotaxis: inspiraci´on y limitaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2. Modelopropuesto..................................... 14 3.3. Metodolog´ıas aplicadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3.1. Swarming..................................... 17 3.3.2. Algoritmos gen´eticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4. Herramientas utilizadas 21 4.1. Unreal Tournament 2004 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2. Pogamut.......................................... 23 4.3. UnrealED......................................... 24 4.4. Dise˜no del bot en el entorno UT2004 . . . . . . . . . . . . . . . . . . . . . . . . . . 24 v 5. Experimento 1 - siSosiG Bot 27 5.1. Descripci´on del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.2. Implementaci´on...................................... 28 5.3. Estudio anal´ıtico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.3.1. Probabilidad de encontrar la bandera . . . . . . . . . . . . . . . . . . . . . 30 5.3.2. Estructura del equipo seg´un su IH . . . . . . . . . . . . . . . . . . . . . . . 32 5.3.3. Evoluci´on gen´etica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.4. Resultados......................................... 33 5.4.1. An´alisis de Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.4.2. Interpretaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6. Experimento 2 - Pathwalker Bot 39 6.1. Descripci´on del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.2. Implementaci´on...................................... 40 6.3. Estudio anal´ıtico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 6.3.1. Evoluci´on gen´etica y Fitness . . . . . . . . . . . . . . . . . . . . . . . . . . 44 6.4. Resultados......................................... 45 6.4.1. An´alisis de Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.4.2. Interpretaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 7. Conclusiones 49 7.1. Trabajofuturo ...................................... 50 Glosario 51 vi ´ Indice de figuras 1.1. Explicaci´on gr´afica del test de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Diagrama Gantt del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1. Representaci´on de sistemas multiagente . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2. Ciclo de vida de un sistema CBR, tomada de [Spalazzi, 2001] . . . . . . . . . . . . 11 2.3. Equilibrio entre la recuperaci´on y la reutilizaci´on de casos, tomada de [Spalazzi, 2001] 12 3.1. Gr´afica comparativa entre funciones de distribuci´on de probabilidad de tiempo de b´usqueda para cuatro estrategias diferentes. (1) Infotaxis (negro), (2) Algoritmo voraz donde el agente elige moverse hacia estados de mayor probabilidad esperada (azul), (3) Estrategia de maximizaci´on local de la probabilidad de detecci´on (morado), (4) Estrategia complementaria a (2) (roja). Figura tomada de [Vergassola et al, 2008] 14 3.2. Funci´on de ajuste en fase de exploraci´on . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3. Funci´on de ajuste en fase de explotaci´on . . . . . . . . . . . . . . . . . . . . . . . 15 3.4. Comparaci´on de estrategias. Representaci´on de la funci´on de ajuste a(t), y el ajuste global a(T) para (a)la estrategia voraz, y (b) el modelo tipo infotaxis. Podemos comprobar que el ajuste global es mayor para el segundo modelo. .................... 16 3.5. Representaci´on del ajuste global a(t) para diferentes parejas de valores τ,ε. . . . 16 3.6. Distribuci´on de valores de ajuste global a(T) en t´erminos de los par´ametros εyτ. 17 3.7. Etapas t´ıpicas de un algoritmo gen´etico . . . . . . . . . . . . . . . . . . . . . . . . 19 3.8. Aproximaci´on clonal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.9. Aproximaci´on aclonal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.1. Unreal Tournament 2004 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2. Arquitectura de Pogamut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.3. Arquitectura de GaviaLib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.4. Mapa creado en UnrealED . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.5. Modelo de representaci´on cl´asico de la mente . . . . . . . . . . . . . . . . . . . . . 25 5.1. Representaci´on del algorimto siSosiG . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.2. Malla de puntos de navegaci´on para el mapa de pruebas del experimento siSosiG en UT2004 .......................................... 30 vii shooter) donde los objetivos van desde acabar con el enemigo hasta capturar la bandera enemiga. Unreal Tournament 2004 es la herramienta empleada en el concurso a nivel mundial 2kBotPrize2, celebrado todos los a˜nos, donde investigadores de todo el mundo presentan sus bots con el objetivo de superar una adaptaci´on del test de Turing. Varios jueces tendr´an que evaluar y votar durante varias partidas el comportamiento de los bots programados, obteniendo ´estos una puntuaci´on que corresponde a su grado de humanidad. Adem´as, este videojuego cuenta con la plataforma Pogamut [Gemrot et al., 2009], desarrollada en la Universidad de Praga y que se encuentra actualmente en su versi´on 3.2, la cual nos facilita un conjunto de librer´ıas para implementar nuestros bots en el lenguaje de programaci´on Java. Otro objetivo del proyecto es abrir una nueva l´ınea de investigaci´on desde la Universidad de Zaragoza que gire entorno a la programaci´on de agentes inteligentes en la plataforma UT2004. Para ello, primero deberemos demostrar la capacidad y validez de Pogamut a la hora realizar este tipo de estudios, comprobando que nos permita realizar las simulaciones de nuestros experimentos con las menores limitaciones posibles. Al tratarse de un trabajo pionero, ser´a necesaria una fase previa a la realizaci´on de los experimentos, que consistir´a en la formaci´on en dicha plataforma. Nuestro marco formal previo a los experimentos y las simulaciones en s´ı, pretenden explorar distintas estrategias multiagente para resolver problemas que puedan ser ´utiles para trabajos futuros que giren en torno a los videojuegos. Adem´as se realizar´a un manual adecuado para programadores, dado que Pogamut al principio de este proyecto no contaba con uno. Con ello se pretende sentar las bases para futuros proyectos en el ´area de IA en videojuegos utilizando Pogamut y Unreal Tournament 2004. 1.2. Contexto 1.2.1. ¿Pueden pensar las m´aquinas? Con esta sugerente pregunta comenzaba el art´ıculo “Computing Machinery and Intelligence” publicado por Alan Turing en la revista de filosof´ıa brit´anica Mind (1950). Aqu´ı se trat´o por primera vez la cuesti´on de la posible existencia de una inteligencia artificial y propuso el famoso test de Turing [Mind, 1950], considerando que si una m´aquina se comporta en todos los aspectos como inteligente, entonces debe ser inteligente. Mediante dicho test, Turing introduce un criterio operacional para dirimir si el comportamiento de un artefacto deber´ıa ser considerado como inteligente. En principio parecer´ıa obvio que este atributo solo se pueda asociar a los seres humanos, que durante millones de a˜nos han desarrollado las estructuras neuronales que conforman sus complejos cerebros. Sin embargo, la respuesta a esta pregunta no es sencilla. Depender´a, como bien dijo Turing, de qu´e entendamos por pensar. Seg´un la Real Academia Espa˜nola de la Lengua, “pensar” supone “el acto de examinar con cuidado algo para formar dictamen”. Una definici´on de este tipo deja una puerta abierta a la existencia de m´aquinas inteligentes. La intenci´on del test de Turing es la de corroborar la existencia de inteligencia en las m´aquinas. La prueba est´a estructurada de forma que un jurado situado en una habitaci´on, se encargaba de formular preguntas a dos competidores (una m´aquina y un ser humano) situados en otras habitaciones y, bas´andose en sus respuestas, deb´ıa decidir cu´al era la m´aquina y cu´al el ser humano. De este modo, se considerar´ıa que el test hab´ıa sido superado si el jurado no fuese capaz de descubrir la identidad real de cada uno de los participantes. Desde entonces, han surgido numerosas variantes de este test que persiguen un mismo objetivo, pero con aplicaci´on en diversos campos de investigaci´on. Hasta el d´ıa de hoy, ninguna m´aquina ha sido capaz de superar el test con ´exito3. En el mundo de los videojuegos, que los NPC’s superaran el test de turing, supondr´ıa que el usuario no sabr´ıa si esta jugando contra una persona o un bot controlado por el computador. 2http://botprize.org 3http://www.loebner.net/Prizef/loebner-prize.html 2 Figura 1.1: Explicaci´on gr´afica del test de Turing 1.2.2. Inteligencia Artificial y Videojuegos Durante la d´ecada de los 90 comenzaron a utilizarse, aunque de forma muy rudimentaria, t´ecnicas vinculadas a la Inteligencia Artificial (IA) con el objetivo de desarrollar videojuegos mucho m´as complejos que los que hab´ıa hasta entonces. Esta necesidad ven´ıa acuciada por los juegos enormemente predecibles que hab´ıa en aquella ´epoca, en los que las acciones realizadas por los jugadores no controlados por el usuario (non-playing characters, NPC’s), se repet´ıan con cierta asiduidad. Videojuegos como Herzog Zwei4o Dune II5comenzaban a aplicar m´aquinas de estados para poder desarrollar estrategias en tiempo real. Del mismo modo, en 1996 el videojuego Battlecruiser 3000AD6utiliz´o por primera vez redes de neuronas artificiales. En este contexto, a˜nos m´as tarde nace un videojuego que merece una menci´on especial. Este videojuego es Golden Eye7, basado en las aventuras del personaje cinematogr´afico James Bond, al convertirse en el primer juego de tipo FPS que aplicaba t´ecnicas de Inteligencia Artificial durante el juego. De este modo, los NPC’s reaccionaban convenientemente al movimiento del jugador controlado por el usuario. A´un as´ı, este juego presentaba un gran inconveniente: los enemigos del usuario sab´ıan en todo momento d´onde se encontraba ´este, incluso si a´un no lo hab´ıan visto, con lo que era imposible esconderse para desarrollar acciones m´as reales de comportamiento. En actualidad, se ha producido un incremento significativo en la producci´on de videojuegos. El mercado de los videojuegos ha superado a la industria del cine y de la m´usica juntas, con unas ventas superiores a los 23.000 millones de euros. Con un coste cada vez menor de la potencia computacional, los gr´aficos y la f´ısica de los juegos son cada vez m´as realistas. Sin embargo, estos no son los ´unicos elementos que hacen que un juego de ´exito. El comportamiento de los NPC’s es incluso m´as importante a la hora de hacer un juego realista y entretenido para el usuario. La industria parece no ser consciente del problema y muestra reticencias a la hora de cambiar las t´ecnicas de IA tradicional utilizadas, tales como m´aquinas de estados finitas, ´arboles de comportamiento y algoritmos de planificaci´on. Incluso en los juegos que han visto la luz recientemente, la comunidad de jugadores parece no estar satisfecha con el IA de los juegos. El objetivo de toda IA aplicada a videojuegos deber´ıa ser que los bots mostraran un comportamiento humano y por tanto realista. Las expectativas de los jugadores deben ser cumplidas. Dichas expectativas se pueden clasificar en tres clases [J. Laird, 2000]: 1. Los jugadores esperan nuevas situaciones. Las situaciones repetitivas hacen que los jugadores se desinteresen. Si hacemos que los bots tengan un comportamiento impredecible a la vez que coherente, conseguiremos crear nuevas situaciones. 4http://en.wikipedia.org/wiki/Herzog Zwei 5http://duneii.com/ 6http://www.3000ad.com/ 7http://en.wikipedia.org/wiki/GoldenEye 007 3 2. Tambi´en se espera una total interactividad. Los jugadores quieren que los bots reaccionen ante ellos y sean capaces de modificar su comportamiento dependiendo de las acciones del usuario. Tambi´en deben ser conscientes del entorno y reaccionar ante ´el. 3. Es deseable un alto grado de desaf´ıo. Dentro de la comunidad de jugadores, especialmente en los m´as avanzados que llevan jugando durante a˜nos, necesitan nuevos retos en el juego para no perder el inter´es en ´el. Los bots deben hacerlo bien, pero sin llegar al extremo de tener el control y conocimiento sobre todas las cosas, al igual que un jugador humano. Existe un problema con los videojuegos comerciales mejor desarrollados y es que, en el mejor de los casos, llegan a desvelar en qu´e aspectos aplican t´ecnicas de Inteligencia Artificial. No obstante no se proporciona informaci´on detallada respecto a la t´ecnica en cuesti´on, por lo que ´unicamente se pueden emitir conjeturas respecto a cu´ales son las que, con mayor probabilidad, se han aplicado en cada caso. Sin embargo, existen juegos que a pesar de haber tenido una gran aceptaci´on popular, mantienen su c´odigo abierto a todos los usuarios o, al menos, facilitan herramientas para poder personalizarlos, de manera que sea mucho m´as sencillo comprender el funcionamiento interno del mismo. Este es el caso de Unreal Tournament 2004, usado en el presente proyecto. 1.3. Contenido de la Memoria La estructura de este documento esta dividida en los siguientes cap´ıtulos: 1. Introducci´on: Se establecen los objetivos, el contexto en el que se encuadra el trabajo y la planificaci´on que se ha llevado a cabo para realizar este proyecto. 2. Estado del arte: Se examinan las diferentes estrategias que se han llevado a cabo en los ´ultimos a˜nos en el dise˜no de comportamientos colectivos. 3. Marco formal y metodolog´ıa: Se detalla el marco formal donde se encuadran nuestros experimentos as´ı como las t´ecnicas que se han empleado para la realizaci´on de este proyecto, tales como los comportamientos de enjambre y los algoritmos gen´eticos. 4. Herramientas utilizadas: En este capitulo se detallan las herramientas que nos han permitido realizar nuestros experimentos. 5. Experimento 1 - siSosiG Bot: Se plantea un experimento basado en un comportamiento de roles impl´ıcito, donde se detallan sus objetivos, su implementaci´on y los resultados obtenidos junto a las conclusiones sacadas. 6. Experimento 2 - PathWalker Bot: En este cap´ıtulo analizamos el experimento de nuestros bots Pathwalkers, donde un equipo con comportamiento de enjambre es capaz de resolver una tarea. Para llevar a cabo su an´alisis, se presentan los objetivos, implementaci´on y resultados al igual que en el experimento previo. 7. Conclusiones: Conclusi´on general sobre el desarrollo del proyecto, posibles l´ıneas futuras y valoraci´on personal del proyecto. 8. Anexos: Informaci´on adicional del proyecto, referenciada desde apartados anteriores. 4 1.4. Planificaci´on Durante los meses de duraci´on del proyecto, se han realizado labores de documentaci´on y formaci´on en las plataformas usadas, se ha redactado el manual de Pogamut, se han implementado y ejecutado los experimentos, as´ı como se ha llevado a cabo un an´alisis de resultados y se han sacado conclusiones de los mismos. De manera paralela se ha escrito el presente documento. El diagrama de Gantt correspondiente a la realizaci´on del proyecto se muestra en la figura 1.2. Figura 1.2: Diagrama Gantt del proyecto 5 6 Cap´ıtulo 2 Estado del arte Antes de pasar a detallar nuestros experimentos en UT2004, vamos a presentar el estado del que nos ha empujado a llevar a nuestra propuesta de modelo, con objetivo de asentar las bases de la problem´atica a la que nos enfrentamos y facilitar el trabajo futuro en esta l´ınea de trabajo. 2.1. Sistemas multiagente Existen tareas, independientes del contexto donde nos encontremos, en las que un ´unico agente no es capaz de llevarlas a cabo, o si lo puede, lo hace de manera muy ineficiente y costosa. En esos casos, el trabajo en equipo de varias entidades puede ser una buena opci´on. Entramos as´ı, en el contexto de los sistemas multiagente (figura 2.11), que permiten la gesti´on inteligente de un sistema complejo, coordinando los distintos subsistemas que lo componen e integrando los objetivos particulares de cada subsistema en un objetivo com´un. Estos sistemas se emplean cuando los problemas son f´ısicamente distribuidos, cuando la soluci´on requiere de experiencia muy heterog´enea o cuando el problema a resolver est´a definido sobre una red de computadores. En realidad, la complejidad de la mayor parte de los problemas que nos encontramos hoy en d´ıa es tal que se requiere una soluci´on distribuida, capaz de adaptarse a cambios en la estructura y en el entorno, as´ı como una metodolog´ıa de desarrollo que permita la construcci´on de todo un sistema a partir de distintas unidades aut´onomas [Ferber, 1999]. En general, un sistema multiagente cooperante [Wesson et al., 1988] presentar´a las siguientes caracter´ısticas: Estar´a formado por un conjunto de agentes, cada uno de los cuales mantiene sus propias habilidades: adquisici´on de datos, comunicaci´on, planificaci´on y actuaci´on. El sistema multiagente tiene una misi´on com´un. La misi´on puede descomponerse en diferentes tareas independientes, de forma que se pueden ejecutar en paralelo. El sistema multiagente debe ser capaz de asignar a cada uno de sus componentes una o varias tareas concretas teniendo en cuenta cu´al es el objetivo com´un. Cada agente del sistema tiene un conocimiento limitado. Esta limitaci´on puede ser tanto del conocimiento del entorno, como de la misi´on del grupo, como de las intenciones de los dem´as agentes a la hora de realizar sus propias tareas. 1http://www.codeproject.com/Articles/13544/Agents-and-Multi-agent-Sys 7 Figura 2.1: Representaci´on de sistemas multiagente Cada agente del sistema tiene cierta especializaci´on para realizar determinadas tareas, en funci´on de lo que conoce, la capacidad de proceso y la habilidad requerida. Ronald Arkin (1998) enumera algunos de los aspectos positivos del trabajo en equipo con varios agentes: Mejora en el rendimiento del sistema, ya que si las tareas pueden descomponerse de un modo natural, la estrategia de divide y vencer´as es apropiada. Se pueden realizar ciertas tareas que serian imposibles para un solo bot; un equipo puede llevar a cabo de modo simult´aneo acciones en diferentes localizaciones. Presentan una mayor tolerancia a fallos ante un mal funcionamiento de alg´un bot. Pero no todo son ventajas, ya que el uso de sistemas multiagente tambi´en puede traer consigo algunas consecuencias. Como aspectos negativos, podr´ıamos destacar: Interferencia a la hora de realizar la tarea, que Arkin explica con el conocido dicho de que “demasiados cocineros estropean el guiso”, dada la mayor probabilidad de choques o bloqueos. La necesidad de comunicaci´on, directa o indirecta, con el coste computacional y estructural que ello conlleva. En el problema de la coordinaci´on entre los agentes es tan importante el proceso de razonamiento interno como el proceso de comunicaci´on. El proceso de razonamiento interno consistir´a en la toma de decisiones y en la identificaci´on de la informaci´on que se debe compartir. El proceso de comunicaci´on debe modelar c´omo y cu´ando debe producirse la interacci´on entre los agentes. 2.1.1. T´ecnicas cl´asicas empleadas para el modelado de comportamiento colectivo Para intentar modelar el comportamiento de equipos de agentes se han empleado diferentes t´ecnicas a lo largo de los a˜nos, las cuales podemos englobar en dos tipos principales: algoritmos tipo flocking y algoritmos voraces. 8 Algoritmos tipo flocking Este tipo de algoritmos han sido empleados para modelar sistemas de vida artificial, que se componen de un conjunto de organismos sint´eticos modelados mediante reglas simples de las que emergen comportamientos caracter´ısticos de los sistemas naturales vivos [Langton, 1989]. La comunidad cient´ıfica estudia las cualidades inherentes a los seres vivos como son el crecimiento, la reproducci´on, la percepci´on del entorno, la respuesta al medio ambiente, la adaptabilidad, el metabolismo, la autonom´ıa, la capacidad de reacci´on y la evoluci´on con objeto de resolver problemas, utilizando agentes inspirados biol´ogicamente que exhiben un comportamiento colectivo inteligente [Terzopoulos, 1999]. En particular, en el trabajo pionero de Reynolds, se modela el comportamiento de las bandadas, manadas o muchedumbres, utilizando tres reglas sint´acticas muy sencillas y logrando la emergencia de comportamientos relacionados con la alineaci´on, no colisi´on y movimiento de agregaci´on [Bajec et al, 2007]. Sin embargo, en la mayor´ıa de los trabajos de investigaci´on relacionados con el tipo de problemas citados, a cada individuo hay que dotarle de un conocimiento completo de la posici´on, velocidad y direcci´on de vuelo de, al menos, un subconjunto de los individuos de la bandada. Por decirlo de una manera m´as expresiva, dentro de su conciencia del mundo los datos que utiliza son bastante exactos sobre magnitudes normalmente f´ısicas. Ese tipo de requerimientos son antinaturales (un p´ajaro o un pez tiene una capacidad de percepci´on limitada e inexacta), y por lo tanto la filosof´ıa del modelo se aleja de los enfoques naturalistas y entra en contradicci´on con las premisas de qu´e es un sistema de vida artificial. Algorimos voraces En algoritmo un voraz siempre se hace la mejor elecci´on disponible en cada paso (´optimos locales) de la implementaci´on, con la esperanza de que de esta manera se pueda obtener el mejor resultado global. En contraste, m´etodos como los algoritmos gen´eticos, discutido abajo, no son voraces; a veces, estos m´etodos hacen elecciones menos ´optimas al principio con la esperanza de que conducir´an hacia una soluci´on mejor m´as adelante. El uso de algoritmos voraces en contextos de exploraci´on y b´usqueda sin modelos basados en la reducci´on del gradiente de la concentraci´on de un est´ımulo. Seg´un el tipo de fuente del est´ımulo, podemos encontrar diferente implementaciones en la literatura cient´ıfica: Quimiotaxis si el comportamiento esta guiado por un gradiente qu´ımico, Fototaxis cuando el tenemos un est´ımulo luminoso, Fonotaxis cuando la fuente es sonora, etc. Si un agente es modelado mediante este tipo de estrategias tendr´ıa un comportamiento descrito por las siguiente acciones:(1) realizar´ıa un movimiento, (2) medir´ıa el cambio en la se˜nal sensorial, (3) si el cambio es positivo seguir´ıa movi´endose en la misma direcci´on, en caso contrario, cambiar´ıa el sentido de su movimiento. Tal estrategia de b´usqueda requiere que la concentraci´on del est´ımulo sea lo suficientemente alta como para asegurar que la diferencia entre las medidas en posiciones vecinas sea mayor que sus fluctuaciones [Berg, 1993]. Existen diversos trabajos donde se emplean est´as t´ecnicas de manera exitosa ([Russel et al, 2003],[Grasso et al, 2000]) pero en todos ellos la relaci´on se˜nal-ruido(SNR) es muy alta para que el rendimiento del agente sea aceptable. Sin embargo, estos m´etodos de b´usqueda no resultan satisfactorios cuando nos encontramos en entornos din´amicos o con incertidumbre. Desde que [Barlow, 1969] propusiera el principio de codificaci´on eficiente se acepta que para que un sistema procese se˜nales de forma eficaz en entornos con incertidumbre debe aprovecharse de la estructura estad´ıstica de la se˜nal de entrada. Es decir, que un agente m´as que combatir la incertidumbre deber´ıa tratar de beneficiarse de ella. Estos comportamientos son observados frecuentemente en organismos vivos y de igual forma constituyen un campo de trabajo en la rob´otica[Hamza, 2006]. 9 2.1.2. T´ecnicas empleadas para el modelado de comportamiento colectivo en entornos inciertos Cuando un agente se encuentra en un entorno din´amico, modelos predise˜nados como los citados anteriormente, no proporcionan un comportamiento satisfactorio. Como el agente no posee, en un principio, una estrategia para actuar correctamente, deber´a evaluar las diferentes acciones posibles mediante un proceso de ensayo y error [Sutton et al, 1998]. Existen varios m´etodos que han sido desarrollados para resolver este tipo de tareas: m´etodos de Montecarlo, actualizaci´on de diferencias temporales, trazas de elegibilidad [Sutton et al, 1998],etc. Todos estos m´etodos presentan dos aspectos incompatibles: (1) por un lado para maximizar la evaluaci´on los agentes deben seleccionar las acciones que ya conocen, y por otro lado, (2) se deber´ıan probar nuevas acciones para descubrir nuevas posibilidades. Si nos centr´aramos exclusivamente en el primer aspecto estar´ıamos explotando solo la informaci´on de la que disponemos, sin posibilidad de adaptarnos a nuevas situaciones. En cambio un agente que base su comportamiento solo en el segundo aspecto, ejecutar´ıa acciones sin ning´un prop´osito concreto. Por este motivo, el comportamiento ideal se construir´ıa mediante un equilibrio entre las dos estrategias. Tradicionalmente, la b´usqueda del equilibrio entre estos dos factores en entornos cambiantes, recibe el nombre del “dilema de exploraci´on-explotaci´on”. 2.2. Dilema de exploraci´on-explotaci´on El “dilema de exploraci´on vs explotaci´on” (exploration vs exploitation, E-E), plantea el problema de encontrar el ´optimo global en un espacio que posee ´optimos locales. Esta paradoja se produce en todos los sistemas que pueden adaptarse y aprender [Holland, 1992]. La decisi´on de aprender es fundamentalmente una elecci´on entre actuar inmediantamente bas´andose en la mejor informaci´on que disponemos actualmente o esperar a conseguir m´as informaci´on, la cual puede permitirnos posteriormente obtener un mejor rendimiento. Obtener m´as informaci´on conlleva una perdida de rendimiento, mientras que la explotaci´on de los mejores datos que tenemos conlleva el riesgo de perpetuar un error (Holland, 1992). Si nos decantamos por recavar m´as informaci´on acerca del entorno en el que estamos, estaremos incurriendo en un coste a corto plazo para conseguir una mejor respuesta en un periodo m´as largo. En cambio, si empleamos la informaci´on de la que ya disponemos, obtendremos en principio un mejor rendimiento al obtener los beneficios de actuar ahora. Podr´ıamos definir2cada una de las estrategias como: Exploraci´ on: Incluye estrategias representadas por t´erminos como b´usqueda, variaci´on, experimentaci´on, juego, flexibilidad, descubrimiento, innovaci´on. Explotaci´ on: Sus estrategias van definidas en el sentido de refinamiento, elecci´on, producci´on, eficiencia, selecci´on, implementaci´on y ejecuci´on. El equilibrio entre aprendizaje y rendimiento es el objetivo a resolver en un problema donde se nos plantee el dilema E-E. Este tipo de modelos se han empleado para modelar el comportamiento de agentes con aprendizaje por refuerzo [Thrun, 1992]. Dicho aprendizaje consiste en aprender a decidir antes una situaci´on determinada, qu´e acci´on es la m´as adecuada para logar un determinado objetivo bas´andose en resultados previos. En este marco podemos distinguir dos facetas, las cuales nos podemos encontrar dependiendo el entorno donde nos situemos: 2http://www.analytictech.com/mb874/papers/march.pdf 10 1. El agente se encuentra ante un entorno din´amico donde las condiciones y variables cambian constantemente, por tanto necesitaremos elegir el mejor momento en el que explorar, lo suficientemente pronto para poder adaptarnos a los cambios, y lo suficientemente tarde como para obtener un m´ınimo de informaci´on necesaria. 2. El agente se enfrenta a en un espacio grande de con muchos estados y acciones. En este escenario explorar cada uno de estos estados y acciones podr´ıa ser muy costoso. Por ello necesita elegir un subconjunto prometedor de estados y acciones a explorar. En ambos casos habr´a que buscar el equilibrio entre ambos factores, que nos permitir´a ajustarnos a la soluci´on del problema de una manera m´as eficaz. El dilema E-E aparece en multitud de escenarios de diferente naturaleza, en algunas ocasiones con nombres distintos, para adaptar el dilema a su problema en particular. Ejemplo de ello, son: El dilema de“stabilidad vs sensiblidad” (stability vs sensitivity dilemma), presente en modelos neurocomputacionales3que intentan buscar el equilibrio entre el procesamiento neuronal de la informaci´on y la eficiencia del sistema. El problema de “precisi´on vs robustez” (accuracy vs Robustness dilemma), que podemos encontrar en modelos de mecatr´onica [Sang Hoon et al., 2009], donde se busca la estabilidad entre la precisi´on de la impedancia y robustez frente al error de modelado. Los sistemas multiclasificadores, los cuales son empleados com´unmente para resolver problemas de clasificaci´on, presentan el dilema de diversidad vs precisi´on (diversity vs accuracy dilemma [Diego F. et al, 2009]) donde para construir ensambladores robustos, es necesario que los clasificadores individuales sean tan precisos como diversos entre ellos. Figura 2.2: Ciclo de vida de un sistema CBR, tomada de [Spalazzi, 2001] Otro ejemplo, que analizaremos con m´as detalle, es el de los sistemas de razonamiento basado en casos (CBR). Este sistema se basa en las soluciones de problemas anteriores para intentar 3http://inls.ucsd.edu/wlc locust.html 11 3.3.2. Algoritmos gen´eticos Aunque las primeras nociones de algoritmo gen´eticos pueden encontrarse hace m´as tiempo, es reconocido que fueron impulsados definitivamente por los trabajos de John Holland [Holland, 1992]. Se consideran una t´ecnica destacada en el contexto de la computaci´on evolutiva. Son mecanismos de optimizaci´on o b´usqueda en un espacio de estados multidimensional, cuya mayor utilidad se demuestra en problemas en los que la soluci´on es el resultado de un proceso no lineal, aplicado a un conjunto de par´ametros que definen dicho espacio de estados multidimensional [Goldberg, 1989]. Dicho conjunto de par´ametros definen una posible soluci´on al problema, y son un punto en el espacio de estados, denominado tambi´en genotipo. En este tipo de problemas es imposible aislar las variables para obtener su valor ´optimo por separado. El proceso general de evoluci´on simulada parte de una poblaci´on de individuos que codifican en su material gen´etico (genotipo) un comportamiento o morfolog´ıa como una posible soluci´on a un determinado problema que se quiere optimizar. Esta poblaci´on de individuos no son mas que un conjunto de posibles soluciones al problema (puntos en el espacio de estados). Los individuos se someten a lo largo de varias generaciones a procesos de selecci´on, para procrear y pasar su material gen´etico a siguientes generaciones. Tal selecci´on requiere asignar un valor num´erico a cada individuo de la poblaci´on, que ser´a una medida de lo que se acerca la soluci´on ´optima. Este valor se denomina “valor de adecuaci´on” o “fitness”, y se calcula con una funci´on del mismo nombre. La elecci´on de la funci´on fitness tiene consecuencias muy importantes en la posibilidad de evoluci´on del bot, din´amicas del proceso evolutivo y por ´ultimo en la salida del proceso evolutivo. Desafortunadamente, no hay una manera de definir una funci´on de adecuaci´on a partir de una descripci´on del resultado esperado. Normalmente, (1) uno define una funci´on basada en su propia experiencia, (2) a continuaci´on, prueba su idoneidad a base de prueba y error (cuyo consumo de tiempo es uno de los mayores problemas en la evoluci´on de agentes), y (3) Modifica gradualmente su valor introduciendo variables y constantes adicionales. Estas variables y constantes no son f´aciles de elegir, ya que no hay un conocimiento total del comportamiento del robot una vez ha evolucionado. Podr´ıa decirse que dise˜nar una funci´on de adecuaci´on aplicable para un comportamiento deseado es normalmente m´as f´acil que dise˜nar el programa correspondiente. No obstante el grado de conocimiento de un comportamiento esperado es inversamente proporcional a la necesidad de aplicaci´on de estrategias evolutivas. Si el espacio de estados es de dimensi´on n, el “paisaje de adecuaci´on” (fitness landscape) es un conjunto de puntos en un espacio de n+ 1 dimensiones, que puede ser continuo y formar una superficie (como un paisaje), o ser rugoso o completamente inconexo, lo que influye en la capacidad de b´usqueda en el algoritmo gen´etico. De entre todas las soluciones posibles se escogen, en funci´on de su adecuaci´on, las mejores y se genera la descendencia, que sustituye a los individuos no elegidos o a todos los de la poblaci´on anterior. Se puede mantener una elite de individuos que pasa a la siguiente generaci´on sin modificaciones. Al igual que en la evoluci´on natural, a lo largo de las generaciones ir´an apareciendo individuos u organismos mejor adaptados en su comportamiento a su entorno virtual, con una morfolog´ıa m´as adaptada al entorno en el que act´ua y las tareas que debe realizar, o sencillamente, m´as cercanos a una soluci´on buena al problema a optimizar. En la figura 2.1 podemos ver los pasos t´ıpicos que se realizan en un algoritmo gen´etico, cuyas fases se detallan a continuaci´on: Poblaci´on inicial: La poblaci´on inicial de individuos se genera de forma aleatoria, considerando los valores m´ınimos y m´aximos de cada variable. Evaluaci´on: Para cada individuo de la poblaci´on, se simula en el entorno correspondiente y obtenemos el valor de adecuaci´on para cada agente. Selecci´on: Este operador elige aquellos individuos que van a generar nuevos descendientes, teniendo en cuenta el valor fitness, de modo que ser´an seleccionado con mayor probabilidad aquellos con un mejor valor. Existen varios m´etodos para realizar la selecci´on, nosotros 18 Figura 3.7: Etapas t´ıpicas de un algoritmo gen´etico emplearemos la “selecci´on por torneo”. Este m´etodo consiste en determinar subconjuntos de individuos, elegidos de modo aleatorio entre la poblaci´on, y se elige para procrear el mejor de ese subconjunto. Cruce (Crossover): En esta fase, se combina el operador gen´etico de dos progenitores previamente seleccionados por el operador anterior. El m´etodo aplicado en este operador depender´a de la codificaci´on del genotipo de cada individuo. Mutaci´on: Este operador cambia el contenido del material gen´etico de un determinado cromosoma. En el caso de una codificaci´on del genotipo de tipo binario, una mutaci´on podr´ıa ser el cambio de un bit. Algoritmos gen´eticos en sistemas multiagente: Clonal vs Aclonal En los ´ultimos a˜nos un buen n´umero de investigadores han aplicado satisfactoriamente la evoluci´on artificial en bots aut´onomos (e.g. Baldassarre et al., 2003a; Botee and Bonabeau, 1998; Luke and Spector, 1996; Mitchell et al., 1996; Wu et al., 1999). Sin embargo, se han centrado casi exclusivamente en sistemas individuales. El paso de sistemas individuales a sistemas multiagente lleva asociado consigo una serie de problemas metodol´ogicos. Tal vez el m´as b´asico de estos problemas surge al plantearnos la siguiente cuesti´on: ¿Como deber´ıan organizarse las generaciones y pruebas de los distintos agentes? La respuesta a esta pregunta nos introduce en una comparaci´on entre las dos posibles aproximaciones: clonal y aclonal. La implementaci´on clonal, es una simple variaci´on de la evoluci´on gen´etica que se aplica a sistemas individuales. Los genotipos son evolucionados en una ´unica poblaci´on, con cada genotipo codificando los par´ametros necesarios para definir el comportamiento de cada uno de los agentes del sistema. La evaluaci´on de un genotipo se realiza de la siguiente manera: Primero, el genotipo es codificado para producir un elemento del sistema. Despu´es ese elemento es clonado hasta que el sistema tiene el tama˜no que queremos. Por ´utlimo, todo el sistema es evaluado acorde con un criterio apropiado, y se la asigna un valor fitness al genotipo. Figura 3.8: Aproximaci´on clonal 19 Con esta estrategia obtenemos un sistema que est´a especificado por el material gen´etico de un solo individuo; por tanto, desde la perspectiva de evoluci´on, un sistema clonal es el fenotipo de un s´olo genotipo. Es decir, un solo individuo distribuido. El m´etodo clonal ha sido empleado por muchos investigadores; entre los que podemos destacar a Bottee y Bonabeau (1998), los cuales usaron esta aproximaci´on para evolucionar propiedades de una colonia de hormigas, para resolver el problema del vendedor viajero. Las algoritmos de colonias de hormigas son paralelos y distribuidos, con agentes id´enticos, inspir´andose en los rastros de feromona de las hormigas reales. Por otro lado tenemos la aproximaci´on aclonal. Dos caracter´ısticas principales definen esta implementaci´on: En primer lugar, al igual que en la aproximaci´on clonal, tenemos una ´unica poblaci´on, donde cada genotipo en la poblaci´on codifica el comportamiento de un agente. La siguiente caracter´ıstica, es que cada agente esta especificado por un genotipo distinto; por tanto, cada agente necesita un genotipo para ser codificado. Figura 3.9: Aproximaci´on aclonal Con la implementaci´on aclonal, se esta favoreciendo la creaci´on de roles o subgrupos dentro de los individuos. Este sistema se ha empleado con mucha frecuencia para investigar la evoluci´on de comunicaciones naturales entre varios agentes (Bullock,1998, Quinn an Noble,2001). En la secci´on siguiente propondremos dos tipos de experimentos: (1) con t´ecnicas clonal y (2) t´ecnicas aclonal, con el objetivo de comprobar la versatilidad de cada una de estas metodolog´ıas. 20 Cap´ıtulo 4 Herramientas utilizadas 4.1. Unreal Tournament 2004 Unreal Tournament 2004 (UT2004) es un videojuego de acci´on tipo FPS (first-person shooter), como podemos ver en la figura 4.1, desarrollado por Epic Games and Digital Extremes. Est´a principalmente orientado a la experiencia multijugador, aunque tambi´en existe el modo de un solo jugador, el cual emula el juego multijugador a trav´es del uso de bots controlados por la computadora. Pero tal como UT2004 anuncia en su pantalla de inicio: “Game experience may change during online play”; Si queremos disfrutar del juego plenamente, deberemos jugar en modo multijugador a trav´es de la red, puesto que la experiencia de juego dada por los bots controlados por el juego, no tiene nada que ver con jugar contra jugadores humanos. Cada vez con m´as inter´es se pretende que la IA aplicada a videojuegos permita mostrar bots con un comportamiento humano y por tanto realista, lo que ha d´ıa de hoy todav´ıa no se ha conseguido completamente en ning´un videojuego. Existen varios modos de juego en UT2004, los cuales tienen objetivos diferentes y diferente mapas. Los formatos existentes son los siguientes: Capture the Flag (Captura la Bandera). Modo de juego por equipos en el que cada grupo tiene una base y una bandera que defender. El objetivo es robar la bandera del enemigo y llevarla hasta la base de equipo contrario. Deathmatch (Todos contra todos). Modo de juego individual en el que gana el jugador que m´as muertes registre en un tiempo determinado o que alcance un nivel predefinido de muertes de jugadores rivales. Team Deathmatch (Combate por equipos). En este modo, las reglas son las mismas que en la modalidad Deathmatch, pero en este caso el marcador ser´a la suma de los resultados individuales de todos los miembros del equipo. Double Domination (Doble dominaci´on). Similar al modo Capture the Flag, este modo por equipos consiste en controlar de manera presencial y simult´anea, la base del propio equipo y del contrario durante un tiempo determinado. Bombing Run (Carrera de bombardeo). Modalidad por equipos con un esquema similar al de un partido de f´utbol adaptado a los escenarios de UT04. Gana el equipo que consiga pasar una bola por un portal un n´umero determinado de veces en un tiempo prefijado. 21 Last Man Standing (´ Ultimo hombre en pie). Similar al modo Deathmatch, pero en este caso cada jugador participa con un n´umero limitado de vidas en la partida. Aunque por la tem´atica de este proyecto, parezca que los modos de juegos por equipos son los m´as indicados, en realidad lo qu´e m´as se ajusta al objetivo de nuestros experimentos es el modo “Capturar la Bandera”. En este modo de juego, tambi´en existe un equipo y adem´as, puesto que el objetivo de nuestros experimentos girar´a alrededor de la exploraci´on del entorno, podremos utilizar las banderas como puntos clave. Figura 4.1: Unreal Tournament 2004 En la actualidad existen muchos videojuegos donde el juego en equipo est´a contemplado. Similares a Unreal tournament podemos encontrar el popular videojuego Counter strike y tambi´en el no menos conocido, Quake. Hemos elegido Unreal tournament por varios motivos, que se enumeran a continuaci´on: Mantiene su c´odigo abierto a todos los usuarios, lo que permite codificar nuestras propias implementaciones de bots a traves de su lenguaje script, Unreal Script, as´ı como la creaci´on de nuevos mapas con la herramienta UnrealEd, incluida en el juego. Existe la herramienta Pogamut, desarrollada por investigadores ajenos a la empresa del videojuego, pero que nos simplificar´a la tarea de crear un bot. Esta herramienta se explicar´a con detalle en la pr´oxima secci´on. Es la herramienta empleada en el concurso a nivel mundial 2kBotPrize, celebrado todos los a˜nos, donde investigadores de todo el mundo presentan sus bots con el objetivo de superar una adaptaci´on al test de Turing. Todos estos puntos parecen indicar que estamos ante la herramienta adecuada donde dise˜nar nuestros experimentos de inteligencia artificial. 22 4.2. Pogamut Pogamut es una plataforma de c´odigo abierto usada para el r´apido desarrollo de comportamientos en agentes virtuales incrustados en un entorno 3D del videojuego Unreal Tournament 2004. Esta herramienta se integra con el entorno de programaci´on NetBeans como un plugin adicional y permite definir el comportamiento de los agentes mediante el uso de Java. Figura 4.2: Arquitectura de Pogamut Pogamut es el encargado de las siguientes tareas: Traducir la informaci´on procedente del servidor mediante el uso de un traductor (o parser) local. El m´odulo traductor es un elemento que precede al cliente y permite simplificar el procesamiento de los mensajes de Gamebots, convirti´endolos de su formato ASCII original, a objetos propios del lenguaje Java. Adem´as, el traductor se encarga de reducir el flujo de informaci´on que llega al cliente, puesto que s´olo le env´ıa aquella que ha sufrido modificaciones desde el ´ultimo env´ıo. Devolver al cliente toda la informaci´on del agente relativa a su propio estado o a la situaci´on del entorno que lo rodea en cada momento de la partida. Esta gesti´on de informaci´on, queda reflejada en NetBeans, ya que dicha herramienta se encarga de mostrar los registros del agente obtenidos por Pogamut. La informaci´on que llega a dichos registros del agente, puede ser s´ıncrona (toda aquella procedente de llamadas realizadas por el usuario) o as´ıncrona (la notificaci´on de eventos ocurridos a lo largo de la partida en momentos puntuales en imprevisibles y que pueden requerir de un trato especial por parte del agente, si as´ı est´a definido en su comportamiento). Gamebots es el m´odulo encargado de la gesti´on de informaci´on en el lado del servidor. Gamebots es una extensi´on de UT2004 que permite controlar los distintos agentes aut´onomos virtuales a trav´es de Unreal Script, mediante una interfaz de comunicaci´on TCP/IP que utiliza mensajes de texto en formato ASCII para transmitir datos. De este modo, no s´olo se pueden controlar los agentes del juego mediante comandos de texto, sino que se recibe informaci´on relativa al estado de la partida en cada instante de tiempo. Figura 4.3: Arquitectura de GaviaLib 23 GaviaLib es una librer´ıa dentro de Pogamut que se encarga de traducir UnrealScript y pasarlo a Java. Permite conectar agentes a casi cualquier entorno virtual. En la Figura podemos ver su arquitectura a alto nivel. (1) Procesa los mensajes del entorno. (2) Env´ıa los comandos al mundo virtual. (3) Interfaz del agente. 4.3. UnrealED Una de las caracter´ısticas centrales y definitivas de Unreal Tournament 2004, y uno de los mayores componentes de su ´exito, es la facilidad con la cual muchos jugadores pueden crear y compartir sus propias modificaciones y contenido propio tales como mapas. Varios de los mapas creados por jugadores suelen ser superiores a aquellos que vienen con el juego. En consecuencia, muchos, sino la mayor´ıa, de los servidores de UT alrededor del mundo incluyen mapas de terceros en sus rotaciones. Los mapas personalizados pueden ser creados con el editor UnrealED incluido con el juego. Nosotros emplearemos la herramienta para construir un mapa sencillo que se adapte a las caracter´ısticas de nuestros experimentos y nos permita ver de forma clara los resultados. Figura 4.4: Mapa creado en UnrealED 4.4. Dise˜no del bot en el entorno UT2004 El dise˜no del bot, es decir, su capacidad de percibir su entorno y de ejecutar sus acciones, viene limitado por las posibilidades del entorno de simulaci´on utilizado. A la hora de abordar el dise˜no de nuestro agente, deberemos tener en cuenta lo que Unreal Tournament 2004 y Pogamut nos permiten hacer. Tendremos que conocer de que manera UT2004 nos posibilita percibir el entorno, as´ı como las posibles acciones que nuestro bot puede ejecutar. 24 Podemos asemejar el comportamiento del bot con el modelo cl´asico de representaci´on de la mente, el cual podemos ver en la figura 4.5. La capa de razonamiento quedar´a de lado del programador, d´onde usando las entradas (percepci´on) facilitadas por el entorno implementaremos un comportamiento para nuestro bot, generando una salida a trav´es de las acciones posibles. Figura 4.5: Modelo de representaci´on cl´asico de la mente Percepci´on Existen dos modos b´asicos de percepci´on para un bot, en el entorno Unreal: percepci´on por “Raycasting” o por mapas de navegaci´on. El raycasting es un m´etodo de percibir el entorno que se basa en rayos, a trav´es de los cuales veremos sus intersecciones con el mapa. Podemos configurar el n´umero de rayos que queramos que nuestro bot lance, as´ı como su longitud. En cada rayo y en cada momento, el bot nos devolver´a un valor binario que nos notificar´a si el rayo correspondiente est´a detectando alg´un objeto, ya sea un bot enemigo, un bot amigo o una pared. La percepci´on a trav´es de mapas de navegaci´ on se apoya en el hecho de que los mapas en UT2004 est´an cubiertos por nodos llamados puntos de navegaci´on (NavPoints). El bot es capaz de saber en todo momento en qu´e punto se encuentra, as´ı como d´onde se encuentran los dem´as puntos en el mapa. En mapas de Unreal bien construidos, cada navpoint est´a situado en un sitio seguro y alcanzable por el bot. Los puntos conectados est´an unidos por una l´ınea. Existen m´as elementos que desarrollan la percepci´on del agente, los cu´ales no vamos a emplear en nuestros experimentos, pero se pueden consultar en el anexo A: Manual de Pogamut. Razonamiento Esta es la capa que corresponde a la implementaci´on del bot, d´onde usaremos los datos proporcionados por la capa perceptiva para modelar el comportamiento de nuestros agentes inteligentes a trav´es de las acciones que ´estos pueden realizar. Para manejar los resultados obtenidos por un bot perceptivo de tipo Raycasting, podemos hacerlos de dos maneras: Creando un listener (Ver glosario), el cual nos notifique cuando un rayo ha recibido alguna se˜nal del entorno o bien comprobando la presencia de alg´un objeto de forma peri´odica. Para usar Raycasting en nuestro bot, debemos seguir dos pasos: 1. Activar raycasting y visualizaci´on de rayos: podemos hacerlo de dos formas, o bien computar continuamente las intersecciones de los rayos con el mundo (Autotrace=true) o bien denir nuestros rayos y calcular solo las intersecciones que nos interesen (DrawTraceLine= true). 2. Inicializar rayos: definimos los rayos que deseemos a trav´es de AddRay, pasandole como par´ametros principales el nombre, el vector de direcci´on y la longitud del rayo. Podemos crear tantos rayos como queramos. 25 En el caso de un bot que base su percepci´on en mapas de navegaci´on, recibiremos a trav´es de un listener el estado del mismo. Para que el bot sea capaz de ir de un sitio A a un sitio B, vamos a necesitar una planificador de ruta: Path planner. En Pogamut existen distintos interfaces de Path planner, siendo UT2004A StarPathPlanner el planificador por defecto. Este planificador usa el algoritmo A* para el calculo de rutas, siendo exactamente el mismo que el de los bots nativos de UT. Tambien existe otra implementaci´on declarada en FloydWarshallPathPlanner, la cual precalcula todas las rutas posibles entre todos los nodos al principio, lo cual tiene un coste inicial considerable. Cabe decir que podemos implementar nuestro propio algoritmo planificador. Una vez tenemos la ruta calculada ya solo nos queda ejecutarla, de ello se encarga el Path executor. Este m´odulo contiene el Path navigator que es el que se encargar de recorrer la ruta calculada anteriormente, evitar obst´aculos, abrir puertas, esperar ascensores, etc. El navegador por defecto es UT2004PathNavigator. En este caso, tambi´en podemos crear nuestro propio navegador. Acciones Las acciones son operadores que pueden llamarse desde la capa de implementaci´on para provocar cambios en el estado del mundo en el que nos encontramos. El movimiento ser´a la acci´on m´as empleada en nuestros experimentos, debido a la naturaleza de los mismos, pero Pogamut nos permite llevar a cabo un gran n´umero de acciones que podemos ver en la tabla 4.2. Act AddBot AddInventory AddRay Combo CommandPlayer Configuration ConfigurationObserver Console ContinuousMove DialogBegin DialogCancel DialogEnd DialogItem DisconnectObserver Dodge DriveTo EndPlayers EnterVehicle FactoryUse FastTrace GetAllInvetories GetAllNavPoints GetAllStatus GetGameInfo GetItemCategory GetMaps GetPath GetPlayers GetSelf GetSpecialObjects GetVisibleObjects GiveInventory ChangeAttribute ChangeMap ChangeTeam ChangeWeapon CheckReachability Initialize InitializeObserver Jump Kick LeaveVehicle Move PasswordReply Pause Pick Ping PlaySound Quit Ready Record RemoveRay Respawn Rotate SendMessage SetCrouch SetDialog SetGameSpeed SetLock SetPassword SetPlayerControl SetRoute SetSendKeys SetSkin SetWalk Shoot ShowText SpawnActor StartAnimation StartPlayers Stop StopRecord StopShooting Throw Trace TurnTo Tabla 4.2: Acciones posibles del bot en Pogamut 26 Cap´ıtulo 5 Experimento 1 - siSosiG Bot Should I stay or should I go now? If I go there will be trouble And if I stay it will be double So come on and let me know (The Clash) 5.1. Descripci´on del problema En este experimento veremos como un equipo de bots en el entorno UT2004, modelado mediante la propuesta presentada en el capitulo 3, es capaz de resolver el problema de encontrar la bandera utilizando t´ecnicas de comunicaci´on a larga distancia. Emplearemos un algoritmo gen´etico para encontrar que combinaciones de bots creen un sistema m´as eficiente. El experimento se desarrolla en un escenario de encontrar la bandera, en el que el objetivo final es que todos los bots lleguen a la bandera enemiga en el menor tiempo posible, sin conocer previamente ning´un dato sobre el mapa. El objetivo de cada bot del equipo es, en primer lugar, encontrar la bandera y posteriormente avisar al resto de sus compa˜neros para que acudan a ella, como podemos ver en la figura 5.1. As´ı pues, cada bot debe escuchar las transmisiones de sus compa˜neros mientras sigue con la b´usqueda individual de la bandera, no pudiendo realizar ambas tareas a la vez. Por este motivo, nos encontramos con el dilema de exploraci´on-explotaci´on planteado en cap´ıtulos previos. Nuestros agentes se mover´an por todo el mapa de manera aleatoria en busca de la bandera, pero tambi´en podr´an esperar a que otros bots la encuentren. Por tanto cada bot tiene dos estados: Escuchando: Cuando se encuentra en este modo, el bot es capaz de recibir transmisiones de sus compa˜neros y se encuentra parado. Por lo tanto, el bot una vez avisado por un compa˜nero de la localizaci´on de la bandera, acudir´a inmediatamente. Rastreando: En este estado el bot se encuentra en movimiento, buscando por puntos aleatorios la bandera. El agente puede encontrar la bandera y avisar a sus compa˜neros, pero si el es avisado por otro bot, la transmisi´on no la recibe hasta que cambia al estado escuchando. 27 Fitness IH - Bot 1 IH - Bot 2 IH - Bot 3 7.187 0.32 0.48 0.56 7.312 0.19 0.41 0.41 7.766 0.02 0.08 0.26 7.766 0.15 0.17 0.29 7.828 0.36 0.46 0.48 7.844 0.15 0.17 0.47 7.875 0.19 0.27 0.93 7.89 0.26 0.34 0.36 8.25 0.35 0.49 0.99 8.25 0.2 0.58 0.66 8.313 0.32 0.48 0.56 8.375 0.04 0.22 0.7 8.437 0.32 0.48 0.56 8.828 0.41 0.45 0.47 8.875 0.34 0.58 0.98 Tabla 5.2: 15 mejores resultados del experimento siSosiG Porcentaje Resuelve en menos de 60.88 % 35 segundos 42.46 % 25 segundos 15.56 % 15 segundos 2.59 % 10 segundos Tabla 5.3: Resultados siSosiG Regresi´on log´ıstica La regresi´on log´ıstica es un modelo de regresi´on para variables dependientes o de respuesta binomialmente distribuidas. El objetivo primordial que resuelve esta t´ecnica es el de modelar c´omo influye en la probabilidad de aparici´on de un suceso, habitualmente dicot´omico, la presencia o no de diversos factores y el valor o nivel de los mismos. En nuestro caso, el suceso ser´a el umbral de segundos que los bots deben superar y los factores ser´an las distintas estructuras y combinaci´on de genotipos. La expresi´on de la regresi´on log´ıstica viene dada por: p(x) = 1 1+e−(B0+B1·x1+...+Bn·xn) donde: p: es la probabilidad de que ocurra el suceso Bx: son los par´ametros calculados por la regresi´on Xi: son las entradas para las que calculamos la probabilidad, en nuestro caso los ´ındices de hiperactividad de cada bot del equipo. El prop´osito del an´alisis con la regresi´on log´ıstica nos permitir´a en nuestro caso: Predecir la probabilidad de que se resuelva el problema por debajo de un determinado umbral (en segundos) para un determinado genotipo. 34 Determinar qu´e variables (´ındices de hiperactividad) pesan m´as para aumentar o disminuir la probabilidad de tener ´exito en la tarea. Esta asignaci´on de probabilidad de ocurrencia del evento a un cierto genotipo, as´ı como la determinaci´on del peso para cada una de las variables dependientes en esta probabilidad, se basan en las caracter´ısticas que presentan los distintos genotipos simulados. Para poder analizar correctamente los resultados, hemos ordenado los ´ındices de hiperactividad de los bots en orden creciente. Estos nos permitir´an calcular de forma coherente las medias y desviaciones t´ıpicas de cada uno de los ´ındices, como podemos ver en la figura 5.4, lo que nos servir´a para realizar unas nuevas simulaciones de comprobaci´on de los resultados de la regresi´on. Los resultados obtenidos con la regresi´on log´ıstica para los 2900 datos y los umbrales de fitness 35, 25, 15 y 10 los podemos ver en la tabla 5.5. En dicha tabla podemos ver tanto los coeficientes que se aplicar´an a cada entrada (IH del bot), as´ı como sus respectivos p-valores. Un coeficiente positivo, indica que un valor m´as alto de la entrada har´a que el sistema tenga m´as posibilidad de tener ´exito. Lo contrario ocurre con coeficientes negativos. El p-valor nos indica la relevancia, a la hora de calcular la probabilidad final de que un objetivo se cumpla, de cada uno de los coeficientes. En la regresi´on log´ıstica, un p-valor mayor que 0.05, indica que el coeficiente sobre el que se aplica no es significativo (marcados en rojo). Bot Media Desv. T´ıpica Rango B1 (bajo) 0.26 0.19 0.07 - 0.45 B2 (medio) 0.51 0.22 0.29 - 0.73 B3 (alto) 0.75 0.19 0.56 - 0.94 Tabla 5.4: Medias y desviaciones t´ıpicas para cada uno de los bots en el experimento siSosiG Umbral B1 B2 B3 Coef. P-valor Coef. P-valor Coef. P-valor 35 1.00155 0.0 0.982621 0.0 0.184483 0.453 25 0.705250 0.003 1.01927 0.0 0.583642 0.023 15 0.742842 0.012 1.16226 0.001 0.996409 0.010 10 0.0120865 0.988 -0.046455 0.956 -2.18946 0.003 Tabla 5.5: Resultados obtenidos en el experimentos siSosiG con regresi´on log´ıstica Con todos los datos calculados, queremos comprobar si la regresi´on ha sido efectiva y nos ha servido para configurar equipos de bots que resuelvan de forma m´as r´apida el problema de encontrar la bandera, dentro de sus umbrales de tiempo. Para ello vamos a crear un equipo de bots para cada umbral, siguiendo las siguientes normas: 1. Si el p-valor nos indica que el coeficiente de un determinado bot no es significativo, tomaremos el valor medio del IH de dicho bot. 2. En caso de que el coeficiente sea positivo, y el p-valor indique que es relevante, cogeremos el IH m´as grande dentro de su rango. 3. Si nos encontramos con que el coeficiente es negativo y el p-valor nos revela que es significativo, cogeremos el IH m´as peque˜no dentro del rango obtenido con la media y la desviaci´on t´ıpica. Por tanto, siguiendo esta reglas obtenemos los distintos equipos para cada uno de los umbrales que podemos ver en la figura 5.6. 35 Umbral B1 B2 B3 35 0.45 0.73 0.75 25 0.45 0.73 0.94 15 0.45 0.73 0.94 10 0.26 0.51 0.56 Tabla 5.6: Equipos de bots creados para probar los resultados de la regresi´on log´ıstica Con los equipos ya creados, simularemos cada uno de ellos 2900 veces, esta vez sin un proceso gen´etico puesto que estamos ante genotipos que no van a cambiar. El objetivo de estas simulaciones es ver si los resultados que nos ha proporcionado la regresi´on log´ıstica son v´alidos y nos ha permitido obtener unas configuraciones de bots, que son m´as eficientes a la hora de afrontar la tarea en sus diferente umbrales. Los resultados de las simulaciones los podemos ver en la tabla 5.7, donde marcamos con verde los que han superado a simulaci´on general y en rojo los que no. Gr´aficamente podemos ver los resultados en la figura 5.5. Umbral General Equipo 35 Equipo 25-15 Equipo 10 35 60.88 % 71.11 % (*) 67.20 % 64.52 % 25 42.46 % 53.45 % (*) 51.33 % 43.67 % 15 15.56 % 20.18 % 20.98 % 10.62 % 10 2.59 % 0.76 % 0.49 % 4.75 % (*) Tabla 5.7: Resultados de las simulaciones de los equipos de bots que hemos generado a partir de la regresi´on log´ıstica. (*) Mejores resultados para el umbral Figura 5.5: Resultados gr´aficos de las simulaciones de los equipos de bots que hemos generado a partir de la regresi´on log´ıstica 5.4.2. Interpretaci´on En primer lugar vamos a presentar las posibles razones de las configuraciones de los equipos que nos ha dado la regresi´on log´ıstica: Equipo umbral 35: Resolver el problema en menos de 35 segundos no es algo complicado, como podemos deducir de los resultados de la simulaci´on general, en la que casi un 61 % de los equipos los consiguen. Como el tiempo de ciclo son 10 segundos, tenemos 3 ciclos y medio para llegar a nuestro objetivo. Con bots con un IH bajo, estamos perdiendo capacidad 36 de exploraci´on y como tenemos varios ciclos (los bots que encuentren la bandera tienen tiempo para avisar a sus compa˜neros) nos interesa tener bots bastante activos, que busquen la bandera y avisen a sus compa˜neros. El bot 3 ya es activo de por s´ı, por lo que nos dar´a igual su valor siempre que nos movamos en sus rangos de valores. Equipo umbral 25-15: En este caso tenemos menos ciclos para resolver el problema, por lo que necesitaremos bots todav´ıa m´as activos, a´un a riesgo de tener problema de comunicaci´on. Por ese motivo cogemos el valor m´as alto del B3, al igual que en B1 y B2. Equipo umbral 10: Superar este umbral es algo muy complicado, un porcentaje muy bajo de equipos lo consigue. En este caso todo depende del bot m´as activo (B3), puesto que un valor muy alto le supondr´a tener que encontrar la bandera y avisar a los dem´as. En el caso de que ´este no la encuentre y lo haga uno de sus compa˜neros, es posible que no escuche la transmisi´on puesto que sigue explorando el terreno. Por tanto, nos interesa un valor bajo de B3 para que cualquiera de los bots que componen el equipo sea capaz de recibir la transmisi´on y llegar hasta la bandera en menos de 10 segundos. Los resultados obtenidos en la primera simulaci´on, son inferiores a casi todos los obtenidos por los nuevo equipos. Esto es debido a que la evoluci´on gen´etica introduce en muchas ocasiones genotipos con poco sentido, como puede ser un equipo de bots con los valores B1=0.01, B2=0.05, B3=0.06. Estamos ante un entorno muy aleatorio, puesto que hemos dejado mucha libertad en los movimientos de los bots, y la funci´on fitness no castiga ni premia ning´un comportamiento, solo es dependiente del tiempo en el que se resuelve la tarea. Esto se hace latente en los resultados, puesto que para el mismo equipo de bots, rara vez se obtiene el mismo resultado. La aleatoriedad del experimento no lo hace inv´alido, si no que introduce un factor de peso que marcar´a los resultados. Podemos dar el experimentos como v´alido, demostrando que si queremos superar alguno de los umbrales, con el uso de los equipos obtenidos con la regresi´on log´ıstica, tendremos mas posibilidades de ´exito. 37 38 Cap´ıtulo 6 Experimento 2 - Pathwalker Bot Wanderer, your footsteps are the road,and nothing more; wanderer, there is no road, the road is made by walking. (Antonio Machado) El objetivo de este experimento es demostrar que un grupo de bots totalmente iguales (aproximaci´on clonal), usando t´ecnicas basadas en algoritmos bioinspirados tipo swarming, son capaces de resolver ciertas tareas en su entorno. Para poder quitar ese grado de aleatoriedad que ten´ıa el experimento anterior vamos a introducir: (1) una implementaci´on del bot con un movimiento menos aleatorio, gracias a la feromona, y (2) una funci´on fitness m´as espec´ıfica, lo que nos permitir´a reducir la aleatoriedad de los resultados cuando se repite el experimento con los mismos genotipos. 6.1. Descripci´on del problema Nos encontramos en un mapa de captura de bandera. El objetivo de nuestro equipo de bots es en primer lugar encontrar una de las banderas (la enemiga o la del propio equipo) y posteriormente normalizar un camino entre ellas, a trav´es de un rastro que los bots dejan a su paso, como podemos ver en la figura 6.1, para que todos los dem´as bots del equipo puedan encontrarlas tambi´en. En el momento que el ultimo bot encuentre una de las dos banderas, daremos el experimento como v´alido. Es este caso no habr´a comunicaci´on directa entres los miembros del equipo, pero podr´an guiar su movimiento gracias al rastro de una “feromona”. Tal y como explicamos en el cap´ıtulo anterior, los mapas de Unreal Tournament, tienen definidos una serie de puntos de navegaci´on (NavPoints) que el bot puede emplear para moverse por ellos. Inicialmente, los bots ser´an creados en varios puntos de navegaci´on predefinidos, etiquetados como “PlayerStart-X”. Deber´an encontrar el punto de navegaci´on en el cual se encuentra la bandera enemiga. Para ello, se mover´an entre los puntos de navegaci´on, calcul´andose donde tienen que realizar el pr´oximo movimiento, realizando siempre un movimiento a los puntos de navegaci´on adyacentes. Vamos a crear un modelo bioinspirado, asemej´andonos con el mecanismo que tienen las hormigas para crear caminos. Uno de los retos de trabajar con algoritmos de hormigas, es que estos 39 Figura 6.1: Ejemplo del rastro de feromona que los bots dejan a su paso incluyen una serie de par´ametros que regulan el comportamiento de nuestro sistema. Estos par´ametros regulan la influencia de la selecci´on de los distintos caminos por parte de las hormigas, pudiendo: Seguir: El bot toma un camino ya creado y conocido. Explorar: El bot sigue un camino desconocido, con la posibilidad de encontrar una soluci´on al problema. Como podemos observar, se nos plantea de nuevo el dilema de exploraci´on-explotaci´on explicado en el cap´ıtulo anterior. Ambos factores tendr´an relaci´on directa con el valor de la feromona en los distintos puntos y con los par´ametros que marcar´an la rapidez de crecimiento y evaporaci´on de la feromona. 6.2. Implementaci´on Para simbolizar el comportamiento de un grupo de hormigas, vamos a crear un tabla con los diferentes puntos de navegaci´on del mapa, asignando un valor de feromona a cada NavPoint. Inicialmente el valor de la feromona ser´a vac´ıo, lo que nosotros representaremos con el valor num´erico 1 por cuestiones de implementaci´on. La feromona puede variar por dos motivos: 1. Un bot pasa por el punto de navegaci´on: Esto har´a que el valor de la feromona aumente. El aumento depender´a de una funci´on matem´atica que definiremos m´as adelante. 2. Evaporaci´on de la feromona: Tal como en el mundo natural, el entorno hace que la cantidad de feromona depositada en punto se vaya diluyendo con el paso del tiempo, si dicho punto no es visitado por ninguna hormiga. Al igual que en el punto anterior, una funci´on matem´atica se aplicar´a cada cierto tiempo para simular esa p´erdida de feromona. A la hora de moverse por el mapa, los bots tendr´an en cuenta la feromona de sus puntos adyacente. El siguiente movimiento de cada bot vendr´a decidido por un algoritmo aleatorio con pesos, por tanto tendr´a m´as posibilidades de ser visitado un NavPoint con un mayor nivel de feromona. Se emplear´a un algoritmo de selecci´on por ruleta para calcular el punto destino. Se ponderar´a a 100 la suma de los valores de la feromona de todos los puntos de navegaci´on adyacentes, y a cada NavPoint se le asignar´a una porci´on de ruleta, que corresponder´a con su valor 40 de feromona ponderado. Seguidamente se lanza el selector y nos da el punto destino. Evidentemente tiene mayor probabilidad el NavPoint con mayor activaci´on de feromona. Uno de los aspectos m´as importantes del sistema es mediar como el nivel de feromona va cambiando a lo largo de la partida. Esto vendr´a determinado por el n´umero de bots que pasen por cada NavPoint, as´ı como el proceso que diluye dicha feromona. Como hemos dicho anteriormente, vamos a calcular la velocidad con la que la feromona aumenta o se diluye, a trav´es de dos par´ametros incluidos en las funciones matem´aticas de incremento y decremento. A continuaci´on podemos ver la funci´on de incremento de feromona: I(ti) = A(1 −e−ti/τ )+1 donde: A: L´ımite superior de feromona. Es el valor donde la feromona satura, es decir, llega un momento que por muchos bots que pasen, la feromona no sigue creciendo. Nosotros hemos puesto en 30 el valor l´ımite. τ: Par´ametro que marca la rapidez de crecimiento, inversamente proporcional a su valor Figura 6.2: Funci´on de incremento con τ= 2,5 En la figura 6.2, podemos ver un ejemplo de como se comportar´ıa el crecimiento de la feromona con un valor de τde 2.5. Dicha gr´afica representar´ıa la evoluci´on de un ´unico Navpoint. Podemos ver que, aproximadamente, cuando 14 bots pasen por encima de dicho punto, la feromona saturar´a. Eso suponiendo que no tuvi´eramos ning´un funci´on que diluya la feromona, lo cual, no es nuestro caso. Cuando en un punto de navegaci´on no pase ning´un bot, cada segundo se ejecutara una funci´on matem´atica que har´a que la feromona vaya perdiendo fuerza. Esta funci´on depende del par´ametro ε: I(td) = A(e−td/ε)+1 donde: A= L´ımite superior de feromona, igual que en la f´ormula anterior. ε= Par´ametro que marca la rapidez de decrecimiento, inversamente proporcional a su valor. En la figura 6.3 podemos ver como un NavPoint con la feromona saturada, se diluye con el paso el tiempo hasta llegar a su l´ımite inferior, 1. 41 Figura 6.3: Funci´on de decremento con ε= 5,5 Una vez con ambas f´ormulas en funcionamiento, aparte de las gr´aficas anteriores, podremos obtener durante la simulaci´on una gr´afica que sea una mezcla de ambas. Esto es debido al paso intermitente de bots por los puntos de navegaci´on, que har´an que el valor de la feromona vaya aumentando o disminuyendo de una manera no lineal. Figura 6.4: Ejemplo del valor de la feromona de un NavPoint con τ= 2,5 y ε= 5,5 En la figura 6.4, vemos un ejemplo de c´omo se comportar´a el valor de la feromona en un determinado NavPoint para los valores dados de tau y epsilon. A la hora de aplicar estas dos funciones simult´aneamente hay que tener en cuenta el valor de la feromona en el instante en el que se aplica cada una. Como podemos ver en la figura 6.5, cuando en un determinado momento tengamos que cambiar la funci´on a aplicar (punto A), deberemos conocer el valor de tiempo que provocar´ıa que nuestra funci´on a aplicar tuviera el valor de feromona actual (punto B). Una vez que tenemos dicho valor lo incrementaremos en una unidad y calcularemos en siguiente valor de feromona (punto C). Dependiendo de la funci´on que queramos aplicar deberemos calcular Tipara la funci´on de incremento, siendo I el valor actual de la feromona, la cual podemos se define de la siguiente manera: Ti =−ln(1−I A+ 1) ·τ oTd, en el caso del decremento: Td =−ln(I−1 A)· 42 Figura 6.5: C´alculo del siguiente valor de la feromona al cambiar la funci´on a aplicar 6.3. Estudio anal´ıtico Como podemos ver en el apartado anterior, el valor de la feromona es lo que va a marcar en mayor medida el movimiento de nuestros bots. Nos interesa entonces, una vez que el primer bot ha encontrado la ruta entre banderas, que en el camino existente en dicha ruta el valor de la feromona est´e siempre saturado, tal y como podemos ver en la figura 6.6, representando el valor medio de la feromona en el camino entre banderas con respecto al tiempo: phpath(t). Esto provocar´ıa que todos los agentes que todav´ıa no est´an por ese camino, se sintieran fuertemente atra´ıdos por ´el, abandonando su exploraci´on propia en curso. Figura 6.6: Escenario ideal del valor de la feromona, donde T0es el tiempo que tarda el primer bot en encontrar el camino entre banderas. El eje Yrepresenta el valor medio de la feromona en todos los puntos del camino. Hemos descrito la situaci´on ideal, algo imposible que se de en la realidad, puesto que los valores de τyque dieran lugar al estado descrito provocar´ıan que se crearan otros caminos con un alto valor de feromona( ya que no tenemos manera alguna de indicar que solo queremos que se alimente el camino entre banderas). Por tanto, tendremos que buscar el equilibrio entre la creaci´on de caminos y la realimentaci´on de los ya creados, lo cual ser´a totalmente dependiente de τy. Puesto que no podemos llegar a obtener la situaci´on ideal descrita, tendremos que intentar alcanzar una soluci´on que sea lo m´as parecida posible, es decir, una soluci´on que se ajuste lo m´aximo posible al ideal. Este ajuste es lo que nos dir´a lo buena o mala que es una soluci´on propuesta. Una funci´on dependiente de la feromona y el tiempo se estar´a ajustando al estado ´optimo cuando el valor de la 43 Pogamut provoca alternancias entre dos valores (siendo el m´as habitual un tiempo de ciclo 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). Por este motivo, hemos optado por la implementaci´on de un Timer en Java. Debido a la mala gesti´on de los recursos por parte de Pogamut, en ocasiones el c´alculo de rutas no se calcula correctamente, 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. En cuanto a las simulaciones que hemos realizado, nos hemos dado cuenta la importancia, por un lado, del estudio anal´ıtico previo que nos permite definir una correcta funci´on de adecuaci´on y por otro, las t´ecnicas que empleemos para analizar los resultados obtenidos. Los algoritmos gen´eticos han sido una pieza clave para resolver nuestros problemas, puesto que nos han permitido realizar una tarea de b´usqueda y ajuste a soluciones ´optimas. Modelos y recursos como las cadenas de Markov y la regresi´on log´ıstica nos han sido de gran utilidad para poder implementar nuestros experimentos correctamente y poder sacar conclusiones acertadas sobre nuestros resultados. 7.1. Trabajo futuro Durante la realizaci´on de este proyecto se ha realizado un manual de Pogamut para programadores (ver Anexo A), por lo que los trabajos futuros podr´an montar su sistema r´apidamente y comenzar directamente a realizar sus simulaciones. Tambi´en se podr´a emplear las clases en Java creadas que implementan algoritmos gen´eticos, para ajustar diferentes implementaciones de los bots que se programen. Tras la realizaci´on de este proyecto se proponen a continuaci´on algunas de las posibles l´ıneas de trabajo futuras: Probar nuevas t´ecnicas y metodolog´ıas de IA sobre la plataforma UT2004 + Pogamut Emplear m´as variables de entrada al sistema (percepci´on del bot) y su vez generar m´as variedad de salidas del bot (acciones) para implementar bots m´as reactivos. Trabajar con las nuevas actualizaciones de Pogamut, las cuales permiten obtener m´as y mejores datos, de esta manera se podr´ıa depurar el c´odigo obteniendo seguramente mejores resultados, especialmente en lo referente a movimientos y disparos del bot Contribuir al desarrollo de la plataforma Pogamut, de forma que ´esta permita la paralelizaci´on de evoluciones de cara al aprendizaje evolutivo. Introducir nuevas hip´otesis anal´ıticas derivadas de las ya existentes. Nuevas funciones de ajuste, nuevos dilemas E-E, etc. 50 Glosario Bot: Agente aut´onomo virtual. E-E: exploration vs exploitation Dilemma. IA: Inteligencia artificial. Listener: Evento manejable por el programador, creado por el entorno Unreal. SISOSIG: Should I Stay Or Should I Go. NPC: Siglas del t´ermino ingl´es “Non-Playing Character”. Utilizado como sin´onimo de bot y agente aut´onomo. Juegos de Shooter: Juegos de car´acter b´elico en los que el objetivo del usuario es abrirse camino a trav´es del juego disparando a todo jugador que se ponga a tiro. FPS: Siglas del t´ermino ingl´es “First Person Shooter”. Genero de videojuegos de disparos en primera persona. TCP/IP: Modelo de descripci´on de protocolos de red. El modelo TCP/IP, describe un conjunto de gu´ıas generales de dise˜no e implementaci´on de protocolos de red espec´ıficos para permitir que un ordenador pueda comunicarse en una red. UnrealScript: Lenguaje pensado exclusivamente para desarrollar contenido para juegos que usen el motor Unreal. Est´a basado en Java y C++. Es un lenguaje de programaci´on orientado a objetos (OOP - Object Oriented Programming) lo que significa que est´a basado en los conceptos de clases y herencias. Es importante hacer notar que UnrealScript no tiene todas las caracter´ısticas de un lenguaje de programaci´on m´as completo. API: Interfaz de programaci´on de aplicaciones (del ingl´es Application Programming Interface) es el conjunto de funciones y procedimientos (o m´etodos, en la programaci´on orientada a objetos) que ofrece cierta biblioteca para ser utilizado por otro software como una capa de abstracci´on. 51 52 Bibliograf´ıa [J. Laird, 2000] Laird, J. E. It Knows What You’re Going To Do: Adding Anticipation to a Quakebot (2000) 1.1, 1.2.2 [Gemrot et al., 2009] Gemrot, J. and Kadlec, R. and B´ıda, M. and Burkert, O. and P´ıbil, R. and Havl´ıcek, J. and Zemc´ak, L. and Simlovic, J. and Vansa, R. and Stolba, M. and Plch, T. and Brom, C. Pogamut 3 Can Assist Developers in Building AI (Not Only) for Their Videogame Agents. Agents for Games and Simulations: Lecture Notes in Computer Science, 2009, Volume 5920/2009, 1-15, DOI: 10.1007/978-3-642-11198-3 1. 2009. 2.1, 5.1 (document), 1.1 [Holland, 1992] John H. Holland, Adaptation in Natural and Artificial Systems, MIT Press, 1992. (document), 1.1, 2.2, 3.3.2 [Mind, 1950] Turing, A.M. Computing Machinery and Intelligence. Mind 49: 433-460. 1950. 1.3 1.2.1 [Thrun, 1992] S. B. Thrun, “Efficient exploration in reinforcement learning”, Technical Report CMU-CS-92-102, School of Computer Science, Carnegie Mellon University, 1992. 2.2 [Reynolds, 1987] Reynolds CW (1987). ”Flocks, herds and schools: A distributed behavioral model”. Computer Graphics 21 (4): 25–34. doi:10.1145/37401.37406. ISBN 0-89791-227- 6.owards an ai behavior toolkit for games”, AAAI Symposium on AI and Interactive Entertainment, 2001. [Buro, 2005] M. Buro, ”ORTS: A Hack-Free RTS Game Environment”, Proceedings of the International Computers and Games Conference 2002, Edmonton, Canada. [Buro, 2003] M. Buro,”Real-Time Strategy Games: A new AI Research Challenge”, Proceedings of the International Joint Conference on AI 2003, Acapulco, Mexico. [Goldberg, 1989] Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA. 3.3.2 [T. Furtak, 2004] M. Buro and T. Furtak, ”RTS Games and Real-Time AI Research”, Proc. of the Behavior Representation in Modeling and Simulation Conference (BRIMS 2004), Arlington VA. [Hoang el al, 2005 ] Hoang, H., Lee-Urban, S., and Mu˜noz-Avila, H. Hierarchical Plan Representations for Encoding Strategic Game AI . Proceedings of Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE-05). AAAI Press. [Sukthankar, 2007] G. Sukthankar and K. Sycara.” Policy Recognition for Multi-Player Tactical Scenarios”. Proc. of Int. Conf. on Autonomous Agents and Multi-agent Systems (AAMAS), 2007. 53 [Brooks, 1987] R. A. Brooks, ”Planning is just a way of avoiding figuring out what to do next”, Technical report, MIT Artificial Intelligence Laboratory. 1987. [Arrabales, 2009] R. Arrabales, A. Ledezma and A. Sanchis. Establishing a roadmap and metrics for conscious machines development. Proceedings of the 8th IEEE International Conference on Cognitive Informatics, to be published 2009. [Lemke, 2008] A. Lemke and L. Zilmer-Perdersen, ”Virtual Evacuation Training using Interactive Cognitive Agents,” Master’s Thesis. Technical University of Denmark, 2008. [van Lent el al, 1999] van Lent, Laird, J. E., Buckman, J., Hartford, J., Houchard, S., Steinkraus, K., and Tedrake, R. Intelligent Agents in Computer Games, Proceedings of the National Conference on Artificial Intelligence, July 1999, Orlando, FL, pp. 929-930. [Ferber, 1999] Ferber. J. Multi-Agent Systems. An Introduction to Distributed Artificial Intelligence. Addison Wesley, London, 1999. 2.1 [Wesson et al., 1988] Wesson R.: et all ”Network Structures for Distributed Situation Assessment”. Readings in Distributed Artificial Intelligence, Ed. Alan H. Bond and Les Gasser, Morgan Kaufmann 1988. 2.1 [Sang Hoon et al., 2009] Sang Hoon Kang, Maolin Jin, and Pyung Hun Chang. “A Solution to the Accuracy/Robustness Dilemma in Impedance Control” 2009. 2.2 [Diego F. et al, 2009] Diogo F. De Oliveira, Anne M. P. Canuto, and Marcilio C. P. De Souto. 2009. The diversity/accuracy dilemma: an empirical analysis in the context of heterogeneous ensembles. In Proceedings of the Eleventh conference on Congress on Evolutionary Computation (CEC’09). IEEE Press, Piscataway, NJ, USA, 939-946. 2.2 [Kramer, 2001] D. Kramer and R. McLaughlin. The behavioural ecology of intermittent locomotion. American Zoologist, 41:137–153, 2001. [O’Brien et al, 1989] W. J. O’Brien, B. I. Evans, and H. I. Browman. Flexible search tactics and efficient foraging in saltatory searching animals. Oecologia, 80(1):100–110, 1989. [Sonerud, 1992] A. Sonerud. Search tactics of a pause-travel predator: adaptive adjustments of perching times and move distances by hawk owls (surnia ulula). Behavioral Ecology and Sociobiology, 30(3): 207–217, 1992 [Langton, 1989] C. G. Langton, “Artificial Life,” Artificial Life, vol. 73, no. 1-2, p. xxix + 655, 1989. 2.1.1 [Terzopoulos, 1999] D. Terzopoulos, “Artificial life for computer graphics,” Communications of the ACM, vol. 42, no. 8, pp. 32-42, Aug. 1999. 2.1.1 [Bajec et al, 2007] I. L. Bajec, N. Zimic, and M. Mraz, “The computational beauty of flocking: boids revisited,” Mathematical and Computer Modelling of Dynamical Systems, vol. 13, no. 4, pp. 331-347, Aug. 2007. 2.1.1 [Berg, 1993] Berg, BC. Random Walks in Biology. Princeton University Press. 1993 2.1.1 [Russel et al, 2003] ] R. A. Russell, A. Bab-Hadiashar, R. L. Shepherd, and G. W. Gordon, “A comparison of reactive robot chemotaxis algorithms,” Robot. Auton. Syst., vol. 45, pp. 83–97, 2003. 2.1.1 [Grasso et al, 2000] Grasso, F.W. , T.R. Consi, D.C. Mountain and J. Atema (2000) Chemo- Orientation in Turbulence with a Biomimetic Robot Lobster. Journal of Robotics and Autonomous Systems. 30:115-131. 2.1.1, 3.1 54 [Barlow, 1969] H.B. Barlow, Sensory Communication. MIT Press, 1969. 2.1.1 [Hamza, 2006] Hamza, MH, Robotics and Applications. Salzburgo ACTA Press, 2006. 2.1.1 [Sutton et al, 1998] ] Sutton, R.S. & Barto, A.G.. Reinforcement Learning: An Introduction (Adaptive Computation and Machine Learning). MIT Press, Cambridge, MA (1998). 2.1.2 [Vergassola et al, 2008] Massimo Vergassola, Emmanuel Villermaux & Boris I. Shraiman, ”’Infotaxis’ as a strategy for searching without gradients”, in Nature, volume 445, pages 406–409 (2007 January 25); 2008 (document), 1.1, 3, 3.1, 3.1 [Spivey, 2007] Spivey, J. (2007). The continuity of mind. New York: Oxford University Press. [Busemeyer et al, 2006] Busemeyer,T., Ryan K. Jessup, Joseph G. Johnson, James T. Townsend (2006). Building bridges between neural models and complex decision making behaviour. Neural Netw. 2006, 19(8):1047-58. [von Mammen et al, 2009] von Mammen, S., Jacob, C. (2009). Swarming for Games: Immersion in Complex Systems. In Applications of Evolutionary Computing, EvoWorkshops 2009. Springer. 3.2 [Spalazzi, 2001] Luca Spalazzi, A Survey on Case-Based Planning. Articial Intelligence Review 16: 3–36, 2001 (document), 2.2, 2.3 [Oviedo, 2005] Oviedo, J. M. (2005). Programaci´on Din´amica. La Ecuaci´on de Bellman y el Teorema de la Envolvente. Universidad Nacional de C´ordoba - Argentina 55