Learning the synergy of a new teammate

Abstract

In many multi-robot problems, the performance of a team of robots is not the sum of their individual capabilities; there is often synergy among the robots. We recently introduced the synergy graph model to model such phenomena, where robots are represented by vertices in a graph, their capabilities represented by Normally-distributed variables, and the interactions of robots represented with the structure of the graph. The synergy graph is learned from observations of robot team performances, with the underlying assumption that observations of all the robots are available at once. However, it is common that new information becomes available over time, in particular as new robots enter the domain. In this paper, we contribute a learning algorithm that uses new information to add a new robot into an existing synergy graph, that requires a smaller number of observations and faster computation than relearning the entire synergy graph using the existing learning algorithms. We introduce three heuristics to initialize the learning algorithm, and perform extensive simulations to analyze their characteristics, as well as compare two methods of learning robot capabilities, over a variety of graph structure types. We also compare three approaches to learning synergy graphs, and demonstrate that adding a new teammate into an existing synergy graph introduces higher error than completely relearning the synergy graph. However, it is computationally less expensive to add a new teammate, especially when the number of robots is large.