# Learning Behavior Trees for Autonomous Agents with Hybrid Constraints Evolution
## 3 Methodology
### Dynamic Constrain Based on Frequent Sub-Tree Mining
#### 3.2.1 Frequent Sub-Tree Mining  
In this section, an adaptation of FREQT [28] is used to mine frequent sub-tree structures in population. FREQT is a classic pattern mining algorithm to discover frequent tree patterns from a collection of labeled ordered trees (LOT). It adopts _rightmost expansion_ technique to construct candidate frequent patterns incrementally. At the same time, frequencies of the candidates are computed by maintaining only the occurrences of the rightmost leaf efficiently. It has been demonstrated that FREQT can scale almost linearly in the total size of maximal tree patterns slightly depending on the size of the longest pattern [28; 29].  
A labeled ordered tree usually represents a semi-structured data structure such as XML. According to the structure and semantics, a behavior tree is a typical labeled ordered tree. Thus the formalism of BT can be expanded from definition of LOT as \(BT_{LOT}=<V,E,\tau,L,\preceq>\), where \(BT=<V,E,\tau>\) is the basic structure of a BT, \(\tau\in V\) is the root node. The mapping \(L:V\rightarrow\iota\) is the labeling function, \(\iota\) includes the labels of root node, control nodes and leaf nodes (condition nodes and action nodes) of a BT. The binary relation \(\preceq\subseteq V\times V\) represents a sibling relation for two nodes in a BT. For two nodes \(\mu\) and \(\upsilon\) of the same parent, iff \(\mu\preceq\upsilon\) then \(\mu\) is an elder brother of \(\upsilon\). The execution of BT is following order of depth first from left to right, \(\preceq\) represents execution orders of two nodes. Thus, we can construct indexes for all the nodes as depth first in an LOT, which can be consistent with records in GP.  
Let \(T_{D}=\{T_{1},T_{2},...,T_{n}\}\) be the dataset of tree mining, which includes a small fraction of individuals with higher fitness in current population. \(T_{p}\) is a candidate frequent pattern, which is usually a sub-tree in tree mining. \(\delta_{T}(T_{p})\) is the frequency of \(T_{p}\) in a tree \(T\), \(d_{T}(T_{p})\) depicts whether \(T_{p}\) exists in \(T\). There is \(d_{T}(T_{p})=1\) if \(\delta_{T}(T_{p})>0\), else \(d_{T}(T_{p})=0\). \(\sigma(T_{p})=\sum_{T\in T_{D}}d_{T}(T_{p})\) represents the number of trees where frequent pattern sub-tree \(T_{p}\) exists. \(n_{t}(T_{p})\) depicts terminal node size of frequent pattern tree \(T_{p}\) in tree \(T\).  
To adapt the notions from FREQT to BTs mining in GP system, we modify the rules to judge whether a sub-tree is frequent. According to BT syntax and its design pattern, a tree \(T_{p}\) can be regarded as a frequent pattern iff it satisfies all the following proposed rules.  
1. \(\sigma(T_{p})/|T_{D}|>\sigma_{min}\) and \(N_{T_{pmin}}<|T_{p}|<N_{T_{pmax}}\), where \(\sigma_{min}\) depicts the minimal support of a frequent pattern, \(N_{T_{pmin}}\) depicts the minimal node size of a frequent pattern and \(N_{T_{pmax}}\) depicts the maximal node size of a frequent pattern.
2. All terminal nodes in a frequent pattern \(|T_{p}|\) must be leaf nodes (condition nodes or action nodes).
3. \(n_{t}(T_{p})>N_{T_{pmin}}\), where \(N_{T_{pmin}}\) depicts the minimal terminal node size of a frequent pattern.  
Rule 1 is the basic requirement of FREQT data mining algorithms. Rule 2 and rule 3 represent proposed form requirements of expected patterns in behavior modeling with BT. As a decision making tool, the core of a BT is rooted in the logic relation among its leaf nodes. Thus, in rule 2, we believe if a terminal node is a control node, it is meaningless for its located branch. For rule 3, if a frequent pattern has too few terminal nodes (for example only one terminal node), it shows trivial effect on the whole tree construction.