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.

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.

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.

<p dir="ltr">Task-oriented programming is a way of programming manipulators in terms of high-level tasks instead of explicit motions. It has been a long-standing vision in robotics since its early days. Despite its potential, several challenges have hindered its full realization. This thesis identifies three major challenges, particularly in task specification and the planning-to-execution transition: 1) The absence of natural language integration in system input. 2) The dilemma of continuously developing non-uniform and domain-specific primitive-task libraries. 3) The requirement for much human intervention.</p><p dir="ltr">To overcome these difficulties, this thesis introduces a novel approach that integrates natural language inputs, eliminates the need on fixed primitive-task libraries, and minimizes human intervention. It adopts the behavior tree, a modular and user-friendly form, as the task representation and advances its usage in task specification and planning-to-execution transition. The thesis is structured into two parts – Task Specification and Planning-to-Execution Transition.</p><p dir="ltr">Task specification explores the use of large language models to generate a behavior tree from an end-user's input. A Phase-Step prompt is designed to enable the automatic behavior-tree generation from end-user's abstract task descriptions in natural languages. With the powerful generalizability of large language models, it breaks the dilemma that stays with fixed primitive-task libraries in task generation. A full-process case study demonstrated the proposed approach. An ablation study was conducted to evaluate the effectiveness of the Phase-Step prompts. Task specification also proposes behavior-tree embeddings to facilitate the retrieval-augmented generation of behavior trees. The integration of behavior-tree embeddings not only eliminates the need for manual prompt configuration but also provides a way to incorporate external domain knowledge into the generation process. Three types of evaluations were performed to assess the performance of the behavior-tree embedding method.</p><p dir="ltr">Planning-to-execution transition explores how to transit primitive tasks from task specification into manipulator executions. Two types of primitive tasks are considered separately: point-to-point movement tasks and object-interaction tasks. For point-to-point movement tasks, a behavior-tree reward is proposed to enable reinforcement learning over low-level movement while following high-level running order of the behavior tree. End-users only need to specify rewards on the primitive tasks over the behavior tree, and the rest of the process will be handled automatically. A 2D space movement simulation was provided to justify the approach. For object-interaction tasks, the planning-to-execution transition uses a large-language-model-based generation approach. This approach takes natural-language-described primitive tasks as input and directly produces task-frame-formalism set-points. Combined with hybrid position/force control systems, a transition process from primitive tasks directly into joint-level execution can be realized. Evaluations over a set of 30 primitive tasks were conducted.</p><p dir="ltr">Overall, this thesis proposes an approach that advances the behavior-tree towards automated task specification and planning-to-execution transitions. It opens up new possibilities for building better task-oriented manipulator programming systems.</p>

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.