# Auction-Based Behavior Tree Evolution for Heterogeneous Multi-Agent Systems
## 2 Three-Way Handshaking Communication Protocol
### Task Allocation Architecture  
To enhance the robustness of heterogeneous MAS, we implemented a distributed auction architecture where each robot can potentially take on the role of auctioneer or bidder. Task allocation initiates when a robot becomes the auctioneer upon receiving task information, prompting other robots to calculate their capability and bid. Task Instruction is the first handshaking, which involves the auctioneer sharing task details, followed by a blocking state waiting for bids. The unblocking occurs when the auctioneer receives all bids from or waits beyond the time limit. During the Capability Instruction, which is the second handshaking, bidders calculate their bids using information on tasks and their states, employing diverse algorithms and normalizing results. Task Appointment is the third handshaking, and during this period, the auctioneer calculates the auction results and informs all bidders. After finishing the auction, robots that have received tasks will evolve BTs in parallel and replicate the original BTs with the evolved BTs, then continue to run the BTs to execute tasks. The procedure can be viewed in Figure 2.  
In applications of MASs, auction algorithms like single-round combinatorial (SRC) auction, parallel single-item (PSI) auction, and sequential single-item (SSI) auction [15] are typically used for task allocation. In these auction algorithms, SSI auctions integrate the advantages of both SRC auctions and PSI auctions. They are much easier to implement than SRC auctions since the central auctioneer receives exponentially less information and does not need to solve an NP-hard problem, and the team performance of the coordinate system based on SSI auctions is empirically close to optimal and much better than PSI  
Figure 2: Three-way handshaking communication process based on auction algorithm. auctions. Additionally, in comparison to SRC auctions, SSI auctions encounter challenges in attaining the optimal solution for total travel distance. However, in the scenarios primarily discussed in this paper, the energy of the robot is mainly consumed during task execution rather than movement. Therefore, we take SSI auctions as the basic algorithm of the task allocation architecture in this paper. Our SSI-based algorithm starts with unassigned tasks. Robots bid on each task and the highest bidder wins the corresponding task. This repeats until all tasks are assigned. To calculate bid value, the bidders simulate their task execution processes respectively, considering path cost \(P_{c}\), time cost \(T_{c}\), and energy consumption \(E_{c}\). The path cost of the robot moving to the task is described in terms of the Manhattan distance, as follows:  
\[P_{c}=|l(x)-L(x)|+|l(y)-L(y)|, \tag{1}\]  
Time cost consists of movement and execution, as follows:  
\[T_{c}=\frac{P_{c}}{V}+\frac{\sigma}{C_{k}} \tag{2}\]  
Similar to time cost, energy consumption consists of movement and execution, as follows:  
\[E_{c}=f\times P_{c}+\mu\times\frac{\sigma}{C_{k}} \tag{3}\]  
\(f\) represents the energy factor in Equation (6), set to constant in the program. Based on the above calculation results, the bid value \(B_{im}\) of robot \(R_{i}\) to task \(Tk_{m}\) can be calculated as follows:  
\[B_{im}=\frac{E-E_{c}}{E_{initial}}\times 100\times\frac{1}{T_{c}} \tag{4}\]  
Thus, the bid value prioritizes residual time and energy consumption to evenly distribute tasks. Upon task allocation, bidders update their state information. Specifically, the location L and energy E will be modified after the completion of tasks so as to enable participation in subsequent auctions. The auction concludes when tasks are fully assigned or robots deplete their energy during task execution. The procedure of task allocation based on the auction algorithm is shown in Algorithm 1.