Using Quality Diversity in Genetic Programming to Improve Automatic Learning of Behaviour Trees

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