Evolutionary Behavior Trees for Multi-Agent Task-Oriented Environment

Title Evolutionary Behavior Trees for Multi-Agent Task-Oriented Environment
Summary Evolutionary generating Behavior Trees for use in multi-agent task-oriented environment.
TimeFrame Spring 2015
References http://frail.ii.pwr.edu.pl/
Prerequisites Artificial Intelligence and Learning Systems courses
Author Milosz Mazur
Supervisor Slawomir Nowaczyk
Level Master
Status Finished

Behavior Trees are a system for AI programming that consists of a tree of hierarchical nodes controlling the flow of agent's decision making. At the leaves of the tree are actions - usually the actual commands for the agent to execute. They have proven, while being a pretty straightforward means to implement an AI, to be incredibly powerful way of obtaining autonomous agents, both due to a fact that the development can be iterable (one can start with implementing simple behavior and gradually improve the tree by adding and modifying nodes and branches) and allowing for, so to say, “fallback tactics”, should the currently executed action fail. Born in the game industry, they have since gained fair amount of popularity in other domains, including robotics.

Evolutionary algorithms, developed in John Holland’s Adaptation in Natural and Artificial Systems (1975), have been adapted for use in a vast variety of different problems, including optimisation issues and decision handling.

This project is an attempt to combine the two subjects, resulting in a way to automatically produce well-performing behavior trees, ready to use when autonomy and certain performance level consistency is required.

The environment chosen for handling the simulations is FRAIL, an in-house project of Wroclaw’s University of Technology. Developed to ease the process of AI testing for designers and game developers, it has since been adapted for the purpose of genetic calculations.

Research Questions: 1. What fitness evaluation method is best suited to dealing with behavioral trees? 2. How to deal with bad (botched) trees, that are not going to produce an action every time they are evaluated? 3. Will making Genetic Programming (Koza, 1992) operators content - aware while performing their operations produce better results? 4. What’s a good way to deal with the impact of the initial generation?