Genetiska algoritmer och beteendeträd är två populära AI-tekniker som använts i både kommersiella produkter och forskningssyfte. Kombinationen av dem genom evolution av beteendeträd är däremot ett väldigt outforskat ämne som denna rapport handskas med. Arbetet beskriver först bakgrunden av de individuella teknikerna samt de få artiklar som relaterar till den specifika ämneskombinationen. Sedan presenteras problemformuleringen vilket angår jämförelsen av en singel- och multimål genetisk algoritm i syftet att utveckla beteendeträd till ett 2d-skjutspel. En artefakt skapades för att sätta upp spelet, implementera algoritmerna och testa dem gentemot varandra. Progression och designval för implementationen beskrivs i detalj följt av en pilotstudie och sedan en slutgiltig utvärdering. Resultatet pekade på att singelmålsalgoritmen lyckades vinna fler matcher. Detta faktum analyseras och diskuteras. Till slut avslutas rapporten med ett avsnitt om framtida arbeten vari ämnen såsom utforskning av olika genomstrukturer och automatiskt genererad AI för företag föreslås.

Ett simulationsbaserat testningssystem tas fram i samarbete med molntjänsten Coredination för att testa deras API (Application Programing Interface) och tjänst. Design och utveckling skedde iterativt med en loggbok för informationsinsamling. Arbetet baserade sig i riktlinjer för agentbaserad simulering framtagna av Macal & North (2010). Simulationstestningen bestod av ett antal agenter som med hjälp utav beteendeträd fattade beslut som liknar de beslut en användare av systemet skulle göra. Från detta togs ett antal lärdomar samt en systemarkitektursmodell fram för att underlätta utveckling av simulationsbaserad testning i andra sammanhang. Dessa lärdomar innefattar att göra en tydlig förstudie, arbeta iterativt med projektet, utveckla för modularitet och initialt för kommunikation mellan agenterna, bygg på nodernas funktionalitet i efterhand, avsätt gott om tid för design av beteendeträd, utveckla endast det absolut enklaste fallet först samt var inte rädd att ändra systemarkitekturen utefter agenternas planerade beteenden.

Detta arbete undersöker skillnader i tidseffektivitet mellan beteendeträd ochHierarchical Task Network. En enklare spelprototyp av typen top-down 2D shoot-emup implementerades. Spelprototypen använder två typer av autonom motspelare så kallade botar. En bot för beteendeträd och en bot för Hierarchical Task Network. Spelprototypen mäter körtiden för varje typ av bot i sex olika situationer. Varje situation svarar mot ett bestämt beteende hos boten. Ett beteende kan brytas ned i en samling uppgifter som boten kan utföra. Spelprototypen mäter körtiden för att bestämma ett enskilt beteende i en specifik situation. Resultaten från mätningarna tyder på att beteendeträd har bättre tidseffektivitet än Hierarchical Task Network.

Arbetet undersöker mänskligt beteende hos beteendeträd och LSTM nätverk. Ett spel skapades som testades av personer i en undersökning där deltagarna fick spela tillsammans med vardera agent i slumpmässig ordning för att bedöma agenternas beteende. Resultatet från undersökningen visade att beteendeträdet var den mänskliga varianten enligt deltagarna oavsett ordning som testpersonerna spelade med vardera agent. Problemet med resultatet beror antagligen till störst del på att det inte fanns tillräckligt med tid och bristande CPU kraft för att utveckla LSTM agenten ytterligare. För att förbättra och arbeta vidare med arbetet kan mer tid läggas på att träna LSTM nätverket och finjustera beteendeträdet. För att förbättra testet borde riktig multiplayer funktionalitet implementeras som gör att det går att testa agenterna jämfört med riktiga mänskliga spelare.

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.

