# Learning Behavior Trees for Autonomous Agents with Hybrid Constraints Evolution
## 2 Background and Related Works
### Agent Behavior Modeling and Evolving Behavior Trees  
In computer games and simulation, a variety of agent programming techniques have been employed to represent and embed agent behaviors, especially for decision-making process. Those techniques usually encode agent behaviors in well-defined structures/models based on domain expertise and customizable constrains, such as FSMs, hierarchical finite state machines (HFSMs), rule-based systems and BTs etc. [2; 3]. Among which, BTs have come to the forefront recently for their modularity, scalability, reusability and accessibility [8; 9; 10]. However, most of the developments based on those scripting approaches rely on domain expertise and suffer from time-consuming, expensive and difficult endeavor of programming complexity [2; 4; 19]. On the other side of the spectrum, various approaches are emerged in machine learning community to generate adaptive agent behavior automatically [5; 20; 21; 22]. This field has been studied basically from two perspectives [1; 2]: learning from observation (LfO) (a.k.a, learning from demonstration, programming from demonstration) and learning from experience. The former allows agent to extract the behavior model of the target agent by observing the behavior trace of another agent (e.g., using NN and case-based learning) [4; 20]. For example, [PERSON] et al. [20] adopted LfO to build agents capable of driving a simulated automobile in a city environment. [PERSON] et al. [23] use learning from demonstration for realtime strategy games in the context of case-based planning. While the later leads virtual agent to learn and optimize its behavior by interacting with environment repeatedly (e.g., reinforcement learning and evolutionary algorithms) [5; 22]. The performance of the agent is measured according to how well the task is performed as expert's evaluation criterions, which may sometimes find creative solutions that are not found by humans termed as computational creativity [4]. For instance, [PERSON] and [PERSON] [24], propose Reinforcement learning (RL) to compensate for situations where the domain expert has limited knowledge of the subject being modeled. [PERSON] et al. [22] use a self-organizing neural network to learn incrementally through real-time interactions with the environment, which can improve air combat maneuvering strategies of CGFs. Please note that most of those machine learning methods generate behavior model as a black box system [6; 7]. As a result, domain expert could not produce a clear explanation of the relationship between behaviors and models, which is hard to analyze and validate. To remedy the disadvantages, in both behavior learning perspectives, there are some attempts to generate behavior models represented as BTs from observation [7; 25] or experience [11; 12; 14; 26; 27] automatically. In this paper, we are focusing on generate BTs through experiential learning, especially evolving BTs. Please note that comparing with other policy representation approaches (decision tree etc. ), BT is a more flexible representation which allows explicitly a course of actions as a sub-policy for certain situation. Therefore, for evolving BTs, the scalability is still an open problem stemming from the random large space search [12; 14]. In [12], the author points out it is too flexible for evolving BTs without structural guidelines, which would result in most trees that are quite inefficient and impossible to read. So the author constrains the crossover with fixed 'behavior block' sub-trees, which yield comparable reactive behavior. In [14], the authors investigate the effect of'standard BT design' constraint on evolving BTs approach, which is domain-independent and efficient. They also point out most existing evolving BT approaches adopt different manual constraints to design what the BTs represent and the nature of the tree's constraints. Some of those approaches can speed up learning efficiently but need a lot of knowledge engineering works, which may limit the application of evolving BT approaches.