# Learning Behavior Trees for Autonomous Agents with Hybrid Constraints Evolution
## 3 Methodology
### Dynamic Constrain Based on Frequent Sub-Tree Mining
#### 3.2.2 Nodes Crossover Probability Adjustment  
After finding the frequent sub-trees collection, the crossover probability of each node is adjusted according to its relation to discovered frequent sub-trees, which can protect those preponderant structures to be inherited to the next generation more likely.  
Formally, let \(T_{D_{i}}\) depict the set of the selected superior individuals of BTs population at generation \(i\), \(T\) is a chromosome tree selected for crossover in \(T_{D_{i}}\), \(V(T)\) is the set of all the tree nodes in \(T\) except the root node \(\tau\). Let \(T_{Df}\) depict the set of the mined frequent sub-trees in \(T_{D_{i}}\), \(T_{p}\) is a frequent sub-tree in \(T_{Df}\), \(V_{p}(T)\) is the set of all the tree nodes in \(T_{p}\), where we define \(V_{p}^{\prime}(T)\) as the root node of \(T_{p}\), \(V_{p}^{in}(T)=V_{p}(T)\setminus V_{p}^{\prime}(T)\) as the set of nodes in \(T_{p}\).  
Provided we find \(N\) distinct frequent sub-trees \(T_{p}^{k}\) in \(T\), \(k=1,2,...,N\), \(T_{p}^{k}\in T_{Df}\). Then for the tree \(T\), we define the root node set \(V^{r}(T)=\bigcup_{k=1}^{N}V_{p,k}^{r}(T)\), the inside node set \(V^{in}(T)=\bigcup_{k=1}^{N}V_{p,k}^{in}(T)\), and the other node set \(V^{neu}(T)=V(T)\setminus(V^{r}(T)\cup V^{in}(T))\). To protect the frequent sub-trees unbroken more likely in crossover, we can classify \(V(T)\) to two sets, protected nodes set \(V_{pro}(T)\) and unprotected nodes set \(V_{unpro}(T)\). That is, \(V_{pro}(T)=V^{in}(T)\), which stores nodes needing to be protected in \(T\), and \(V_{unpro}(T)=V^{r}(T)\cup V^{neu}(T)\), which stores nodes to be unprotected in \(T\).  
Obviously, to protect preponderant sub-trees inherited to the next generation, we should decrease the select probability of nodes in \(V_{pro}(T)\) and increase the select probability of nodes in \(V_{unpro}(T)\) as crossover point. We consider the fact that standard sub-tree crossover operation produce two child trees, as illustrated in Figure 3.  
As we can see in the leftup parent tree, except the root node, its nodes are classified to unprotected nodes and protected nodes enclosed with two dashed curves respectively. The mined frequent sub-tree is enclosed with a non-dashed curve including all the protected nodes and the root node of the frequent sub-tree. Let us denote the select probability as a crossover point at a node \(v\) by \(p_{cross}(v)\). The GP system picks up two individuals (e.g., by a tournament selection) from the population, and performs a crossover operation at a node \(v\) with the probability \(p_{cross}(v)\), which has been modified and normalized as follows:  
\[p_{cross}(v)=\frac{\gamma}{|V_{pro}(T)|+|V_{unpro}(T)|}\quad v\in V_{pro}(T) \tag{1}\]  
\[p_{cross}(v)=\frac{1}{|V_{pro}(T)|+|V_{unpro}(T)|}+\frac{\frac{1-\gamma}{|V_{ pro}(T)|+|V_{unpro}(T)|}*|V_{pro}(T)|}{|V_{unpro}(T)|}\quad v\in V_{unpro}(T) \tag{2}\]  
where \(\gamma\) depicts the discount factor, which control the select probability preference for nodes in the protected nodes set.  
In Figure 3, the light protected nodes have more chance to be selected in crossover, node 'A4' with red square in the figure. Then two sub-trees including preponderant structures will be combined in the right up child tree inherited to next generation. Besides, we can see in Equations (1) and (2), if we cannot find any frequent sub-trees, there is no effect on the standard evolving process. With generation increasing, the crossover probability adjustment would have bigger effect on exploiting frequent preponderant sub-trees.