# Auction-Based Behavior Tree Evolution for Heterogeneous Multi-Agent Systems
###### Abstract
In contrast, decentralized architecture is robust and has lower computing overhead, but it usually results in a sub-optimal solution [10]. In our design, we combine the advantages of centralized and decentralized methods. Each robot is able to become the central coordinator once the tasks are allocated. In terms of the task allocation algorithm, we adopt the auction algorithm, which is a commonly used market-based approach to assign tasks [11]. Inspired by economics, this kind of algorithm carries out multi-robot task allocation through an auction-like process [12]. [PERSON] et al. [13] first used a centralized auction algorithm to solve the multi-robot task allocation problem and proposed a polynomial-time auction algorithm for single-task allocation. Auction-based methods can utilize the information and preferences of robots to obtain effective solutions in resource-limited situations [14]. In addition, such methods support dynamic task allocation and are highly inclusive of changes in the environment. Therefore, this paper aims to study the autonomous planning and collaboration of heterogeneous MASs in environments that involve a great deal of task variety, focusing on building a BT framework to enhance the autonomy of systems. In this framework, all available information about robots and the environment is considered comprehensively in the autonomous generation of behaviors, and a novel three-way handshaking communication protocol for task allocation is integrated. As the command layer in the framework, the communication protocol consists of a sequence of fixed behaviors and standardized package formats, which are capable of controlling the generation and initiation of behaviors at the execution layer. The overall framework is shown in Figure 1.  
The contribution of this study lies in providing a general solution for heterogeneous MASs to plan collaboratively and adapt autonomously in multi-task environments. The details are as follows:  
* We propose Auction-Based Behavior Tree Evolution (ABTE), a novel hierarchical behavior control framework that consists of a command layer and an execution layer. This framework makes full use of the modularity of behavior tree models by layeringcommand and execution behaviors. Command behaviors remain fixed, handling task allocation and controlling the generation of execution behaviors. Execution behaviors are generated by the GE algorithm after task allocation, which is designed to improve the completion rate and execution efficiency of MAS. * We propose a three-way handshaking communication protocol based on the SSI auction algorithm. This communication protocol, which comprises a set of auction behaviors and standard data formats, is a crucial component of the command layer. With this protocol, the command layer can fully utilize the information of the environment and robots to allocate tasks, thereby maximizing the strengths of heterogeneous robots. * We design simulation experiments in the Disaster Rescue Scenario, where there are a large number of tasks with different priorities. Our framework aims to complete as many high-priority tasks as possible while consuming less energy. The results prove that ABTE, compared to GEESE, can achieve higher resource utilization in heterogeneous MASs and display robust effectiveness in covering high-priority tasks. In the ensuing section, an innovative three-way handshaking communication protocol based on auction algorithms is discussed, which constructs a task allocation architecture among agents. Section 3 proposes Auction-Based Behavior Tree Evolution (ABTE), a hierarchical behavioral control framework used for combining fixed behaviors with generated behaviors. The results of the experiments are presented in Section 4. Finally, the main conclusions are summarized and future lines of research are proposed in Section 5.