[robocup-worldwide] Dissertation: Representation, Planning and Learning of Dynamic Ad Hoc Robot Teams

[Somchaya Liemhetcharat]

Hi everyone,

I would also like to share my thesis dissertation with you: the research
was largely inspired by my experiences at RoboCup. I participated in
RoboCup from 2006-2012, in the Four-Legged League (4LL) and Standard
Platform League (SPL). I led the CMurfs SPL team in 2009-2012, and I was
primarily focused on the attacker/supporter behaviors and multi-robot
coordination within the team. Something that struck me was how we would
pick specific robots for specific roles, e.g., "Robot2 should be the
attacker since its kicks are the most accurate, and Robot1 should be the
goalkeeper since it doesn't walk very quickly."

>From there, I formed my thesis topic: Representation, Planning and Learning
of Dynamic Ad Hoc Robot Teams. The key idea is that the performance of a
robot team is not just the sum of their individual capabilities --- there
is *synergy* among the team members. Using a RoboCup example, the
performance of a team is affected by how good the attacker, supporter and
goalkeeper robots are at their roles, and more importantly, how well they
work together as a team (e.g., how quickly another robot on the team gains
possession of the ball if the attacker falls down). My thesis contributes
the Synergy Graph model that captures the robots' capabilities and their
synergy, and algorithms that learn the model through observations, and
selects the best team for the task.

My thesis is applicable to robot teams in general and considers ad hoc
teams, i.e., teams of robots that have not collaborated in the past, so
their capabilities and synergy are initially unknown. I believe many ad hoc
team scenarios exist, since different institutions develop their robots
(such as in RoboCup), and a complex task will require combining robots from
different sources together in a team (e.g., the drop-in player competition
in SPL), so a key question is how to learn their capabilities and synergy,
and then form the team for the task.

The thesis is available for download at: http://www.somchaya.org/thesis.pdf
 I have included my thesis abstract at the bottom of the email for those
that are interested.

Regards,
Somchaya


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

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
delta-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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/robocup-worldwide/attachments/20140707/b3163363/attachment.html>