TAP: Distributed team assignment in heterogeneous multi-agent systems

Abstract

In this article we introduce and study the problem of autonomous balanced team assignment in a heterogeneous multi-robot (i.e. multi-agent) system. The system includes n robots that are initially located in a large open area. We consider a scenario where there are two types of robots namely worker and service with limited communication ranges and specialized capabilities. The robots should be divided into teams so that each team can be assigned to a different location. The objective is to minimize the maximum distance traveled among the worker robots while ensuring that each constructed team is of equal size and has exactly one service robot to assist the worker robots in the team. Depending on the robot's initial configuration the robot can be either single or a part of a connected communication network of robots. In the former case the robot does not know the location of any other robot whereas in the latter case the robot only knows the locations of the robots in its network but not the ones outside it. For this problem we propose two algorithms TA<inf>m</inf> and TA<inf>nm</inf> that combine the distributed coordination and online motion planning methods. For assignment TA<inf>m</inf> uses a mutual decision making approach whereas TA<inf>nm</inf> uses a nonmutual decision making approach. We evaluate the performances of our strategies through extensive simulations varying the key parameters of interest including communication range environment size number of worker robots and number of service robots. The results show that TA<inf>m</inf> outperforms TA<inf>nm</inf> in sparse configurations but the performances of the algorithms approach to each other as the configuration becomes dense. © 2025 Elsevier B.V. All rights reserved.