«Summary. The design of a coordination strategy for a distributed robotic team is challenging in domains with high uncertainty and dynamic ...»
Distributed, Play-Based Role Assignment for
Robot Teams in Dynamic Environments
Colin McMillen and Manuela Veloso
School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, U.S.A.
Summary. The design of a coordination strategy for a distributed robotic team is
challenging in domains with high uncertainty and dynamic environments. We present
a distributed, play-based role assignment algorithm that has been implemented on
real robots in the RoboCup four-legged league. The algorithm allows the robots to adapt their strategy based on the current state of the environment, the game, and the behavior of opponents. The distributed play-based approach also enables the robots to reason about task-based temporal constraints and has been designed to be resistant to the problem of role oscillation.
1 Introduction A common goal of distributed autonomous robotic systems is the development of teamwork and coordination strategies. The beneﬁts of adding multiple robots to a system, such as increased performance and reliability, have been demonstrated in many diﬀerent situations. However, depending on the domain and the task, diﬀerent sorts of approaches might be needed. We are interested in the implementation of multi-robot coordination in domains with high uncertainty and dynamic environments.
In this paper, we present our approach to role assignment in the RoboCup four-legged league , in which two teams of four Sony AIBO robots compete in a robot soccer game. Figure 1 shows a snapshot of a recent AIBO game.
This domain presents many challenges, including: full robot autonomy, distributed robot team control, limited individual robot perception, the presence of robot adversaries, task-dependent temporal constraints, and high communication latency. In this paper, we contribute a new distributed play-based system that equips the robots with plays – alternative teamwork strategies.
This method was developed to overcome limitations of previous approaches.
In particular, it assigns roles to robots in a fault-tolerant manner that minimizes role switching and synchronization problems. Our approach has been fully implemented within robot soccer, but is designed to be relevant to genColin McMillen and Manuela Veloso eral multi-robot domains that share some of the challenging features of robot soccer, as identiﬁed in this paper.
Fig. 1. A RoboCup four-legged league soccer match.
We discuss the RoboCup legged league in section 2, identifying the technical features that we address as especially challenging for multi-robot coordination. Section 3 introduces our approach to teamwork. Section 4 presents experimental results that highlight some of the advantages of our approach.
We present our conclusions in section 5. Related work is discussed throughout the paper as needed.
2 Challenges of the RoboCup Legged League In the RoboCup four-legged league, two teams of four Sony AIBO robots play each other in a time-limited and space-limited setting (currently two game halves of ten minutes each and a ﬁeld of 6m×4m). The settings and the rules of the game change every year to create new research challenges. The current complete rules of the domain are available at . We focus on the discussion of the general features of the game that are of relevance to team coordination.
These features include:
1. Full autonomy: each team of robots operates completely without human supervision. However, teams are allowed to change the robots’ programming at halftime or during a timeout. Each team is granted one timeout per game.
2. Distributed teams: all perception, computation, and action is done onboard the robots. The robots are equipped with 802.11b wireless networking, which enables communication among team members; however, the robots are not allowed to communicate with any oﬀ-board computers.
Distributed, Play-Based Role Assignment 3
3. Limited perception: each robot’s primary sensor is a low-resolution camera with a very narrow ﬁeld of view (under 60 degrees). A single robot therefore has a very limited view of the world, so teams can beneﬁt greatly from communication strategies that build a shared world model.
4. Dynamic, adversarial environment: the presence of adversaries in the environment is a signiﬁcant challenge. Opponents ensure that the environment is extremely dynamic: within a few seconds, the state of the world may change signiﬁcantly.
5. Temporal constraints: there are two temporal constraints that arise due to the presence of adversaries. First, all team decisions must occur in real time. A team that takes too long to coordinate will have robots that display hesitation in carrying out their tasks, which gives the opponents a signiﬁcant advantage. Second, soccer is a ﬁnite-horizon zero-sum game.
A game of soccer has a winning team, a losing team, and a deﬁned ending point. Playing a conservative strategy – which might work well over a long period of time – is of no use to a team that is losing and only has a few seconds remaining in the game. A team in this situation must choose a strategy that can score a goal quickly, even if such a strategy has other weaknesses. Multiple team coordination strategies are needed. The selection algorithm faces complex multi-objective optimization criteria.
6. High network latency: the presence of dozens of robots in the competition environment leads to very unpredictable quality of the robots’ wireless network. Teams may experience periods of high network latency and collisions; latencies of over a second have been observed. To achieve consistent performance, a team needs to ensure that the coordination strategies employed are robust to disruptions in communication.
The issues of limited perception in the four-legged league have already been addressed in previous work. Our speciﬁc implementation of a shared world model  is not discussed at length here, but it is important to note that some of the decisions made by individual robots on our team are inﬂuenced by information that has been communicated by teammates.
In this paper, we focus on the challenges of role assignment (also known as task allocation) in the RoboCup legged league. Due to the constraints of our domain, it is a requirement that the solution be implemented on fully autonomous, distributed robots. The work presented in this paper speciﬁcally addresses the issues of adversarial environments, temporal constraints, and robustness under high network latency.
Gerkey and Mataric  discuss role assignment in RoboCup, giving an overview of the strategies used by teams in each of the RoboCup leagues. In the
four-legged league, the predominant approach involves allocating three roles:
an attacker, a defender, and some sort of supporter. According to Gerkey’s survey, nearly all RoboCup teams assign roles to robots in a greedy fashion.
For example, in previous years, our own team (CMPack) assigned the roles in a ﬁxed order using a well-deﬁned objective function, namely ﬁrst the attacker 4 Colin McMillen and Manuela Veloso role to the robot that could reach the ball most quickly, then the defender role to whichever of the other two robots was closest to our own goal, and ﬁnally the supporter role to the remaining robot . To prevent robots from interfering with one another, the attacker was the only robot allowed to actually approach the ball for a kick; the other robots would position themselves in useful supporting locations. If the ball came near to another robot, the team members would negotiate a role switch. After the role switch, the closest robot to the ball would become the new attacker, and the attack would continue.
This was a very eﬀective strategy that contributed strongly to our world championship in 2002. However, this strategy has some limitations, particularly in terms of role switching and oscillation. Two robots that are equally suited to the attacker role might ﬁght over it. The potential outcome is an undesirable role oscillation between the robots – a period of hesitation where neither robot makes signiﬁcant progress toward completing the task. A standard solution to this problem, which has previously been implemented in our own team and other RoboCup teams, is to add some hysteresis to the role assignment: either allowing role assignments to occur infrequently (e.g., every few seconds) or ensuring that a role switch will not occur unless one robot is signiﬁcantly more suited to the task than another. However, adding hysteresis to a system can be diﬃcult: if too much hysteresis is added, the robots will miss out on opportunities because they are no longer reacting as quickly to changes in their dynamic environment. In practice, ﬁnding a solution that balances these two constraints (lack of role oscillation and immediate response to environmental changes) can be diﬃcult. This problem is exacerbated under the presence of communication failures or high network latency, where the negotiation of a role switch may take several seconds to complete. Another limitation of this design is that there can be a signiﬁcant cost to role switching, as the robots reconﬁgure themselves for their new roles. The work presented in this paper attempts to minimize the eﬀect of these limitations.
Dylla et al.  propose a soccer strategy language that formalizes the strategies and tactics used by human soccer teams. Their goal is to be able to specify soccer strategies in an
way that does not depend strongly on the speciﬁc robot hardware used in the competition. However, to our knowledge, the authors do not yet plan to use this language in the implementation of any real robot soccer team. In this paper, we present a strategy language that could be used in any multi-robot system and that has been implemented in the four-legged league of the 2005 RoboCup competition.
3 Distributed Play-Based Role Assignment
We can say that teamwork in general consists of a team control policy, i.e., a selection of a joint action by teammates given a perceived state of the environment . It is our experience that it is rather challenging to generate or learn a team control policy in complex, highly dynamic (in particular adversarial), Distributed, Play-Based Role Assignment 5 multi-robot domains. Therefore, instead of approaching teamwork in terms of a mapping between state and joint actions, we follow a play-based approach, as introduced by Bowling et al. . We introduce a distributed play-based approach to teamwork, which allows us to handle the domain challenges introduced in section 2. A play speciﬁes a plan for the team; i.e., under some applicability conditions, a play provides a sequence of steps for the team to execute. Multiple plays can capture diﬀerent teamwork strategies, as explicit responses to diﬀerent types of opponents. Bowling showed that play selection weights could be adapted to match an opponent. Plays also allow the team to
reason about the zero-sum, ﬁnite-horizon aspects of a game-playing domain:
the team can change plays as a function of the score and time left in the game. Our play-based teamwork approach ensures that robots do not suﬀer from hesitation nor oscillation, and that team performance is not signiﬁcantly degraded by possible periods of high network latency. We believe that ours is the ﬁrst implemented distributed play-based teamwork approach, at least in the context of the RoboCup four-legged league.
A play is a team plan that provides a set of roles, which are assigned to the robots upon initiation of the play. Bowling  introduced a play-based method for team coordination in the RoboCup small-size league. However, the small-size league has centralized control of the robots. One of the signiﬁcant contributions of our work is the development of a play system that works in a distributed team. The play language described by Bowling assumes that the number of robots is ﬁxed, and therefore always provides exactly four diﬀerent roles for the robots. In another extension to Bowling’s work, our plays also specify which roles are to be used if the team loses some number of robots due to penalties or crashes. This extension to the role-assignment aspects of Bowling’s play language allows the team to robustly adapt to the loss of team members without the need for additional communication. This is a particularly important extension for domains where limited or high-latency communication is the norm.
Our play language itself is also strongly inspired by the work of Bowling.
Our language allows us to deﬁne applicability conditions, which denote when a play is suitable for execution; what roles should be assigned when we have a speciﬁc number of active robots on the team; and a weight, which is used to decide which play to run when multiple plays are applicable.
Applicability. An applicability condition denotes when a play is suitable for execution. Each applicability condition is a conjunction of binary predicates. A play may specify multiple applicability conditions; in this case, the play is considered executable if any of the separate applicability conditions are satisﬁed.
6 Colin McMillen and Manuela Veloso Roles. Each play speciﬁes which roles should be assigned to a team with a variable number of robots by deﬁning diﬀerent ROLES directives. A directive applies when a team has k active robots, and speciﬁes the corresponding k roles to be assigned. If a robot team has n members, each play has a maximum of n ROLES directives. Since our AIBO teams are composed of four robots, our plays have four ROLES directives.
Weight. Weight is used to decide which play to run when multiple plays are applicable. In our current implementation, the play selector always chooses the applicable play with greatest weight. Future work could include choosing plays probabilistically based on the weight values or updating the weights at execution time to automatically improve team performance.
Playbook adaptation of this sort has been implemented by Bowling for the small-size league . In the work presented in this paper, adaptation was not used – the weights were set manually.