Starting Out / Idea

I have a thesis idea which both an examiner as well as a supervisor at KTH have agreed to oversee. Officially, the thesis work has not started. The starting phase will be in "period 4", which earliest is on March 16. Most likely, my idea will be okay so I may as well start with the work now, rather than waiting for an official notice. The basis for the thesis idea will likely remain unchanged, altough the direction may go towards some specific area.

Title: Adapting Behavior Trees using NEAT

Description:

Behavior trees are used a lot in the video games industry for creating AIs. A BT consist of nodes, also known as leaves. The leaves contain code that execute arbitrary actions. In a BT all leaves are executed orderly, unless certain conditions make some be skipped. It can go fast for developers to create trivial BTs manually. Only utilizing manual tweaking sets limitations to AIs. The reason is that it’s impossible to hard-code actions to handle all possible events that can occur in most games. Recently, attempts have been made to mix the process of hard-coding BTs with machine learning. This is done as a compromise between hard-coding and handling as many different events as possible. In this thesis I want to use a genetic algorithm called NEAT with pre-defined leaves to automatically generate advanced BTs. How well the final solution solves a set of problems will be measured, along with other performance tests. By gathering data, it becomes possible to compare the prototype solution made for my thesis with other AIs and find out whether there are pragmatic reasons for favoring the use of NEAT when making BTs.

Connection to existing research/development:

The research is interesting to people that create AIs for video games. In games you do not always want the AI to perform so well that no human can win. On the other side you do not want an AI that is too bad either. I believe that answering the research question may help provide a tool that can make it easier to quickly prototype AIs for games. Other people, as seen in some research papers, have for the most part created highly specialized solutions when combining BTs with genetic algorithms or machine learning. They leave some questions unanswered in favor of potential future work. The full capabilities of using a NEAT therefore remains unknown. Existing research has shown that genetic algorithms can be used for creating an AI for certain types of games, such as RTS games. However, in the RTS game mentioned the agent was given complete information about the world. Allowing an agent to have full information is in many ways like cheating, and something that should be avoided if possible. On the plus side though, by having complete information it can be easier to filter out redundant information in order to deal with the curse of dimensionality.

Resources:

I have previous code for a NEAT (https://github.com/marcus1337/NEAT) that I can continue to work on. There seems to exist free and open source solutions for BTs on the internet.

I also got myself the book "Behavior Trees in Robotics and AI" by Michele Colledanchise and Petter Ögren. The book brings up different topics related to particularly BTs, but also machine learning. It would have been useful if the book had more pages, but by having it being short it makes it more likely that I will actually read all of it. The book have many visalizations and images (in color) that makes it easier to understand the topics than if it only had contained raw text.

Current Progress:

There were some apparent bugs in my existing NEAT code so I have spent the last few days fixing those and also refactored the code a lot. The code obviously use heap memory way more than what's necessary. What I will work on in the coming days is to make even more refactoring to the code in order to reduce calls to "new" and "delete" in C++. Not that I do that manually, but the STL data-structures does. A funny solution that I have implemented to mitigate this so far is that I have tried switching out the standard memory allocator to a better one called minimalloc (https://github.com/microsoft/mimalloc).

The goal of my NEAT code is to train neural networks. I tested the speed of training 50 neural networks 10 times by measuring the time in milliseconds with std::chrono. From the tests one can see improvements when the code is run in release mode before, and after minimalloc is used below;

[1] [2] [1] [2] 840 739 585 551 799 714 538 665 1009 745 615 819 1740 1195 768 973 3557 2240 1369 1325 8942 4614 1983 2240 23994 11048 1273 4947 <stop> 38007 2342 5246 <stop> <stop> 10940 13440

Here the columns 1,2 means test run 1 & 2. Each row is one function call consisting of 50*10 mutations as well as 50*10 quick random fitness-value assignments to the NEATs. Judging from these tests, minimalloc increase the speed of the current code-base more than 100%. As mentioned before, the code can still be optimized further, which is something that I am working on. Using the double-buffer pattern for creating new generations seemed to improve the speed a little bit. Hopefully, implementing two large arrays that are allocated only once will help even more. This is primarily because arrays improve cache-locality.