Master thesis proposal

Avoiding local minima with Genetic Programming of Behavior Trees

Background

Today, industrial robots can solve very complex tasks in controlled environments, but modern industrial applications in workspaces shared with humans, require robots able to operate in unpredictable surroundings as well. One common way to deal with this is to control the robot with a reactive policy such as Behavior Trees (BTs). Also, with increased variation and smaller production batches, the time needed for programming, system integration, validation and verification is prohibitively long. It is therefore desirable that new robot policies or programs can be created automatically.

There are two main branches of algorithms to generate policies automatically, both with their own drawbacks. The first branch, automated planners, can be very efficient but is limited by the amount of knowledge that has been given to the planner in advance, as planners typically do not interact with the environment. The second branch, machine learning algorithms, often do interact with the environment and is thus not limited by a static set of knowledge. A drawback is that many of the most efficient machine learning algorithms, often based on Reinforcement Learning, are adapted to neural networks that have several important disadvantages compared to BTs, as neural networks are not particularly transparent nor as modular.

Problem description

The most popular machine learning algorithm for learning Behavior Tree structures is Genetic Programming. The main drawback is that it’s slow compared to the state of the art Deep Reinforcement Learning techniques. One of the major reasons for that is that Genetic Programming, like other algorithms, has a tendency to get stuck in local minima. There exists a number of mitigation methods, all with their own advantages and disadvantages. However, these mitigation methods have not been studied for the particular problems of learning Behavior Trees for robotic tasks.

Project proposal

• Perform a literature study of current methods to avoid local minima for Genetic programming.
• If possible, come up with novel ideas.
• Test and compare the different methods empirically on a number of benchmark applications.

Research questions

• What are the currently available methods for avoiding local minima for Genetic Programming?
• What are the advantages and disadvantages of the different methods?
• How do the different methods compare on a number of different tasks of learning Behavior Trees for robotic manipulation.

Expected outcome

• A comprehensive literature study on local minima avoidance for Genetic Programming, listing claimed advantages and disadvantages
• Implementation and empirical comparison of different methods for avoiding local minima.

Details

• Supervisor: Jonathan Styrud ()
• Period: fall semester 2021
• Place of thesis: division of Robotics, Perception, and Learning (RPL), Teknikringen 14. Depending on the pandemic situation, most of the thesis may be performed from home.

Requirements

• Enthusiasm, passion, and good spirit
• Experience with programming in Python
• Basic knowledge of automated programming, machine learning and optimization
• Demonstrated ability with technical and scientific writing