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.

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.

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 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.

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.

This thesis investigates combining learning action nodes in behavior trees with control barrier functions based on the extended active constraint conditions of the nodes and whether the approach improves the performance, in terms of training time and policy quality, compared to a purely learning-based approach. Behavior trees combine several behaviors, called action nodes, into one behavior by switching between them based on the current state. Those behaviors can be hand-coded or learned in so-called learning action nodes. In these nodes, the behavior is a reinforcement learning agent. Behavior trees can be constructed in a process called backward chaining. In order to ensure the success of a backward-chained behavior tree, each action node must uphold previously achieved subgoals. So-called extended active constraint conditions formalize this notion as conditions that must stay true for the action node to continue execution. In order to incentivize upholding extended active constraint conditions in learning action nodes, a negative reward can be given to the agent upon violating extended active constraint conditions. However, this approach does not guarantee not violating the extended active constraint conditions since it is purely learning-based. Control barrier functions can be used to restrict the actions available to an agent so that it stays within a safe subset of the state space. By defining the safe subset of the state space as the set in which the extended active constraint conditions are satisfied, control barrier functions can be employed to, ideally, guarantee that the extended active constraint conditions will not be violated. The results show that significantly less training is needed to get comparable, or slightly better, results, when compared to not using control barrier functions. Furthermore, extended active constraint conditions are considerably less frequently violated and the overall performance is slightly improved. / Denna avhandling undersöker kombinationen av inlärningsregulatornoder i beteendeträd med styrbarriärfunktioner baserade på utökade aktiva begränsningsvillkor för noderna, samt om detta tillvägagångssätt förbättrar prestandan avseende tränings- och policynkvalitet, jämfört med ett rent inlärningsbaserat tillvägagångssätt. Beteendeträd kombinerar flera regulatorer, kallade regulatornoder, till en enda regulator genom att växla mellan dem baserat på det aktuella tillståndet. Dessa regulatorer kan vara handkodade eller inlärda i så kallade inlärningsnoder. I dessa noder är regulatorn en förstärkningsinlärningsagent. Beteendeträd kan konstrueras genom en process som kallas bakåtkoppling. För att säkerställa framgången för ett bakåtkopplat beteendeträd måste varje regulatornod upprätthålla tidigare uppnådda delmål. Utökade aktiva begränsningsvillkor formaliserar denna uppfattning som villkor som inte får överträdas för att regulatornoden ska fortsätta exekvera. För att uppmuntra till att upprätthålla utökade aktiva begränsningsvillkor i inlärningsnoder kan en negativ belöning ges till agenten vid överträdelse av utökade aktiva begränsningsvillkor. Denna metod garanterar dock inte att utökade aktiva begränsningsvillkor inte kommer att överträdas, eftersom den är helt inlärningsbaserad. Kontrollbarriärfunktioner kan användas för att begränsa de åtgärder som är tillgängliga för en agent så att den förblir inom en säker delmängd av tillståndsrymden. Genom att definiera den säkra delmängden av tillståndsrymden som den uppsättning där de utökade aktiva begränsningsvillkoren uppfylls kan kontrollbarriärfunktioner användas för att, i bästa fall, garantera att de utökade aktiva begränsningsvillkoren inte kommer att överträdas. Resultaten visar att det krävs betydligt mindre träning för att få jämförbara, eller något bättre, resultat jämfört med att inte använda kontrollbarriärfunktioner. Dessutom överträds utökade aktiva begränsningsvillkor betydligt mer sällan och den övergripande prestandan är något förbättrad. I would like to thank Katrina Liang and Petter Ögren for translating the to Swedish. / Diese Arbeit untersucht die Kombination von Lernaktionsknoten in Verhaltensbäumen mit Kontrollbarrierefunktionen, die auf den erweiterten aktiven Einschränkungsbedingungen und Vorbedingungen der Knoten basieren, und ob dieser Ansatz die Leistung hinsichtlich Trainingszeit und Qualität der erlernten Strategie im Vergleich zu einem rein lernbasierten Ansatz verbessert. Verhaltensbäume kombinieren mehrere Regler, die als Aktionsknoten bezeichnet werden, zu einem zusammengesetzten Regler, indem sie abhängig vom aktuellem Zustand zwischen ihnen wechseln. Diese Regler können entweder manuell programmiert oder in sogenannten lernenden Aktionsknoten erlernt werden. In diesen Knoten ist der Regler ein Reinforcement Learning Agent. Verhaltensbäume können in einem Prozess namens Rückwärtsverkettung erstellt werden. Um den Erfolg eines rückwärtsverketteten Verhaltensbaums sicherzustellen, muss jeder Aktionsknoten zuvor erreichte Teilerfolge aufrechterhalten. Sogenannte erweiterte aktive Einschränkungsbedingungen formalisieren diesen Gedanken als Bedingungen, die nicht verletzt werden dürfen, damit der Aktionsknoten die Ausführung fortsetzen kann. Um einen Anreiz für die Aufrechterhaltung erweiterter aktiver Einschränkungsbedingungen in Lernaktionsknoten zu schaffen, kann dem Agenten bei Verstoß gegen erweiterte aktive Einschränkungsbedingungen eine negative Belohnung gewährt werden. Diese Herangehensweise garantiert jedoch nicht die Einhaltung der erweiterten aktiven Einschränkungsbedingungen, da sie rein lernbasiert ist. Kontrollbarrierefunktionen können verwendet werden, um die verfügbaren Aktionen eines Agenten zu beschränken, damit dieser in einer sicheren Teilmenge des Zustandsraums bleibt. Indem die sichere Teilmenge des Zustandsraums als die Menge definiert wird, in der die erweiterten aktiven Einschränkungsbedingungen erfüllt sind, können Kontrollbarrierefunktionen idealerweise verwendet werden, um sicherzustellen, dass die erweiterten aktiven Einschränkungsbedingungen nicht verletzt werden. Die Ergebnisse zeigen, dass im Vergleich zur Nichtverwendung von Kontrollbarrierefunktionen deutlich weniger Training erforderlich ist, um vergleichbare oder etwas bessere Ergebnisse zu erzielen. Darüber hinaus werden erweiterte aktive Einschränkungsbedingungen deutlich seltener verletzt und die Gesamtleistung wird leicht verbessert.