One of the main purposes of the fields of Robotics and Artificial Intelligence is to develop solutions that can autonomously solve problems. An important part of this is synthesising behaviours of robots. Behaviour Trees are a tree structure that enables combining existing lower level behaviours into a high level behaviour through task switching. However, designing appropriate Behaviour Trees can be prohibitive due to time and knowledge requirements. One way of automating the creation of Behaviour Trees is through Genetic Programming, which evolves solutions through mutations and combinations akin to biological evolution. This Masters thesis explores how Genetic Programming can be used to generate Behaviour Trees in an automatic fashion. More specifically, whether so-called Quality Diversity can be used to improve the search. Quality Diversity describes a field of algorithms that combine both performance and novelty of behaviour to evaluate solutions. By including a novelty aspect the search space is more thoroughly explored, and deceptive local optima may be more easily avoided. In this thesis three Quality Diversity algorithms are implemented and evaluated in different settings: Novelty Search, Novelty Search with Local Competition, and Multi-dimensional Archive of Phenotypic Elites. The results show that Quality Diversity has potential to both increase the speed at which solutions are found and decrease the likelihood of premature convergence due to local optima. However, we also find that care must be taken in how behaviours are defined, and how some common techniques of Genetic Programming need to be adapted for Quality Diversity algorithms. / Ett av huvudsyftena med robotik och artificiell intelligens är att skapa system som självständigt kan lösa problem. En viktig del av detta är att skapa robotars beteenden. Beteendeträd är en trädstruktur som gör det möjligt att kombinera befintliga beteenden på lägre nivå till ett beteende på hög nivå. Att utforma lämpliga beteendeträd kan dock kräva både mycket tid och kunskap. Ett sätt att automatisera skapandet av beteendeträd är genom genetisk programmering, som utvecklar lösningar genom mutationer och kombinationer i likhet med biologisk evolution. Detta examensarbete undersöker hur genetisk programmering kan användas för att automatiskt generera beteendeträd. Mer specifikt undersöks om kvalitetsmångfald (Quality Diversity) kan användas för att förbättra sökningen. Kvalitetsmångfald beskriver en familj av algoritmer som kombinerar både prestanda och innovation i en lösnings beteende för att utvärdera lösningar. Genom att inkludera en innovationsaspekt blir sökområdet mer noggrant utforskat och vilseledande lokala optima kan lättare undvikas. I detta examensarbete implementeras och utvärderas tre kvalitetsmångfaldsalgoritmer i olika miljöer: Novelty Search, Novelty Search with Local Competition, och Multi-dimensional Archive of Phenotypic Elites. Resultaten visar att kvalitetsmångfald har potential att både öka hastigheten med vilken lösningar hittas och minska sannolikheten för tidig konvergens på grund av lokala optima. Vi konstaterar dock också att man måste vara försiktig med hur beteenden definieras och hur vissa vanliga tekniker för genetisk programmering måste anpassas för algoritmer med kvalitetsmångfald. / Eén van de belangrijkste doelstellingen van het vakgebied Robotica en Kunstmatige Intelligentie is het ontwikkelen van oplossingen die autonoom problemen kunnen oplossen. Een belangrijk onderdeel hiervan is het synthetiseren van gedragingen van robots. Gedragsbomen zijn een boomstructuur waarmee bestaande gedragingen van een lager niveau kunnen worden gecombineerd tot een gedrag van een hoger niveau door middel van taakwisseling. Het ontwerpen van geschikte gedragsbomen is echter soms niet haalbaar haalbaar vanwege de benodigde tijd en kennis. Een manier om het maken van gedragsbomen te automatiseren is door middel van genetisch programmeren, dat oplossingen ontwikkelt door mutaties en combinaties, vergelijkbaar met biologische evolutie. Deze masterproef onderzoekt hoe genetische programmering kan worden gebruikt om automatisch gedragsbomen te genereren. Meer specifiek of kwaliteitsdiversiteit (Quality Diversity) kan worden gebruikt om het zoeken te verbeteren. Kwaliteitsdiversiteit beschrijft een gebied van algoritmen die zowel prestaties als nieuwheid van een oplossingsgedrag combineren om oplossingen te evalueren. Door een nieuwheidsaspect te introduceren wordt de zoekruimte grondiger verkend en kunnen bedrieglijke lokale optima gemakkelijker worden vermeden. In deze masterproef worden drie algoritmen voor kwaliteitsdiversiteit toegepast en geëvalueerd in verschillende omgevingen: Novelty Search, Novelty Search with Local Competition en Multi-dimensional Archive of Phenotypic Elites. De resultaten tonen aan dat kwaliteitsdiversiteit het potentieel heeft om zowel de snelheid waarmee oplossingen worden gevonden te verhogen als de kans op voortijdige convergentie als gevolg van lokale optima te verminderen. Wij stellen echter ook vast dat zorgvuldigheid geboden is bij de definitie van gedragingen en dat sommige gebruikelijke technieken van genetisch programmeren moeten worden aangepast voor algoritmen met kwaliteitsdiversiteit.

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.

