This thesis presents the implementation and functionality of the user interface for creating behavior trees in the Unreal Engine (version 4.10). The thesis analyzes the final version of the behavior trees in a game development project carried out over one year with a group ranging between four and seven members. The game which is analyzed is a third person adventure game which contains four types of simple behavior trees. These include two enemies who mainly move towards the player to attack whenever in range and two bosses with individual behavior. The thesis describes the various types of nodes available in the Unreal Engine as well as how the behavior trees in the game are structured. Focus is placed on how the structure achieves the required result and how the process resulted in the final version of the behavior trees. / Detta examensarbete beskriver implementationen och funktionaliteten av användargränssnittet för att skapa beteendeträd i Unreal Engine (version 4.10). Arbetet analyserar den slutgiltiga versionen av beteendeträden i ett spelutvecklingsprojekt som utfördes under ett år med en grupp vars antal växlade mellan fyra och sju medlemmar. Spelat som analyseras är ett tredjepersons äventyrsspel som innehåller fyra typer av grundläggande beteendeträd. Två fiender som huvudsakligen rör sig mot spelaren för att anfalla när de är inom räckhåll, och två bossar med individuella beteenden. Arbetet beskriver de olika typerna av noder tillgängliga i Unreal Engine och även hur beteendeträden i spelet är uppbyggda. Fokus läggs på hur strukturen uppnår det nödvändiga resultatet samt på hur processen resulterade i den slutgiltiga versionen av beteendeträden.

Behavior Trees are a method for AI programming that consists of a tree of hierarchical nodes controlling the flow of agent's decision making. They have proven, while being a pretty straightforward means to implement an AI, to be incredibly powerful way of obtaining autonomous agents, both due to a fact that the development can be iterable (one can start with implementing simple behavior and gradually improve the tree by adding and modifying nodes and branches) and allowing for, so to say, ``fallback tactics'', should the currently executed action fail. Born in the game industry, they have since gained fair amount of popularity in other domains, including robotics.Evolutionary algorithms, largely popularized by John Holland, have been adapted for use in a vast variety of different problems, including optimization issues and decision handling, often through introducing serious changes to both the algorithm structure and data structures used. Arguably, one of the most valuable modifications was Genetic Programming, popularized through works of John Koza. This thesis documents the work on combining Behavior Trees and Genetic Programming in order to study and observe cooperative and adversative behaviors between agents controlled by genetically generated Behavior Trees. Evolving two kinds of agents in two contrasting scenarios, this thesis focuses on feasibility of selfishness versus utilitarian behaviors and their evolution. After defining what constitutes a success for each case, we attempt to compare the results from respective scenarios to see which behavior type is profitable to exhibit.

Animals such as bees, ants, birds, fish, and others are able to efficiently perform complex coordinated tasks like foraging, nest-selection, flocking and escaping predators without centralized control or coordination. These complex collective behaviors are the result of emergence. Conventionally, mimicking these collective behaviors with robots requires researchers to study actual behaviors, derive mathematical models, and implement these models as algorithms. Since the conventional approach is very time consuming and cumbersome, this thesis uses an emergence-based method for the efficient evolution of collective behaviors. Our method, Grammatical Evolution algorithm for Evolution of Swarm bEhaviors (GEESE), is based on Grammatical Evolution (GE) and extends the literature on using genetic methods to generate collective behaviors for robot swarms. GEESE uses GE to evolve a primitive set of human-provided rules, represented in a BNF grammar, into productive individual behaviors represented by Behavior Tree (BT). We show that GEESE is generic enough, given an initial grammar, that it can be applied to evolve collective behaviors for multiple problems with just a minor change in objective function. Our method is validated as follows: First, GEESE is compared with state-of-the-art genetic algorithms on the canonical Santa Fe Trail problem. Results show that GEESE outperforms the state-of-the-art by a)~providing better solutions given sufficient population size while b)~utilizing fewer evolutionary steps. Second, GEESE is used to evolve collective swarm behavior for a foraging task. Results show that the evolved foraging behavior using GEESE outperformed both hand-coded solutions as well as solutions generated by conventional Grammatical Evolution. Third, the behaviors evolved for single-source foraging task were able to perform well in a multiple-source foraging task, indicating a type of robustness. Finally, with a minor change to the objective function, the same BNF grammar used for foraging can be shown to evolve solutions to the nest-maintenance and the cooperative transport tasks.

