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 TAm and TAnm that combine the distributed coordination and online motion planning methods. For assignment TAm uses a mutual decision making approach whereas TAnm 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 TAm outperforms TAnm in sparse configurations but the performances of the algorithms approach to each other as the configuration becomes dense.