FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 |

«Summary. The design of a coordination strategy for a distributed robotic team is challenging in domains with high uncertainty and dynamic ...»

-- [ Page 1 ] --

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 benefits of adding multiple robots to a system, such as increased performance and reliability, have been demonstrated in many different situations. However, depending on the domain and the task, different 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 [2], 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 identified 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 field 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 [2]. 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 off-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 field of view (under 60 degrees). A single robot therefore has a very limited view of the world, so teams can benefit greatly from communication strategies that build a shared world model.

4. Dynamic, adversarial environment: the presence of adversaries in the environment is a significant challenge. Opponents ensure that the environment is extremely dynamic: within a few seconds, the state of the world may change significantly.

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 significant advantage. Second, soccer is a finite-horizon zero-sum game.

A game of soccer has a winning team, a losing team, and a defined 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 specific implementation of a shared world model [7] 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 influenced 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 specifically addresses the issues of adversarial environments, temporal constraints, and robustness under high network latency.

Gerkey and Mataric [4] 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 fixed order using a well-defined objective function, namely first 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 finally the supporter role to the remaining robot [8]. 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 effective 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 fight over it. The potential outcome is an undesirable role oscillation between the robots – a period of hesitation where neither robot makes significant 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 significantly more suited to the task than another. However, adding hysteresis to a system can be difficult: 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, finding a solution that balances these two constraints (lack of role oscillation and immediate response to environmental changes) can be difficult. 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 significant cost to role switching, as the robots reconfigure themselves for their new roles. The work presented in this paper attempts to minimize the effect of these limitations.

Dylla et al. [3] 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 specific 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 [6]. 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. [1]. We introduce a distributed play-based approach to teamwork, which allows us to handle the domain challenges introduced in section 2. A play specifies 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 different teamwork strategies, as explicit responses to different 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, finite-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 suffer from hesitation nor oscillation, and that team performance is not significantly degraded by possible periods of high network latency. We believe that ours is the first implemented distributed play-based teamwork approach, at least in the context of the RoboCup four-legged league.

3.1 Plays

A play is a team plan that provides a set of roles, which are assigned to the robots upon initiation of the play. Bowling [1] 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 significant 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 fixed, and therefore always provides exactly four different 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 define applicability conditions, which denote when a play is suitable for execution; what roles should be assigned when we have a specific 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 satisfied.

6 Colin McMillen and Manuela Veloso Roles. Each play specifies which roles should be assigned to a team with a variable number of robots by defining different ROLES directives. A directive applies when a team has k active robots, and specifies 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 [1]. In the work presented in this paper, adaptation was not used – the weights were set manually.

Pages:   || 2 |

Similar works:

«THE RHETORIC OF SHAKESPEAREAN APPROPRIATION: CONTEMPORARY WOMEN WRITERS RESPOND TO KING LEAR AND THE TEMPEST by ERIN MELINDA DENISE PRESLEY (Under the Direction of Christy Desmet) ABSTRACT This dissertation examines the rhetorical relationship between Shakespeare as an appropriator and Shakespeare as a source for contemporary women novelists. Influenced by early modern pedagogy and its emphasis on imitation, Shakespeare’s relation to his sources reflects the primary sense of “invention”:...»

«2 What Is a Virus? Abstract Viruses are built from short sequences of nucleic acid, either DNA or RNA wrapped in a protein shell. Until the invention of the electron microscope, it was impossible to visualize a virus. The first viruses to be visualized were bacteriophage, which appeared to have a head and tail-like structure. Only the nucleic acid entered the bacterial cell through the tail. Animal viruses were described as spherical or rod-shaped; they were bound to receptors and were taken...»

«www.heronhill.cumbria.sch.uk @heronhillschool HERON HILL PRIMARY SCHOOL NEWSLETTER NO. 14 19th JULY 2016 Dear Parents and Carers Another school year draws to a close which leads us all to think about the successes this year and to look forward to new and exciting challenges to come next year. The children of Heron Hill School never stop making me feel immensely proud of their abilities, talents and achievements across all areas of their school life and beyond. Sport has been good this year, we...»

«Welcome to the Graduation Ceremony of the University of Johannesburg 16 March 2016 at 09:00 Welkom by die Gradeplegtigheid van die Universiteit van Johannesburg 16 Maart 2016 om 09:00 Le a Amogelwa Moletlong wa Dikapešo wa Yunibesithi ya Johannesburg 16 Hlakola 2016 ka 09:00 Niyamukelwa eMcimbini wokweThweswa kweZiqu weNyuvesi yaseJohannesburg 16 kuNdasa 2016 ngele-09:00 1 UNIVERSITY OF JOHANNESBURG CHANCELLOR Prof NS Ndebele BA (Lesotho), MA (Cambridge UK), PhD (Denver USA) SENIOR...»

