# Auction-Based Behavior Tree Evolution for Heterogeneous Multi-Agent Systems
## 3 The Hierarchical Behavior Control Framework
### The Evolution of Execution BTs  
GE is a context-free grammar-based genetic program paradigm proposed based on GP. Through the conversion rule of \"Backus-Naur Form (BNF)\" grammar, the derived tree is mapped into a binary string to implement a string-based genetic operation. Therefore, GE is capable of enhancing the efficiency of modeling BTs with high reliability and interpretability. It represents commendable explorations in the realm of generating BTs autonomously. A central work of incorporating BTs into the framework of GE is to find a grammar that can be used in the genotype-to-phenotype mapping [17]. The transformation uses BNF grammar, which specifies the language of the produced solution. In our experiments, robots are required to complete various tasks in the environment. The basic experiment assumes that there are four types of tasks: Excavation, Communication, Transportation, and Search. The production rules in BNF grammar for basic task coverage experiment are defined in Equations (5)-(13). Equation (5) indicates that BT as a whole follows the sequence structure. Equations (6)-(8) recursively expand the control nodes. Equations (9)-(11) define multiple execution nodes. Production rules Equations (12) and (13) define specific behaviors that robots need to perform. The phenotype created from this mapping process is a BT controller represented by a string (e.g., ['Seq', 'action', 'condition', '/Seq']). \[\langle root\rangle ::=\langle sequence\rangle \tag{5}\] \[\langle sequence\rangle ::=\_Seq\langle control\rangle\langle control\rangle_{-}/Seq\mid\_Seq \langle executions\rangle_{-}/Seq\] (6) \[\langle selector\rangle ::=\_Seq\langle control\rangle\langle control\rangle_{-}/Seq\mid\_ Sel\langle executions\rangle_{-}/Sel\] (7) \[\langle control\rangle ::=\langle sequence\rangle\mid\langle selector\rangle\] (8) \[\langle executions\rangle ::=\langle conditions\rangle\langle actions\rangle\mid\langle actions\rangle\] (9) \[\langle actions\rangle ::=\langle action\rangle\langle actions\rangle\mid\langle action\rangle\] (10) \[\langle conditions\rangle ::=\langle condition\rangle\langle conditions\rangle\mid\langle condition\rangle\] (11) \[\langle condition\rangle ::=\_IsBlocked?\mid\_ReachLocation?\mid\_Excavation?\mid\] (12) \[\langle Amputation?\mid\_Transportation?\mid\_Search?\] \[\langle action\rangle ::=\_CheckState\mid\_GetTasks\mid\_MoveToTask\mid\_AvoidObstacle\mid\] \[\langle sequence\rangle ::=\_Seq\langle control\rangle\langle control\rangle_{-}/Seq\mid\_Seq \langle executions\rangle_{-}/Seq\]0 (13) \[\langle sequence\rangle ::=\_Seq\langle control\rangle\langle control\rangle_{-}/Seq\mid\_Seq \langle executions\rangle_{-}/Seq\]1  
The initial population is composed of BTs with a maximum depth of no more than 7, which are randomly generated based on the derivation tree method. For the crossover and mutation, Tournament Selection is often used to choose better parents for the next generation. This method generally works with any fitness value, including negative fitness, leading to a full exploration of the search space and a reduced likelihood of falling into local minima [18]. Since selection determines the initial population of every generation, the fitness function guides the evolutionary process. To measure the performance of the BT controller, we design the fitness function as Equation (14). In our system, lower fitness means better performance. \[\langle sequence\rangle ::=\_Seq\langle control\rangle\langle control\rangle_{-}/Seq\mid\_Seq \langle executions\rangle_{-}/Seq\]2  
where function _S(w,d)_ is the size of BT, which consists of width \(w\) and depth \(d\), as follows:  
\[\langle sequence\rangle ::=\_Seq\langle control\rangle\langle control\rangle_{-}/Seq\mid\_Seq \langle executions\rangle_{-}/Seq\]3In Equation (14), \(D\) represents the distance one robot travels to complete all tasks, and \(T\) means the total time cost, including the time spent traveling and executing. Parameters {\(\alpha\),\(\beta\),\(\gamma\)} are weights of {\(D\),\(T\),\(S\)}.