Extending Behavior Trees with Classical Planning

Student thesis: Master thesis (including HD thesis)

  • Søren Larsen
  • Jonas Øgendahl Groth
2. term, Computer Science, Master (Master Programme)
We investigate the area of behavior trees and planning in video game AI. The syntax and semantics of behavior trees and the concept of classical planning is described along with the theory behind the widely used search algorithm A*. A comparison of scripting and behavior trees is performed to identify the advantages of behavior trees. The advantages are used to validate that our extension of behavior trees does not violate them. We describe an extension of behavior trees with classical planning including a method for using states with the otherwise stateless behavior tree formalism. An implementation of the A* search algorithm for finding a sequence of behavior trees that will change the state of the world to some predefined goal state is also proposed. We test the approach with good results including the fact that the advantages of behavior trees are maintained as intended.
Publication date9 Jun 2011
Number of pages72
ID: 52867037