Weighted Synergy Graphs for Role Assignment in Ad Hoc Heterogeneous Robot Teams

Heterogeneous robot teams are formed to perform complex tasks that are sub-divided into different roles. In ad hoc domains, the capabilities of the robots and how well they perform as a team is initially unknown, and the goal is to find the optimal role assignment policy of the robots that will attain the highest value. In this paper, we formally define the weighted synergy graph for role assignment (WeSGRA), that models the capabilities of robots in different roles as Normal distributions, and uses a weighted graph structure to model how different role assignments affect the overall team value. We contribute a learning algorithm that learns a WeSGRA from training examples of role assignment policies and observed values, and a team formation algorithm that approximates the optimal role assignment policy. We evaluate our model and algorithms in extensive experiments, and show that the learning algorithm learns a WeSGRA model with high log-likelihood that is used to form a near-optimal team. Further, we apply the WeSGRA model to simulated robots in the RoboCup Rescue domain, and to real robots in a foraging task, and show that the role assignment policy found by WeSGRA attains a high value and outperforms other algorithms, thus demonstrating the efficacy of the WeSGRA model.