# Auction-Based Behavior Tree Evolution for Heterogeneous Multi-Agent Systems
## 3 The Hierarchical Behavior Control Framework
### The Layers of The Framework  
BTs have attracted much attention in the robotics field in recent years, which generalize existing control architectures and bring unique advantages for building robot systems [16]. BT is a kind of control model with strong modularity; this characteristic is very helpful for expansion and pruning. Therefore, we propose an extensible two-layer framework. The behaviors defined by the three-way handshaking communication protocol, which we define as auction behaviors, are incorporated within the first layer of the framework, namely the command layer. Such a design is the basis for the framework to be distributed in heterogeneous MASs, ensuring accurate execution of protocol-related actions. The second layer, also known as the execution layer, is an empty tree in the initial state of MASs. After the system completes task allocation in the command layer, the node for grammatical evolution will be activated. Robots then generate heterogeneous execution behavior trees according to task planning, thus forming the execution layer of our framework. In summary, we create a mechanism to convert the auction-based communication protocol into fixed BT behaviors while allowing the autonomous generation of execution behaviors based on tasks and improving the adaptability and flexibility of MASs. Figure 3 shows the BTs for robots in an experiment required to execute excavation tasks.  
The task allocation behaviors based on the three-way handshaking communication protocol are fixed in the BT controller. After the control flow is started by _ticks_, the robots start the \"Auction()\" thread through the \"Call Service\" node to continuously monitor the tasks in the environment. While one robot in the cluster receives a demand to allocate tasks, the auction process begins. The robot that receives tasks acts as an auctioneer, as well as a bidder, and the others serve as bidders. The auctioneer robot executes \"Notify\", \"Receive Information\", \"Calculate Bid\", and \"Allocate Tasks\" in sequence in the \"Auction()\" thread. Bidder robots are subjected to the BT controller to execute \"Send Information\" after the blocked \"Receive Notification\" node receives the auction notification and then blocks in the \"Wait Allocation\" node. If the allocation is received within a time constraint, robots continue to evolve, matching BTs according to the allocated tasks; then replace the original \"Execution Behaviors\" with the generated BTs; and continue to execute tasks.  
There are two significant advantages of using ABTE to generate BTs. First of all, we implement a multi-thread approach to represent the auction-based three-way handshaking communication protocol with a singular behavioral sequence. This allows every robot  
Figure 3: ABTE generates BT with auction behaviors and execution behaviors.  
embedded with this BT to simultaneously possess the capabilities of both auctioneer and bidder. Subsequently, the BTs for executing tasks can be generated according to the allocated tasks and environment information, which improves the adaptation of MASs to face unknown changes and challenges in the environment. The details of evolving execution behaviors will be explained next.