Representation, Planning, and Learning of Dynamic Ad Hoc Robot Teams

Abstract

Forming an effective multi-robot team to perform a task is a key problem in many domains. The performance of a multi-robot team depends on the robots the team is composed of, where each robot has different capabilities. Team performance has previously been modeled as the sum of single-robot capabilities, and these capabilities are assumed to be known. Is team performance just the sum of single-robot capabilities? This thesis is motivated by instances where agents perform differently depending on their teammates, i.e., there is synergy in the team. For example, in human sports teams, a well-trained team performs better than an all-stars team composed of top players from around the world. This thesis introduces a novel model of team synergy — the Synergy Graph model — where the performance of a team depends on each robot’s individual capabilities and a task-based relationship among them. Robots are capable of learning to collaborate and improving team performance over time, and this thesis explores how such robots are represented in the Synergy Graph Model. This thesis contributes a novel algorithm that allocates training instances for the robots to improve, so as to form an effective multi-robot team. The goal of team formation is the optimal selection of a subset of robots to perform the task, and this thesis contributes team formation algorithms that use a Synergy Graph to form an effective multi-robot team with high performance. In particular, the performance of a team is modeled with a Normal distribution to represent the nondeterminism of the robots’ actions in a dynamic world, and this thesis introduces the concept of a -optimal team that trades off risk versus reward. Further, robots may fail from time to time, and this thesis considers the formation of a robust multi-robot team that attains high performance even if failures occur. This thesis considers ad hoc teams, where the robots of the team have not collaborated together, and so their capabilities and synergy are initially unknown. This thesis contributes a novel learning algorithm that uses observations of team performance to learn a Synergy Graph that models the capabilities and synergy of the team. Further, new robots may become available, and this thesis introduces an algorithm that iteratively updates a Synergy Graph with new robots. This thesis validates the Synergy Graph model in extensive simulations and on real robots, such as the NAO humanoid robots, CreBots, and Lego Mindstorms NXTs. These robots vary in terms of their locomotion type, sensor capabilities, and processing power, and show that the Synergy Graph model is general and applicable to a wide range of robots. In the empirical evaluations, this thesis demonstrates the effectiveness of the Synergy Graph representation, planning, and learning in a rich spectrum of ad hoc team formation scenarios.