Home

Extendiendo Darmok, un Sistema de Planificación Basada en

image

Contents

1. 5 3 Resultados del experimento 3 por cer e b XIII XIV NDICE DE TABLAS Introducci n El desarrollo de videojuegos ha experimentado una gran evoluci n durante las ltimas dos d cadas en especial gracias a la aparici n de equipos inform ti cos con un hardware m s potente que ha permitido dar soporte a gr ficos y sonido mucho m s realistas Al mismo tiempo la inteligencia artificial IA en videojuegos est adquiriendo cada vez un papel m s relevante Una IA de alta calidad supone incrementar el valor de entretenimiento de un juego y como consecuencia se alcanza un mayor n mero de ventas Debe tenerse en cuen ta que el mbito de los videojuegos no se reduce solamente al l dico Cada vez m s los videojuegos se est n usando como herramientas de educaci n y entrenamiento en todo tipo de reas militar econ mica o universitaria por nombrar unos ejemplos El problema del desarrollo de IAs en videojuegos es que por lo general stos simulan entornos virtuales donde el espacio de soluciones es inmaneja ble y en los que adem s se tiene que tomar decisiones en tiempo real En este contexto las t cnicas cl sicas de b squeda mediante la exploraci n del espacio de soluciones son inaplicables hecho que ha motivado la aparici n de t cnicas alternativas capaces de hacer frente a este doble requerimiento Los juegos de estrategia en tiempo real son un claro ejemplo de ello tienen espacios de decis
2. lt ExecutionConditionsOutputDirectory gt Name of the directory where execution conditions are created lt ExecutionConditionsOutputDirectory gt lt Configuration gt The order in which the elements are specified is not relevant If the input files do contain only actions parameters related to conditions may not be specified and vice versa The r option is used to add a path to the beginning of the files listed in the configuration file as a result each file is considered to be placed at the path specified in the r option The r option may not be specified in which case the files are considered to be at the current execution directory The o option standing for overwrite is either is specified or not If it is not specified generated output files will not overwrite any existing file in the file system and as a result the corresponding class file will not be produced in case there is a file with the same name in the file system If the option o is specified then generated output files will overwrite any file in the file system whose name matches So in brief this program parses a MMPM domain file and for each action and boolean sensors produces the JBT classes that are required to run such actions and conditions in a BT In particular the created execution classes define what they will do when spawned and ticked The generated ModelAction and ModelCondition classes are complete so they do not need to be modified after being
3. 4 1 2 Modelo Independiente de Ejecuci n Cuando se ejecutan rboles de comportamiento surge la necesidad de reuti lizar un mismo rbol en varias entidades del juego es decir hacer que varias entidades del juego sigan el comportamiento definido en un mismo rbol El enfoque m s simple a trav s del que resolver esta situaci n consiste en partir de un modelo de rbol arquetipo y hacer una copia del rbol para cada entidad del juego que necesite usarlo El problema de este m todo es que si son numerosas las unidades que hacen uso del rbol para cada una de ellas existir a una copia ntegra de ste En caso de que el rbol sea grande y o muchas entidades del juego lo requieran el consumo en memoria podr a dispararse Una soluci n m s adecuada pasa por definir el rbol a nivel conceptual de modo que un int rprete de rboles se encarga de leerlo e ir ejecut ndolo conforme se necesite Seg n este enfoque que es el adoptado por JBT existe un int rprete por cada entidad del juego que necesita ejecutar el rbol Cada int rprete recibe una referencia al modelo del rbol que se quiere ejecutar de modo que todos comparten el nico modelo definido para el rbol As aunque para cada entidad exista un int rprete a nivel global existe una nica copia del rbol con el consiguiente ahorro en memoria Se hace as una clara distinci n entre el rbol que est siendo ejecutado el modelo y c mo est siendo ejecutad
4. A 2 1 Model Driven by Ticks JBT implements a BT model driven by ticks A BT must be evaluated through ticks so every game cycle an external caller ticks the tree in order for the tree to update its status A tick is just a way of giving the tree some CPU time to update their status in particular ticks are used to give the nodes of the tree some time to evaluate whether they have finished or not and consequently make the tree evolve The simplest approach to BTs driven by ticks is that of ticking the root node and then letting each node recursively tick its children according to its semantics However this is a very inefficient process since in general the major part of the nodes of the tree are just waiting for their children to finish The refore they should not receive ticks since unless their children are done they will do nothing useful when receiving the tick Therefore in general only very few nodes should be ticked at a game cycle and as a result JBT implements a model in which there is a list of tickable nodes Only the nodes in the list can be ticked A 2 JBT AN OVERVIEW 55 BT Executor Model BT sy Control module OVA K k m Entity N W Execution BT y BT A BT T Entity 1 Entity 2 tick Game Al Figura A 1 Overview of the BT architecture A 2 2 Model Independent from Execution When running
5. Extendiendo Darmok un Sistema de Planificaci n Basada en Casos mediante Arboles de Comportamiento Proyecto Fin de M ster en Sistemas Inteligentes M ster en Investigaci n en Inform tica Facultad de Inform tica Universidad Complutense de Madrid Autor Ricardo Juan Palma Dur n Director Pedro Antonio Gonz lez Calero Curso 2009 2010 Extendiendo Darmok un Sistema de Planificaci n Basada en Casos mediante Arboles de Comportamiento Ricardo Juan Palma Dur n Universidad Complutense de Madrid odracirnumiraQgmail com II Agradecimientos Desde un principio querr a dar las gracias a todas aquellas personas que han hecho posible la realizaci n de este proyecto A Santiago Onta n Villar por ofrecerme su ayuda de forma continua hasta el ltimo momento y por llevar a sus espaldas la dura tarea de definir el dominio MakeMePlayMe de StarCraft A Pedro y Marco G mez Mart n gracias a cuyas ideas fue posible la implementaci n del framework de desarrollo de rboles de comportamiento Y a Pedro Antonio Gonz lez Calero director de este proyecto el cual a pesar de las incontables tareas que como investigador profesional le agobian pudo sacar tiempo y ganas de guiar a este pobre hombre descarriado III AGRADECIMIENTOS Abstract The combination of learning and planning has proved an effective solution for real time strategy games Nevertheless learning hierarchical plans from expert traces also has its limi
6. En el contexto de los rboles de comportamiento un decorador es una tarea que tiene un nico hijo y que modifica su comportamiento Como todos los nodos de los rboles de comportamiento comparten la misma interfaz a nivel externo el resto del rbol no ver diferencia con respecto a si est lidiando con 18 CAP TULO 2 RBOLES DE COMPORTAMIENTO el decorador o con la tarea original decorada Existe un amplio repertorio de tareas decoradoras El inversor es un decorador que invierte el resultado de la ejecuci n de la tarea que decora As el inversor ejecuta su tarea decorada y cuando sta finaliza invierte su estado Si devuelve xito el inversor devolver fracaso y su devuelve fracaso el inversor devolver xito El decorador repetir juega el papel de un bucle sin fin Este decorador ejecuta su hijo y cuando ste finaliza vuelve a ejecutarlo En realidad el nodo repetir no finaliza su ejecuci n nunca de modo que nunca devuelve un estado de xito o de fracaso El nodo hasta fallo se comporta de forma similar al nodo repetir con la diferencia de que la ejecuci n del hijo se repite s lo mientras el hijo tenga xito En cuanto el hijo finaliza su ejecuci n en fracaso el decorador hasta fallo finaliza y devuelve xito como estado de su ejecuci n este decorador s lo puede devolver xito como estado de ejecuci n El decorador limitar limita el n mero de veces que la tarea decorada se ejecuta Este decorador e
7. FAILURE o no terminaci n RUNNING Para tareas intermedias el m todo update llama de manera recursiva al m todo update de sus hijos activos analiza sus estados de terminaci n y dependiendo de ellos devuelve uno u otro estado de terminaci n El m todo abort se emplea en situaciones en las que se debe terminar de manera abrupta la ejecuci n de una tarea La estructura descrita para las tareas de los rboles de comportamiento es meramente conceptual con la finalidad de describir de manera formal c mo procede su ejecuci n A la hora de implementarlos sin embargo se pueden seguir diversas filosof as 2 2 Contexto de Ejecuci n Todos los nodos de un rbol de comportamiento disponen de un contexto de ejecuci n el cual es compartido por todos ellos El contexto de ejecuci n o simplemente contexto act a como una pizarra que pueden usar los nodos para escribir y leer variables El contexto no es m s que un repertorio de varia 12 CAP TULO 2 RBOLES DE COMPORTAMIENTO public class Context 1 private Hashtable lt String Object gt variables public void setVariable String name Object value i variables put name value public Object getVariable String name return variables get name Figura 2 2 El contexto de ejecuci n bles donde cada variable es un par de la forma nombre de variable valor El contexto representa la porci n del estado del juego que es accesible a la entidad controlad
8. be that of figure A 9 The behaviour is pretty simple the tree is always executing see the Re peat node a Dynamic Priority List DPL that is constantly checking three conditions If the current unit is in a low danger situation then the unit is ordered to attack the closest dangerous enemy This is represented by the first child of the DPL If the current unit is in a high danger situation then the unit runs away to the closest base This is represented by the second child of the DPL the Sequence Finally if none of the above conditions are met the unit just patrols This is represented by the third child of the DPL the Subtree Lookup node we will further explain this later There are some details that must still be defined though So far the tree does not provide a way of checking the three conditions above In order to do so we can make use of guards since the DPL interacts with children that have guards defined In order to add a guard to a node just right click on the node and select Edit Guard A dialog should appear that lets the user edit the guard of the node In JBT guards are represented by BTs In particular a guard can be a single node or a complete and correct BT When the user clicks on Add simple guard a dialog lets the user select a single leaf node action condition or a standard leaf node to be used as a guard If the user clicks on the Add A 5 CREATING BTS WITH JBT EDITO
9. de negro remarcado se se alan las acciones y condiciones depen dientes del dominio 3 Lars 4 de 248 4 ee Yo eS 5 6 Escenario del experimento 1 5 7 rbol de comportamiento para la acci n Atacar Ahora el rbol contempla la presencia de b nkeres Cercanos 5 8 Escenario del experimento 2 lt 4 4 46 5 9 rbol de comportamiento para la acci n Atacar del buitre Terran 48 5 10 Escenario del experimento 3 4 see ROY EE S LE a A 1 Overview of the BT architecture A 2 a simple behaviour LEE o b Robo Z bab td A 3 a complex behaviour tree lt lt lt lt lt lt lt lt lt A 4 JBT Editor after being opened XI 49 XII NDICE DE FIGURAS A 5 The Nodes Navigator after loading the domain file 75 A 6 The dialog for editing the input parameters of the AttackMove ACON dido Genet EDA is Get PE ra 75 A T A parameter for which an actual value is provided 75 A 8 A parameter whose value will be retrieved from the context 75 A 9 Initial tree for the Terran Marine behaviour 76 A 10 Selecting a guard for the Attack node 77 A 11 The input parameter of Attack lt lt lt lt lt lt lt 77 A 12 The BT for the Standard Patrol behaviour 78 ndice de tablas 5 1 Resultados del experimento 1 5 2 Resultados del experimento 2
10. se construyen planes b sicos para cada objetivo los cuales son posteriorimente simplificados y ordenados en una jerarqu a de subojetivos mediante el uso del grafo de dependencias En cualquier caso ya se trate de Darmok o Darmok 2 el resultado de la fase de aprendizaje son casos en forma de snippets y episodios que se usan en la posterior fase de ejecuci n 6 CAP TULO 1 PLANIFICACI N BASADA EN CASOS DARMOK 1 3 3 Recuperaci n de Planes El ciclo OLCBP que implementa Darmok descompone el objetivo inicial en subobjetivos y estos a su vez en subsubobjetivos de manera recursiva En cada caso para resolver cada uno de dichos objetivos Darmok debe recurrir a su base de casos y encontrar qu planes snippets son m s adecuados para cada circunstancia La base de casos de Darmok contiene casos de la forma c p e donde p representa el snippet y donde e G S O representa el episodio siendo G el objetivo perseguido S el estado del mundo y O un valor num rico entre O y 1 indicando la medida del xito de la aplicaci n del plan de p para la consecuci n de G en el estado S La fase de recuperaci n de Darmok tiene como objetivo dado un objetivo a resolver y un estado del mundo encontrar el plan que previsiblemente mejor lo resuelva Para ello se aplica la medida de relevancia de episodio que dado un objetivo y un estado del mundo define c mo de importante es un episodio respecto a dicho estado y a dicho objetivo E
11. 56 AP NDICE A JBT GU A DEL USUARIO gt A Root mA Sequence J A DoorClosed A OpenDoor PLA Figura A 2 a simple behaviour tree in order to run his own trees at least he should know the general architecture of JBT A 2 4 BT Model Before even starting to explain all the steps required to build and run BTs with JBT we have to first think about what BT model JBT offers JBT implements a BT model that is mainly based on that of 19 Our model also include guards and static and dynamic priority lists as described in 8 With this model the user can implement a wide range of behaviours For instance the tree of figure A 2 represents a simple tree that is used by a game character that wants to open a door First of all it checks if the door is closed condition DoorClosed If so then it tries to open it by executing the action OpenDoor In the tree of figure A 2 we can see four nodes The node called Root is just the root of the tree and it has no actual meaning apart from it Then there is a Sequence node which runs in sequence both of its children the DoorClosed condition and the OpenDoor action The Sequence node is a standard node but both the DoorClosed and the OpenDoor nodes are domain dependent that is they have been defined by the user so they have a useful meaning within the context of the game being played The tree of figure A 3 represents the behaviour of a character that is trying to enter a room The topm
12. 9 recoge de manera simplificada el comportamiento explicado En la implementaci n real dado que la nube de la derecha marcada con el mensaje repetir proceso de colocaci n de minas coincide con la parte de la izquierda del rbol se llev acabo una abstracci n de todo el proceso para que pudiera ser reutilizado en ambos lugares sin necesidad de repetir toda la estructura El mapa donde se ha llevado a cabo el experimento es el de la figura 5 10 Este escenario es similar al del experimento 1 En este caso sin embargo se enfrentan por un lado un grupo de 6 buitres Terran controlados por Darmok y por otro un grupo de 24 murci lagos de fuego controlados por la IA est ndar de StarCraft Un murci lago de fuego es un soldado Terran cuya arma es el lanzallamas y que s lo puede atacar por tanto cuerpo a cuerpo La idea del experimento es comprobar c mo de efectivo es el proceso de colocaci n de minas ara a de Darmok en lo que a infligir da o en el ej rcito enemigo se refiere En un escenario normal no es de esperar que los 6 buitres puedan derrotar a los 24 murci lagos de fuego motivo por el que en realidad en el experimento se llevar a cabo un recuento de cu ntos murci lagos de fuego han conseguido ser eliminados Para entrenar a Darmok se ha hecho uso de tres trazas distintas juga das en el escenario planteado en las que se muestra c mo llevar a cabo el emplazamiento de minas ara a El experimento consiste en llevar a c
13. La capa t ctica pide a una Base de BTs externa un rbol de comportamiento para gestionar la acci n Dependiendo del tipo de acci n la Base de BTs recupera un conjunto de rboles de comportamiento candidatos los dise ados para ese tipo de acci n entonces compara el estado del mundo actual con los estados de los rboles de comportamiento en el conjunto de candidatos y aqu l cuyo estado es m s cercano es devuelto Este rbol de comportamiento es entonces incorporado a una Piscina de BTs compuesta por todos los rboles de comportamiento que la capa t ctica est gestionando actualmente Tanto la capa t ctica como los rboles de comportamiento conocen en todo momento cu l es el estado del juego para as tener un mayor grado de control de lo que en l acontece En el caso de que un rbol de comportamiento no pudiera ser recuperado de la Base de BTs la acci n de bajo nivel ser a enviada finalmente a la API del juego Es importante notar que esta parte de la capa t ctica es completamente independiente de Darmok es decir no requiere modificaci n de la arquitectura de Darmok 3 2 Capa T ctica para la Gesti n de Planes Objetivo En aquellos casos en los que Darmok no ha sido capaz de aprender pla nes efectivos para algunos objetivos los rboles de comportamiento se pueden usar como alternativa La idea es similar a la de la gesti n de las acciones de bajo nivel Un experto construye rboles de comportamiento Estos rbo
14. Navigator the user can build complex behaviour trees However in order to build really useful trees the user must use the domain dependent actions and conditions from the game The JBT Editor lets the user load a MMPM domain file as described 74 AP NDICE A JBT GU A DEL USUARIO File View Help a 4 lt Nodes Navigator 23 Ol D6 Node info 3 lt gt Standard nodes y Nodes Searcher x Figura A 4 JBT Editor after being opened in section A 3 Just click on the Load MMPM Domain or select File Load MMPM Domain and select the file that contains the low level actions and conditions After doing so the Nodes Navigator will be added a new entry for the actions and conditions within the domain file which the user will be able to use when building BTs For instance if we load the domain file described in section A 3 we get the actions and conditions shown in figure A 5 The JBT Editor lets the user specify values for the input parameters of nodes By double clicking on a node that has input parameters a dialog whe re the user can specify values for the input parameters For instance if the AttackMove action is double clicked then the dialog of figure A 6 is shown In the dialog the user can specify a value for the parameter target whose type is COORDINATE Thus the text field only supports values such as 45 62 or 10 3 45 As we mentioned in section A 4 when building a BT the user
15. Razonamiento Basado en Casos VII VIII RESUMEN ndice general Agradecimientos Abstract Resumen Introducci n 1 Planificaci n Basada en Casos Darmok 1 1 Razonamiento Basado en Casos lt lt lt 1 2 Planificaci n Basada en Casos o o 1 3 Darmok un Sistema CBP para Juegos de Estrategia 1 3 1 Representaci n de Planes 1 3 2 Adquisici n de Planes x ear 1 3 3 Recuperaci n de Planes 1 3 4 Fase de Expansi n y Ejecuci n En Linea 13 5 Adaptaci n 2002 A O e AS 2 rboles de Comportamiento 2 1 Mec nica de Funcionamiento o 2 2 Contexto de Ejecuci n 2402 2 2 ef et A o A r hod bn 2 34 TIPOS de Tareas lt de te dele 48 od Je AR O 2 3 1 Tareas de Bajo Nivel 4 2 zv ki Aa ale AAA 2 9 2 Tareas Compuestas lt mld 212 al da SAS 23 3 Decoradores a ia E A OHA 2 4 Reutilizaci n de rboles lt lt lt lt lt lt lt 3 Combinando Darmok con BTs 3 1 Capa T ctica de Bajo Nivel 3 2 Capa T ctica para la Gesti n de Planes Objetivo 3 3 Arquitectura Global io 54 e a hou a r O A 3 4 Recuperaci n de Arboles cb erga A AA EA AA A Da Escenario az dal ch Pte at a de Abc A pase S 3 5 1 Escenario de Acciones de Bajo Nivel 3 5 2 Escenario de Plan Objetivo 4 Java Behaviour Trees 4 1 Caracter sticas Principales de JB
16. V inverter A UnsetSiegeMode Node 21 z 4 Node 22 G9 Limit A Attack Node 23 x a Node 24 AD Repeat S Perform interruption aces U J 4 Sequence Searched in TankAttackabt gt Figura 4 2 JBT Editor 4 2 JBT Editor Para facilitar la creaci n de rboles de comportamiento JBT incluye un editor gr fico de rboles de comportamiento JBT Editor figura 4 2 El JBT Editor permite al usuario crear rboles de comportamiento de ma nera r pida y sencilla Mediante un sencillo mecanismo de arrastrar y soltar el usuario puede a adir cualquier tipo de nodo a sus rboles de comportamien to JBT Editor permite adem s cargar ficheros XML que definen las acciones y condiciones de bajo nivel dependientes del dominio las cuales pueden ser usadas como cualquier otro tipo de nodos a la hora de crear rboles de com portamiento Los rboles creados pueden ser exportados a ficheros XML que son posteriormente analizados por JBT para construir clases Java que repre sentan a los rboles en cuesti n Cap tulo 5 Estudio Experimental Inicialmente este trabajo se plante en el contexto del concurso de Star Craft organizado por Expressive Intelligence Studio en la Universidad de Ca lifornia Santa Cruz en el 2010 motivo por el cual se decidi implantar para su uso en el videojuego StarCraft En este cap tulo se recoge el estudio experimental llevado a cabo para evaluar la arquitectura
17. a BT there should be a clear distinction between the tree that is being run the model and how it is actually being run the execution For each particular behaviour we distinguish between the Model BT that de fines it and how it is being run The how is what the BT Executor does Basically for every entity in the game that wants to run a behaviour Model BT there is a BT Executor The BT Executor takes the Model BT and pro cesses it without modifying it simulating the behaviour that is represented by the Model BT This choice implies that apart from the Model BT there is another type of tree the Execution BT When an entity wants to execute a behaviour the BT Executor takes the Model BT and creates an Execution BT to execute the behaviour The BT Executor along with the Execution BT know how to run the behaviour that the Model BT represents A 2 3 Architecture Figure A 1 shows an overview of the JBT Core architecture There is a Model BT that represents a particular behaviour Also there is a BT Executor for every entity that wants to run the Model BT Each BT Executor makes use of the Model BT and builds an Execution BT that actually runs the behaviour conceptualized by the Model BT An external Game AI ticks the BT Executors in order for them to update the trees that they are running The user of the framework does not have to know all the details about how JBT internally works However since he has to implement some classes
18. cuando una unidad enemiga pasa cerca suya Cuando la mina se activa se acerca r pidamente a la unidad que la ha activado y explosiona causando un gran da o a las unidades cercanas a la explosi n es decir la mina causa da o en toda una zona del mapa Si a la capacidad de plantar minas ara a se le a ade el hecho de que el buitre Terran es la unidad m s veloz del juego el resultado es el de una unidad que si es manejada con estrategia puede suponer la diferencia entre una batalla ganada y una batalla perdida Una estrategia que suele ser usada por expertos jugadores consiste en mandar buitres Terran a plantar minas ara a en medio de las tropas enemigas tras lo cual abandonan la zona r pidamente Aunque muchas minas puedan ser interceptadas por el enemigo basta que exploten unas pocas para que se causen da os irreversibles en el ej rcito contrario Es dif cil que Darmok aprenda a usar de manera precisa las minas ara a Por un lado cuando Darmok genera la orden EmplazarMinaAra a debe de llevar un paso previo de adaptaci n basada en el ciclo CBP para calcular el nuevo lugar donde situar la mina pudiendo ser que dicho lugar no sea el adecuado Por otro durante un combate Darmok deber a ser consciente de que siempre que pudiera deber a hacer uso de minas ara a y que adem s deber a de huir de ellas si hubiera enemigos cerca puesto que de lo contrario la explosi n podr a alcanzar a las unidades aliadas Para solventar es
19. en dos fases 2De ahora en adelante salvo que se especifique lo contrario usaremos Darmok para referirnos a Darmok 2 su versi n m s avanzada 4 CAP TULO 1 PLANIFICACI N BASADA EN CASOS DARMOK Subproblemas Problema ass Solucion Adaptada v 2 Recuperaci n gt Adaptaci n Expansi n Petici n z A Retrasada de Adaptaci n Y soluci n Estado del Mundo mundo v vy Retenci n FSS A T Ejecuci n Figura 1 2 El ciclo OLCBP e Fase de aprendizaje donde el experto juega al videojuego gener ndose trazas que describen de forma precisa todos los eventos acaecidos durante la partida Estas trazas son almacenadas en forma de planes casos del sistema que son empleados posteriormente durante la fase de ejecuci n e Fase de ejecuci n donde se aplica el ciclo OLCBP para mantener un plan global compuesto a su vez de subplanes que gestiona la partida 1 3 1 Representaci n de Planes En Darmok la pieza b sica constituyente de un plan es el snippet el cual representa una serie de instrucciones acciones a ejecutar Un snippet consta de e Un conjunto de precondiciones las cuales deben ser satisfechas para que el plan pueda ejecutarse por ejemplo antes de poder construir un tanque se deben tener los recursos suficientes para ello e Un conjunto de condiciones de vida las cuales deben mantenerse ciertas durante la ejecuci n del plan Si no el plan se considera fallido
20. en videojuegos y que para ello se requiere contemplar en general multitud de situaciones En la terminolog a de los rboles de comportamiento normalmente se ha bla de tres tipos de tareas tareas compuestas decoradores y tareas de bajo nivel acciones y condiciones Las tareas compuestas constan de uno o varios hijos y su estado de ejecuci n depende del estado de ejecuci n de stos Los decoradores basados en el patr n software del mismo nombre tienen un nico hijo cuyo comportamiento alteran de cierta manera Por ltimo las tareas de bajo nivel se dividen en dos subgrupos las acciones que representan tareas que alteran el estado del videojuego y que se ejecutan contra ste y las condi ciones que simplemente consultan el estado del mundo para ver si se satisface una determinada condici n tambi n deben ejecutarse contra el videojuego 2 3 1 Tareas de Bajo Nivel Las tareas de bajo nivel son las m s simples conceptualmente dentro de los rboles de comportamiento stas forman las hojas de los rboles y se dividen en dos tipos acciones y condiciones Las tareas de bajo nivel se comunican directamente con el videojuego pre ferentemente a trav s de alg n tipo de API para llevar a cabo actividades de consulta sobre el estado del mundo o bien para modificarlo En este sentido las acciones son tareas de bajo nivel que modifican el estado del mundo y que tambi n pueden leerlo Son acciones tareas como ordenar a la
21. entidad controlada moverse a una determinada posici n o bien ordenarle desenfundar un arma Si la orden realizada tiene xito la acci n fina liza en xito de otro modo finaliza en fracaso Por otro lado las condiciones son tareas de bajo nivel que comprueban que se cumple cierta propiedad en el estado del mundo a diferencia de las acciones las condiciones no alteran el estado del mundo Las condiciones se muestran extremadamente tiles cuan do se quiere realizar acciones s lo bajo ciertas circunstancias En ese caso las acciones se ven guardadas por una condici n garantizando que si la acci n se ejecuta es porque la condici n se cumple por ejemplo la acci n atacar al enemigo con granada s lo deber a ejecutarse si el personaje dispusiera de una granada 2 3 2 Tareas Compuestas Una tarea compuesta es una tarea que dispone de uno o varios hijos y cuya ejecuci n depende del estado de ejecuci n de stos Cuando una tarea compuesta comienza a ejecutarse lanza a ejecuci n uno o varios de sus hijos 14 CAP TULO 2 RBOLES DE COMPORTAMIENTO dependiendo de su sem ntica y monitoriza la evoluci n de stos Una vez finalizados los hijos dependiendo de sus estados de ejecuci n xito o fracaso la tarea compuesta bien puede lanzar a ejecuci n a otros hijos o bien decidir finalizar ella misma en xito o en fracaso Los dos tipos m s tiles de tareas compuestas son la secuencia y el selector El nodo de tipo se
22. es decir no tienen ning n snippet asociado o el snippet que se les asoci fall y preparados es decir no hay ning n snippet que se tenga que ejecutar an tes consulta al m dulo de recuperaci n para obtener un snippet para dicho objetivo Mientras tanto de forma paralela el m dulo de ejecuci n se encarga de comenzar la ejecuci n de cada snippet tan pronto como compruebe que sus precondiciones se satisfacen Si el estado del mundo ha cambiado en gran me dida respecto a cuando el snippet fue recuperado de la base de casos ste es enviado al m dulo de adaptaci n para intentar adecuarlo al estado actual Si 1 3 DARMOK UN SISTEMA CBP PARA JUEGOS DE ESTRATEGIA 7 plan Snippet 0 en ejecuci n objetivos abiertos acciones Construir Ej rcito Atacar Construir Base listo en espera nuevos actualizar snippets Snippet 1 plan estado E fi xi z M dulo de PE exito P M dulo de Expansi n Ejecuci n Estado del juego acciones snippets adaptados snippets adaptados M dulo de nuevos snippets Adaptaci n snippets fracasados Figura 1 4 Fase de ejecuci n en Darmok alg n snippet en ejecuci n contiene acciones b sicas que pueden ser ejecuta das sus precondiciones se satisfacen se env an al motor de IA subyacente para que sean ejecutadas Si las precondiciones no se satisfacen el snippet es
23. ganar o perder una batalla El hacer un uso correcto de las habilidades especiales de ciertas unidades puede adem s tener como con secuencia un mejor desempe o de las labores tanto ofensivas como defensivas de la IA La experimentaci n llevada a cabo demuestra c mo el uso de rboles de comportamiento a trav s de la capa t ctica de bajo nivel sin recuperaci n basada en similitud consigue mejorar sensiblemente el rendimiento de Darmok en diversos escenarios A grandes rasgos los experimentos propuestos comprueban la capacidad de Darmok de reaccionar correctamente durante un combate bien emplean do las acciones b sicas de las unidades enfrentadas bien haciendo uso de sus habilidades especiales Se proponen escenarios donde se pone a prueba dis tintas habilidades as como la capacidad estrat gica de Darmok a la hora de emplearlas 2 Tambi n implementado por Santiago Onta n 40 CAP TULO 5 ESTUDIO EXPERIMENTAL 5 4 Experimento 1 En este experimento se pone a prueba la capacidad de reacci n de Darmok en un combate simple entre grupos de soldados Terran El soldado es la unidad ofensiva m s b sica de los Terran apenas tiene capacidad de ataque y de defensa y puede atacar a distancia con su rifle Cuando Darmok analiza las trazas del juego es capaz de aprender que en determinadas circunstancias las unidades aliadas deben atacar a las unidades enemigas Sin embargo dado que Darmok no tiene una capacidad reactiva al
24. h brida entre Darmok y rboles de comportamiento propuesta Se describe el dominio elegido StarCraft la tecnolog a emplea da para la comunicaci n con ste desde un programa Java los experimentos planteados y los resultados obtenidos 5 1 Dominio StarCraft El dominio elegido para testear la arquitectura propuesta es StarCraft 5 StarCraft ver figura 5 1 es un juego de estrategia en tiempo real que ha cosechado millones de jugadores alrededor del mundo en la ltima d cada y que se ha convertido posiblemente en el juego de estrategia m s famoso de la historia Como en la mayor a de los juegos de estrategia en tiempo real en StarCraft el jugador controla un ej rcito a elegir entre tres razas distintas siendo su deber el de derrotar a uno o varios oponentes Inicialmente el jugador dispone de un edificio central y cuatro trabajadores Los trabajadores son usados para extraer recursos del mapa bien minerales bien gas vespeno los cuales se emplean para construir edificios y unidades Los trabajadores tambi n se usan para la construcci n de edificios Para vencer al enemigo o enemigos el jugador debe disponer de un ej rcito lo suficiente mente bien armado generalmente compuesto de tropas de diversos tipos y para construir el ej rcito requiere de edificios con los que entrenar a las tropas adecuadas Adem s ciertos edificios pueden emplearse para mejorar la tecno log a del armamento de las unidades lo cual pu
25. of the closest base has been computed by the ComputeClosestBasePosition action and written into the context in a variable with name ClosestBasePosition then the input argument of Move must be read from the context and its value must be the variable name ClosestBasePosition Now let us look at the final part of the tree When none of the danger conditions are met the marine has to patrol around its current position Since patrolling is a complex task that may be reused in another trees we decide to put it into another BT and reuse of from the Terran Marine BT This is accomplished by the Subtree Lookup task whose input parameter is set to StandardPatrol StandardPatrol is the name of the tree that will implement the patrol behaviour The tree of figure A 12 implements the patrol behaviour Initially the cu rrent position of the unit is computed by the ComputeCharacterPosition ac 78 AP NDICE A JBT GU A DEL USUARIO 4 z i S 4 Root gt Sequence A ComputeCharacterPosition 41 o Repeat gt Sequence A ComputeRandomClosePosition PAS AttackMove LT Figura A 12 The BT for the Standard Patrol behaviour tion This position is written into the variable CharacterPosition of the context as we mentioned in section A 3 From then on the is a forever loop Repeat node that constantly computes a random position that is close to the one computed by the ComputeCharacterPosition task and then orders the unit to AttackMov
26. que extender dicho modelo el cual se proporciona en forma de dominio de planificaci n SiN puede adem s razonar con informaci n no exacta del estado del mundo incorporando preferencias en los casos Mientras que en SiN el m dulo basado en casos y el modelo del dominio se desarrollan inde pendientemente el uno del otro nosotros proponemos un enfoque m s eficiente basado en desarrollar un modelo del dominio espec fico para cubrir los vac os presentes en los datos emp ricos obtenidos en forma de trazas Respecto a posible trabajo futuro el primer paso ser a completar la im plementaci n de la arquitectura planteada ya que debido a la complejidad del dominio de juego StarCraft no pudo finalizarse a tiempo Por un lado la incorporaci n de recuperaci n de rboles de comportamiento basada en un criterio de similitud puede suponer un empuje positivo en lo que al rendimiento de la arquitectura se refiere ya que es de esperar que rboles particularizados para cada tipo de situaci n se comporten de mejor manera que rboles gen ri cos que no tienen en cuenta el estado del mundo en el que son aplicados Por otro lado la gesti n de planes objetivo mediante rboles de comportamiento podr a mejorar el rendimiento en aquellos objetivos para los que Darmok no ha conseguido aprender planes lo suficientemente estructurados Tambi n contemplamos la exploraci n de posibles t cnicas para facilitar la tarea de identificar las reas de la b
27. t ctica de rboles de com portamiento es capaz de resistir 500 oleadas mientras que sin la capa t ctica 5 6 EXPERIMENTO 3 47 resiste 402 En promedio Darmok sin la intervenci n de la capa t ctica resiste 2 01 oleadas de enemigos por cada simulaci n mientras que Darmok con la capa t ctica resiste 2 5 oleadas Se deduce por tanto que incluir conocimiento experto en los rboles de com portamiento acerca del uso de b nkeres cercanos supone una mejora apreciable del rendimiento general del sistema En particular se obtiene un porcentaje de mejora del 24 38 lo cual representa casi una cuarta parte m s de victo rias Al analizar la partida jugada se pudo observar que gracias a los rboles de comportamiento un mayor n mero de soldados hizo uso de los b nkeres con lo cual en general aguantaban m s tiempo con vida dando lugar as a la mejora de rendimiento observada 5 6 Experimento 3 El rendimiento de ciertas unidades durante el juego depende en gran medida de c mo hagan uso de sus habilidades especiales Un ejemplo de ello es el buitre Terran El buitre es una moto de combate que inflige un da o m nimo a las unidades enemigas A pesar de ello dispone de una potente habilidad la capacidad de emplazar minas ara a en cualquier posici n del mapa en total puede emplazar tres minas Una mina ara a es una mina que se entierra en el suelo tras lo cual no puede ser detectada por las unidades enemigas y que se activa
28. two projects under the JBTEditor directory of the repository a GUI application through which it is really easy to define behaviour trees The JBT Editor is an Eclipse RCP application As such it must be run under the Eclipse SDK environment or use the executable files provided for each platform When opening if from Eclipse you have to open the project Jbt tools bteditor and then open the file bteditor product with the Product Con figuration Editor Once it has been opened go to the Overview page and click on Launch an Eclipse application A window like that of figure A 4 should show up The JBT Editor is a very simple tool so learning how to use it should not take very long In order to create a new BT just click on the new BT icon or select File New BT A new editor should open up showing an empty BT that is a tree containing only a single node the root of the tree To the right of the window there is a tree like menu the Nodes Navigator where the user can select nodes to build the tree In order to add a node to a tree just drag it from the Nodes Navigator and drop it onto whatever node of the tree to insert it as a child or sibling of the target node The root node can have only one child However other nodes such as sequences or selectors may have many of them Decorators can have only one child and leaf nodes do not have any children By using the set of provided standard nodes of the Nodes
29. used within the internal execution of the tree In this case it means that the context that is initially passed to the tree must contain the BT StandardPatrol If it does not when the Terran Marine tree is run it will throw an exception complaining about not being able to find the corresponding tree We can see that an appropriate context must be created to run the tree JBT Core provides a factory class the jbt execution core ContextFactory java Remember that the BT that actually runs is the Execution BT but that detail is of no interest at this point 82 AP NDICE A JBT GU A DEL USUARIO that defines several methods for creating generic contexts IContext objects of the Basic Context type described in section A 2 4 1 In our case we can make use of the method that takes as input an BTLibrary and makes an Context that contains all the BTs of the BT library Then we could make use of the methods in the Context interface to add the identifier of the marine that is supposed to be run by the tree First of all we create the BT library IBTLibrary btLibrary new TerranMarineBTLibrary x Then we create the initial context that the tree will use IContext context ContextFactory createContext btLibrary Now we are assuming that the marine that is going to be controlled has an id of terranMarinel context setVariable CurrentEntityID terranMarinel The next step is to create
30. 1 39 59 1994 Perry Alexander and Costas Tsatsoulis Using sub cases for skeletal plan ning and partial case reuse Int J Expert Syst 4 2 221 247 1991 William M Bain Judge a case based reasoning system pages 1 4 1986 Ray Bareiss Exemplar Based Knowledge Acquisition Academic Press 1989 Blizzard http us blizzard com en us games sc Robin Douglas Burke Representation storage and retrieval of tutorial stories in a social simulation PhD thesis Evanston IL USA 1993 Richard E Fikes and Nils J Nilsson Strips A new approach to the application of theorem proving to problem solving Artificial Intelligence 2 3 4 189 208 1971 Gonzalo Fl rez Puga Marco A G mez Mart n Pedro P G mez Mart n Bel n D az Agudo and Pedro A Gonz lez Calero Query enabled beha viour trees IEEE Transactions On Computational Intelligence And Al In Games 1 4 298 308 November 2009 Damian Isla Halo 3 building a better battle In Game Developers Conference 2008 Bobby D Bryant Kenneth O Stanley and Risto Miikkulainen Real time neuroevolution in the nero video game JEEE Transactions on Evolutio nary Computation pages 653 668 2005 Janet Kolodner Case based reasoning Morgan Kauffmann first edition 1993 John Krajewski Creating all humans A data driven AI framework for open game worlds Gamasutra February 2009 Gun Ho Lee Rule based and case based reasoning approach for internal audit of
31. 1 est ndar en caso de que no Obj 1 se obtenga ning n rbol de la 7 2 Base de BTs o S Parallel Librer a de Planes Z Acci n 1 Obj 2 Obj 3 RS 7 Objetivo detectado v M dulo de petici nBT Obj 3 Expansion rbol respuestaBT Base de BTs de D2 Nuevo Obj 1 plan Nuevo plan para Obj 1 M z X s Estado del juego l Parallel Estado del juego y rbol on e BANE A Capa T ctica BT sy z bez S rbol Insertar rbol Piscina de BTs Figura 3 2 Capa t ctica de alto nivel 3 4 RECUPERACI N DE RBOLES 27 t ctica mencionada con anterioridad La capa t ctica gestiona una piscina de rboles de comportamiento la Piscina de BTs Esta piscina contiene todos los rboles de comportamiento actualmente en ejecuci n Cuando Darmok genera una nueva acci n de bajo nivel la capa t ctica pide a la Base de BTs un rbol de comportamiento para la acci n dado el estado actual del juego Si puede encontrar una la capa t ctica la inserta en la Piscina de BTs Si no la acci n es enviada directamente a la API del juego Adem s si el plan que Darmok est ejecutando contiene planes objetivo adecuados para ser gestionados por rboles de comportamiento como el Obj 3 de la figura 3 2 se construyen rboles de comportamiento para gestionarlos los cuales son consecuentemente generados por Darmok junto con las acciones de bajo nivel Estos rboles de comportamiento son
32. 37 38 38 39 40 44 47 51 ndice de figuras 1 1 El ciclo del razonamiento basado en casos L2 co DLE LE A AA E 1 3 Extracci n de casos en Darmok a partir de una traza 1 4 Fase de ejecuci n en Darmok 2 1 Estructura de un nodo de un rbol de comportamiento 2 2 El contexto de ejecuci n saje dp 4p ae wd de NE Do E A 2 3 Pseudo implementaci n del nodo secuencia 2 4 Un rbol de comportamiento simple con un nodo secuencia 2 5 Un rbol de comportamiento simple con un nodo selector 2 6 Un rbol de comportamiento para el comportamiento Entrar en AA A O Moc 2 7 El rbol de comportamiento de la figura 2 6 simplificado 3 1 Capa t ctica de bajo nivel z s p o 2 6 4 e ea 3 2 Capa t ctica de alto nivel Loa A Ae ee da no 3 3 Arbol de comportamiento para la acci n ConvocarTormentaP SLOTVVC A wis eh ee thee voje edhe a ee a 4 1 Arquitectura global de JBT 8 LL ye ia U 2 JBT Edit r eb 4 Bag Ate DL Warde de SB a DA 5 1 Una partida de StarCraft donde se enfrentan dos ej rcitos 5 2 Integraci n de BWAPI con StarCraft 5 3 Proxy Bot para la comunicaci n Java con Starcraft 5 4 rbol de comportamiento para la acci n Atacar Con un borde negro remarcado se se alan las acciones y condiciones depen dientes del dominio ds is S O e a ee 5 5 rbol de comportamiento para la acci n Moverse Con un bor
33. 5 y Darmok 2 23 son sistemas CBP orientados a juegos de estrategia en tiempo real aunque en teor a Darmok 2 puede jugar a cualquier juego de competici n entre adversarios Darmok implementa una filosof a de aprendizaje mediante ejemplos un jugador experto muestra al sistema c mo jugar y ste autom ticamente aprende a partir de las demostraciones Las demostraciones se almacenan en la base de casos en forma de planes de modo que durante su ejecuci n Darmok emplea dichos casos para construir un plan jer rquico al estilo de las HTNs con el que ganar la partida Algunas de las mayores limitaciones de la planificaci n cl sica incluyendo los sistemas CBP es que asumen tanto la presencia de un mundo est tico como que disponen de un tiempo ilimitado para trazar sus planes El hecho de que una gran parte de los dominios del mundo real tenga esta doble restricci n ha conllevado estudios acerca de c mo darle una soluci n En particular los juegos de estrategia de tiempo real son un claro ejemplo de este doble requerimiento el cual debe ser tomado en consideraci n Darmok implementa una versi n modificada del ciclo CBR a saber el ciclo CBR en l nea OLCBR El ciclo OLCBR figura 1 2 25 es una versi n adaptada del ciclo CBR para dominios de planificaci n de estrategia en tiempo real El ciclo tradicional presupone que un problema puede resolverse con una sola vuelta al ciclo En CBP sin embargo es posible que el problem
34. Aspects of Game Pro gramming Jim Prentzas and loannis Hatzilygeroudis Categorizing approaches com bining rule based and case based reasoning Expert Systems 24 2 97 122 2007 Gonzalo Fl rez Puga Marco Antonio G mez Mart n Bel n D az Agudo and Pedro A Gonz lez Calero Dynamic expansion of behaviour trees In AIIDE 2008 A Ram and J C Santamari Continuous case based reasoning Artif Intell 90 1 2 25 77 1997 E L Rissland and K D Ashley A case based system for trade secrets law In ICAIL 87 Proceedings of the 1st international conference on Artificial intelligence and law pages 60 66 New York NY USA 1987 ACM Barry Smyth and Mark T Keane Design la d j vu reducing the adaptation overhead 1996 Pieter Spronck Marc Ponsen Ida Sprinkhuizen Kuyper and Eric Postma Adaptive game ai with dynamic scripting Mach Learn 63 3 217 248 2006 Kenneth O Stanley Evolving neural network agents in the nero video game In In Proceedings of the IEEE 2005 Symposium on Computational Intelligence and Games pages 182 189 2005 Neha Sugandh Santiago Onta n and Ashwin Ram Real time plan adaptation for case based planning in real time strategy games In Klaus Dieter Althoff Ralph Bergmann Mirjam Minor and Alexandre Hanft editors Advances in Case Based Reasoning volume 5239 of Lecture Notes in Computer Science pages 533 547 Springer Berlin Heidelberg 2008 BWAPI Team http c
35. Figura 3 3 rbol de comportamiento para la acci n Convocar TormentaPsionica 3 5 1 Escenario de Acciones de Bajo Nivel En el escenario de acciones de bajo nivel fij monos en la acci n Convocar TormentaPsionica definida con anterioridad La figura 3 3 muestra un rbol de comportamiento que implementa el mode lo reactivo explicado en la secci n 3 1 el alto templario no s lo tiene constancia de la posici n objetivo sobre la que tiene que convocar la tormenta sino que tambi n reacciona ante situaciones de peligro Este rbol de comportamiento tambi n define un estado del juego que especifica cu ndo es conveniente hacer uso de l Dado que ste es un rbol muy est ndar podr a ser usado en muchos escenarios si bien probablemente estar a mejor adecuado para escenarios en los que tanto las fuerzas aliadas como enemigas estuvieran balanceadas En ese caso el alto templario deber a intentar no da ar unidades aliadas as como huir en caso de peligro para no perder ventaja En otros escenarios por ejemplo cuando el ej rcito aliado supera en gran medida al enemigo los altos templarios podr an comportarse de manera m s agresiva o incluso temeraria as que se podr an implementar nuevos comporta mientos rboles de comportamiento con distintos estados del juego asociados Cuando Darmok genera la orden Convocar TormentaPsionica la capa t cti ca la procesa Si en el estado actual del juego tanto las fuerzas aliadas como
36. OMPORTAMIENTO Cap tulo 3 Combinando Darmok con Arboles de Comportamiento A pesar de que Darmok muestra un rendimiento aceptable en general pre senta varios problemas que en ciertos casos y bastante frecuentes pueden degradar su rendimiento de manera severa En el bajo nivel de la ejecuci n de sus planes Darmok presenta un proble ma de reactividad Darmok construye un plan global mediante la extracci n de subplanes de su base de casos alcanzando finalmente acciones de bajo ni vel que son enviadas directamente al motor del videojuego para su ejecuci n inmediata En escenarios de larga duraci n macro gesti n las acciones de bajo nivel se comportan lo suficientemente bien como para que el plan global evolucione exitosamente Sin embargo cuando las acciones deben ser alteradas o incluso canceladas en su totalidad debido a cambios r pidos en el estado del mundo el hecho de que Darmok se adhiera a ellas deteriora su rendimiento mientras la condiciones de vida de las acciones se mantengan activas el plan seguir ejecut ndose incluso si eventos recientes sugieren que la acci n deber a ser cancelada o modificada Esto se debe en parte al modo en que Darmok aprende sus planes a partir de las trazas que se le proporcionan Si fuera capaz de aprender planes mejor estructurados ser a capaz de crear planes m s complicados para las acciones de bajo nivel Sin embargo ello requerir a no s lo una abrumadora mayor can tidad de tr
37. OutputDirectory gt src bts actions execution lt ExecutionActionsOutputDirectory gt lt ExecutionConditionsOutputDirectory gt src bts conditions execution A 4 IMPLEMENTING ACTIONS AND CONDITIONS 71 lt ExecutionConditionsOutputDirectory gt lt Configuration gt Let us suppose that the ActionsAndConditionsGenerator is called with the following arguments ActionsAndConditionsGenerator c configurationFile xml r home outputDirectory Then the ActionsAndConditionsGenerator will parse the domain file home outputDirectory TerranMarine cml and it will create output classes for each action and boolean sensor in the domain file which will be stored in the corresponding files For instance for the Attack action two classes will be created home outputDirectory src bts actions Attack java the model task class and home outputDirectory src bts actions execution Attack java the execution task class For the boolean LowDanger sensor two classes will be created home outputDirectory src bts conditions LowDanger java the model task class and home outputDirectory src bts conditions execution LowDanger java the execution task class Then we should implement the abstract methods of all the execution classes For instance the implementa tion of the Move java execution class may be like this EzecutionAction class created from MMPM action Move public class Move extends ExecutionAction 1 Ak Returns the value of the param
38. R TT Figura A 10 Selecting a guard for the Attack node x A Node Editor Parameters target String LowDangerTarget From context Figura A 11 The input parameter of Attack complex guard however a new editor is opened so the user can create a complete BT to be used as the node s guard In our example the guard of the Attack action is just the condition Low Danger Therefore we have to click on the Add simple guard button and select the LowDanger task from the list as shown in figure A 10 Note that after inserting the guard a small shield icon will appear on top of the node that has been added a guard In the case of the Seguence node its guard is just the condition HighDanger so we add it just the same way Now we have to define the input parameters of the tasks First of all there is the Attack node The intended behaviour is for the soldier to attack the closest unit once that the LowDanger condition has been triggered Thankfully LowDanger writes into the context the identifier of the closest entity as we described in section A 3 in a variable with name LowDan gerTarget Therefore the input parameter of Attack should be as represented in figure A 11 since the value of the input parameter of the Attack action is present in a variable of the context whose name is LowDangerTarget With respect to the Move action the idea is that the unit goes to the closest base Since the position
39. R e S G aGS e G G 1 a SS e S S Donde GS es una medida de distancia entre objetivos con valores entre 0 y 1 SS es una medida de distancia entre estados del mundo con valores entre O y 1 y donde a es una constante entre O y 1 que indica la importancia de cada una de las medidas de distancia Por ltimo para predecir el rendimiento de un snippet se toman los k episodios m s relevantes asociados a dicho snippet y se obtiene una media ponderada del xito e O de los k episodios relevantes El resultado de la fase de recuperaci n es el snippet de mayor rendimiento 1 3 4 Fase de Expansi n y Ejecuci n En Linea La fase de ejecuci n de Darmok est gestionada por tres m dulos inde pendientes que interaccionan entre s el m dulo de expansi n el m dulo de ejecuci n y el m dulo de adaptaci n Entre ellos van construyendo un plan en forma de rbol que van desarrollando durante el juego Dicho rbol contiene dos tipos de nodos nodos snippet y nodos objetivo Inicialmente el plan contiene un s lo nodo el objetivo GanarJuego El m dulo de expansi n pide al m dulo de recuperaci n de casos un snippet para satisfacer dicho objetivo Dicho snippet podr a tener a su vez subobjetivos para los cuales el m dulo de expansi n deber a volver a pedir al m dulo de recuperaci n un snippet adecuado y as sucesivamente En general cuando el m dulo de expansi n encuentra en el plan nodos objetivo que est n abiertos
40. Really not any A 3 DEFINING ACTIONS AND CONDITIONS 63 lt Sensor name MySensorName type BOOLEAN gt lt Parameter name ParameterName1 type ParameterType1 gt lt Parameter name ParameterNameM type ParameterTypeM gt lt Sensor gt MMPM supports the following types for parameter types FLOAT BOO LEAN STRING INTEGER DIRECTION COORDINATE PLAYER EN TITY ID and ENTITY_TYPE This set of parameter types may seem overw helming which is why in general several of them are not used FLOAT BOO LEAN STRING and INTEGER are self explanatory DIRECTION represents an integer value which is why if it is used as the type of a parameter JBT will treat it just as an integer COORDINATE represents a coordinate in an N dimensional coordinate system In practice a COORDINATE value is a non empty sequence of real values for instance 23 4 5 67 3 45 r 12 45 0 34 9 44 12 3 PLAYER represents the name of a player of the game so in practice it is treated as a string STRING ENTITY_ID represents the iden tifier of an entity in the game In practice it is treated as a string STRING ENTITY_TYPE represents the type of an entity In practice it is treated as a string STRING As a consequence the user will generally use just FLOAT BOOLEAN STRING INTEGER and COORDINATE since the rest of MMPM parameter types are equivalent to STRING MMPM format however does not include an important parameter type object In g
41. T 4 1 1 Modelo Gonducido por Tieks 47 3 4 bov VA a 4 1 2 Modelo Independiente de Ejecuci n 4 1 3 Arquitectura Global atra rr a III VII XV 10 11 13 13 13 17 18 21 23 24 25 2 28 29 29 NDICE GENERAL 4 1 4 Modelo de rboles de Comportamiento 42 BEI e on OS 9 bo o dd a ak PL de Ee M Estudio Experimental 5 1 Dominio StarCraft sa AAC 5 2 Comunicaci n con StarCraft oe ea 5 2 1 Comunicaci n en Java aria sey es Saye A IN 5 3 Dise o de los Experimentos 5 3 1 Definici n del Dominio spa A A 5 3 2 Experimentos A red A er eee she 5A de en er eaters He Be pede Be wee da cee 9 00 Bxperimento 4 2450232 E ae le ein r 904 BRDOTNSTLOG dos 3558 bo OE Baad ca fee ca ae ea el Ge oae Conclusiones y Trabajo Futuro JBT Gu a del Usuario AA diod BOB oso O A A2 JBT an ONE aro a te A A 2 1 Model Driven by Ticks a ah 9a LL a A 2 2 Model Independent from Execution 4 Architecture oi oa A ee a o Se AZA BT Model 33 n 6 Lire AG b ra e a er e A 2 4 1 Execution Context ora dun es a s AI A 2 4 2 Native Tasks esas A 3 Defining Actions And Conditions A 4 Implementing Actions And Conditions A 5 Creating BTs with JBT Editor 4 4 6406 8 ea es ee ea A 6 Creating a Java Declaration of the BTs A 7 Running the Bthaviour Trees 2 4 0 400124 eee be Me r 35 35 36
42. a intentar cumplirla pero tambi n deber a ser capaz de cambiar su comportamiento en ciertos casos Sin embargo no es un enfoque realista esperar que un nico rbol de comportamiento proporcio ne buenos resultados a la hora de controlar cada tipo de acci n por ejemplo las acciones AtacarEnemigo o Moverse antes mencionadas en todas las si tuaciones posibles Nuestro enfoque consiste en disponer de varios rboles de comportamiento para cada tipo de acci n La capa t ctica se encarga de aso ciar un rbol de comportamiento concreto de la lista de posibles rboles a cada acci n Para realizar esta decisi n a nivel de dise o el dise ador debe especificar una descripci n del estado del mundo en aquellas situaciones en las que se espera que el rbol muestre un buen comportamiento En tiempo de ejecuci n la capa t ctica comprueba la similitud entre el estado actual del mundo y los estados proporcionados por todos los rboles de comportamiento para el tipo de acci n y el rbol con el estado m s cercano es seleccionado En el caso de que ning n rbol de comportamiento pueda ser recuperado por ejemplo si el rbol m s cercano no supera un determinado umbral de distan cia la acci n se env a directamente a la API del juego en cuyo caso ning n rbol de comportamiento le ser a asociado La figura 3 1 muestra la arquitectura de la capa t ctica a bajo nivel Para cada acci n que Darmok produce la capa t ctica la procesa
43. a original se tenga que descom poner en subproblemas para cada uno de los cuales el ciclo de CBR deber a volver a aplicarse En planificaci n cl sica adem s normalmente se supone que el plan una vez construido tendr xito En dominios de estrategia en tiempo real sin embargo puede no darse el caso ya que en muchas ocasiones el conocimiento que se tiene del mundo no es lo suficientemente preciso o sim plemente al ser el entorno din mico el plan no puede completarse Asegurarse de que el plan se ejecuta correctamente es pues un aspecto importante en este tipo de dominios El ciclo OLCBR incluye dos fases adicionales para hacer frente a la plani ficaci n basada en casos en dominios de estrategia en tiempo real e Expansi n encargada de tomar la soluci n actual plan y analizar si en l hay subproblemas actualmente abiertos Si los encuentra los env a al comienzo del ciclo CBR fase de recuperaci n para resolverlos Adem s el m dulo de expansi n es el encargado de realizar adaptaci n retrasada de planes en caso de que cuando vayan a ejecutarse el estado del mundo haya cambiado lo suficiente como para que puedan no ser aplicables e Ejecuci n encargada de ejecutar el plan y actualizar su estado de eje cuci n Si alg n subplan falla el estado de ejecuci n del plan global es actualizado para que el m dulo de expansi n pueda encontrar una solu ci n alternativa El funcionamiento de Darmok puede dividirse
44. a por el rbol Toda la informaci n que la entidad necesite del mundo s lo puede ser accedida a trav s del contexto ya que los rboles de comportamiento no tienen otro modo de comunicarse con el exterior La figura 2 2 muestra c mo se define el contexto de ejecuci n a nivel de pseudoc digo En general todo contexto dispone de al menos dos variables e this que referencia al agente que est siendo controlado por el rbol A trav s de esta variable se puede acceder a las propiedades de dicho agente e world que referencia al mundo donde el juego tiene lugar No obstante el contexto tiene una utilidad mucho m s amplia ya que es el mecanismo a trav s del cual los nodos del rbol pueden comunicarse entre s mediante el intercambio de variables Al actuar como una pizarra de lectura y escritura las tareas generalmente las hojas del rbol pueden escribir variables en el contexto para que posteriormente puedan ser usadas por otros nodos Por ejemplo un nodo podr a escribir un variable de nombre MiVariable en el contexto la cual podr a ser le da posteriormente por otro nodo accediendo por su nombre MiVariable Se puede establecer as una sem ntica de comunicaci n entre tareas A una tarea se le pueden asociar una serie de par metros de entrada nece sarios para su correcta ejecuci n Cuando sta comienza a cada par metro se le asocia un valor bien literal bien le do del contexto de ejecuci n Por normal ge
45. abo 500 repeticiones del combate ex plicado Para cada combate se calcula cu ntos murci lagos de fuego han sido 5 6 EXPERIMENTO 3 49 Figura 5 10 Escenario del experimento 3 eliminados con el fin de comprobar la diferencia de rendimiento cuando es s lo Darmok el que controla al jugador al mando de los buitres y cuando Darmok es extendido mediante la capa t ctica de bajo nivel El terreno del mapa es completamente visible a ambos jugadores de modo que en todo momento co nocen la localizaci n exacta de las unidades enemigas La tabla 5 3 muestra los resultados del experimento Darmok sin BTs Darmok con BTs Murci lagos de Fuego Muertos 4927 6607 Murci lagos por Simulaci n 9 85 13 21 o Murci lagos por Simulaci n 5 42 5 83 Mejora 34 10 Tabla 5 3 Resultados del experimento 3 Nuevamente se puede comprobar que la inclusi n de rboles de comporta miento para la gesti n de acciones de bajo nivel supone una mejora respecto al Darmok puro En este caso se ha producido un incremento del 34 10 en el n mero total de murci lagos de fuego destruidos y una diferencia de 3 36 murci lagos de fuego en promedio por cada combate Tras analizar el desa rrollo de la partida se pudo observar que en numerosas ocasiones Darmok no era capaz de situar las minas ara a en posiciones adecuadas Los rboles de comportamiento las situaban m s cerca de los enemigos con lo que causa ban en general mayor da o Adem s los bu
46. ackage where model action classes are placed lt ModelActionsPackage gt lt ModelConditionsPackage gt Name of the package where model condition classes are placed lt ModelConditionsPackage gt lt LibraryClassName gt Name of the class that is going to be created lt LibraryClassName gt lt LibraryPackage gt Name of the package for the generated BT library lt LibraryPackage gt lt LibraryOutputDirectory gt Name of the directory where the generated library is going to be stored lt LibraryOutputDirectory gt lt BTLibrary gt lt BTLibrary gt lt BTLibrary gt lt Configuration gt 80 AP NDICE A JBT GU A DEL USUARIO The order in which the elements are specified is not relevant In the file the user can define several BT libraries each one within the BTLibrary element For each BT library defined in a BTLibrary element the program will produce an output file class implementing the BT Library in terface for the library The r option is used to add a path to the beginning of the files listed in the configuration file as a result each file is considered to be placed at the path specified in the r option The r option may not be specified in which case the files are considered to be at the current execution directory The o option standing for overwrite is either is specified or not If it is not specified the generated output files will not overwrite any existing file in the file system and as a result a be
47. ad los soldados no eran capaces de reaccionar ante enemigos no planificados por Darmok y por tanto eran destruidos en el camino 5 5 Experimento 2 En este experimento se pretende refinar la concepci n que Darmok tiene del entorno de juego para mejorar su reacci n ante situaciones diversas La raza Terran dispone de un edificio llamado b nker El b nker es un edificio protector en el cual pueden introducirse cuatro soldados de modo que una vez dentro no reciben da o directo de las unidades externas En su lugar el b nker es el que recibe los ataques Desde dentro del b nker los soldados pueden atacar al enemigo y tambi n disponen de un mayor rango de ataque Una vez el b nker es destruido los soldados salen ilesos de l En general es buena idea que ante el peligro los soldados Terran se intro duzcan en los b nkeres cercanos As no s lo vivir n durante m s tiempo sino que adem s podr n alcanzar a enemigos m s lejanos Salvo que Darmok d una orden expl cita respecto a los soldados para que se introduzcan en b nkeres stos no lo har n As puede darse el caso de que aunque Darmok ordene a ciertos soldados atacar al enemigo y a pesar de que haya b nkeres cerca su falta de capacidad para analizar de forma precisa el entorno le impida ver que dichos b nkeres podr an ser usados Para remediarlo se propone modificar el rbol de comportamiento de la acci n Atacar extendiendo el planteado en el experiment
48. amente en la resoluci n de todo tipo de pro blemas en particular en dominios poco formalizados en los que el aprendizaje autom tico juega un papel importante ya que se pueden proponer soluciones a problemas incluso cuando no se comprenden con todo detalle Algunos de los campos en los que se ha empleado CBR son diagn stico sistemas Protos 4 para enfermedades del o do y Caseline 16 para la detec ci n y soluci n de fallos en Boeing 747 ense anza sistemas Hypo 30 para la ense anza de razonamiento legal y Spiel 6 para el aprendizaje de habilidades sociales razonamiento con adversarios Judge 3 un sistema que emula a un De sus siglas en ingl s case based reasoning 2 CAP TULO 1 PLANIFICACI N BASADA EN CASOS DARMOK Precedent Case Domain Knowledge Revised Case Figura 1 1 El ciclo del razonamiento basado en casos juez que sentencia a criminales soporte t cnico Smart 22 que ayuda a los t cnicos de soporte en la resoluci n de incidencias de sus usuarios o resoluci n de problemas y planificaci n como Bolero 15 que ayuda a la construcci n de pruebas m dicas para la obtenci n de un diagn stico entre otros 1 2 Planificaci n Basada en Casos Una de las reas donde el CBR ha sido aplicado con resultados positivos es el de la resoluci n de problemas mediante t cnicas de planificaci n autom tica La planificaci n autom tica de tareas 7 tiene como objetivo la resoluci n
49. antidad de tiempo de CPU que se le 31 32 CAP TULO 4 JAVA BEHAVIOUR TREES proporciona al rbol para que se ejecute As en cada ciclo de la IA del video juego una entidad externa hace tick en el rbol para que ste pueda actualizar su estado En concreto cada tick hace que los nodos del rbol eval en si han finalizado o no para que consecuentemente el rbol evolucione En el modelo abstracto conceptual planteado en la secci n 2 1 un tick se corresponde con una llamada al m todo update de la clase BT Node El enfoque m s simple para implementar el modelo conducido por ticks es justamente el de la secci n 2 1 el nodo ra z recibe el tick llamada al m todo update el cual es propagado de manera recursiva hacia sus descendientes de acuerdo con la sem ntica de cada nodo Sin embargo ste es un proceso ineficiente sobretodo para rboles de comportamiento suficientemente grandes ya que en general la mayor parte de los nodos del rbol est n esperando a que sus hijos finalicen su ejecuci n Por tanto el que dichos nodos reciban ticks se convierte en un desperdicio de tiempo CPU ya que al menos que sus hijos hayan finalizado su ejecuci n no har n nada al recibir el tick En realidad en general s lo un conjunto muy reducido de nodos deber a recibir ticks en cada ciclo de IA Como resultado JBT implementa un modelo en el que existe una lista de nodos tickeables S lo los nodos en esta lista pueden recibir ticks
50. azas sino tambi n un gran esfuerzo por parte del experto a la hora de anotar las trazas en Darmok o a la hora de definir el conocimiento de pendiente del dominio necesario para el proceso de aprendizaje Darmok 2 Desafortunadamente la reactividad de dichos planes tambi n estar a compro metida dado que el modelo de ejecuci n de Darmok no se replantea los planes actualmente en ejecuci n a no ser que fallen Este problema tiene especial importancia cuando unidades individuales de ben ser controladas a muy bajo nivel Cuando a una unidad se le env a una orden acci n de bajo nivel del plan que Darmok construye puede darse el caso de que mientras la ejecuta debiera ser modificada de alg n modo debido a cualquier tipo de evento relevante observado en el mundo En juegos como StarCraft es f cil encontrar situaciones como sta Por ejemplo en StarCraft muchas unidades tienen habilidades especiales como en el caso de los altos templarios Los altos templarios tienen la capacidad de convocar tormentas psi nicas en ciertas posiciones del mapa Una tormenta psi nica no es m s que un hechizo que ocupa un peque o rea del mapa y que causa da os seve 21 22 CAP TULO 3 COMBINANDO DARMOK CON BTS ros a las unidades situadas bajo ella Las tormentas psi nicas pueden resultar tremendamente tiles durante el juego ya que se pueden usar en ataque y defensa destruyendo de forma masiva unidades enemigas En ciertos casos pueden supon
51. bank Know Based Syst 21 2 140 147 2008 Team Liquid http wiki teamliquid net starcraft chaoslauncher 83 84 BIBLIOGRAF A 15 Beatriz L pez and Enric Plaza Case based planning for medical diag nosis In ISMIS 93 Proceedings of the 7th International Symposium on Methodologies for Intelligent Systems pages 96 105 London UK 1993 Springer Verlag 16 R V Magaldi R v cbr for troubleshooting aircraft on the flightline In Proceedings of the IEE Colloquium on Case Based Reasoning Prospects for Applications 1994 17 MakeMEPlayME http sourceforge net projects darmok2 18 aS Cynthia R Marling and Peter Whitehouse Case based reasoning in the care of alzheimer s disease patients In David W Aha and Ian Watson editors 4th International Conference on Case Based Reasoning ICCBR 2001 Proceedings pages 702 715 2001 19 1 lan Millington and John Funge Artificial Intelligence for Games Morgan Kaufmann second edition 2009 20 a H ctor Mu oz Avila David W Aha Dana S Nau Rosina Weber Len Breslow and Fusun Yamal Sin integrating case based reasoning with task decomposition In I JCAI 01 Proceedings of the 17th international joint conference on Artificial intelligence pages 999 1004 2001 21 Dana S Nau Yue Cao Amnon Lotem and Hector Mu noz Avila Shop Simple hierarchical ordered planner In IJCAI 99 Proceedings of the Sixteenth International Joint Conferen
52. c Priority List task that executes the child with the highest priority whose guard is evaluated to true At every Al cycle the chil dren s guards are re evaluated so if the guard of the running child is evaluated to false it is terminated and the child with the hig hest priority starts running The Dynamic Priority List task finishes when no guard is evaluated to true thus failing or when its active child finishes returning the active child s termination status Static Priority List task that executes the child with the highest priority whose guard is evaluated to true Unlike the Dynamic Prio rity List the Static Priority List does not keep evaluating its chil dren s guards once a child is spawned The Static Priority List task finishes when no guard is evaluated to true thus failing or when its active child finishes returning the active child s termination sta tus Decorator tasks tasks with one child whose purpose is to alter the way other tasks behave Interrupter task that controls the termination of its child task An Interrupter simply lets its child task run normally If the child re turns a result the Interrupter will return it However the Interrup ter can be asked to terminate the child task and return an specified 60 AP NDICE A JBT GU A DEL USUARIO status when done so The task that can interrupt an Interrupter is the Perform Interruption task e Inverter task used to invert the status code return
53. can specify whether the input parameters of actions and conditions are retrieved from the context or an actual value is provided at construction time The From context check box lets the user specify if the parameter has to be retrieved from the context or not If the check box is not ticked then the user must provide a value for the parameter in the text field However if the check box is ticked then what the user does is to specify the name of the context s variable where the value of the parameter will be retrieved from For instance in figure A 7 the user has specified a value 12 34 4 5 for the input parameter target of the AttackMove action However in figure A 8 the user has indicated that the value of the input parameter target will be retrieved from the variable TargetVariable of the context Once the BT has been completed the user can save it as an XML file In order to do so just click on the Save or Save As icons or select File Save or File Save As and enter a file name When saving a BT the JBT Editor checks if the structure of the tree is correct If not incorrect nodes are highlighted in red color and an explanation for the error is shown in the Node Info view to the right of the window when the node is selected A 5 CREATING BTS WITH JBT EDITOR 75 A Move A AttackMove A ComputeClosestBasePosition A ComputeCharacterPosition A ComputeRandomClosePos
54. ce IBTLibrary extends Iterable lt Pair lt String ModelTask gt gt Returns the BT of name name or null if not found public ModelTask getBT String name A 6 CREATING A JAVA DECLARATION OF THE BTS 79 Note that in JBT a Model BT see section A 2 2 is represented by the abstract class ModelTask Thus when we ask an IBTLibrary to give us a BT by its name it just retrieves the Mode BT that represents the tree which is represented by a ModelTask What the BTLibraryGenerator does is to automatically create a BT library that is a class that implements the IB TLibrary interface that can be used to retrieve the BTs defined in the XML files In particular given a set of behaviour trees specified in XML files and the MMPM definition of the low level actions and conditions that are used in the trees it creates the corresponding Java class The syntax of this program is as follows BTLibraryGenerator c configurationFile r relativePath o Where configurationFile is an XML file that contains all the information required to run the application The syntax of such a file is lt Configuration gt lt BTLibrary gt lt BTFile gt BTFile1 lt BTFile gt lt BTFile gt BTFile2 lt BTFile gt lt BTFile gt BTFileN lt BTFile gt lt DomainFile gt MMPMDomainFile1 lt DomainFile gt lt DomainFile gt MMPMDomainFile2 lt DomainFile gt lt DomainFile gt MMPMDomainFileN lt DomainFile gt lt ModelActionsPackage gt Name of the p
55. ce on Artificial Intelligence pages 968 975 San Francisco CA USA 1999 Morgan Kaufmann Publishers Inc 22 lt a Trung Nguyen Mary Czerwinski and Dan Lee Compaq quicksource Providing the consumer with the power of artificial intelligence In JAAI 93 Proceedings of the The Fifth Conference on Innovative Applications of Artificial Intelligence pages 142 151 AAAI Press 1993 23 iS Santiago Onta n n Kane Bonnette Prafulla Mahindrakar Marco A G mez Mart n Katie Long Jainarayan Radhakrishnan Rushabh Shah and Ashwin Ram Learning from human demonstrations for real time case based planning IJCAI 09 Workshop on Learning Structural Know ledge From Observations 2009 Ww Santiago Onta n Kane Bonnette Prafulla Mahindrakar Marco A G mez Mart n Katie Long Jainarayan Radhakrishnan Rushabh Shah and Ashwin Ram Learning from human demonstrations for real time case based planning In Ugur Kuter and H ctor Munoz Avila editors Proceedings of the IJCAI 09 Workshop on Learning Structural Knowled ge From Observations 2009 25 ee Santiago Onta n Kinshuk Mishra Neha Sugandh and Ashwin Ram On line case based planning Computational Intelligence 26 1 84 119 2010 BIBLIOGRAF A 85 20 35 36 Marc Ponsen Pieter Spronck H ctor Mu oz A vila and David W Aha Knowledge acquisition for adaptive game ai Science of Computer Pro gramming 67 1 59 75 2007 Special Issue on
56. ci nDePeligro en la variable enemigo del contexto Volviendo a la lista din mica de prioridad de m s alto nivel en caso de que el objetivo inicial estuviera al alcance se le mandar a atacarlo 5 5 EXPERIMENTO 2 45 Repetir ListaDinamica DePriodidad Situaci nDe Peligro 88 NoAlcanzable objetivolnicial ListaDinamica DePriodidad B nker Disponble EntrarEnB nker b nker Realizar Interrupci n DentroDe Condici n B nker Verdadera Atacar enemigo Atacar objetivo Inicial DentroDe B nker Figura 5 7 rbol de comportamiento para la acci n Atacar Ahora el rbol contempla la presencia de b nkeres cercanos Tal y como se ha explicado con anterioridad una de las ventajas de los rboles de comportamiento es su capacidad de reutilizaci n Recu rdese que el rbol de comportamiento de la figura 5 5 representaba el comportamiento moverse reactivo Dicho rbol reutilizaba el rbol asociado a la acci n Atacar Al haber actualizado el rbol de la acci n Atacar para que tenga constancia de los b nkeres cercanos el rbol de la acci n Moverse tambi n es actualizado autom ticamente Es m s cualquier otro rbol que reutilice el rbol de Atacar se habr visto actualizado El mapa donde se ha llevado a cabo el experimento figura 5 8 consiste en dos porciones de tierra plana separadas por un muro El trozo de la izquierda representa una base aliada que d
57. como inyectar en el juego bibliotecas DLL Para poder comunicar una IA con el juego se hace uso de BWAPI 35 una API escrita ntegramente en C que permite compilar bibliotecas DLL que inyectadas a trav s de Chaouslauncher son capaces de acceder al estado del juego y modificarlo Con BWAPI el usuario puede consultar el estado completo del juego en StarCraft Por ejemplo puede consultar cu ntas unidades hay actualmente en el mapa qu rdenes est n ejecutando y cu l es su estado de salud BWAPI no s lo accede a StarCraft en modo lectura sino que permite modificar su estado mediante el env o de rdenes a las unidades del mapa Cualquier tipo de orden que un jugador podr a enviar a las unidades durante una partida pueden tambi n enviarse a trav s de BWAPI La figura 5 2 muestra el esquema de integraci n de BWAPI con StarCraft El usuario construye un m dulo de IA haciendo uso de la biblioteca BWAPI Es en dicho m dulo donde el usuario define c mo va a funcionar su IA accediendo 5 2 COMUNICACI N CON STARCRAFT 37 BWAPI lib IAUsuario cpp Y gt an Y AUsuario dll Chaoslauncher Starcraft Figura 5 2 Integraci n de BWAPI con StarCraft al estado del mundo y enviando rdenes al juego Luego compila dicho m dulo en una biblioteca DLL la cual es finalmente inyectada por Chaoslauncher al proceso de StarCraft Cuando el usuario comie
58. created by the ActionsAndCon ditionsGenerator However the ExecutionAction and ExecutionCondition ge nerated classes contain a set of abstract method that must be implemented according to the semantics of the respective actions and conditions so that A 4 IMPLEMENTING ACTIONS AND CONDITIONS 67 they do what they are expected to do This is the only step that must be done in order for JBT to be able to work with the low level actions and conditions provided by the user In particular the abstract methods that must be implemented are protected void internalSpawn protected Status internalTick protected void internaTerminate protected void restoreState ITaskState state protected ITaskState storeState protected ITaskState storeTerminationState internalSpawn and internalTick are the most important methods so they should be well implemented internalSpawn represents the spawning process of the task action or condition When the flow of execution of the tree reaches the task internalS pawn gets called Therefore this method must be defined so that it starts the process associated to the task For instance the internalSpawn method of the Move action above should order the current unit to go to the target position the internalSpawn method of the Attack action above should order the current unit to attack the target enemy The automatically generated skeleton contains an initial implementation of the inter
59. ctural La adaptaci n de par metros m s sencilla tiene como objetivo adaptar los par metros de las acciones b sicas que componen los planes de la base de casos Las acciones b sicas como Moverse o Atacar tienen par metros por ejemplo moverse a la posici n 2 3 o atacar a la unidad 34 Cuando se recupera un plan de la base de casos es probable que los par metros de sus acciones b sicas no sean aplicables al estado actual del juego as que Darmok lleva a cabo un paso de adaptaci n previo antes de aplicarlas 8 CAP TULO 1 PLANIFICACI N BASADA EN CASOS DARMOK La adaptaci n estructural es sensiblemente m s compleja que la adaptaci n de par metros y permite adaptar la estructura a nivel de acciones del plan original La adaptaci n estructural permite tanto eliminar del plan acciones innece sarias como a adirle nuevas acciones que permitan hacer ciertas precondiciones no satisfechas inicialmente Para ello se hace uso del grafo de dependencias el cual muestra las dependencias existentes entre las distintas acciones que lo conforman indicando cu ndo el xito de alguna de ellas evaluable mediante las condiciones de xito contribuye a la satisfacci n de las precondiciones de otra La eliminaci n de acciones innecesarias hace uso directo del grafo del plan y permite eliminar aquellas acciones que no tienen una dependencia di recta en la consecuci n del objetivo del plan Este tipo de situaciones se dan con frecue
60. cuencia contiene uno o varios hijos que ejecuta secuen cialmente Cuando el nodo secuencia es ejecutado lanza al primero de sus hijos Si ste finaliza en xito la secuencia contin a con el siguiente de sus hijos Si por contra falla la secuencia se considera fallida En general el nodo secuencia tiene xito si todos sus hijos logran ejecutarse secuencialmente con xito Si alguno de ellos falla la secuencia se considera fallida Una secuencia representa una serie de tareas que deben ser realizadas para cumplir un objeti vo determinado El pseudoc digo de la figura 2 3 muestra una implementaci n del nodo secuencia acorde al prototipo de la figura 2 1 La figura 2 4 muestra un rbol de comportamiento simple con un nodo secuencia como ra z y con tres tareas de bajo nivel Este rbol recoge el com portamiento de un personaje que huye ante la presencia de un enemigo En efecto cuando el rbol comienza su ejecuci n en su ra z el nodo secuencia ste comienza a ejecutar secuencialmente a sus hijos El primer hijo es una condici n que comprueba si hay alg n enemigo a la vista De no haberlo la condici n falla y como consecuencia falla la secuencia no ejecut ndose as las otras dos tareas de bajo nivel No obstante si la condici n es cierta la se cuencia pasa a ejecutar el siguiente hijo la acci n Darse la vuelta Si sta tiene xito finalmente se ejecuta la acci n Huir El rbol representa el com portamiento Huir ant
61. d y capacidad de reutilizaci n Mediante el uso de rboles de comportamiento se reduce significativamente la dificultad a la hora de dise ar inteligencias complejas El desarrollo de t cnicas de IA m s avanzadas aplicables al campo de los XV XVI INTRODUCCI N videojuegos tiene como objetivos principales ayudar a los desarrolladores a la creaci n de IAs de una manera eficiente y a que stas tengan un car cter adaptativo que incremente su realismo y capacidad El empleo de t cnicas de aprendizaje autom tico facilita a los desarrolladores la construcci n de inte ligencias siguiendo una filosof a de demostraci n mediante ejemplos permi tiendo dise ar de una manera mucho m s sencilla IAs igualmente complejas y realistas La adopci n de t cnicas de aprendizaje autom tico embebidas en el propio videojuego permite que las TAs evolucionen con el paso del tiempo adapt ndose a entornos din micos y situaciones desconocidas En este contexto se han aplicado con un xito parcial t cnicas como redes neuronales 10 33 planificaci n basada en casos 23 o m s recientemente el scripting din mico 32 En este estudio proponemos extender un sistema completo de planifica ci n basada en casos orientado a juegos de estrategia en tiempo real Darmok 23 mediante la inclusi n de conocimiento experto en la forma de rboles de comportamiento con el prop sito de eliminar algunas de las carencias m s im portantes de dicho siste
62. de problemas objetivos mediante la generaci n de secuencias espec ficas de ins trucciones Tradicionalmente las t cnicas de planificaci n autom tica se han basado en explorar de forma inteligente el espacio de todas las posibles secuen cias de instrucciones encontrando una que logre satisfacer el objetivo inicial Debido a la inmensidad del espacio de posibles secuencias de acciones en do minios reales m s recientemente se han propuesto otras alternativas como la planificaci n autom tica mediante redes de tareas jer rquicas HTNs 21 La planificaci n HTN se basa en descomponer el objetivo original en una jerar qu a de objetivos cada uno de los cuales se resuelve de forma independiente acelerando como consecuencia la obtenci n de un plan global Las t cnicas que combinan planificaci n con CBR reciben el nombre de planificaci n basada en casos CBP y se basan en crear casos que representan o bien planes completos o bien planes parciales en el segundo caso dichos planes deben ir ensambl ndose para lo cual se debe incluir alg n mecanismo de control que se encargue de ello La CBP se ha aplicado con xito en numerosos mbitos como el diagn stico de enfermedades ASP II 2 la planificaci n navegacional SINS 29 o el dise o de software DEJA VU 31 entre otros 1 3 DARMOK UN SISTEMA CBP PARA JUEGOS DE ESTRATEGIA 3 1 3 Darmok un Sistema CBP para Juegos de Estrategia Los sistemas Darmok Darmok 2
63. del estado del mundo se deben utilizar a la hora de obtener el rbol Dada una consulta y un caso C se computa la similitud entre y C seg n sim Q O J0 Q clase C clase sim Q C l SiMatr Q C Q clase C clase siMatr Q C gt deD 0 c Wa simMiolQa Ca D Q C Q descriptores N C descriptores E Qq valor Cq valor stiMioe Qa Ca 1 m Los pesos wa asociados a cada descriptor miden la importancia que se le da a cada uno a la hora de calcular la medida de similitud tienen un valor en el intervalo 0 1 y la suma de todos ellos debe ser 1 gt ep Wa 1 tama representa el tama o del intervalo para los valores del descriptor d valores v lidos dentro del sistema As se fuerza a que la medida de similitud calculada est normalizada en el intervalo 0 1 Es importante recordar que los valores de los descriptores pueden ser tanto num ricos como simb licos en cuyo caso se les debe asignar un valor num rico a la hora de realizar el c mputo de distancias Dada una consulta la medida de similitud respecto a un caso C permite recuperar aquel caso m s similar a la consulta dada usando para ello el estado del mundo actual y el estado del mundo al cual el caso recuperado deber a parecerse especificado en los descriptores de la consulta En el contexto de la arquitectura de la capa t ctica planteada cuando se lleva a cabo una recuperaci n de rboles de comportamiento se debe construir u
64. del juego Un Plan de BT no es m s que un plan de Darmok cuya ejecuci n no es gestionada por Darmok sino por un rbol de comportamiento externo En lo que a Darmok respecta no importa si el plan es gestionado fuera suya ya que mientras pueda proporcionar la misma interfaz que la de un plan est ndar de Darmok ste sabr c mo gestionarlo De este modo en cada ciclo del juego Darmok no s lo genera acciones de bajo nivel a ser pro cesadas como se ha descrito en la secci n 3 1 sino que tambi n genera rboles de comportamiento que deben ser ejecutados por la capa t ctica y que son insertados en la Piscina de BTs En caso de que un rbol de comportamien to no pueda ser obtenido de la Base de B T s Darmok procede como siempre es decir expandiendo el objetivo mediante un plan obtenido de la base de planes La figura 3 2 se corresponde con la situaci n en la que un rbol de comportamiento rbol en la figura es recuperado para la ejecuci n del Obj 3 3 3 Arquitectura Global En las secciones 3 1 y 3 2 se ha descrito c mo se puede hacer uso de rboles de comportamiento para gestionar tanto acciones de bajo nivel generadas por Darmok as como planes objetivo La parte central de la arquitectura es la capa 26 CAP TULO 3 COMBINANDO DARMOK CON BTS Recuperaci n de casos De Plan para Obj
65. e Un conjunto de condiciones de xito las cuales determinan cu ndo el plan ha tenido xito Obs rvese que las condiciones de xito no son lo mismo que las postcondiciones A diferencia de la planificaci n cl sica no se pueden especificar postcondiciones ya que no est garantizado que un plan vaya a tener xito e Un plan Mientras que en Darmok 2 el plan se almacena como una red de petri jer rquica en Darmok el plan est compuesto de construcciones de tipo se cuencia paralelo acci n y subobjetivo En cualquier caso ambas son represen taciones jer rquicas que permiten descomponer un plan global en subplanes asociados a cada subobjetivo Para poder usar Darmok se debe proporcionar informaci n espec fica del domino del juego definidas en un fichero de dominio escrito en el lenguaje de MakeMEPlayME 17 un framework para conectar sistemas de IA a juegos de estrategia en tiempo real incluyendo 1 3 DARMOK UN SISTEMA CBP PARA JUEGOS DE ESTRATEGIA 5 a2 Subgoal g2 Parallel CITE OK Touradas ES 0 Subgoal g5 EE ET Pus o 17 Game State 137 Gaga a ua n ta a ta bol be m n m a gt m A co M na p R m m na m tra LA m Figura 1 3 Extracci n de casos en Darmok a partir de una traza e Acciones b sicas que se pueden ejecutar en el dominio como por ejemplo Atacar o Moverse e Sensores que permiten obtener informaci n acerca del estado del mundo e Objeti
66. e and task are used interchangeably 93 54 AP NDICE A JBT GU A DEL USUARIO lists which make use of guards JBT BTs are driven by ticks which means that in order for them to have CPU time they need to be externally ticked By following this pattern the user can control how much CPU time the BT consumes In this document we explain how JBT can be used to build and run BTs This process has the following steps Defining low level actions and conditions to be used in the trees These actions and conditions are defined in the MMPM format Implementing the low level actions and conditions The user has to define how the low level actions and conditions work JBT does not know how these domain dependent actions and conditions work so the user has to provide a Java implementation of them Creating BTs with the JBT Editor Here the user creates BTs that are exported into generic XML files z Creating the Java declaration of the BTs that were declared in the XML files This is automatically done by one of JBT s tools Running the BTs by using the core classes of JBT In the next sections we will describe all of these steps Also we will con ceptualize them through a real example on a real game since we will build a tree that is able to control a Terran Marine of the Real Time Strategy Game StarCraft A 2 JBT an Overview In this section we describe the JBT architecture as well as the main features that BTs have
67. e comportamiento hacen uso de guardas Cada tarea del rbol puede ser etiquetada con una guarda que debe ser evaluada como cierta para que el comportamiento se active A este respecto los rboles de comportamiento incluye la tarea compuesta conocida como lista est tica de prioridad la cual permite al dise ador etiquetar a cada uno de sus hijos con una guarda Cuando la lista se ejecuta las guardas de sus hijos se eval an de modo que s lo se ejecuta el primer hijo cuya guarda haya sido evaluada como cierta Una variante de este tipo de tarea es la lista din mica de prioridad la cual eval a continuamente las guardas de sus hijos pudiendo abortar la ejecuci n del hijo actualmente activo si la guarda de alg n otro de mayor prioridad se eval a como cierta en cuyo caso el hijo de mayor prioridad comienza su ejecuci n Gracias a las guardas los rboles de comportamiento pueden concebirse como estructuras orientadas por objetivos que representan c mo un objetivo de alto nivel puede descomponerse en objetivos de bajo nivel En este sentido los rboles de comportamiento se asemejan a las redes de tareas jer rquicas HTNs que se usan en planificaci n autom tica si bien su prop sito es to talmente diferente Mientras que las HTNS se usan para generar planes los rboles de comportamiento se usan para almacenar planes codificados ma nualmente Los rboles de comportamiento pueden entenderse como rboles de tipo and or que almacenan
68. e el peligro para cuyo xito es necesario que se ejecuten exitosamente las tres tareas de bajo nivel que lo componen El nodo de tipo selector muestra un comportamiento parecido ya que ste ejecuta secuencialmente a sus hijos Sin embargo tan pronto como uno de ellos finalice con xito el selector tambi n finaliza con xito Si alguno de los hijos del selector acaban en fracaso el selector no finaliza sino que sigue ejecutando al siguiente de sus hijos El selector s lo se considera fallido cuando todos sus hijos fallan El selector puede verse como una tarea que intenta realizar una determinada acci n de diversas maneras Si una de ellas falla prueba la siguiente hasta que se acaban todas las opciones disponibles El rbol de la figura 2 5 muestra un rbol de comportamiento simple con un nodo selector y tres acciones de bajo nivel El rbol representa el compor tamiento Hacer feliz a madre y su prop sito es hacer feliz a una madre triste mediante una serie de alternativas a cada cual m s ruin Cuando el rbol co mienza su ejecuci n en el nodo ra z el selector ste expande al primero de sus hijos e intenta ejecutarlo Si la acci n Decir te quiero tiene xito la madre es ya feliz y el comportamiento nodo selector finaliza Sin embargo si fra casa se intenta la siguiente opci n para hacer a la madre feliz ejecut ndose la acci n Hacer un postre Si tiene xito el rbol finaliza en xito pero si fracasa s
69. e intenta la ltima de las opciones Hacer un regalo En efecto el rbol inten ta satisfacer el objetivo inicial mediante tres alternativas distintas y mientras alguna de ellas tenga xito el comportamiento se considerar exitoso Los nodos secuencia y selector son las tareas compuestas m s comunes cuando se dise an rboles de comportamiento stas permiten dise ar todo tipo de comportamientos desde los m s simples como los de las figuras 2 4 y 2 5 a otros muchos m s complejos como el de la figura 2 6 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 2 3 TIPOS DE TAREAS 15 public class Sequence extends BTNode Indice del hijo activo private int activeChild 1 public void spawn Context context 1 Comenzar la ejecucion del primer hijo activeChild O children activeChild spawn context public Status update 1 Actualizar el estado de ejecucion del hijo activo y avanzar la ejecucion del nodo selector acorde a ello Status childStatus childStatus children activeChild update if childStatus RUNNING childStatus FAILURE return childStatus T else El hijo ha finalizado con exito S es el ultimo se devuelve exito Si no se comienza la ejecucion del siguiente hijo if activeChild children size 1 return childStatus J else ac
70. e to that target position It is important to note that the tree must have a name it is set in the root of the tree in this case StandardPatrol which is the name that was used in the SubtreeLookup task of the Terran Marine BT Note that a name for the Terran Marine BT must be provided so we will assume that its name is TerranMarine A 6 Step 4 Creating a Java Declaration of the BTs Once our BTs have been defined in the XML format of the JBT Editor the next steps are quite easy Actually there is no more complex work to be done by the user from now on So far we have provided a definition and implementation of domain depen dent low level actions and conditions We have also defined our BTs and stored them in XML files using the JBT Editor The next step is to provide a Java implementation of the trees so that JBT can actually run them This step is automatically performed by the JBT Core The JBT Core has an application the jbt tools btlibrarygenerator BTLibraryGenerator java that basically takes the XML definition of some BTs and creates a java file that contains the implementation of such trees In JBT BTs are grouped together in BT libraries A BT library is just a collection of BTs that can be retrieved by name actually the name that is specified for the tree in the JBT Editor A BT library is implemented by the IBTLibrary interface This interface just represents a set of BTs that can be retrieved by name public interfa
71. ebe ser defendida de oleadas de enemigos La base dispone de dos grupos de 9 soldados Terran para defenderla En el trozo de la derecha se van generando peri dicamente enemigos que se lanzan al ataque de la base aliada En concreto se generan 6 zerlings Zerg y 6 hidraliscos Zerg Los zerlings son peque as unidades que atacan cuerpo a cuerpo es decir no pueden atacar a distancia pero son d biles en general con lo que se suelen utilizar como defensa de unidades m s potentes Los hidraliscos por contra atacan a distancia infligen m s da o y son capaces de aguantar m s ataques enemigos La idea es que los zerlings defiendan a los hidraliscos mientras stos causan el mayor da o posible El muro que separa ambos terrenos tiene una apertura que representa la entrada a la base En la apertura as como a lo largo de la base aliada hay situados varios b nkeres que deber an ser usados por los soldados para defenderse de los ataques El escenario planteado es t pico en una partida de StarCraft Es frecuente que el emplazamiento de la base aliada sea una formaci n geogr fica con una sola entrada terrestre estrecha En este tipo de escenarios es una buena idea 46 CAP TULO 5 ESTUDIO EXPERIMENTAL Figura 5 8 Escenario del experimento 2 concentrar las defensas en la entrada ya que el enemigo al menos por tierra s lo podr entrar por ah Para entrenar a Darmok se ha hecho uso de tres trazas consistentes en tres demostracion
72. ecuci n de uno o varios de sus hijos y as sucesivamente El proceso finaliza cuando la ejecuci n alcanza las hojas del rbol tareas de bajo nivel las cuales llevan a cabo acciones en el entorno virtual del videojuego Dependiendo del estado de finalizaci n de las tareas de bajo nivel xito o fracaso sus respectivos padres actuar n de una manera u otra bien iniciando la ejecuci n de nuevos hijos bien considerando finalizada su ejecuci n en xito o fracaso y propagando el control de la ejecuci n de vuelta a sus padres de forma recursiva A nivel conceptual una tarea o nodo de un rbol de comportamiento mues tra la interfaz de la figura 2 1 El m todo spawn es el que desencadena la ejecuci n del nodo Para tareas de bajo nivel generalmente se encarga de enviar rdenes a las entidades del juego o bien analizar el estado de algunas variables de inter s del mundo En el caso de tareas intermedias nodos compuestos spawn se encarga de acorde a la sem ntica del nodo lanzar recursivamente la ejecuci n de uno o varios de sus hijos llamando para ello a sus respectivos m todos spawn Una vez que se ha comenzado la ejecuci n de una tarea el m todo update se encarga de actualizar su estado de ejecuci n Para tareas de bajo nivel el m todo update analiza el estado de terminaci n de la tarea que se est rea lizando en el videojuego y dependiendo de l devuelve un c digo Status de xito SUCCESS fracaso
73. ed by its child When the decorated task finishes its status code gets inverted e Limit task that limits the number of times a task can be executed This decorator is used when a task the child of the decorator must be run a maximum number of times When the maximum number of times is exceeded the decorator will fail forever on e Repeat task that runs its child task forever When its child task finishes it runs it once more e Until Fail task that runs its child as long as it does not fail When the child task fails Until Fail succeeds e Hierarchical Context Manager task that creates a new context for its child The context that it creates is an empty with no varia bles Hierarchical Context whose input context is the context that is passed to the Hierarchical Context Manager e Safe Output Context Manager task that creates a new context for its child The context that it creates is an empty with no variables Safe Output Context whose input context is the context that is passed to the Safe Output Context Manager e Safe Context Manager task that creates a new context for its child The context that it creates is an empty with no variables Safe Context whose input context is the context that is passed to the Safe Context Manager Leaf tasks tasks with no children e Wait task that keeps running for a period of time and then suc ceeds The user can specify for how long in milliseconds the Wait task should be
74. ede otorgar una gran ventaja durante el desarrollo de la partida Al igual que en la mayor a de los videojuegos actuales StarCraft emplea una IA codificada manualmente predecible y que puede ser derrotada f cil mente una vez se aprende su patr n de juego En concreto StarCraft dispone de una serie de estrategias predefinidas de modo que al inicio de cada partida la IA de la m quina elige una para el resto de la partida StarCraft dispone de tres razas a elegir a la hora de jugar una partida Terran que juegan el papel de los humanos Protoss que juegan el papel de 35 36 CAP TULO 5 ESTUDIO EXPERIMENTAL Figura 5 1 Una partida de StarCraft donde se enfrentan dos ej rcitos civilizaci n alien gena avanzada tecnol gicamente y Zerg que juegan el papel de alien genas no inteligentes que hace uso de sus fuerza f sica para vencer al enemigo la figura 5 1 muestra una batalla entre Zerg y Terran Cada raza tiene distintos tipos de unidades y diferentes habilidades especiales con lo que el tipo de estrategia que se puede seguir con una generalmente no es aplicable al resto 5 2 Comunicaci n con StarCraft Para poder testear la arquitectura propuesta se necesita de un m todo de comunicaci n con StarCraft para poder enviar desde Darmok las instrucciones que se quieran ejecutar dentro del juego Chaoslauncher 14 es una aplicaci n gr fica que permite al usuario eje cutar StarCraft con varios plugins adicionales as
75. en casos CRB Algunos sistemas toman la 51 52 CAP TULO 6 CONCLUSIONES Y TRABAJO FUTURO salida de un componente basado en reglas y la utilizan como entrada de uno basado en casos como el descrito en 13 un sistema de auditor a bancaria que detecta autom ticamente transacciones fuera de lo normal irregulares o arriesgadas aplicando posteriormente CBR el cual inspecciona las transac ciones detectadas y calcula un nivel de castigo Por otro lado otros sistemas toman un enfoque m s cercano al presentado en este trabajo donde la salida de un m dulo basado en casos alimenta a uno basado en reglas Un ejemplo es el descrito en 18 un sistema m dico para pacientes con Alzheimer donde se llama al m dulo basado en casos para determinar si se deber a recetar un f rmaco neorul ptico al paciente de ser as el sistema basado en reglas se encarga de seleccionar uno de entre cinco f rmacos posibles Si consideramos a los rboles de comportamiento como un tipo particular de artefacto de planificaci n que almacena planes codificados a mano tam bi n podemos encontrar trabajo relacionado centrado en la combinaci n de planificaci n basada en casos y otros enfoques de planificaci n El sistema SiN 20 hace uso de un algoritmo de planificaci n basada en casos que combina recuperaci n de casos conversacional con planificaci n generativa SiN puede generar planes dado un modelo del dominio incompleto mediante el uso de casos con los
76. enemigas est n balanceadas el rbol de la figura 3 3 podr a ser recuperado para gestionar dicha acci n En ese caso ser a insertado en la Piscina de BTs para su uso posterior Si no se encontrase ning n rbol de comportamiento la acci n ConvocarTormentaPsionica ser a enviada de forma directa a la API del juego para ser ejecutada 3 5 2 Escenario de Plan Objetivo Cuando Darmok gestiona algunos de sus objetivos no es de esperar que se comporte correctamente T mese por ejemplo el caso del objetivo DestruirA lEnemigo mencionado anteriormente Cuando Darmok construye planes para dicho objetivo stos tomar n la forma de numerosas acciones de bajo nivel tal vez organizadas en estructuras de tipo paralelo o secuencia Aunque los pla nes pudieran parecer muy complejos todos compartir an la misma estructura 30 CAP TULO 3 COMBINANDO DARMOK CON BTS estando compuestos de numerosas acciones de bajo nivel sin apenas ning n subobjetivo Cuando una acci n o subplan falle el plan entero fallar y un nuevo plan deber ser recuperado para la gesti n del objetivo Destruir ALE nemigo Dado que este problema se repetir continuamente Darmok no se comportar de manera adecuada en esta situaci n Para solventar el problema podemos definir rboles de comportamiento para gestionar el objetivo DestruirAlEnemigo en diversos escenarios Por ejem plo se podr a construir un rbol a usar en situaciones donde el ej rcito aliado supera
77. eneral there will be actions and sensors will make use of input parameters of many types In order to be able to manage a wide range of types JBT extends the MMPM domain file format so that parameters also accept the OBJECT type An OBJECT is just a variable of any type The MMPM domain file that defines the set of actions and conditions for the Terran Marine example is as follows lt Domain package mypackage gt lt ActionSet gt lt Orders the current unit to attack another unit gt lt Action name Attack gt lt Parameter name target type ENTITY _ID gt lt Action gt lt Orders the current unit to go to a target position gt lt Action name Move gt lt Parameter name target type COORDINATE gt lt Action gt lt Orders the current unit to go to a target position If an enemy is found along the way the unit will combat him gt lt Action name AttackMove gt lt Parameter name target type COORDINATE gt lt Action gt 64 AP NDICE A JBT GU A DEL USUARIO lt Orders the position of the base that is closest to the current unit gt lt Action name ComputeClosestBasePosition gt lt Computes the position of the current unit gt lt Action name ComputeCharacterPosition gt lt Computes a random position that is close to the input position gt lt Action name ComputeRandomClosePosition gt lt Parameter name initialPosition type COORDINATE gt l
78. ent defines the set of sensors that can be used in the game A lt SensorSet gt element contains a sequence of lt Sensor gt elements each one being a sensor A lt Sensor gt element has two attributes its name and its type In MMPM a sensor is an operation that queries something about the world As a result a sensor can return any type of value Here we are interested in sensors whose type is boolean BOOLEAN in the MMPM domain file since they represent what in BTs is known as conditions that is a query operation that returns either true or false Therefore the set of boolean sensors of the MMPM domain file is the set of conditions that can be used when building BTs Both actions and sensors may have input parameters An input parameter is a parameter that is supposed to be used by the action or sensor when running For instance the Move action above does have one input parameter which is the target position where the unit must go to An input parameter has a name and a type Thus both lt Action gt and lt Sensor gt elements may have a sequence of lt Parameter gt elements each one being a parameter Each lt Parameter gt element has two attributes its name and its type Therefore actions and sensors have the following structure lt Action name MyActionName gt lt Parameter name ParameterName1 type ParameterType1 gt lt Parameter name ParameterNameN type ParameterTypeN gt lt Action gt 3
79. entEntityID float targetPosition this getTarget if Math distance currentPosition targetPosition lt 0 5 return Status SUCCESS else return Status RUNNING protected void internalTerminate We just order the unit to stop String currentEntityID String this getContext getVariable Constants CONTEXT CURRENT ENTITY GameEngine stopUnit currentEntitylD protected void restoreState jbt execution core ITaskState state 1 Does nothing J A 5 CREATING BTS WITH JBT EDITOR 73 protected jbt execution core ITaskState storeState 1 No persistent state information to return return null protected jbt execution core ITaskState storeTerminationState 1 No persistent state information to return return null A 5 Step 3 Creating BTs with JBT Editor Once that the domain dependent actions and conditions of the game have been defined and a JBT implementation for them has been provided the next steps are quite easy to follow It is now when the user should define the behaviour trees to use in the game Following our Terran Marine example we will define several trees that implement the behaviour that we described in section A 3 Behaviour trees are first described in XML files Here we are not going to describe the XML format that JBT understands since we discourage the user from writing them in plain text Instead we propose to use the JBT Editor composed of the
80. enviado al m dulo de adaptaci n para repararlo Adem s el m dulo de eje cuci n comprueba peri dicamente las condiciones de vida y de xito de cada snippet y acci n b sica de modo que cuando el snippet o acci n se da por finalizado se actualiza el estado del snippet padre si ha finalizado con xito el snippet padre puede continuar su ejecuci n si ha fracasado el snippet se marca como fallido y su objetivo asociado se marca como abierto nuevamente La figura 1 4 muestra la ejecuci n de un plan El objetivo global Ganar Juego ha decidido resolverse mediante la ejecuci n del snippet 0 El plan de dicho snippet contiene tres subobjetivos Construir Base Construir Ej rcito y Atacar El objetivo Construir Base ha sido cumplido ya que el plan que se re cuper para resolverlo snippet 1 ha finalizado con xito El objetivo Construir Ej rcito est listo y a la espera de que el m dulo de expansi n le proporcione un snippet adecuado Mientras tanto el ltimo objetivo Atacar est en espera de que se cumpla el objetivo Construir Ej rcito 1 3 5 Adaptaci n Como en todo sistema CBR en Darmok es necesario llevar a cabo una fase de adaptaci n de los casos almacenados en la base de casos Cuando se va aplicar un plan es posible que ste no sea aplicable al estado actual del mundo motivo por el cual deber a ser revisado En Darmok se dan dos tipos de adaptaci n la adaptaci n de par metros y la adaptaci n estru
81. er la diferencia entre ganar y perder una batalla Cuando Darmok ordena a un alto templario convocar una tormenta psi ni ca en una posici n X Y es decir genera la instrucci n Convocar Tormen taPsionica el alto templario ir a la posici n de destino y lanzar la tormenta Dado que Darmok ha llevado a cabo un paso previo de adaptaci n es proba ble que X Y sea una posici n similar a la de la traza original la cual a su vez deber a ser una regi n con muchas unidades enemigas y casi ningu na unidad aliada para que as la tormenta no matara unidades aliadas Sin embargo mientras el alto templario se desplaza hasta X Y las unidades enemigas podr an haberse movido por los alrededores con lo que lanzar la tor menta ser a para entonces totalmente in til ya que ning n enemigo resultar a da ado Es m s si muchas unidades aliadas se hubieran desplazado a X Y podr an ser destruidas por la tormenta En estos casos ser a conveniente que el alto templario pensara acerca del rea en la que se le ha ordenado lanzar la tormenta Si bien es cierto que el problema podr a solucionarse a adiendo nuevas condiciones de vida a la acci n ConvocarTormentaPsionica para que por ejemplo si la posici n alcanzada no es apropiada para la tormenta la acci n fuera cancelada la idea detr s de Darmok es aprender mediante ejemplos con la menor cantidad posible de conocimiento del dominio Para que Darmok fuera muy reactivo deber a
82. es de c mo defenderse en el escenario mostrado En las demos traciones se muestra c mo los soldados deben introducirse en los b nkeres as como c mo deben atacar a los enemigos El experimento a realizar consiste en la repetici n de 200 simulaciones de defensa de la base En cada simulaci n se env an continuamente r fagas de 6 zerlings y 6 hidraliscos a la base aliada Cuando la base aliada es destruida se reinicia el escenario y se lleva a cabo otra simulaci n En cada simulaci n se hace un recuento de cu ntas r fagas de enemigos el jugador ha podido aguantar En un caso la defensa de la base la lleva a cabo Darmok sin la capa t ctica de rboles de comportamiento En el otro es Darmok con la capa t ctica de rboles de comportamiento el que lleva a cabo la defensa de la base Con el prop sito de llevar a cabo un experimento m s realista el terreno del mapa no es completamente visible al jugador que realiza la defensa As se evita tener una visi n anticipada del ataque enemigo lo cual va m s en consonancia con una situaci n real en la que el ataque puede llegar en cualquier momento sin que el jugador lo prevea Darmok sin BTs Darmok con BTs Oleadas Resistidas 402 500 u Oleadas por Simulaci n 2 01 2 5 c Oleadas por Simulaci n 0 5 0 7 Mejora 24 38 Tabla 5 2 Resultados del experimento 2 La tabla 5 2 muestra los resultados obtenidos del experimento En total sobre las 200 simulaciones Darmok con la capa
83. eter target or null if not found anywhere public float getTarget 1 Whatever has been automatically generated protected void internalSpawn this getExecutor requestInsertionIntoList jbt execution core BTExecutor BTExecutorList TICKABLE this Retrieve the identifier of the entity Terran Marine running this action from the context Here we are x assuming that the context will contain it String currentEntityID String this getContext getVariable CurrentEntityID Now we assume that there is a generic Game Engine that can be used to send generic orders to units of the game Note that in order to retrieve the target AP NDICE A JBT GU A DEL USUARIO position we use the automatically generated getter method af GameEngine sendMoveOrder currentEntityID this getTarget protected jbt execution core ExecutionTask Status internalTick x In this method we will just check whether the unit has reached the target position If the target x position is unreachable then Status FAILURE is returned Utherwise if the unit has reached the x target position Status SUCCESS is returned Otherwise Status RUNNING is returned String currentEntityID String this getContext getVariable CurrentEntityID if Util reachablePosition currentEntityID this getTarget return Status FAILURE float currentPosition GameEngine getPosition curr
84. haviour tree library may not be produced in case there is a file with the same name in the file system If the option o is specified then generated output files will overwrite any file in the file system whose name matches In the Terran Marine example we want to create a BT library that con tains the two BTs that we created in section A 5 Let us suppose that the tree defining the Terran Marine behaviour was stored in the file TerranMarine xbt and that the tree defining the patrol behaviour was stored in the file Standard Patrol xbt Then we could use the following configuration file to produce the BT library lt Configuration gt lt BTLibrary gt lt BTFile gt TerranMarine xbt lt BTFile gt lt BTFile gt StandardPatrol xbt lt BTFile gt lt LibraryClassName gt TerranMarineBTLibrary lt LibraryClassName gt lt LibraryPackage gt bts btlibrary lt LibraryPackage gt lt Library0utputDirectory gt src bts btlibrary lt Library0utputDirectory gt lt DomainFile gt TerranMarineDomain xml lt DomainFile gt lt ModelActionsPackage gt bts actions lt ModelActionsPackage gt lt ModelConditionsPackage gt bts conditions lt ModelConditionsPackage gt lt BTLibrary gt lt Configuration gt Where note that TerranMarineDomain zml is the domain file that we crea ted in section A 3 The ModelActionsPackage and ModelConditionsPackage must also be those specified in the configuration file of the ActionsAndCondi tionsGenerator So now let us su
85. hod is called just before the task is spawned that is befo re calling internalSpawn In restoreState ITaskState state the task should analyse the input TaskState object and restore whatever information it con tains if null then it means that there is no past information to remember In the case of the Move action of the Terran Marine example the storeSta te storeTerminationState and restoreState ITaskState state methods are empty As a final example on implementing low level actions and conditions lets follow the whole process for the few actions and conditions defined in the domain explained in section A 3 Let us suppose that the MMPM domain file is stored in the file TerranMari neDomain zml Then the ActionsAndConditionsGenerator application could be run with the next configuration file stored in configurationFile zml lt Configuration gt lt DomainFile gt TerranMarineDomain xml lt DomainFile gt lt ModelActionsPackage gt bts actions lt ModelActionsPackage gt lt ModelConditionsPackage gt bts conditions lt ModelConditionsPackage gt lt ModelActionsOutputDirectory gt src bts actions lt ModelActionsOutputDirectory gt lt ModelConditionsOutputDirectory gt src bts conditions lt ModelConditionsOutputDirectory gt lt ExecutionActionsPackage gt bts actions execution lt ExecutionActionsPackage gt lt ExecutionConditionsPackage gt bts conditions execution lt ExecutionConditionsPackage gt lt ExecutionActions
86. i n enormes son dominios de competici n entre adversarios son no determin sticos no son completamente observables y adem s suele ser dif cil definir postcondiciones para las acciones del dominio las acciones no siempre tienen xito y pueden darse interacciones inimaginablemente complejas que son dif cilmente modelables 25 En Wargus un juego de estrategia en tiempo real parecido al conocido Warcraft 2 por ejemplo poco despu s del inicio de una partida el espacio de decisi n alcanza un tama o del orden de las miles de acciones 26 lo cual da una idea de la complejidad de este tipo de dominios Tradicionalmente esta situaci n ha dado lugar a que los desarrolladores acaben codificando manualmente la IA de los videojuegos Sin embargo el esfuerzo requerido para la codificaci n manual de una IA capaz de interaccionar con jugadores humanos suele ser muy grande Durante el proceso adem s los desarrolladores suelen cometer errores que degradan la calidad de la IA que finalmente ver la luz M s a n las IAs codificadas manualmente carecen del componente adaptativo que se requiere cuando se juega contra seres humanos En este sentido es f cil que los jugadores exploten tanto la estaticidad como las deficiencias de las IAs pudiendo derrotarlas f cilmente Dentro de los sistemas de codificaci n manual los rboles de comportamiento han adquirido cierta popularidad en los ltimos a os debido principalmente a su gran simplicida
87. iblioteca de planes que requieren la inter venci n del experto Tenemos en mente la idea de un proceso de identificaci n asistido por computador en el que se generen trazas de la IA gestionada por la biblioteca de planes para que el sistema autom ticamente detecte aquellos objetivos y acciones que fallan con cierta frecuencia como sitios donde se deba llevar a cabo una posible mejora Ap ndice A JBT Gu a del Usuario A l Introduction Java Behaviour Trees JBT is a Java framework for building and running behaviour trees BTs In the past few years BTs have been widely accepted as a tool for defining the behaviour of video games characters However to the best of our knowledge there is no free software Java implementation of such technology With JBT we intend to provide a solid framework to build and run BTs in Java JBT has two main parts On the one hand there is the JBT Core it is the Eclipse SDK project under the JBTCore directory of the repository which implements all the classes needed to create and run BTs JBT Core basically lets the user create BTs in pure Java and then run them In order to case the task of creating BTs JBT Core includes several tools that automatize the process of creating BTs In particular it can create the Java source code of a BT from its description in an XML format By doing so the user of this framework basically has to worry only about defining BTs in XML files and implementing the lo
88. ido usados en videojuegos de ltima generaci n tales como Halo Spore o GTA Chinatown Wars Los rboles de comportamiento pueden verse como una evoluci n natural de las HFSMs que favorece la reutilizaci n de comportamientos reemplazando las transiciones expl citas de las FSMs con mecanismos procedurales que permiten calcular cu l el siguiente estado del comportamiento del agente Aunque los rboles de comportamiento inicialmente nacieron como una herramienta dirigida a programadores con el paso del tiempo los dise adores profesionales de videojuegos han comenzado a usarlos de manera constante para la creaci n de los comportamientos de los personajes 9 12 Quiz s uno de los puntos claves de los rboles de comportamiento es que tal y como ocurre con las FSMs es f cil concebir entornos de desarrollo integrado que permitan crear y editar comportamientos a trav s de una interfaz gr fica lo cual favorece y acelera en gran medida el proceso de desarrollo Otras t cnicas como los scripts no son propicias a ello lo cual las hacen m s inefectivas Los rboles de comportamiento son estructuras jer rquicas de tipo rbol cuya principal componente es la tarea En un rbol de comportamiento un no do del rbol representa una tarea y una tarea representa un comportamiento Mientras que las hojas del rbol son tareas de bajo nivel que se ejecutan en el entorno virtual del juego los nodos intermedios representan tareas compuestas ta
89. ile format For those unaware of what MMPM is this does not really pose a problem since what we are really interested in is the format that MMPM follows in order to define actions and conditions A MMPM domain file defines the conceptual level of a game its domain by declaring what entities actions sensors and goals are present in the game We will not describe all of them but only what we need to declare actions and conditions that can be used in BTs A MMPM domain file has the following structure 62 AP NDICE A JBT GU A DEL USUARIO lt Domain package valid Java package name gt lt ActionSet gt lt Actions declaration gt lt ActionSet gt lt SensorSet gt lt Sensors declaration gt lt SensorSet gt lt GoalSet gt lt Goals declaration gt lt GoalSet gt lt EntitySet gt lt Entities declaration gt lt EntitySet gt lt Domain gt However we are only interested in the set of actions and conditions so lt GoalSet gt and lt EntitySet gt can be left empty but they actually have to be present The lt ActionSet gt element defines the set of actions that are present in the game which are also the set of low level actions that can be used when building BTs An lt ActionSet gt element contains a sequence of lt Action gt elements each one being an action An lt Action gt element has one attribute its name which is called name The lt SensorSet gt elem
90. ill explain this later The syntax of the program is as follows ActionsAndConditionsGenerator c configurationFile r relativePath o Where configurationFile is an XML file that contains all the information required to run the application The syntax of such file is lt Configuration gt lt DomainFile gt MMPMDomainFile1 lt DomainFile gt Remember that in BT terminology a task and a node are the same thing 66 AP NDICE A JBT GU A DEL USUARIO lt DomainFile gt MMPMDomainFile2 lt DomainFile gt lt DomainFile gt MMPMDomainFileN lt DomainFile gt lt ModelActionsPackage gt Name of the package for generated model action classes lt ModelActionsPackage gt lt ModelConditionsPackage gt Name of the package for generated model condition classes lt ModelConditionsPackage gt lt ModelActionsOutputDirectory gt Name of the directory where model actions are created lt ModelActionsOutputDirectory gt lt ModelConditionsOutputDirectory gt Name of the directory where model conditions are created lt ModelConditionsOutputDirectory gt lt ExecutionActionsPackage gt Name of the package for generated execution action classes lt ExecutionActionsPackage gt lt ExecutionConditionsPackage gt Name of the package for generated execution condition classes lt ExecutionConditionsPackage gt lt ExecutionActionsOutputDirectory gt Name of the directory where execution actions are created lt ExecutionActionsOutputDirectory gt
91. insertados entonces en la Piscina de BTs En cada ciclo del juego la capa t ctica da a los rboles de comportamiento de la Piscina de BTs algo de tiempo para que se ejecuten Es en ese momento cuando los rboles env an acciones a la API del juego En lo que respecta a los rboles de comportamiento de acciones de bajo nivel stos son finalizados por la capa t ctica cuando las condiciones de fallo o de xito conforme a la sem ntica de Darmok de las acciones que representan se hacen ciertas dado que es en ese momento cuando Darmok espera que dejen de ejecutarse para que pueda continuar con la evoluci n del plan global Con respecto a los rboles de comportamiento de planes objetivo stos interaccionan con Darmok a trav s de Planes de BT especiales Mientras estos planes proporcionen un modo de comprobar sus condiciones de xito y sus condiciones de fracaso Darmok puede interaccionar con ellos de manera normal Las condiciones de xito de estos planes son las mismas que la del objetivo que representan El aspecto relevante son las condiciones de fallo En una situaci n normal el plan ser a marcado como fallado tan pronto como una acci n o subplan de l fallase En este caso sin embargo dado que toda la ejecuci n del plan es gestionada por un rbol de comportamiento las condiciones de fallo son establecidas por el mismo rbol permitiendo as finalizar el plan cuando se considere oportuno 3 4 Recuperaci n de rboles media
92. ipos de unidades la acci n Atacar podr a tener que gestionarse de una manera muy distinta Mediante la reutilizaci n se evitar a tener que replicar el rbol original de la acci n Atacar 5 4 EXPERIMENTO 1 41 Repetir ListaDinamica DePriodidad Situaci nDe Peligro 88 Condici n NoAlcanzable Verdadera objetivolnicial Atacar enemigo Atacar objetivo Realizar Inicial Interrupci n Figura 5 4 Arbol de comportamiento para la acci n Atacar Con un borde negro remarcado se se alan las acciones y condiciones dependientes del dominio 42 CAP TULO 5 ESTUDIO EXPERIMENTAL Repetir ListaDinamica DePriodidad Situaci nDe Condici n Peligro Verdadera B squeda de rbol Atacar Moverse posici n Objetivo Realizar Interrupci n Figura 5 5 Arbol de comportamiento para la acci n Moverse Con un borde negro remarcado se se alan las acciones y condiciones dependientes del dominio 5 4 EXPERIMENTO 1 43 Figura 5 6 Escenario del experimento 1 El mapa de juego donde se plantea la batalla del experimento figura 5 6 consiste en una porci n de tierra plana con forma de rombo El terreno es com pletamente visible a los soldados de modo que en todo instante cada jugador sabe d nde est su oponente Para entrenar a Darmok se ha hecho uso de tres trazas consistentes en tres demostraciones de c mo llevar a cabo un combate en el escenario en cuesti n El ex
93. is spawned again All the persistent information of a task should be saved into an TaskState object The ITaskState interface represents a collection of variables that can 70 AP NDICE A JBT GU A DEL USUARIO be accessed public interface ITaskState 1 Returns the value of a state variable by its name public Object getStateVariable String name a When a task finishes it returns Status SUCCESS or Status FAILURE in internalTick the storeState method is automatically called by the fra mework This method should then create and return an TaskState object containing all the persistent information that the task may need if it is spaw ned again in the future If no persistent information is needed then null must be returned An TaskState object is just a collection of variables that can be retrieved by name In order for the user to create ITaskState objects he can make use of the factory class jbt execution core TaskState Factory It also may be the case that a task that is abruptly terminated inter nal Terminate is called needs to store persistent information If that is the case then storeTerminationState is automatically called by the framework instead of storeState storeTerminationState follows the same semantics as storeState The persistent information that a task stores via its storeState and store TerminationState methods is restored via the restoreState ITaskState state method This met
94. ition lt gt Conditions LowDanger HighDanger Figura A 5 The Nodes Navigator after loading the domain file Parameters target Coordinate From context Figura A 6 The dialog for editing the input parameters of the AttackMove action Parameters target Coordinate 12 34 4 5 O From context Figura A 7 A parameter for which an actual value is provided Parameters target Coordinate TargetVariable From context Figura A 8 A parameter whose value will be retrieved from the context 76 AP NDICE A JBT GU A DEL USUARIO 4 1 11 i A Root o Repeat A Dynamic Priority List A Attack S gt Sequence Aj ComputeClosestBasePosition 41 A Move PAS 4 Subtree Lookup StandardPatrol Figura A 9 Initial tree for the Terran Marine behaviour Also note that a name for the BT must be provided The name of a BT is specified in the root node of the tree When the root is double clicked a dialog appears that lets the user assign the tree a name BTs ames are very important because it is the way that trees are referenced In particular names are essential in terms of reusability For instance the Subtree Lookup task simulates a particular BT and the way that the Subtree Lookup knows what BT to simulate is by providing the name of the tree Let us now design the BT that implements the Terran Marine behaviour that we described in section A 3 An initial implementation for such tree could
95. itres controlados por los rboles de comportamiento se ve an menos afectados por las explosiones de las minas ara a al ser consciente de su presencia y poder huir del lugar a tiempo antes de que hiciera explosi n 50 CAP TULO 5 ESTUDIO EXPERIMENTAL Cap tulo 6 Conclusiones y Trabajo Futuro Este trabajo se ha centrado en el estudio de la idoneidad de la combinaci n de conocimiento experto en forma de rboles de comportamiento con Darmok un sistema de planificaci n basada en casos para juegos de estrategia en tiempo real Darmok presenta varios problemas en lo que respecta a su capacidad de reacci n ante eventos acontecidos en el mundo En particular en ciertos esce narios en la gesti n de acciones de bajo nivel muestra una baja reactividad que le impide tomar decisiones que pueden resultar trascendentales para el transcurso de batallas en otros escenarios en la gesti n de ciertos planes ob jetivo muestra una reactividad excesivamente alta pudiendo cancelar planes completos por la mera falla de una de sus acciones constituyentes Para solventar ambos problemas hemos propuesto una arquitectura h bri da basada en la inclusi n de conocimiento experto en forma de rboles de comportamiento y gestionado mediante una capa t ctica que se comunica di rectamente con Darmok Para probar la validez de la arquitectura presentada se llev a cabo un estudio experimental en un juego de estrategia en tiem po real StarCraf
96. la puerta que es romperla embisti ndola Si tras embestir contra ella la puerta se percibe como abierta se considerar que el intento de derribarla ha tenido xito En cualquier caso si el sub rbol que intenta abrir la puerta bien con la llave bien derrib ndola tiene xito el personaje entra en la habitaci n Si la puerta no ha podido ser abierta el comportamiento finalmente se considera fracasado Existen variantes de los nodos secuencia y selector que en lugar de ejecutar sus hijos de forma secuencial primero los barajan de forma aleatoria y luego los ejecutan en el orden establecido Estas variantes se emplean en situaciones en las que se quiera conferir un mayor realismo al comportamiento ya que elimina el componente de predictibilidad asociado a una ejecuci n secuencial est tica Otros tipos de tareas compuestas m s sofisticadas permiten dise ar com portamientos m s complejos y reactivos El nodo paralelo por ejemplo permite ejecutar de forma concurrente a todos sus hijos Los nodos paralelos son tiles en situaciones en las que por ejemplo se quiere asegurar que una condici n se mantiene v lida al mismo 2 3 TIPOS DE TAREAS 17 p gt Puerta Entrar en Moverse Entrar en abierta habitaci n a la puerta habitaci n S gt Puerta Abrir Cargar Puerta errada co puerta contra la abierta llave con llave puerta Figura 2 6 U
97. la reutilizaci n de rboles de comportamiento surge la nece sidad de poder usar cualquier rbol sin necesidad de incrustarlo literalmente all donde se necesite Para ello a cada rbol comportamiento de inter s se le asigna un nombre nico mediante el cual poder referenciarlo m s tarde En el caso del rbol de la figura 2 6 por ejemplo se le podr a asignar el nombre EntrarEnHabitacion Es m s el nodo selector situado en el tercer nivel del rbol realiza un comportamiento bien definido intentar abrir una puerta que est cerrada Es por ello que dado que es posible que fuera reutilizado en el futuro se le podr a asignar un nombre tal como AbrirPuerta a tal efecto Definida una biblioteca de rboles de comportamiento es decir un reposi torio con todos los rboles de utilidad identificados por nombre se puede hacer uso de una tarea conocida como b squeda de rbol La b squeda de rbol 2 4 REUTILIZACI N DE RBOLES 19 E Puerta Entrar en Moverse B squeda de rbol Entrar en abierta habitaci n a la puerta AbrirPuerta habitaci n Figura 2 7 El rbol de comportamiento de la figura 2 6 simplificado simplemente emula el comportamiento de un determinado rbol de compor tamiento identificado por nombre Haciendo uso de este tipo de nodo por ejemplo el rbol de la figura 2 6 podr a transformarse en el de la figura 2 7 20 CAP TULO 2 RBOLES DE C
98. les 3 3 ARQUITECTURA GLOBAL 25 Capa T ctica Acci n D2 petici nBT Acci n D2 D2 Le Base de rbol respuestaBT BTs rbol null X rbol null Re Estado del juego API D2 Action Insertar rbol Y API del o juego gt Piscina de BTs Figura 3 1 Capa t ctica de bajo nivel contienen una descripci n del estado del juego que especifica cu ndo es ade cuado hacer uso de ellos Cuando un rbol de comportamiento es recuperado con un objetivo particular ser n el rbol en s junto con la capa t ctica los encargados de gestionar el objetivo original La figura 3 2 muestra la arquitectura de la capa t ctica a alto nivel Inicial mente Darmok procede como de costumbre Sin embargo cuando se detecta un objetivo dentro de un plan el m dulo de expansi n de Darmok comprueba si el objetivo debe ser gestionado por un rbol de comportamiento Para rea lizar esta comprobaci n Darmok realiza una petici n a la Base de BTs del mismo modo que en el escenario de las acciones de bajo nivel Si la Base de BTs puede recuperar un rbol de comportamiento para el objetivo y estado del juego actual el plan objetivo actual Obj 3 en la figura es reemplazado por un Plan de BT y el rbol de comportamiento es marcado para ser enviado fuera de Darmok del mismo modo que las acciones de bajo nivel que genera en cada ciclo
99. ma Darmok consta de problemas de reactividad que le impiden reaccionar adecuadamente en ciertos escenarios frecuentes en juegos de estrategia Los rboles de comportamiento por otro lado son estructuras innatamente reactivas que permiten un control preciso de los agentes que ma nejan Mediante la combinaci n de ambos pretendemos resolver esta carencia de Darmok La estructura de este trabajo es la que sigue En el cap tulo 1 presentamos el sistema Darmok como ejemplo de arquitectura de planificaci n basada en casos El cap tulo 2 describe en detalle la t cnica de los rboles de comporta miento A continuaci n en el cap tulo 3 se explican algunas de las deficiencias de Darmok y c mo el uso combinado de rboles de comportamiento y planifi caci n basada en casos pueden resolverlos Posteriormente en el cap tulo 4 se describe brevemente JBT el framework de desarrollo de rboles de comporta miento que implementamos para este proyecto Por ltimo los cap tulos 5 y 6 recogen el estudio experimental llevado a cabo as como las conclusiones y propuestas de trabajo futuro Cap tulo 1 Planificaci n Basada en Casos Darmok 1 1 Razonamiento Basado en Casos El razonamiento basado en casos CBR 1 11 es una metodolog a de resoluci n de problemas basada en la reutilizaci n de conocimiento previo al macenado en forma de casos para hacer frente a problemas similares a los encontrados en el pasado Grosso modo un caso re
100. n rbol de comportamiento para el comportamiento Entrar en habitaci n tiempo que se ejecuta otro comportamiento El concepto de guarda toma forma en las listas est ticas de prioridad y en las listas din micas de prioridad Ambas permiten etiquetar a sus hijos con una condici n guarda que debe ser evaluada como cierta antes de que los hijos comiencen a ejecutarse La lista est tica de prioridad eval a inicialmente las guardas de sus hijos y comienza a ejecutar aqu l de mayor prioridad situado m s a la izquierda en el lista de sus hijos cuya guarda sea cierta Aunque el comportamiento de la lista din mica de prioridad es similar sta representa una estructura m s reactiva La lista din mica de prioridad comienza ejecutando al hijo de mayor prioridad cuya guarda es evaluada como cierta A partir de entonces la lista reeval a constantemente las guardas de modo que si alguna guarda de mayor prioridad se hace cierta se cancela al hijo actualmente en ejecuci n y comienza la ejecuci n del nuevo hijo 2 3 3 Decoradores Un nodo decorador es una tarea que modifica el comportamiento de otra tarea Los decoradores est n basados en el patr n software del mismo nom bre En orientaci n a objetos el patr n decorador se refiere a una clase que encapsula a otra Si el decorador tiene la misma interfaz que la de la clase a la que encapsula el resto del software no necesita saber si est manejando el decorador o la clase original
101. n definirse incontables condiciones de vida que modelasen todos los posibles escenarios lo cual incrementar a de gran manera el esfuerzo requerido para la recopilaci n del conocimiento del dominio Si por ejemplo el alto templario tuviera que huir de una eventual fuente de peligro para que no lo matasen se deber an definir nuevas condiciones de vida para la acci n ConvocarTormentaPsionica Adem s aunque la adici n de m s condiciones de vida puede dar lugar a una mayor reactividad por parte de Darmok el hecho de que se cancelen las acciones supone llevar a cabo una replanificaci n la cual podr a no ser necesaria En general en dominios donde se requiere una capacidad de reacci n r pida a bajo nivel Darmok ve empeorado su rendimiento 24 como es el caso de videojuegos como 52 parecido a StarCraft o BattleCity un juego de acci n m s que de estrategia Darmok fue dise ado inicialmente para competir en juegos de estrategia donde el requerimento de la capacidad de reactividad puede ser elevado en ciertos dominios como el de StarCraft o S2 Es por ello que su baja capacidad reactiva impide que en ciertos escenarios rinda a nivel humano llegando incluso a no superar a las IAs predefinidas Parad jicamente a alto nivel Darmok encuentra situaciones en las que no rinde adecuadamente debido justamente a un comportamiento excesivamente reactivo Cuando Darmok aprende planes a partir de las trazas que se le propor cionan puede dar
102. na consulta adecuada para que se recupere el rbol m s apropiado para ello As a la hora de recuperar un rbol B que gestione una acci n de bajo nivel A capa t ctica para las acciones de bajo nivel se construye una consulta cuya clase es la misma que la de A y cuyos descriptores recogen parte del estado global del juego as como del estado local de la unidad que va a ejecutar la acci n El estado local de la unidad es muy importante ya que en general la estrategia a seguir depende del entorno inmediato de la entidad que ejecuta la acci n No es as el caso de los rboles recuperados por la capa t ctica de alto nivel planes objetivo ya que a la hora de gestionar un objetivo m s general es probable que el estado global del juego influya en mayor medida lo cual no descarta que tambi n se usen descriptores m s espec ficos 3 5 Escenario En esta secci n planteamos dos escenarios en los que nuestra arquitectura mejora el rendimiento de Darmok Uno de ellos es un escenario de acciones de bajo nivel mientras que el otro es un escenario de planes objetivo 3 5 ESCENARIO 29 ListaDinamica DePriodidad Situaci n de Posici n Condici n A objetivo peligro verdadera visible f A A Desplazarse Busqueds de rbol SN a las cercan as sA de posici n obj Recalcular una posici n obj adecuada Lanzar tormenta en posici n obj Posici n objetivo apropiada
103. nalSpawn method which is as follows protected void internalSpawn Do not remove this first line unless you know what it does and you need not do it x this getExecutor requestInsertionIntoList jbt execution core BTExecutor BTExecutorList TICKABLE this TODO this method s implementation must be completed System out println this getClass getCanonicalName spawned This initial definition contains a very important aspect of the execution process of the task As it is said in the comments the first line should not be removed unless the user knows what it does and he thinks it is not necessary to do it What that line does is to request that the task be inserted into the list of tickable nodes section A 2 1 Since in general this is what we want the task to do because we want the task to receive ticks that line should not be removed When implementing all these abstract methods the user may access the execution context of the task by calling this getContext That method just returns the context of the task as an Context object The Context interface defines two main methods one for reading a variable from the context and another one for writing a variable into the context 68 AP NDICE A JBT GU A DEL USUARIO public interface IContext 1 Ak Returns the value of a variable whose name is lt code gt name lt code gt or null if it is not found wd public Object getVariable String
104. name o Sets the value of a variable If the variable already existed its value is overwritten lt code gt value lt code gt may be null in order to clear the value of the variable E public boolean setVariable String name Object value Remember that MMPM domain files also let the designer specify input parameters for actions and sensors These are parameters that actions and sensors are supposed to use when running The generated JBT ExecutionAc tion and ExecutionCondition classes include getter methods for such input parameters As a result the programmer will be able to access the value of the input parameters in the abstract methods he has to implement by using the getter methods The value for the input parameters are either retrieved from the execution context IContext or directly provided at construction time but these details are hidden from the programmer that implements the action or condition he should just use the getter methods to retrieve whatever input parameters may be needed For instance for the Attack action the next getter method is created ek Returns the value of the parameter target or null in case it has not been specified or it cannot be found in the contest public java lang String getTarget 1 Thus in the implementation of all the abstract methods the user should use this getTarget method if he wanted to retrieve the identifier of the target unit to attack This whole
105. nce una partida de StarCraft la DLL se pondr en funcionamiento y su m dulo de IA comenzar a ejecutarse 5 2 1 Comunicaci n en Java Si bien BWAPI proporciona una interacci n completa con la API de Star Craft su principal inconveniente es la dependencia del lenguaje de programa ci n C Darmok as como JBT est n implementados en Java lo cual hace impo sible su integraci n directa con BWAPI Adem s implementar la IA en C lleva consigo los problemas asocia dos a este lenguaje El principal es que la DLL inyectada por Chaoslauncher interfiera con el espacio de direcciones de StarCraft rompiendo el proceso y teniendo que reiniciar StarCraft lo cual podr a ralentizar en gran medida la experimentaci n Para resolver estos problemas se plantea el uso de un proceso externo que se comunique mediante sockets con StarCraft As la DLL que Chaoslauncher inyecta en el proceso de StarCraft se encarga de leer constantemente el estado del mundo y enviarlo fuera a trav s de un socket Por otro lado un proceso externo que puede estar implementado en cualquier lenguaje se encarga de leer del socket el estado del mundo Este proceso externo adem s env a al 38 CAP TULO 5 ESTUDIO EXPERIMENTAL Chaoslauncher IA Usuario Java Starcraft ModuloAl dll Proxy Bot Figura 5 3 Proxy Bot para la comunicaci n Java con Starcraft socket las accione
106. ncia durante el juego ya que es de esperar que haya acciones del plan original cuyas condiciones de xito sean ciertas en la situaci n actual del juego distinta de cuando el plan fue construido y que por tanto no tengan por qu ejecutarse Por otro lado es frecuente que cuando un plan vaya a eje cutarse sus precondiciones no sean ciertas en la situaci n actual En ese caso se lleva a cabo un tipo de adaptaci n estructural que permite insertar nuevos subplanes al plan original con la idea de que la realizaci n de cada uno los subplanes satisfaga alguna de las precondiciones no satisfechas Cap tulo 2 rboles de Comportamiento Tradicionalmente los sistemas de decisi n de bajo nivel que controlan los agentes personajes de videojuegos han hecho uso de alg n tipo de variante de m quina de estados finitos FSMs siendo las m s conocidas las m quinas de estados finitos jer rquicas HFSMs En contextos donde la inteligencia de los agentes es demasiado compleja desafortunadamente las FSMs se muestran en ocasiones insuficientes de modo que otro tipo de enfoques han sido adoptados destacando los lenguajes de scripting que permiten un grado de control mucho mayor sobre el comportamiento de la entidad En los ltimos a os una nueva t cnica conocida como rboles de comporta miento se ha convertido en una alternativa bastante popular en la creaci n de las IAs de personajes de videojuegos Los rboles de comportamiento han s
107. neral todos los nodos de un rbol comparten el mismo con texto ya que ste se suele pasar de los nodos padres a los nodos hijos a trav s del m todo spawn del pseudoc digo de la figura 2 1 Se tiene entonces que el contexto inicial es el de la tarea ra z del rbol que es transferido a sus hi jos los cuales har n lo propio con sus hijos y as sucesivamente En algunos escenarios es deseable a pesar de todo que algunos sub rboles dispongan de su propio rea de almacenamiento de datos privada para que cualquier tipo de modificaci n no afecte al contexto del resto del rbol En ese caso se rompe la regla de transferencia del contexto de padres a hijos pas ndoles en su lugar un nuevo contexto Para emular un paso tradicional de contexto y que los hi jos tengan la sensaci n de trabajar con el contexto original el nuevo contexto 2 3 TIPOS DE TAREAS 13 puede contener una copia de las variables del contexto padre As por un lado el sub rbol interacciona con el nuevo contexto como lo habr a hecho con el contexto original pero por otro no lo modifica 2 3 Tipos de Tareas Definida la sem ntica de funcionamiento de los rboles de comportamien to hay que establecer un conjunto de nodos suficientemente amplio y potente como para que se puedan implementar comportamientos complejos Debe te nerse en cuenta que el objetivo de los rboles de comportamiento es controlar de forma precisa y realista a personajes no jugadores
108. nio para Darmok y se han creado trazas de juego para entrenarlo Darmok puede ser extendido haciendo uso de rboles de comportamiento 5 3 1 Definici n del Dominio La definici n del fichero que contiene toda la informaci n del dominio Star Craft para que Darmok sea capaz de jugar a ste es compleja ya que Star Craft es un juego de estrategia comercial caracterizado por una gran comple jidad en lo que respecta a los tipos de entidades disponibles las acciones que pueden realizar y c mo interaccionan con el resto del mundo StarCraft dispone de 43 tipos de unidades de combate y 45 tipos de edificios repartidos entre las tres razas disponibles Terran Zerg y Protoss y con Llevada a cabo por Santiago Onta n 5 3 DISE O DE LOS EXPERIMENTOS 39 caracter sticas nicas Cada unidad dispone de una serie de acciones b sicas a saber atacar moverse y patrullar Ciertas unidades disponen de habilidades espec ficas como es el caso de las unidades de tipo trabajador que disponen de una acci n para recolectar minerales y otra para recolectar gas En general muchas unidades disponen de habilidades ofensivas y defensivas de diversa ndole En su conjunto todo ello conlleva un gran esfuerzo en la definici n del fichero del dominio de StarCraft Por otro lado la obtenci n de trazas de juego se antoja complicada debido a que la API de StarCraft BWAPI no permite acceder directamente a las acciones que el jugador en
109. nte M tri ca de Similitud Un aspecto importante de la arquitectura propuesta es el de asociar a ca da rbol un estado del mundo As cuando la capa t ctica lleva a cabo la recuperaci n de un rbol elige s lo aquellos cuyo estado del mundo es similar al estado actual En 28 y en 8 se propone un mecanismo de recuperaci n de comportamientos basado en CBR que implementa esta idea aplic ndolo en un caso a m quinas de estado finitas jer rquicas y en otro a rboles de comportamiento La recuperaci n de rboles de comportamiento en nuestra arquitectura se puede llevar a cabo siguiendo un esquema similar pero simpli ficado respecto al propuesto por los autores A cada caso rbol de comportamiento se le asocia un conjunto de ele mentos descriptores que describen el estado del mundo en que es apropiado usar el rbol Un descriptor representa una caracter stica del mundo con un valor num rico o simb lico asociado Adem s se le asocia una clase que in dica el tipo de comportamiento representado las clases pueden organizarse en taxonom as 28 CAP TULO 3 COMBINANDO DARMOK CON BTS Cuando se quiere recuperar un rbol se construye una consulta que indica el tipo de rbol que se desea Dicha consulta incluye tanto la clase del compor tamiento que se desea obtener como un subconjunto de descriptores del estado del mundo que se consideren relevantes a la hora de realizar la consulta es decir qu caracter sticas
110. o su ejecuci n Para cada comportamiento en JBT se distingue entre el rbol Modelo que lo define y el c mo es ejecutado El c mo es gestionado por el int rprete de rboles el Ejecutor de rbol El Ejecutor de rbol analiza un rbol Modelo y lo simula a trav s de los ticks que recibe de una entidad externa al framework Por cada tick el Ejecutor de rbol avanza en la simulaci n del rbol 4 1 CARACTER STICAS PRINCIPALES DE JBT 33 Ejecutor de rbol rbol Modelo M dulo de I in l i a Entidad N cy W rbol de Ejecuci n A Ejecutor de Ejecutor de Arbol Arbol j tick IA del v Juego Entidad 1 Entidad 2 Figura 4 1 Arguitectura global de JBT 4 1 3 Arquitectura Global La figura 4 1 muestra la arquitectura general de JBT Cada comportamien to est definido a trav s de un rbol Modelo Para cada entidad Entidad 1 Entidad 2 Entidad N que quiere ejecutar el comportamiento existe un Ejecutor des bel Cada Ejecutor de rbol hace uso del rbol Modelo lo interpreta y lo ejecuta simulando as el comportamiento definido en l Internamente el Ejecutor de rbol construye un rbol de Ejecuci n par cial que contiene s lo aquellos nodos envueltos en la ejecuci n del rbol Sin embargo esta mec nica interna es ocultada al usuario del Ejecutor de rbol que simplemente percibe que el rb
111. o 1 La idea consiste en hacer que si un soldado se encuentra en peligro hay alg n enemigo pr ximo y hay un b nker cercano en lugar de atacar al enemigo decida introducirse en el b nker El rbol de comportamiento de la figura 5 7 recoge el comportamiento planteado Cuando al soldado se le env a la orden de atacar a un determina do enemigo que inicialmente se debe situar en la variable objetivo nicial del contexto se comprueba si hay alg n enemigo cercano y si el objetivo inicial del ataque almacenado en la variable objetivolnicial no es alcanzable En ese caso el soldado se encuentra cerca de un enemigo distinto del de la acci n Ata car generada por Darmok y por tanto debe reaccionar ante su presencia La diferencia ahora es que el modo de reaccionar ante un peligro tiene en cuenta la presencia de b nkeres cercanos Si hay alg n b nker cercano al soldado ste intentar entrar en l Para ello se hace uso de una segunda lista de prioridad que comprueba tres condiciones diferentes En primer lugar si el soldado ya est dentro de un b nker es buena idea que permanezca dentro de l as que se fuerza a que as sea En segundo lugar si el soldado no est dentro de un b nker pero tiene un b nker cercano se le manda entrar en l Por ltimo si ninguna de las dos condiciones anteriores se sostiene el soldado atacar al enemigo que dispar esta rama del rbol el cual habr sido escrito por la con dici n Situa
112. o original que se su pone que se encuentra en una variable de nombre objetivolnicial del contexto Este comportamiento se repite hasta que la acci n Atacar objetivo nicial se d por concluida es decir cuando el enemigo sea destruido Cuando el enemigo es destruido la acci n RealizarInterrupci n termina la ejecuci n del nodo n terruptor haciendo que el rbol finalice con ello Cuando Darmok genera una acci n de tipo Atacar la capa t ctica crea un rbol de este tipo e inicializa su contexto para que contenga en la variable objetivoInicial el objetivo al que se debe atacar extra do de la acci n Atacar generada por Darmok En el dominio de StarCraft hay tambi n presentes acciones de tipo Moverse Esta acci n ordena a una unidad desplazarse a una determinada posici n sin prestar atenci n a los enemigos que pudiera encontrarse a lo largo del camino pudiendo ser atacada por ellos de forma indiscriminada Para solventar el car cter poco reactivo de la acci n Moverse se propone hacer uso del rbol de comportamiento de la figura 5 5 Este rbol muestra una estructura an loga a la del rbol que controla la acci n Atacar En este caso sin embargo cuando se detecta peligro se reutiliza el rbol Atacar definido anteriormente Si bien se podr a haber hecho uso de la acci n Atacar directamente una de las ventajas de los rboles de comportamiento es su capacidad de reutilizaci n Hay que tener en cuenta que para ciertos t
113. ode google com p bwapi Ben Weber http eis ucsc edu starproxybot 86 BIBLIOGRAF A Autorizaci n El abajo firmante matriculado en el M ster en Investigaci n en Inform ti ca de la Facultad de Inform tica autoriza a la Universidad Complutense de Madrid UCM a difundir y utilizar con fines acad micos no comerciales y mencionando expresamente a su autor el presente Trabajo Fin de M ster Ex tendiendo Darmok un Sistema de Planificaci n Basada en Casos mediante rboles de Comportamiento realizado durante el curso acad mico 2009 2010 bajo la direcci n de Pedro Antonio Gonz lez Calero en el Departamento de Ingenier a del Software e Inteligencia Artificial y a la Biblioteca de la UCM a depositarlo en el Archivo Institucional E Prints Complutense con el objeto de incrementar la difusi n uso e impacto del trabajo en Internet y garantizar su preservaci n y acceso a largo plazo Fdo Ricardo Juan Palma Dur n En Madrid a 13 de setiembre de 2010 87
114. ol Modelo avanza en su ejecuci n a cada tick recibido por el Ejecutor de rbol Por ltimo es el m dulo de IA del videojuego el encargado de hacer tick a cada Ejecutor de Arbol para que stos avancen en la ejecuci n del rbol de comportamiento 4 1 4 Modelo de rboles de Comportamiento JBT implementa un modelo de rboles de comportamiento basado prin cipalmente en el recogido en 19 pero extendido con el concepto de guardas 8 34 CAP TULO 4 JAVA BEHAVIOUR TREES Wj JET Editor File View Help AGA 44 GRAA lt gt Nodes Navigator 23 E StandardPatrolxbt A StandardPointPatrol Node Info 23 O lt gt Standard nodes S Root Type Action n D Node 28 S gt Composite 4 PS Interrupter Name Attack E preFailureTime from context unused Se eat Pe E S o pas failureTime from context unused P Selector a A Dynamic Priority List target from context ComputeClosestEnemyTarget gt Parallel a Seguence A Random Selector a o Dynamic Priority List fond Random Sequence a MBB Sequence E S A Static Priority List A SetSiegeMode 3 A Dynamic Priority List A Attack s 3 Nodes Searcher 23 lt gt decorator a m Sequence s Node ID Search A Hierarchical Context Mar A SetSiegeMode lt Node 0 Safe Output Context Mar A ComputeClosestEnemy ll Node 10 i E Node 11 Safe Context Manager stock Node 13 E SS interrupter 4 Sequence U Ha
115. om the set of variables of the Safe Context instead of reading if from the input context Thus the input context is never modi fied A Safe Context can be used to situations in which a certain context the input context must be used in read only mode Safe Output Context a Safe Output Context behaves much in the same way as the Safe Context It has another context the input context as a base However this context also contains a set of output variables that is a list of variables ames The list of output variables represents the variables that can be modified in the input context Variables other than those in the list of output variables will be stored locally in the set of variables of Safe Output Context just as if it were a Safe Context Thus when the Safe Output Context modifies the value of a variable it will normally set its value in a local variable that is a variable belonging to the Safe Output Context However if the variable is one of the list of output variables the value will be set in the input context which will therefore be modified When retrieving variables a variable in the list of output variables will always be retrieved from the input context A variable that is not in the list of output variables will also be retrieved from the input context however when such variable is modified the value will be retrieved from the Safe Output Context that is from the moment a variable that is not in the list of outpu
116. one of the children of a parallel task which is following the sequence policy fails When that happens all of its children which were being concurrently evaluated get terminated so they must stop running Other scenario in which this happens is when a perform interruption task interrupts an interrupter In that case the interrupter and its child stop running It is for cases like these that the internal Terminate method is defined The internal Terminate method must make the task stop running For instance in the case of the Move action it should order the unit to stop moving Moreover if the task started some other thread to perform some computations it should stop it In general when the internalTerminate is called the task should stop running and should also free whatever resources it acquired With respect to the storeState store TerminationState and restoreState ITaskState state they are related to persistent tasks Some tasks in BTs are persistent in the sense that after finishing if they are spawned again they should remember past information Take for example the Limit task A Limit task allows to run its child node only a certain number of times for example 5 After being spawned it has to remember how many times it has been run so far so that once the threshold is exceeded it fails In general it could be said that some tasks need to retain some persistent information to be used in the future when the task
117. ost selector succeeds as long as one of its children succeed The first child tries to enter the room when the door is locked In such case the character tries several tactics to open the door First if it has the key it uses it to open the door If it does not have the key but it has a grenade then it uses the grenade in order to blow the door up Finally if none of the above conditions are met the character will try to enter the room through its window note that here a Subtree Lookup node is used This node just runs a tree that is already defined in this case the tree that will be run is EnterThrough Window On the other hand if the door is not locked and it is closed the character will just open it up A 2 4 1 Execution Context All nodes in a BT have an execution context which is usually shared by all of them The execution context or context for short acts as a blackboard that can be used by nodes in order to write and read variables For instance a node may write a variable into the context under a name MyVariable This variable can be read then by using its name My Variable This way the context can be A 2 JBT AN OVERVIEW 57 Havekey A UnlockDoor Seguence A HaveGrenade A BlowUpDoor 4 Subtree Lookup EnterThroughWindow Figura A 3 a complex behaviour tree 58 AP NDICE A JBT GU A DEL USUARIO seen as a way for the nodes of a BT to communicate However not always all the nodes share the same conte
118. perimento a realizar consiste en la repetici n de 1000 combates entre dos grupos de soldados Terran cada grupo con 12 soldados Por un lado se enfrenta a Darmok sin la capa t ctica de rboles de comportamiento contra la IA est ndar de StarCraft Luego se repite el mismo enfrentamiento pero a adiendo a Darmok la capa t ctica con los rboles de comportamiento men cionados En cada caso se mide el n mero de victorias sobre el total con el fin de comparar cu l de los dos sistemas muestra un mejor rendimiento Darmok sin BTs Darmok con BTs Victorias 262 423 Derrotas 738 577 Victorias 26 2 42 3 Derrotas 73 8 57 7 Mejora 61 94 Tabla 5 1 Resultados del experimento 1 La tabla 5 1 muestra los resultados obtenidos del experimento Se aprecia que la inclusi n de los rboles de comportamiento descritos anteriormente para la gesti n de las acciones Atacar y Moverse proporciona una mejora sensible de los resultados obtenidos por el Darmok est ndar En concreto se obtiene 44 CAP TULO 5 ESTUDIO EXPERIMENTAL una mejora del 61 94 En este caso jug un papel relevante el hecho de poder reaccionar ante enemigos no previstos Analizando el desarrollo de la partida se pudo observar que cuando era Darmok sin rboles de comportamiento el que controlaba a los soldados Terran muchos de ellos eran destruidos por el enemigo antes de que incluso stos pudieran atacar una sola vez debido al hecho comentado con anteriorid
119. planes gracias a los cuales una entidad puede conseguir sus objetivos En este cap tulo describimos de forma detallada los rboles de comporta miento En primer lugar comentamos su mec nica de funcionamiento Poste riormente hablamos del contexto de ejecuci n que juega un papel especial mente relevante dentro del funcionamiento de los rboles de comportamiento Finalmente describimos las tareas que com nmente se utilizan para su cons trucci n y analizamos algunos ejemplos de rboles 2 1 Mec nica de Funcionamiento La mec nica de funcionamiento de los rboles de comportamiento se basa en el hecho de que todas las tareas nodos del rbol comparten una misma interfaz de operaci n El modo en que un nodo interacciona con sus hijos es in dependiente del tipo de cada hijo es decir del comportamiento que representa y s lo depende de la sem ntica del padre Inicialmente un ejecutor externo pide al nodo ra z del rbol es decir al comportamiento que se quiere ejecutar que comience su ejecuci n El nodo 2 2 CONTEXTO DE EJECUCI N 11 public class BTNode 1 private Vector lt BTNode gt children public void spawn Context context public Status update public void abort Figura 2 1 Estructura de un nodo de un rbol de comportamiento ra z en base a su sem ntica es decir a su tipo comenzar la ejecuci n de uno o varios de sus hijos los cuales dependiendo a su vez de su tipo comenzar n asimismo la ej
120. ppose that the configuration file above is stored in a file called BTConfigurationFile rml The BTLibraryGenerator may be called with the following arguments BTLibraryGenerator c BTConfigurationFile xml r home outputDirectory Then the BTLibraryGenerator will parse the configuration file and it will realize that it has to create just one BT library the only BT Library element in the configuration file It will then parse the XML files of the trees that the library will contain TerranMarine xbt and StandardPatrol xbt and finally will create an BT library class named TerranMarineB T Library which will be A 7 RUNNING THE BTHAVIOUR TREES 81 placed in the output directory home outputDirectory stc bts btlibrary Our purpose here is not to analyse all the details of the produced class but just point out that it can be used through the public interface that it implements the IBT Library mentioned earlier The class TerranMarineBT Library will contain both trees so getBT TerranMarine will return the tree implementing the Terran Marine behaviour and getBT StandardPatrol will return the tree implementing the patrol behaviour The way we can actually run these trees is explained in section A 7 A 7 Step 5 Running the Behaviour Trees So that is almost all The last step is to run the trees that have been put into one or several BT libraries The way BTs are run in JBT is really simple and follows the ideas men tioned in
121. presenta una experiencia usada en el pasado para la resoluci n de un determinado problema Cuando un sistema CBR encuentra un nuevo problema analiza su base de casos en b squeda de alguno que fuera usado en circunstancias similares a la actual fase de recuperaci n con la idea de reutilizarlo Esta reutilizaci n sin em bargo requiere adaptar el caso encontrado al problema actual ya que el caso recuperado en su momento no fue usado para resolver exactamente el mis mo problema fase de reutilizaci n Posteriormente se eval a la calidad de la soluci n propuesta y se corrige en caso de ser necesario fase de revisi n Finalmente la soluci n obtenida se almacena en la base de casos como un nuevo caso para as aumentar el conocimiento disponible fase de retenci n La figura 1 1 muestra el ciclo cl sico de un sistema CBR donde se aprecian las cuatro fases mencionadas Si bien el ciclo CBR actualmente est s lidamente establecido dependiendo del dominio de aplicaci n sus distintas partes pueden dise arse de maneras muy distintas entre s En particular representaciones del dominio muy diferentes pueden dar lugar a fases de recuperaci n o adaptaci n muy diferentes Otras caracter sticas como la organizaci n de la informaci n en la base de casos o las m tricas de similitud usadas en la fase de recuperaci n pueden conllevar amplias diferencias en lo que a eficiencia de c mputo se refiere El CBR ha sido aplicado exitos
122. reas con uno o varios hijos en la estructura del rbol las cuales determinan de qu modo evoluciona la ejecuci n del rbol y en ltima instancia en conse cuencia qu tareas de bajo nivel se ejecutar n En cualquier caso el nodo que encarna un comportamiento determinado puede o bien fallar o bien tener xito en su ejecuci n Dependiendo del resultado la tarea comportamiento padre toma el control de la ejecuci n del rbol y reacciona acorde a su sem ntica 10 CAP TULO 2 RBOLES DE COMPORTAMIENTO Es justamente el hecho de que todos los comportamientos tareas o nodos del rbol comparten la misma interfaz de funcionamiento lo que hace que los rboles de comportamiento sean una herramienta potente y a su vez sencilla Esto permite que se puedan construir comportamientos jer rquicos con gran facilidad partiendo de comportamientos simples para agruparlos posterior mente en comportamientos m s complejos Como en la mayor a de los casos los comportamientos son auto contenidos adem s los nuevos comportamien tos no deben preocuparse acerca de los detalles del funcionamiento de cada subcomportamiento pudiendo reutilizarlos de manera transparente Una de las mayores ventajas de los rboles de comportamiento es su capa cidad para determinar cu ndo se ejecuta un determinado comportamiento sin necesidad de definir como ocurre con las FSMs condiciones expl citas para cada tipo de transici n En lugar de ello los rboles d
123. rrent position Patrolling around a position means that the marine will move randomly around a central point and will attack whatever he finds on its way However if he finds himself in a low level danger situation that is a dangerous situation he thinks he can survive he will try to kill whatever enemy finds dangerous On the other hand if he finds himself in a high level danger situation that is a dangerous situation he thinks he cannot survive he will run away to the closest base We therefore define some actions and conditions that will be used by the BT z Actions e Attack this action just makes the marine attacks a specific unit e Move this action makes the marine move to a specific target posi tion on the map e AttackMove this action makes the marine mote to a specific target position on the map Also if he finds an enemy on its way he will combat the enemy e ComputeClosestBasePosition this action computes the position of the base that is closest to the marine e ComputeCharacterPosition this action just computes the current position of the marine e ComputeRandomClosePosition given a position A this action com putes a random position that is close to A a Conditions e LowDanger this condition checks if the marine is in a low danger situation e HighDanger this condition checks if the marine is in a high danger situation Actions and conditions must be defined according to the MMPM domain f
124. running e Subtree Lookup see the following sections to see what this node does e Perform Interruption task that interrupts an Interrupter task e Variable Renamer task that renames a variable in the context e Success task that immediately succeeds e Failure task that immediately fails e Action generic action that is executed in the game engine e Condition generic condition that is executed in the game engine A 3 Step 1 Defining Low Level Actions and Conditions The first step when creating BTs is to define the set of low level actions and conditions that the trees will be using These actions and conditions are 2Well it does not necessarily have to be the first step but we have to start at somewhere A 3 DEFINING ACTIONS AND CONDITIONS 61 domain dependent that is they depend on the game that the trees will be run for For instance if we are dealing with a first person shooter FPS from now on then we may need actions and conditions such as those used in the trees of section A 2 4 However we are going to build a more complex example Here we are going to define a behaviour tree that is able to control a Terran Marine of StarCraft so we have to define actions and conditions that are useful for such context The behaviour that we want to implant in the Terran Marine is as follows The marine is constantly checking three conditions If there is no danger around the marine then he just patrols around its cu
125. s til en situaciones donde se percibe que seguir re pitiendo un comportamiento no tiene sentido Por ejemplo volviendo al rbol de la figura 2 6 el sub rbol que intenta abrir una puerta embisti ndola podr a ser controlado mediante un nodo limitar para que el personaje intentara de rribarla varias veces intentos tras los cuales finalmente se dar a por vencido 2 4 Reutilizaci n de rboles Una de las propiedades m s interesantes de los rboles de comportamiento es su capacidad de reutilizaci n A diferencia de otras t cnicas donde la reuti lizaci n es complicada como las FSMs la misma naturaleza de los rboles de comportamiento hace posible que sea f cil reutilizarlos en cualquier situaci n En un rbol de comportamiento cualquier nodo representa un comporta miento Salvo en las tareas de bajo nivel estos comportamientos est n a su vez compuestos de otros m s sencillos sus hijos en la jerarqu a del rbol En cualquier caso es la ra z de cada sub rbol lo que representa el compor tamiento en cuesti n As por ejemplo el rbol de la figura 2 6 representa el comportamiento Entrar en habitaci n All donde se quisiera que el personaje entrase en una habitaci n bastar a reusar el rbol de la figura Si dentro de un rbol m s complejo una parte requiriera hacer que el personaje entrase en una habitaci n bastar a colgar el rbol de la figura 2 6 desde su ra z en la parte correspondiente Para favorecer
126. s que se quieren ejecutar en StarCraft las cuales son le das y ejecutadas por la DLL inyectada a trav s de Chaoslauncher Para la experimentaci n se hizo uso de una versi n corregida de Proxy Bot 36 Proxy Bot implementa la arquitectura planteada tal y como se muestra en la figura 5 3 Proxy Bot define una interfaz Java de comunicaci n con StarCraft pu di ndose implementar una IA cualquiera IA Usuario en la figura en Java que trav s del Proxy Bot permita leer el estado de juego de StarCraft as como alterarlo Proxy Bot se comunica a trav s de un socket con una DLL implemen tada mediante BWAPI leyendo el estado del mundo que sta le proporciona y envi ndole a sta las acciones que se desean ejecutar en el juego 5 3 Dise o de los Experimentos Crear una IA que sea capaz de jugar a un nivel competente en un juego comercial es una ardua y ambiciosa tarea Al elegir StarCraft como entorno de pruebas se pretende demostrar que la arquitectura descrita combinaci n de Darmok con rboles de comportamiento puede dar buenos resultados en entornos reales que van m s all de entornos artificiales controlados La arquitectura propuesta parte de la necesidad de un sistema Darmok en trenado para competir a un nivel aceptable en el juego en cuesti n Es por ello que es necesario definir un dominio lo suficientemente detallado como para que Darmok pueda jugar correctamente a StarCraft Una vez se ha dado una defini ci n de domi
127. s tiene tambi n sus limitaciones en particular el n mero de trazas de entrenamiento necesitadas as como la ausencia de mecanismos para reaccio nar r pidamente ante objetivos de alta prioridad En este trabajo proponemos que el dise ador defina de manera expl cita conocimiento para la toma de de cisiones en forma de rboles de comportamiento para as complementar el conocimiento obtenido a partir de las trazas Proporcionando un mecanismo natural para que los dise adores inyecten conocimiento en la librer a de pla nes pretendemos integrar lo mejor de ambos enfoques aprendizaje de trazas y reglas codificadas a mano En este trabajo extendemos un sistema de planificaci n basada en casos Darmok para resolver algunos de sus problemas m s importantes Darmok que fue dise ado para jugar a juegos de estrategia en tiempo real tiene algunas deficiencias en lo que respecta a su capacidad de reactividad En concreto puede ser o demasiado reactivo cuando ejecuta algunos planes o demasiado no reactivo en la ejecuci n de algunas acciones de bajo nivel lo cual en su conjunto hace que su rendimiento se deteriore en algunos escenarios bastante frecuentes Mediante el uso de conocimiento experto en forma de rboles de comportamiento pretendemos solventar estos problemas Palabras clave Toma de Decisiones a Nivel Estrat gico Toma de Deci siones a Nivel T ctico Planificaci n Modelado de Comportamiento Arbol de Comportamiento Darmok
128. se con creces al enemigo En tales situaciones un buen modo de ac tuar consiste en ordenar que todas las unidades aliadas ataquen de manera simultanea los edificios y unidades enemigas hasta que sean destruidos por completo Al igual que en el escenario de bajo nivel el rbol de comporta miento contendr a una descripci n del estado del mundo en el que deber a ser usado Cuando el objetivo DestruirAlEnemigo es generado en el plan que Darmok construye el m dulo de expansi n de Darmok intentar encontrar un rbol de comportamiento apropiado en la Base de BTs para ello usando el estado actual del mundo as como el estado asociado al rbol Si las unidades aliadas superaran con creces a las enemigas el rbol de comportamiento des crito podr a ser recuperado y enviado fuera de Darmok junto con las acciones que normalmente produce A partir de entonces ser a manejado por la capa t ctica Cap tulo 4 Java Behaviour Trees un Framework para el Desarrollo de rboles de Comportamiento en Java Durante el dise o del sistema basado en rboles de comportamiento pa ra la extensi n de Darmok nos encontramos con el problema de hacer uso de alg n framework de rboles de comportamiento que implementara al me nos un modelo suficientemente potente como para que se pudieran dise ar comportamientos elaborados Adem s dicho modelo deb a estar implementa do preferiblemente en Java ya que al ser ste el lenguaje en el que Darmok es
129. se el caso de que algunos de los planes objetivo aprendidos no tengan una estructura adecuada Este problema est en parte relacionado con el modelo de ejecuci n de Darmok Darmok asocia planes a objetivos Cuando alguna de las acciones individuales o de los planes objetivo que componen el plan principal falla el plan principal tambi n se marca como fallido y Dar mok lo descarta marcando su objetivo abierto nuevamente Como resultado Darmok intentar encontrar un plan diferente para el objetivo que pasar a 3 1 CAPA T CTICA DE BAJO NIVEL 23 ejecutar En ciertos escenarios este comportamiento no conlleva un buen resulta do Por ejemplo si un plan objetivo DestruirAlEnemigo se usa para acabar con todas las unidades del enemigo los planes para dicho objetivo estar n compuestos de muchas acciones o subplanes todos ellos con el prop sito de destruirlas En el fragor de la batalla sin embargo en realidad se espera que las unidades fallen las acciones que intentan llevar a cabo ya que en una bata lla hay multitud de ocasiones que pueden impedirles completar sus tareas por ejemplo podr an ser destruidas As en estos casos Darmok seguir fallando los planes que obtenga de la base de casos para el objetivo DestruirAlEnemi go debido al fallo continuado de las acciones o subplanes que lo componen Al final despu s de intentar varios planes Darmok acaba haciendo algo que tiene alg n sentido pero la calidad de la soluci n por
130. sections A 2 1 A 2 2 and A 2 3 Basically the IBT Library is used to retrieve Model BTs Once a Model BT has been retrieved a BT Executor must be created to run it The BT Executor must be fed with an initial context that the BT will use when running Let s suppose that we have created our TerranMarineB T Library and that we want to use it in order to control a particular Terran Marine in the game First of all two details must be taken into account On the one hand the actions that we implemented well we actually im plemented only one action Move but you get the idea made the assumption that the identifier of the unit running the action was present in the context under a variable named CurrentEntityID you can revisit the implementa tion in section A 4 In general it may be necessary for the context that is used by the tree to have some initial variables in it In such case an appropriate context should be created On the other hand the SubtreeLookup task poses a big problem when it is run Remember that the SubtreeLookup node simulates the behaviour of a tree given its name However how does it know from where to retrieve a tree given its name For instance in the case of the Terran Marine tree the SubtreeLookup is suppose to emulate a tree named StandardPatrol but it does not know where to get such a tree from The context is used in order to fix this problem Actually the context must contain all the trees that are
131. supuesto no es en absoluto buena sta es de hecho la principal raz n por la cual Darmok no es bueno en combate necesitando generalmente tener el doble de unidades que el enemigo para poder derrotarlo 25 Por ltimo hay que resaltar el hecho de que la planificaci n basada en ca sos para juegos de estrategia requiere un gran esfuerzo por parte del experto si se quiere refinar escenarios muy espec ficos Si el experto detecta una carencia en la base de casos deber a proporcionar un nuevo plan que aprender Des afortunadamente el nico modo de hacerlo consiste en jugar una partida que simule el escenario concreto a aprender lo cual puede llegar a ser extremada mente dif cil debido a la complejidad y aleatoriedad inherente a los juegos de estrategia Nuestra propuesta consiste en hacer uso de rboles de comportamiento pa ra superar los problemas presentados En primer lugar dado que los rboles de comportamiento permiten al dise ador definir comportamientos a bajo nivel pueden usarse para modelar escenarios muy complejos adem s los dise ado res est n acostumbrados a dise ar comportamientos complejos En segundo lugar pueden emplearse para definir acciones de bajo nivel es decir c mo el sistema debe comportarse ante las acciones enviadas por Darmok Por ltimo pueden usarse para modelar planes para objetivos en situaciones en las que es conveniente tener un mejor control que el que Darmok tiene por defecto La idea es e
132. t desarrollado se conseguir a una mejor integraci n Hasta donde llega nuestro conocimiento no existe actualmente ning n fra mework de rboles de comportamiento basado en licencias de software libre tales como GNU GPL o similares e implementado en Java Es por ello que decidimos implementar por nuestra cuenta nuestro propio framework de rbo les de comportamiento en Java El resultado es Java Behaviour Trees JBT un framework que permite al desarrollador definir de forma r pida y sencilla rboles de comportamiento almacenarlos en ficheros XML est ndar para una posterior reutilizaci n y ejecutarlos como c digo nativo Java JBT est libe rado bajo licencia GNU GPLv3 pudiendo accederse a l a trav s de la p gina oficial de Sourceforge http sourceforge net projects jbt Para una descrip ci n detallada de c mo funciona JBT referimos al lector al ap ndice A 4 1 Caracter sticas Principales de JBT A la hora de implementar JBT se tuvieron que tomar ciertas decisiones de dise o que determinar an c mo todo el framework ser a implementado Adem s se tuvieron en cuenta problemas comunes asociados al uso de rboles de comportamiento para los cuales se intent dar una soluci n adecuada 4 1 1 Modelo Conducido por Ticks JBT implementa un modelo de rboles de comportamiento conducido por ticks Esto significa que un rbol de comportamiento es evaluado s lo a trav s de ticks donde un tick representa una c
133. t Action gt lt ActionSet gt lt SensorSet gt lt Checks if the current unit is in a low danger situation gt lt Sensor name LowDanger type BOOLEAN gt lt Checks if the current unit is in a high danger situation gt lt Sensor name HighDanger type BOOLEAN gt lt SensorSet gt lt EntitySet gt lt EntitySet gt lt GoalSet gt lt GoalSet gt lt Domain gt One of the ways nodes in BTs communicate with each other is by using the execution context a node may write a variable into the context and another node may use it later In this scenario it is therefore very important that nodes know the name of the variables that other nodes put into the context In the set of actions and conditions above there are several nodes that manipulate the context In particular The ComputeCharacterPosition action writes into the context a variable of type COORDINATE containing the current position of the unit The name of such variable is CharacterPosition The ComputeClosestBasePosition action writes into the context a varia ble of type COORDINATE containing the position of the closest base The name of such variable is ClosestBasePosition The ComputeRandomClosePosition action writes into the context a va riable of type COORDINATE containing a random position that is close to the input position The name of such variable is RandomClosePosition The LowDanger sensor writes into the context a variable of
134. t Dada la complejidad del dominio StarCraft s lo lleg a implementarse la capa t ctica para la gesti n de acciones de bajo nivel omi ti ndose detalles tales como la recuperaci n basada en similitud de los rboles de comportamiento Se propusieron una serie de experimentos en los que se comprob la diferencia de rendimiento entre Darmok sin la presencia de rbo les de comportamiento y Darmok con la incorporaci n de rboles de compor tamiento De los resultados obtenidos en la experimentaci n llevada a cabo se desprende no s lo que la inclusi n de conocimiento experto en forma de rboles de comportamiento supone una mejora significativa del rendimiento de Darmok sino que esta mejora se puede dar en escenarios de muy diversa ndole Hasta donde llega nuestro conocimiento no hay ning n otro trabajo que combine planificaci n basada en casos con rboles de comportamiento No obstante este enfoque puede considerarse como un ejemplo particular de una tendencia en IA m s general que busca la combinaci n de datos emp ricos con el modelo del dominio en este caso los casos de la biblioteca de planes representan los datos emp ricos mientras que los rboles de comportamien to codifican una visi n parcial del modelo del dominio por parte del experto Desde este punto de vista se puede encontrar en la literatura 27 muchos ejemplos de combinaci n del modelo del dominio generalmente en forma de reglas con razonamiento basado
135. t variables is modified it is managed locally A 2 JBT AN OVERVIEW 99 A 2 4 2 Native Tasks JBT offers a wide range of tasks that can be used to build behaviour trees JBT basically implements the BT model described in 19 but extended with guards JBT supports the following tasks Composite tasks tasks with one or more children whose execution de pends on the execution of their children The task s children are ordered Sequence task that sequentially executes all its children in order If one fails the Sequence task fails If all succeeds the Sequence task succeeds Selector task that sequentially executes all its children in order If one succeeds the Selector task succeeds If all fail the Selector task fails Parallel task that concurrently executes all its children A Parallel task does have a parallel policy If the parallel task s policy is se guence the parallel fails if one child fails if all succeed then the parallel succeed If the parallel task s policy is selector the parallel fails if all its children fail If one succeeds then the parallel also succeeds Random Selector task that executes all its children in a random or der If one fails the Sequence task fails If all succeeds the Sequence task succeeds Random Seguence task that seguentially executes all its children in random order If one succeeds the Selector task succeeds If all fail the Selector task fails Dynami
136. ta es de esperar que en muchas ocasiones no reaccione ante la presencia de enemigos distintos a los marcados como objetivos del ataque y que insista en atacar al enemigo inicialmente marcado a pesar de que pueda implicar no defenderse Se espera que Darmok tenga problemas a la hora de defenderse de los ata ques enemigos Si un soldado A controlado por Darmok fija como objetivo de su ataque a un soldado B enemigo y antes de poder atacar a B otro enemigo C aparece en su camino es probable que C ataque a A sin que A se defien da produci ndose una baja innecesaria Si este comportamiento se repite para todos los soldados es probable que el resultado global del combate se vea afec tado Para remediarlo proponemos el uso del rbol de comportamiento de la figura 5 4 Dicho rbol comprueba continuamente mediante una lista din mica de prioridad si hay alg n enemigo visible y si el objetivo inicial al que se debe atacar objetivolnicial no es alcanzable condici n Situaci nDePeligro E465 NoAlcanzable objetivolnicial Si lo hay entonces el soldado est cerca de un enemigo distinto al objetivo inicial del ataque ante cuya presencia debe reac cionar el enemigo es almacenado por la condici n Situaci nDePeligro en el contexto de ejecuci n en la variable de nombre enemigo para que a trav s de la acci n Atacar subsiguiente sea atacado Si no hay ninguna situaci n de peligro a la unidad se le env a la orden de atacar al objetiv
137. tations regarding the number of training traces required and the absence of mechanisms for rapidly reacting to high priority goals We propose to bring the game designer back into the loop by allowing him to explicitly inject decision making knowledge in the form of behavior trees to complement the knowledge obtained from the traces By providing a natural mechanism for designers to inject knowledge into the plan library we intend to integrate the best of both worlds learning from traces and hard coded rules In this work we extend a well known case based planning system Darmok to overcome some of its most important flaws Darmok initially designed to play real time strategy games does have some problems concerning its reac tivity capabilities In particular it can be either too reactive when executing some plans or too non reactive when executing some low level actions which makes its performance greately deteriorate in some scenarios By using ex pert knowledge in the form of behaviour trees we intend to overcome these problems Key words Strategic Decision Making Tactical Decision Making Plan ning Behavior Modeling Behaviour Tree Darmok Case Based Reasoning v VI ABSTRACT Resumen La combinaci n de aprendizaje autom tico y planificaci n ha demostra do ser una buena soluci n para los juegos de estrategia en tiempo real Sin embargo aprender planes jer rquicos a partir de trazas demostraciones de experto
138. th them In JBT there are two classes for every type of node Remember from section A 2 2 that in JBT there are two types of BTs the Model BT and the Execution BT The Model BT is composed of model tasks while the Execution BT is composed of execution tasks It is the execution tasks that define how the tasks work that is how they behave when they are spawned and ticked In the case of actions and conditions the four classes presented above are the base classes for their respective representation as model tasks and execution tasks JBT Core offers a tool that semi automatize the task of creating all the classes from each action and condition of the MMPM domain file It is the Java class jbt tools btlibrarygenerator ActionsAndConditionsGenerator java For every MMPM action ActionsAndConditionsGenerator creates two clas ses one extending ModelAction which conceptually represents the action and another one extending ExecutionAction which represents how the action ac tually works whose abstract methods must be completed in order for the action to perform any task at all We will explain this later Also for every MMPM boolean sensor two classes are created one exten ding ModelCondition which conceptually represents the condition sensor and another one extending ExecutionCondition which represents how the con dition actually works whose abstract methods must be completed in order for the condition to perform any task at all We w
139. the BT Executor to run the tree In JBT a BT Executor is represented by the IBTExecutor interface In order to create an IBTExecutor object to run a particular BT the factory class jbt execution core BTExecutorFactory java must be used The BTEzecutorFactory has se veral methods for creating BT Executors one of them receives as input the Model BT to run and the initial context Now we get the Model BT to run ModelTask terranMarineTree btLibrary getBT TerranMarine Then we create the BT Executor to run the tree IBTExecutor btExecutor BTExecutorFactory createBTExecutor terranMarineTree context And finally we run the tree through the BT Executor dof btExecutor tick Jwhile btExecutor getStatus Status RUNNING Note that running a BT is a very simple process The JBTExecutor interface defines one main method tick which implements the ticking process of a BT Every time the tick method is called the BT is given some CPU time to do its work as was explained in section A 2 1 In order to check the current execution status of the tree the getStatus method is used As long as the status is Status RUNNING the tree has not finished so it should continue to receive ticks Bibliograf a 1 10 11 12 13 14 Agnar Aamodt and Enric Plaza Case based reasoning foundational is sues methodological variations and system approaches AI Communica tions 7
140. thing about the getter methods may be a little bit confusing at first However bear in mind that when the user creates a behaviour tree which we will explain later he can either specify that the input parameter of a task must be retrieved from a variable of the context or provide an actual value for the parameter When the task is spawned and run it does not really care about where the parameter comes from as long as there is a value that it can use The generated getter methods hide these details so no matter where the parameter comes from either from the context or from an actual value provided by the user when he created the BT it just provides the value that the task expects to use Once the task has been spawned it will be ticked whenever the BT gets ticked The ticking process is performed by the internal Tick method Thus A 4 IMPLEMENTING ACTIONS AND CONDITIONS 69 from the moment the task gets spawned at every tick internalTick will be called internalTick is in charge of keeping track of the termination status of the task If the task has not finished yet when internalTick is called then it must return the termination status Status RUNNING If the task has finis hed successfully then the method should return the termination status Sta tus SUCCESS If the task has finished unsuccessfully then the method should return Status FAILURE For instance the internalTick method of the Move action of our Terran Marine e
141. tiveChild children activeChild spawn return RUNNING J F public void abort Abortar la ejecucion del hijo activo if activeChild 1 amp amp activeChild children size children activeChild abort Figura 2 3 Pseudo implementaci n del nodo secuencia 16 CAP TULO 2 RBOLES DE COMPORTAMIENTO Sas Enemigo Darse la visible vuelta Huir Figura 2 4 Un rbol de comportamiento simple con un nodo secuencia Decir Hacer Hacer un te quiero un postre regalo Figura 2 5 Un rbol de comportamiento simple con un nodo selector El rbol de la figura 2 6 conceptualiza el comportamiento Entrar en habi taci n El comportamiento recoge dos casos hijos secuencia del nodo selector ra z Si cuando se va a entrar a una habitaci n la puerta est abierta primera secuencia hija de nodo ra z entonces el personaje entra simplemente en la habitaci n Sin embargo si no lo est segunda secuencia hija del nodo ra z el personaje debe intentar abrirla Para ello en primer lugar se acerca a la puerta Luego intenta abrirla de dos modos si la puerta est cerrada con llave se intenta abrir con la llave Obs rvese que si la acci n Abrir puerta con llave tiene xito no se intentar el siguiente modo de abrir la puerta Por contra si la puerta no est cerrada con llave o si la llave no funciona correctamente Abrir puerta con llave falla se intenta otra alternativa para abrir
142. tos inconvenientes se propone implementar un rbol de comportamiento para el buitre Terran figura 5 9 que se encargue de gestio nar su acci n Atacar Este rbol muestra una estructura similar al del soldado Terran del experimento 1 secci n 5 4 es decir es un rbol reactivo ante la presencia de enemigos cercanos Sin embargo ahora cuando el buitre detecte la presencia de enemigos y compruebe que dispone de minas ara a inten tar emplazarlas en una posici n cercana a los enemigos detectados Adem s si el buitre detecta que en las proximidades hay tanto enemigos como minas ara a intentar huir de la zona ante el riesgo de que las minas hagan ex 48 CAP TULO 5 ESTUDIO EXPERIMENTAL Repetir ListaDinamica DePriodidad Situaci nDe Peligro 8 8 NoAlcanzable objetivolnicial Repetir proceso de colocaci n de minas Atacar enemigo Realizar Interrupci n Acercarse enemigo A A x Minas 2 MinaCerca HuirDeMina Disponibles UsarMina Figura 5 9 rbol de comportamiento para la acci n Atacar del buitre Terran plosi n y le hagan da o en el proceso En otro caso si no dispone de minas ara a atacar al enemigo mediante un ataque normal Si el objetivo original del ataque extra do de la acci n Atacar generada por Darmok es visible intentar realizar el mismo proceso pero contra dicho enemigo El rbol de comportamiento de la figura 5
143. type EN TITY_ID containing the identifier of the closest dangerous enemy The name of such variable is LowDangerTarget A 4 IMPLEMENTING ACTIONS AND CONDITIONS 65 A 4 Step 2 Implementing Low Level Actions and Conditions Once that low level actions and conditions have been defined see section A 3 the next step is to provide an implementation for them JBT does not know what does an action such as ComputeCharacterPosition or AttackMove Therefore it is the user of the framework who has to tell JBT how they work The life cycle of actions and conditions of a BT is very simple initially when the flow of execution reaches the node it is spawned From then on at every game tick the node is ticked Every time the node is ticked it has to report about its termination status so that the tree may evolve in case the node has finished As a result the programmer will have to define how all the domain dependent actions and conditions behave when they are spawned and ticked Actions and conditions are each represented by two classes of the JBT Core 3bt model task leaf action ModelAction java and jbt execution task leaf action ExecutionAction java in the case of actions and jbt model task leaf condition ModelCondition java and jbt execution task leaf condition ExecutionCondition java in the case of conditions Domain dependent actions such as the ones defined above must extend these classes in order for JBT to know how to work wi
144. v a a las unidades en cada instante Al tratarse de un videojuego comercial cerrado sin acceso a su c digo fuente adem s se hace imposible obtener dicha informaci n de primera mano Las rdenes deben inferirse de manera artificial mediante el an lisis de los ficheros de las repeticiones de las partidas a pesar de lo cual el procedimiento no es del todo exacto y est sujeto a errores Por todo ello y dado lo abrumador de la tarea finalmente se cre un fichero de dominio para un aprendizaje parcial no preparado para acabar partidas completas con la raza Terran 5 3 2 Experimentos Dado que la complejidad del dominio hizo imposible preparar escenarios m s elaborados como partidas completas la experimentaci n propuesta lleva a cabo un estudio del rendimiento de Darmok en escenarios de bajo nivel S lo se lleg a implementar la capa t ctica para la gesti n de acciones de bajo nivel secci n 3 1 y tampoco se lleg a desarrollar la recuperaci n de rboles mediante m trica de similitud bas ndose en el estado del mundo secci n 3 4 A lo largo de una partida de StarCraft Darmok tiene que hacer frente a numerosas situaciones que requieren un comportamiento altamente reactivo si se desea obtener un buen resultado En general cualquier forma de combate directo o uso de habilidades especiales son un buen ejemplo de ello El que en un combate Darmok sea capaz de reaccionar adecuadamente puede suponer la diferencia entre
145. vos los cuales pueden estar organizados en una jerarqu a 1 3 2 Adquisici n de Planes En la fase de adquisici n de planes se obtienen los planes que almacenar la base de casos con la cual Darmok podr construir un plan para el desarrollo de la partida En Darmok los casos de la base de casos est n formados por snippets y por episodios asociados a los snippets Mientras que el snippet representa un plan concreto el episodio almacena el resultado de aplicar dicho plan en un estado del mundo concreto para satisfacer un objetivo concreto El problema de la adquisici n de planes a partir de la traza de una partida es la imposibilidad de saber qu objetivos persegu a el jugador con cada una de las acciones de la traza En Darmok que no Darmok 2 este problema se resolv a mediante la anotaci n manual de la traza en la cual un experto recorr a la traza de acciones e indicaba para cada una de ellas el objetivo que persegu a el objetivo es seleccionado de entre el listado de objetivos especificados en el dominio Una vez que se tiene para cada acci n qu objetivo se persegu a con ella se lleva a cabo un an lisis temporal de la traza ver figura 1 3 el cual permite extraer los casos snippets y episodios asociados con los que rellenar la base de casos En Darmok 2 la adquisici n de casos se realiza de forma autom tica a trav s de una matriz de objetivos y un grafo de dependencias 23 34 Gracias a la matriz de objetivos
146. w level actions and conditions that his trees will use which are domain dependant that is they depend on the game being played We provide a jar file with all the JBT Core classes Of course in order to get the last version of the JBT Core the repository can be accessed On the other hand there is the JBT Editor which is composed of two Eclipse SDK projects under the JBTEditor directory of the repository The JBT Editor is a GUI application that can be used for defining BTs and then exporting them into XML files in the format that the JBT Core understands The JBT Editor offers a set of standard nodes for building BTs It includes nodes such as sequences parallels decorators etc For low level actions and conditions the user can provide their conceptual definition through Make Me Play Me MMPM domain files for more information on MMPM see the Sourceforge page of the project Darmok 2 The JBT Editor is an Eclipse RCP application so you must use Eclipse SDK in order to run it An alternative to run it is to use the executable files provided for each platform Of course if order to get the last version of the JBT Editor the repository can be accessed JBT implements a BT model which is mainly based on that of the book Artificial Intelligence for Games second edition by Ian Millington and John Funge JBT also includes the concept of guard nd static and dynamic priority Note that when talking about BTs nod
147. xample should check if the unit has arrived at the target position If it has not then Status RUNNING should be returned If the unit has arrived at the target position then Status SUCCESS should be returned Finally y for some reason the action could not be completed for instance because the target position is unreachable then Status FAILURE should be returned Note that even though the Status enum has more values other than SUCCESS FAILURE and RUNNING the internal Tick method must return only one of these three Doing otherwise will throw an exception One of the ideas behind the driven by ticks architecture is that when the tree is ticked it should not take very long for it to return so internalSpawn and internalTick are supposed to return very quickly However sometimes tasks perform computationally expensive processes In that case instead of performing the expensive computation inside the internalSpawn method of the task it should be performed in another execution thread When internalS pawn is called it should create another thread that carries out the compu tation On the other hand the internal Tick method would query the thread to check if its computation has finished or not and return Status RUNNING Status SUCCESS or Status FAILURE accordingly The internal Terminate method is not so important Sometimes when a BT is running some of its tasks get abruptly interrupted This happens for instance when
148. xt In general the context of a BT is passed down from parents to children Thus the initial con text is that of the root of the tree which will pass it to its children The root s children will pass the context to their own children and so on Nevertheless some nodes do not pass their own context to their children but another one instead This new context may be empty or not and it may be of a different type JBT supports the following types Basic Context this is just a normal context with no especial features It is the context that the user of the framework can create Other types of contexts are managed through decorator tasks and the user cannot create them Hierarchical Context a Hierarchical Context has another context the input context as a base When the Hierarchical Context cannot find a variable within its own set of variables it will ask its input context for the variable Note that the Hierarchical Context can be used to build a complex hierarchy of context if the input context is a Hierarchical Context too the request for the variable may go up the hierarchy until a non Hierarchical Context is reached Safe Context a Safe Context has another context the input context as a base Initially all variables are read form the input context However when a variable is modified its value is not modified in the input context but locally modified instead From then on the variable will be locally read that is fr
149. xtender la arquitectura de Darmok mediante una capa t ctica basada en rboles de comportamiento y que se encargue de gestionar algunas accio nes de bajo nivel as como algunos planes de tipo objetivo Cuando Darmok genera una acci n de bajo nivel o un plan objetivo se lleva a cabo una deci si n acerca de si es conveniente o no que sea gestionada mediante un rbol de comportamiento La idea es proporcionar rboles que en algunos escenarios se espera que se comporten de manera correcta como substitutos de acciones de bajo nivel o planes objetivo 3 1 Capa T ctica para la Gesti n de Acciones de Bajo Nivel Las acciones de bajo nivel es decir aquellas generadas por Darmok en cada ciclo del juego deben ser ejecutadas directamente en la API del juego Con el fin de tener un mejor control sobre ellas proponemos el uso de rboles de comportamiento para implementarlas Inicialmente podr a pensarse que para 24 CAP TULO 3 COMBINANDO DARMOK CON BTS cada tipo de acci n tales como AtacarEnemigo o Moverse podr a haber un rbol de comportamiento que las implementara Ser an en ese caso rboles de comportamiento orientados por acci n es decir rboles de comportamiento que persiguen un determinado objetivo la acci n en s pero tambi n con la capacidad de cambiar su comportamiento general en caso de ser necesario Esto es justamente lo que explic bamos anteriormente cuando a una unidad se le da alg n tipo de orden deber

Download Pdf Manuals

image

Related Search

Related Contents

Digitus DK-300105-030-S USB cable  Modicon M221 - Logic Controller - Guía de programación  OBRAS CIVIS: Modelo - Prefeitura Municipal de Bagé  取扱説明書  700IP-C5 User Manual - Smart Bus Home Automation Control  OM, Poulan, 2250, 2450, 2550, 952801687, 952801838  Moduli I/O IS1 - r. stahl home  Info 84 (Octubre) (PDF  USER MANUAL - Dj-магазин HIMUSIC  Manual  

Copyright © All rights reserved.
Failed to retrieve file