This degree project investigates the suitability of using Behavior Trees (BT) as an architecture for the behavioral layer in autonomous driving. BTs originate from video game development but have received attention in robotics research the past couple of years. This project also includes implementation of a simulated traffic environment using the Unity3D engine, where the use of BTs is evaluated and compared to an implementation using finite-state machines (FSM). After the initial implementation, the simulation along with the control architectures were extended with additional behaviors in four steps. The different versions were evaluated using software maintainability metrics (Cyclomatic complexity and Maintainability index) in order to extrapolate and reason about more complex implementations as would be required in a real autonomous vehicle. It is concluded that as the AI requirements scale and grow more complex, the BTs likely become substantially more maintainable than FSMs and hence may prove a viable alternative for autonomous driving.

Resilience is essential for long-term autonomous agents. Swarm behaviors seen in bees, ants, birds, fish, and others are interesting because they resiliently perform complex coordinated tasks like foraging, nest-selection, flocking and escaping predators without centralized control or coordination. Conventionally, mimicking swarm behaviors with robots requires researchers to study actual behaviors, derive mathematical models, and implement these models as state machines. Since the conventional approach is time-consuming and cumbersome, this dissertation uses a grammatical evolution algorithm with Behavior Trees (BTs) to evolve behaviors that are resilient to different perturbations for foraging and nest maintenance tasks. The modular, reactive, and readable properties of BTs make it an excellent controller for implementing swarm behaviors. Our method is based on the author's master's thesis work on a core algorithm called Grammatical Evolution algorithm for Evolution of Swarm bEhaviors using Behavior Trees (GEESE-BT). The GEESE-BT algorithm can be used to evolve swarm behaviors for interesting multiagent problems, but the solutions require ad hoc fitness functions tailored to the specific problems. This dissertation presents the BeTr-GEESE algorithm, which replaces ad hoc fitness functions with direct feedback from the BT modules. BeTr-GEESE learns more efficiently than GEESE-BT. The modular, subtask-specific programs produced by BeTr-GEESE can be exchanged through lateral transfer to perform missions that require sequential execution of subtasks. Lateral transfer produces resilient performance in divisible and additive group tasks like foraging and nest maintenance. However, the behaviors of successful groups must exhibit temporal locality, meaning that an agent must persist in behavior long enough to perform essential functions but also means that agents cannot persist too long or evolution is too slow. A biologically inspired enhancement of using multiple genes with BeTr-GEESE allowed a fixed population of heterogeneous agents to accomplish tasks with high resilience power and efficiency. The last part of the dissertation complements the empirical approach used in designing resilient swarms using grammatical evolution. Goal specification and verification are vital to designing resilient artificial agents. Finite trace Linear Temporal Logic ($LTL_f$) is a potent way of specifying goals, but synthesizing planners that guarantee the goals are satisfied can be computationally prohibitive. This dissertation shows that goals specified using a subset of finite trace Linear Temporal Logic ($LTL_f$) can be decomposed into an equivalent BT that leads to a relaxed behavior synthesis problem in which a wide range of planners can be used to generate effective behaviors that satisfy the goal specification.

Behavior Trees (BTs) are a reactive policy representation that has gained popularity in recent years, especially in the robotics domain. Among the learning methods for BTs, Genetic Programming (GP) is an effective method for learning a good BT. One drawback of GP is that it is likely to get stuck in local minima. In this project, we focus on studying both the existing methods and new directions to avoid local minima and improve the efficiency of learning BT with GP. The methods studied in the project are the grid search, the Bayesian Optimization (BO), the Distributed Island Model (DIM) and the dynamic selection pressure. We performed the experiments with four different benchmark applications implemented with high-level state machines. The changes related to fitness values, diversity, and origin throughout the learning processes were collected and analyzed as part of the quantitative analysis. Some generated BTs were selected for the qualitative analysis to provide insights into the local minima and individuals with ideal performance. Based on our experiments, we conclude that learning BTs with GP can benefit from a fitness function that is sensitive to the performance differences of the individuals. The effect of methods including the DIM and the dynamic selection pressure depends on both the applications and the settings. We recommend the grid search method for hyperparameter searching and the DIM for accelerating the learning process from distributed computing. / BTs är en reaktiv policy-representation som har ökat i popularitet de senaste åren, särskilt inom robotik. Bland inlärningsmetoderna för BTs är GP en effektiv metod för att generera bra BT. En nackdel med GP är att den lätt fastnar i lokala minima. I det här projektet fokuserar vi på att studera på existerande metoder och nya sätt att undvika lokala minima och öka inlärningseffektiviteten för BT med GP. Metoderna som studerats i projektet är grid search, BO, DIM och dynamic selection pressure. Vi genomförde experiment med fyra olika benchmarkapplikationer som implementerats med högnivå-tillståndsmaskiner. Ändringar i fitnessvärden, mångfald och källa till ändringen genom inlärningsprocessen samlades in och analyserades genom kvantitativ analys. Några genererade BTs valdes ut för kvalitativ analys för att ge insikter i de lokala minimumen och vilka individer som ger ideal prestanda. Baserat på våra experiment konkluderar vi att inlärning av BTs med GP kan tjäna på en bra fitnessfunktion som är känslig för prestandaskillnader mellan invidider. Effekten av metoderna DIM och dynamic selection pressure beror på applikationen och inställningarna. Vi rekommenderar grid search för hyperparametersökning och DIM för att accelerera inlärningen från distribuerade system.

