Event Location: GHC 8102

Abstract: Task allocation involves the division of tasks among a team of robots, such that each robot is responsible for a subset of the tasks. Similarly, in role assignment, roles are typically defined to be performed by a single robot whose performance is independent of the composition of its team. Complex tasks, that cannot be sub-divided and require multiple robots cooperating, require the formation of a coalition of robots to complete. We are interested in forming an effective ad hoc team to solve a task, through observations of the robots’ performance in the task and modeling the synergistic effects among robots in the team.

Ad hoc teams are common in sports such as soccer, where human players without prior interactions form a team and are capable of playing the game. Currently, while robots within a team can play soccer well, they are unable to form ad hoc teams with robots developed by multiple research groups. This general problem is also seen in urban search-and-rescue (USAR), where large groups of heterogeneous robots would be deployed to solve complex tasks such as putting out fires, rescuing people and clearing road blockages.

This thesis represents team performance as a function of the individual capabilities of the robots as well as the synergy among members of the team. This model of team performance is learned through observations of coalitions or sub-teams of robots at a task, and by using this learned model, the most effective team is formed to complete the task.

In my previous work, I modeled the pairwise interactions of robots in a heterogeneous team, and concretely defined roles with weights on states and actions. Using this model, the utility of a team performing a complex task, such as robot soccer, is critically dependent on the composition of the team. In addition, because there is inherent uncertainty in the actions and perceptions of robots in the real world, I modeled the utility with a Normal distribution and not a single value. Thus, the definition of optimal utility has to account for both the mean and variance of the distribution, and I introduced the concept of risk in utility, which trades off between the mean and variance. Besides modeling pairwise interactions, I have also developed a synergy graph model that captures the task-based performance of a team of robots. The structure of the graph represents how well robots work together, and defines how the utility of a team is calculated. In addition, I have shown that this synergy graph model can be learned from observations of small subsets of robots, and then be used to find a high-performance team of a greater size.

For the remaining work of this thesis, I will extend my model to include teammate adaptations over time, as ad hoc robots are capable of learning to coordinate better from experience. Thus, instead of learning a static graph model from observations, a dynamic graph-based model will be developed. Furthermore, robots have an inherent sense of its individual capabilities, such as its maximum velocity, the maximum weight it can lift, etc. Also, some of the robots may have coordinated before in the past, or have a sense of how well they would work together. Using such prior knowledge to jump-start the learning of the team performance is another aspect that will be investigated in my thesis. In addition, observations of team performance will be typically noisy, and it is crucial to distinguish between the uncertainty of observations and the uncertainty of the robots’ performance.

I will validate my work both in extensive simulations and also on real robots. In particular, I propose to use several of the robot platforms with which I am familiar, including the NAO humanoid robots, Sony AIBOs, and iRobot Creates. In my empirical evaluation, I will demonstrate the effectiveness of my representation, and planning and learning algorithms in a rich spectrum of ad hoc team formation scenarios.

Committee:Manuela Veloso, Chair

Howie Choset

Bernardine Dias

Peter Stone, University of Texas at Austin