«Editorials Letter from the Editor The Example of Leadership by Timothy D. Norton Guest Editorial Seminaries Must Balance the “Ought to Learn” and the “Need to Know” in Doctor of Ministry Curricula by Thomson K. Mathew Guest Editorial An Editorial Review of Organizing Higher Education for Collaboration: A Guide for Campus Leaders by Kim E. Boyd Reviews Book Review Reviewing The Language of God: A Scientist Presents Evidence for Belief by Martin Crossland Articles Theoretical Article...»

«Beth A. Fischer, PhD University of Pittsburgh +1-412-578-3716 (phone) 3500 Fifth Avenue, Suite 202 +1-412-578-3790 (fax) Pittsburgh, PA 15213 bfischer@pitt.edu _ EDUCATION and TRAINING 2006 Ph.D., Education, University of Pittsburgh, Pittsburgh, PA, William Bickel, Advisor. Dissertation: Promoting Access to Science Careers: Training Faculty to Teach Professional Development and Research Ethics. 1996 M.Ed., Education, University of Pittsburgh, Pittsburgh, PA, Eugenie Potter, Advisor. Focus:...»

«Universidade Estadual de Santa Cruz GOVERNO DO ESTADO DA BAHIA Jaques Wagner Governador SECRETARIA DE EDUCAÇÃO Adeum Hilário Sauer Secretário UNIVERSIDADE ESTADUAL DE SANTA CRUZ Antonio Joaquim Bastos da Silva Reitor Lourice Hage Salume Lessa Vice-Reitora DIRETORA DA EDITUS Maria Luiza Nora Maria Luiza Heine (Coord.) Antonio Carlos do Espírito Santo Alfredo Amorim da Silveira José Nazal Maria Izabel de Souza Lopes Telma Moura Ilhéus Bahia 2007 ©2007 by Maria Luiza Heine et al. Direitos...»

«Hannah Arendt’s Angels and Demons: Ten Spiritual Exercises Markku Koivusalo University of Helsinki Praise this world to the angel, not the unsayable one, you can’t impress him with glorious emotion; in the universe where he feels more powerfully, you are a novice. So show him something simple which, formed over generations, lives as our own, near our hand and within our gaze. Tell him of Things. He will stand astonished. Rilke, Ninth Elegy A Beginning October 14, 1906 – the first cry....»

«1 Molokai Native Hawaiian Beginning Farmer Newsletter – April 2013 Season of the Caterpillar by Glenn I. Teves, County Extension Agent, UH CTAHR CES (tevesg@ctahr.hawaii.edu) The weather is not normal; winter wasn’t normal and neither is the spring. Spring is supposed to have warmer weather than winter, with misty rains, but it’s still cold. Must be ‘Global Chilling’. We’ve had more than our share of rainy days, and it’s sure to influence the outcome of our summer. First it was...»

«TIM ETCHELLS | tim@timetchells.com www.timetchells.com Tim Etchells is an artist and a writer based in the UK. His work ranges from performance to video, photography, text projects, installation and fiction. He has worked in a wide variety of contexts, notably as the leader of the world-renowned Sheffieldbased performance group Forced Entertainment (1984 – present day) and in collaboration with visual artists, choreographers and photographers. He is currently Professor of Performance at...»

«Kidnapping Casey Laurann Dohner Book two in the Zorn Warriors series. All Casey wants is to avoid being arrested on trumped-up charges from her persistent ex-boyfriend. Running through the woods to escape two deputies sounds like a great plan until they catch her. Thinking it’s all over, waiting to hear the snap of the handcuffs, she instead hears a roar. A huge, tall, muscular man comes to her rescue. She’s being saved by Bigfoot—and he’s the sexiest thing she’s ever seen. The...»

«Skilbeck, Julie Kathryn (2014) 'Am I still here?': A longitudinal, ethnographic study of living with frailty. PhD thesis, University of Nottingham.Access from the University of Nottingham repository: http://eprints.nottingham.ac.uk/27709/2/Final%20PHD %20document_15%20October_2014_corrections.pdf Copyright and reuse: The Nottingham ePrints service makes this work by researchers of the University of Nottingham available open access under the following conditions. This article is made available...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.