This report presents a strategy to control multiple collaborative intelligent agents acting in a complex, versatile environment. The proposed method utilizes back-chained behavior trees and 1-to-1 task distribution. The agents claim a task, which prevents other agents in the system to start working on the same task. Backward chaining is an algorithm for generating reactive agents from a set of goals. The method was evaluated in Minecraft with Microsoft’s Project Malmo API. Two different scenarios were considered. In the first one, a group of agents collaborated to build a structure. In the second one, a group of agents collaborated while gathering material. We propose and evaluate three algorithms with different levels of agent-cooperation and complexity (Algorithm 1, Algorithm 2, and Algorithm 3). The evaluation shows that backward chained Behaviour Trees (BTs) works well for multiagent coordination in complex versatile environments and that adding 1-to-1 task distribution increases the efficiency of the agents when completing the experiment tasks. / Rapporten presenterar en metod för styrning av en grupp kollaborativa intelligenta agenter agerande i en komplex dynamisk miljö. Den förslagna metoden använder sig av bakåtkedjade beteendeträd och 1-mot-1 uppgiftsdistribution, där en agent reserverar en uppgift vilket hindrar andra agenter att börja arbeta på samma uppgift. Bakåtkedjning är en metod som möjliggör generering av flexibla agenter utifrån en lista av mål och krav. Metoden utvärderades i två olika scenarion i tv-spelet Minecraft. Agenterna samarbetar i det första scenariot med att bygga en struktur och i det andra scenariot med att samla material. Vi föreslår och utvärderar tre algoritmer med olika nivåer av agentsamarbete och komplexitet (Algoritm 1, Algoritm 2, och Algorithm 3). Utvärderingerarna indikerar att bakåtkedjade beteendeträd fungerar bra för multiagentkoordination i komplexa dynamiska miljöer och att 1-mot-1 uppgiftsdistribution ökar agenternas förmåga att genomföra experimentuppgifterna ytterligare.

In this thesis we study the problem of robotic interaction with objects from a flexible perspective that complements the rigid force-closure approach. In a flexible interaction the object is not firmly bound to the robot (immobilized), which leads to many interesting scenarios. We focus on the secure kind of flexible interactions, commonly referred to as caging grasps. In this context, the adjective secure implies that the object is not able to escape arbitrarily far away from the robot which is caging it. A cage is a secure flexible interaction because it does not immobilize the object, but restricts its motion to a finite set of possible configurations. We study cages in two novel scenarios for objects with holes: caging through multi-agent cooperation and through dual-arm knotting with a rope. From these two case studies, we were able to analyze the caging problem in a broader perspective leading to the definition of a hierarchical classification of flexible interactions and cages. In parallel to the geometric and physical problem of flexible interactions with objects, we study also the problem of discrete action scheduling through a novel control architecture called Behavior Trees (BTs). In this thesis we propose a formulation that unifies the competing BT philosophies into a single framework. We analyze how the mainstream BT formulations differ from each other, as well as their benefits and limitations. We also compare the plan representation capabilities of BTs with respect to the traditional approach of Controlled Hybrid Dynamical Systems (CHDSs). In this regard, we present bidirectional translation algorithms between such representations as well as the necessary and sufficient conditions for translation convergence. Lastly, we demonstrate our action scheduling BT architecture showcasing the aforementioned caging scenarios, as well as other examples that show how BTs can be interfaced with other high level planners. / <p>QC 20170322</p>

