Evolving Behavior Trees

Summary

In this project, we are building a mixed-initiative tool and library for game AI designers in Unreal Engine 4. Working with designer-driven initial trees and objectives, the library evolves and suggests new options for game agents.

Research Topics

Agent AI | Behavior Trees | Genetic Programming | Mixed-Initiative Content Creation | PCG

Contributors

Alex Grundwerg | Isha Srivastava | Magy Seif El-Nasr

Description

We are developing a library and mixed-initiative (AI and human collaboration) tool for game AI design in Unreal Engine 4. Starting with a hand-designed behavior tree, we evolve a set of new behavior trees that maximize a designer-defined set of objectives. By repeating this process over multiple generations and presenting the best resulting behavior trees to designers, the tool can find and suggest creative and novel behavior. In this way, we hope to spark designer creativity and broaden the capabilities of their AI agents in unforeseen situations.

Behavior trees are an expressive and widely-used architecture for specifying game agent behavior (Isla 2005). They represent decision-making in a tree structure, with internal nodes ("composites" and "decorators") controlling the flow of decision-making and leaf nodes ("tasks") representing the actions required to execute the desired behavior. This tree can be thought of as a sort of "program" for the agent to follow.

Genetic programming, a form of evolutionary algorithm, is a technique for evolving programs, specified as trees, to maximize a specific objective (Koza 1989). It has usually been applied to "parse trees" for simple programming languages, but it is very naturally applicable to behavior trees. Some prior work has applied genetic algorithms to behavior in specific, simple games such as Mario (Perez et. al. 2011) and DEFCON (Lim et. al. 2010). By building a generic library for applying genetic programming to the built-in behavior trees in Unreal Engine 4, we can explore the general applicability of this technique. Because Unreal Engine 4 is popular for modern game development, we can also iterate on mixed-initiative tools to make the library more accessible and applicable for real game designers.

We tested the first version of the tool on an open-source third-person shooter, "Epic Survival Game," by Tom Looman. We intentionally disabled the zombie AI in the game, preventing them from effectively patrolling the map, chasing, and attacking the player. Over a few generations, however, the evolved behavior trees regained these capabilities, quickly providing effective zombies that could be selected and further tweaked by a human designer.

Status

In Progress

References

Isla, Damian. 2005. “Handling Complexity in the Halo 2 AI.” In Game Developers Conference. Vol. 2005.
Koza, John R. 1989. “Hierarchical Genetic Algorithms Operating on Populations of Computer Programs.” In Proceedings of the 11th International Joint Conference on Artificial Intelligence - Volume 1, 768–774. IJCAI’89. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. http://dl.acm.org/citation.cfm?id=1623755.1623877.
Lim, Chong-U, Robin Baumgarten, and Simon Colton. 2010. “Evolving Behaviour Trees for the Commercial Game DEFCON.” In , 6024:100–110. Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-12239-2_11.
Perez, Diego, Miguel Nicolau, Michael O’Neill, and Anthony Brabazon. 2011. “Evolving Behaviour Trees for the Mario AI Competition Using Grammatical Evolution.” In , 6624:123–32. Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-20525-5_13.

Publications

None... yet!