# Auction-Based Behavior Tree Evolution for Heterogeneous Multi-Agent Systems
###### Abstract  
Collaboration in Multi-Agent Systems (MASs) is crucial but challenging in robotics, especially in heterogeneous MASs where robots have different capabilities. Nowadays, the key issue in research on collaboration in MASs is to fully utilize the capabilities of heterogeneous agents. To address this issue, we propose Auction-Based Behavior Tree Evolution (ABTE), a novel two-layer framework designed to learn BTs for heterogeneous MASs. In the first layer, we call it the command layer, and robots receive their tasks through the auction algorithm, enhanced by our innovative three-way handshaking communication protocol embedded in BT implementation, ensuring more efficient task allocation. The second layer of ABTE defines the specific execution behaviors of agents and is, therefore, named the execution layer. The behaviors in this layer are automatically generated by Grammatical Evolution (GE), which has been proven to be a general and effective method for generating swarm BTs. Our experiments are conducted within a Disaster Rescue Scenario, which requires intricate collaboration among multiple robots with diverse capabilities. The results indicate that ABTE outperforms the baseline algorithm, GEESE, in terms of resource utilization. Moreover, it demonstrates robust effectiveness in covering high-priority tasks, thereby validating the efficacy of employing an auction algorithm for generating BTs tailored for heterogeneous MAS. multi-agent systems; task allocation; hierarchical behavior tree; grammatical evolution; three-way handshaking communication protocol +
Footnote †: journal: Medical  
Although BTs have been demonstrated as an effective policy representation for various robotic applications, manual coding of BTs remains a time-consuming task that heavily relies on expert knowledge. To address the need for robots to adapt to unexpected environments, several approaches, including reinforcement learning, imitation learning, and evolution algorithms, have been explored [5]. In particular, Genetic Programming (GP) and Grammatical Evolution (GE) are commonly used in research. These algorithms measure the fitness of each population member by some specified metric(s), aiming to improve the performance of population members over multiple generations [6]. For example, [PERSON] et al. [7] used GP to generate BTs and control robots to carry objects in an unknown environment, proving that a learned BT is tolerant to faults in manipulation, localization, and navigation actions. An exploration by [PERSON] et al. [8] designed three common tasks for swarm and verified the effectiveness of learning swarm BTs using GE. These biomimetic swarm-based methods effectively solve complex collective problems but often overlook task matching with heterogeneous robot capabilities. With the advancement of robotics, heterogeneous MASs have been applied to a wider range of scenarios. Therefore, it is necessary to explore a method for heterogeneous MASs to cooperate based on their respective capabilities to perform tasks efficiently. To achieve this goal, two main challenges need addressing: firstly, establishing a cooperative mechanism considering the varying capabilities, and secondly, designing an autonomous generation method for BTs so that robots can adapt to the variation of tasks. The solution explored in this paper is mainly targeted at the scenario where heterogeneous MASs need to perform multiple tasks, so it is necessary to propose a communication protocol for multi-agent collaboration. Although heterogeneity increases computing costs, its application in many scenarios promotes research on task allocation algorithms for heterogeneous MASs [9]. There are two kinds of architectures for task allocation problems: A centralized architecture is able to find optimal solutions without the consensus stage but cannot adapt to the changes in the environment and robots, resulting in poor scalability and robustness.