The field of artificial intelligence has gained much knowledge through the implementation of decision-making systems in video games. One of these systems was the Goal Oriented Action Planning system (GOAP) which directs the behavior of an AI-agent through multiple digital artifacts categorized as goals, actions, and plans. The aim of the thesis is to aid in the understanding and creation of GOAP driven AI-agents in a video game setting to promote research on this topic. The research question of this thesis was about finding out how the GOAP architecture compares to other video game decision-making systems. The theoretical framework introduces the concept of the illusion of intelligence in video games and presents a discussion focused on the different components which make up a GOAP system and other components that support it. Additionally, the theoretical framework explains the need for a comparison between different decision-making systems and explains the social impact of game AI research. The methods section introduces the criteria for the comparison between GOAP and other decision-making systems and presents a comparison process that was driven by a literature review. A GOAP system was designed for this thesis using the unified modeling language and concept maps. It was then implemented using C# code in a free-of-charge game engine called Unity. We present the pseudocode for the implementation of the GOAP system and show that this framework is a modular, customizable, and reusable system that enables AI-agents to create plans from a varied set of actions. Finally, the paper suggests further research within game decision-making AI and emphasizes the importance of game AI research for communities of game developers, hobbyists, and others who could benefit from game AI in their projects.

Robot programming can be an expensive and tedious task and companies may have to employ dedicated staff. A promising framework that can alleviate some of the most repetitive tasks and potentially make robots more accessible to non-experts is Learning from Demonstration (LfD). LfD is a framework where the robot learns how to solve a task by observing a human demonstrating it. A representation of the learned policy is needed and Behavior Trees (BTs) are promising. They are a representation of a controller that organizes the switching between tasks and naturally provides the modularity required for learning and the reactivity required for operating in an uncertain environment. Furthermore, BTs are transparent, allowing the user to inspect the policy and verify its safety before executing it. Learning BTs from demonstration has not been studied much in the past. The aim of this thesis is therefore to investigate the feasibility of using BTs in the context of LfD and how such a structure could be learned. To evaluate the feasibility of BTs and answering how they can be learned, a new algorithm for learning BTs from demonstration is presented and evaluated. The algorithm detects similarities between multiple demonstrations to infer in what reference frames different parts of a task occur. The similarities are also used to detect hidden task constraints and goal conditions that are given to a planner that outputs a reactive task plan in the form of a BT. The algorithm is evaluated on manipulation tasks in both simulation and a real robot. The results show that the resulting BT can successfully solve the task while being robust to initial conditions and reactive towards disturbances. These results suggest that BTs are a suitable policy representation for LfD. Furthermore, the results suggest that the presented algorithm is capable of learning a reactive and fault-tolerant task plan and can be used as a basis for future algorithms. / Robotprogrammering kan vara kostsamt och repetitivt och företag kan behöva anställa särskild personal. Ett lovande ramverk som kan underlätta några av de mest repetitiva uppgifterna och potentiellt göra robotar mer tillgängliga för icke-experter är Inlärning från Demonstrationer (eng. Learning from Demonstration, LfD). LfD är ett ramverk där roboten lär sig lösa en uppgift genom att observera hur en människa gör det. En representation av den inlärda policyn behövs och Beteendeträd (eng. Behavior Trees, BTs) är lovande. De är en representation av en kontroller som organiserar växlandet mellan olika uppgifter och tillhandahåller naturligt den moduläritet som krävs för lärande och den reaktivitet som krävs för att verka i en oviss miljö. Dessutom är BTs transparenta, vilket gör det möjligt för användaren att inspektera policyn och verifiera dess säkerhet innan den körs. Att lära sig BTs från demonstrationer har inte studerats mycket tidigare. Syftet med det här arbetet är därför att undersöka genomförbarheten av att använda BTs inom sammanhanget av LfD och hur en sådan struktur kan läras. För att utvärdera genomförbarheten hos BTs och svara på hur de kan läras in presenteras och utvärderas en ny algoritm för inlärning av BTs. Algoritmen detekterar likheter mellan flera demonstrationer för att avgöra i vilken referensram olika delar av uppgiften sker. Likheterna används även för att upptäcka dolda bivillkor och målvillkor i uppgiften som ges till en planerare som skapar en reaktiv uppgiftsplan i form av en BT. Algoritmen utvärderas på manipuleringsuppgifter både i simulering och på en verklig robot. Resultaten visar att de resulterande BTs kan lösa uppgifterna med framgång och samtidigt vara robusta mot begynnelsevillkor och reaktiva mot störningar. Resultaten antyder att BTs är lämpade som en policyrepresentation för LfD. Vidare antyder resultaten att den presenterade algoritmen är kapabel att lära sig en reaktiv och feltolerant uppgiftsplan och kan användas som en utgångspunkt för framtida algoritmer.