This thesis investigates the performance of the option critic (OC) framework combined with behaviour trees (BTs) in Starcraft 2 mini-games when training time is constrained by a time frame limited by consumer level hardware. We test two such combination models: BTs as macro actions (OCBT) and BTs as options (OCBToptions) and measure the relative performance to the plain OC model through an ablation study. The tests were conducted in two of the mini-games called build marines (BM) and defeat zerglings and banelings (DZAB) and a set of metrics were collected, including game score. We find that BTs improve the performance in the BM mini-game using both OCBT and OCBToptions, but in DZAB the models performed equally. Additionally, results indicate that the improvement in BM scores does not stem solely from the complexity of the BTs but from the OC model learning to use the BTs effectively and learning beneficial options in relation to the BT options. Thus, it is concluded that BTs can improve performance when training time is limited by consumer level hardware. / Denna avhandling undersöker hur kombinationen av option critic (OC) ramverket och beteendeträd (BT) förbättrar resultatet i Starcraft 2 minispel när träningstiden är begränsad av konsumenthårdvara. Vi testar två kombinationsmodeller: BT som makrohandlingar (OCBT) och BT som options (OCBToptions) och mäter den relativa förbättringen jämte OC modellen med en ablationsstudie. Testen utfördes i två minispel build marines (BM) och defeat zerglings and banelings (DZAB) och olika typer av data insamlades, bland annat spelpoängen. Vi fann att BT förbättrade resultatet i BM på båda hierarkiska nivåerna men i DZAB var resultaten ungefär lika mellan de olika modellerna. Resultaten indikerar också att förbättringen i BM inte beror bara på BT komplexitet utan på att OC modellen lär sig att använda BT och lär sig options som kompletterar dess BT options. Vi finner därför att BT kan förbättra resultaten när träningen är begränsad av konsumenthårdvara.

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.

The use of unmanned aerial vehicles (UAVs) is well established in the military sector with great advantages in modern warfare. The concept of using UAV swarms has been discussed over two decades, but is now seeing its first real system used by the Israel defence forces. There is no exact definition what a swarm is, but it is proposed that it should satisfy the following three requirements. A swarm should have limited human control, the number of agents in a swarm should be at least three and the agents in the swarm should cooperate to perform common tasks. The complexity of controlling multiple autonomous UAVs gives way to the problem of how to take advantage of the operators cognitive and tactical abilities to control a swarm to effectively conduct military reconnaissance missions. The method of using behaviour trees as a control structure was derived from previous work in swarm systems. A behaviour tree is a structured way of organising and prioritising actions of autonomous systems. Behaviour trees are similar to finite state machines (FSMs) with the advantages of being modular, reactive, and with better readability. Three different behaviour trees with increasing complexity was created and simulated in the game engine Unity. A fourth more real life behaviour tree was created and used as a basis for discussing the strength and weaknesses of using behaviour trees against previous work. Using behaviour tree as a unifying structure for creating a swarm that integrates the tactical abilities of an operator with the strength of an autonomous swarm seems promising. The proposed method of using behaviour trees i suggested to be used as a platform for discussing the swarm desired functions and to create a common vision for both operators and engineers how a swarm should function. / Användning av drönare är väletablerad inom det militära och ger stora fördelar i dagens moderna krigsföring. Idén om att använda en svärm av drönare har diskuterats under de senaste två decennierna, men först nu sett sin första riktiga system som använts av Israels försvarsmakt. Det finns ingen exakt definition av vad en svärm är, men det har föreslagits att en svärm ska uppfylla de följande tre kraven. En svärm ska ha begränsad mänsklig interaktion, antalet agenter ska vara minst tre och svärmen ska samarbeta för att lösa gemensamma uppgifter. Svårigheterna med att styra en autonom svärm ger upphov till hur man ska utnyttja en operatörs kognitiva och taktiska förmåga för att styra en autonom drönarsvärm för att effektivt utföra militära spaningsuppdrag. Utifrån tidigare arbete inom styrning av svärmar verkade beteende träd som en lovande metod. Beteendeträd är ett strukturerat sätt att organisera och prioritera beteenden för ett autonomt system. Beteendeträd har många likheter med ändliga tillståndsmaskiner, men fördelarna att vara modulära, responsiva och mer lättläsliga. Tre olika beteendeträd med ökande komplexitet skapades och deras funktionalitet simulerades i Unity. Ett fjärde mer verklighetstroget beteendeträd skapades och användes som underlag för att diskutera beteendeträds styrkor och svagheter i jämförelse med tidigare arbeten. Användningen av beteendeträd för att förena den mänskliga operatören med det autonoma systemet verkar lovande. Den föreslagna metoden att använda beteendeträd för att styra en svärm är tänkt att användas som ett gemensamt underlag för att möjliggöra att operatörer och ingenjörer kan ha en gemensam bild hur en svärm ska fungera.