ATT-CMUnited RoboCup-2000 Simulator Team

This page presents the ATT-CMUnited team entered in the RoboCup-2000 simulator league. For more information about our entire project (including small and legged robots) please see our RoboSoccer project page.

People

Patrick Riley, Peter Stone, David McAllester, Manuela Veloso

Results

ATT-CMUnited-2000 is the RoboCup-2000 Simulator League 3rd Place Team!

The tournament included 34 teams from around the world.
Over the course of 8 games, ATT-CMUnited-2000 outscored its opponents by a combined score of 26-11.
Results of RoboCup-2000 are available from the main RoboCup homepage and from the RoboCup-2000 page.

Accelerators
Summary | On-line Planning for Set Plays | Leading Passes | Software

Summary

The ATT-CMUnited-2000 simulator team is based upon the CMUnited-99 simulator team, which in turn is based on CMUnited-98. In particular, it uses all of the techniques that are described in detail, with pointers to relevant publications, on the CMUnited-98 simulator team page:
(1) Hierarchical machine learning (Layered learning)
(2) Flexible, adaptive formations (Locker-room agreement)
(3) Single-channel, low-bandwidth communication
(4) Predictive, locally optimal skills (PLOS)
(5) Strategic positioning using attraction and repulsion (SPAR)

Our goal in creating ATT-CMUnited-2000 was to investigate new research directions. These contributions are described in detail in our team description paper that is included in the source code and binary distributions below.

On-Line Planning for Set Plays

ATT-CMUnited-2000 uses dynamic, adaptive planning for set-plays. Previously, the plans executed for set-plays were fixed, with very little variability. The coach for ATT-CMUnited-2000 makes a new plan for player and ball movement at every offensive set play. The plan is made by using local search over a set of given starting paths.
The plan is represented as a Simple Temporal Network, as introduced by Dechter, et al. The use of Simple Temporal Networks as a multi-agent plan formats appears to be a novel application.
Further, the planning depends on a model of opponent movement. We create a set of models by hand offline and then select between the models on-line. The model selection is done using probabilistic techniques which are close to a Bayesian update of the probability distribution over the models.
For defensive set plays, the coach makes the assumption that future plays will be like past plays and instructs the players to move to locations that would have been good for previous plays. For example, if the opponents free kick set play always goes directly towards the goal first, the coach will put a player directly on that path.
(The on-line planning work was done by Patrick Riley in part while working at Draper Laboratory, Cambridge, MA, May-August 2000.)

@Article{dechter91:_tempor_const, author = {Rina Dechter and Itay Meiri and Judea Pearl}, title = {Temporal Constraint networks}, journal = {Artificial Intelligence}, year = 1991, volume = 49, pages = {61--95} }

Leading Passes

A significant difference between ATT-CMUnited-2000 and its predecessors is that ATT-CMUnited-2000 introduces the concept of a leading pass. In the past, most teams have only considered passing the ball directly to a teammate. However, there is a potentially large advantage to be gained by passing the ball in such a way that the teammate can "run on" to the ball.
ATT-CMUnited-2000 searches hundreds of possible passes to each receiver to find the one that maximizes a score based on probability of reception and strategic value of the resulting position. This search requires computing the points and times at which teammates and opponents could intercept each pass. Forward simulation methods that reason about discrete simulator cycles, such as those used by past champion teams Humboldt and CMUnited, are not computationally efficient enough to evaluate hundreds of potential passes (although they are very effective and tractable for evaluating small numbers of passes). ATT-CMUnited-2000 abstracts the simulation to continuous time and uses a modified Newton's method to efficiently approximate earliest interception times, thus permitting hundreds of pass evaluations per simulator cycle. Leading pass options are also compared with self passes (dribbles) and shot options and the "best" action is selected.

The Software

The low level code of ATT-CMUnited-2000 is based almost entirely on CMUnited-99. Source code is available from the CMUnited-99 page. You may also run ATT-CMUnited-2000 as it ran in Melbourne.
Download the tarred, gzipped executables for Linux. A README file with instructions on how to start the clients is included.
Additional packages are available for download from the CMUnited-99 page.

Simulator Team Homepage | RoboSoccer Project Homepage | Computer Science Department | School of Computer Science

	People Patrick Riley, Peter Stone, David McAllester, Manuela Veloso
	Results ATT-CMUnited-2000 is the RoboCup-2000 Simulator League 3rd Place Team! The tournament included 34 teams from around the world. Over the course of 8 games, ATT-CMUnited-2000 outscored its opponents by a combined score of 26-11. Results of RoboCup-2000 are available from the main RoboCup homepage and from the RoboCup-2000 page.
	Accelerators Summary \| On-line Planning for Set Plays \| Leading Passes \| Software
	Summary The ATT-CMUnited-2000 simulator team is based upon the CMUnited-99 simulator team, which in turn is based on CMUnited-98. In particular, it uses all of the techniques that are described in detail, with pointers to relevant publications, on the CMUnited-98 simulator team page: (1) Hierarchical machine learning (Layered learning) (2) Flexible, adaptive formations (Locker-room agreement) (3) Single-channel, low-bandwidth communication (4) Predictive, locally optimal skills (PLOS) (5) Strategic positioning using attraction and repulsion (SPAR) Our goal in creating ATT-CMUnited-2000 was to investigate new research directions. These contributions are described in detail in our team description paper that is included in the source code and binary distributions below.
	On-Line Planning for Set Plays ATT-CMUnited-2000 uses dynamic, adaptive planning for set-plays. Previously, the plans executed for set-plays were fixed, with very little variability. The coach for ATT-CMUnited-2000 makes a new plan for player and ball movement at every offensive set play. The plan is made by using local search over a set of given starting paths. The plan is represented as a Simple Temporal Network, as introduced by Dechter, et al. The use of Simple Temporal Networks as a multi-agent plan formats appears to be a novel application. Further, the planning depends on a model of opponent movement. We create a set of models by hand offline and then select between the models on-line. The model selection is done using probabilistic techniques which are close to a Bayesian update of the probability distribution over the models. For defensive set plays, the coach makes the assumption that future plays will be like past plays and instructs the players to move to locations that would have been good for previous plays. For example, if the opponents free kick set play always goes directly towards the goal first, the coach will put a player directly on that path. (The on-line planning work was done by Patrick Riley in part while working at Draper Laboratory, Cambridge, MA, May-August 2000.) @Article{dechter91:_tempor_const, author = {Rina Dechter and Itay Meiri and Judea Pearl}, title = {Temporal Constraint networks}, journal = {Artificial Intelligence}, year = 1991, volume = 49, pages = {61--95} }
	Leading Passes A significant difference between ATT-CMUnited-2000 and its predecessors is that ATT-CMUnited-2000 introduces the concept of a leading pass. In the past, most teams have only considered passing the ball directly to a teammate. However, there is a potentially large advantage to be gained by passing the ball in such a way that the teammate can "run on" to the ball. ATT-CMUnited-2000 searches hundreds of possible passes to each receiver to find the one that maximizes a score based on probability of reception and strategic value of the resulting position. This search requires computing the points and times at which teammates and opponents could intercept each pass. Forward simulation methods that reason about discrete simulator cycles, such as those used by past champion teams Humboldt and CMUnited, are not computationally efficient enough to evaluate hundreds of potential passes (although they are very effective and tractable for evaluating small numbers of passes). ATT-CMUnited-2000 abstracts the simulation to continuous time and uses a modified Newton's method to efficiently approximate earliest interception times, thus permitting hundreds of pass evaluations per simulator cycle. Leading pass options are also compared with self passes (dribbles) and shot options and the "best" action is selected.
	The Software The low level code of ATT-CMUnited-2000 is based almost entirely on CMUnited-99. Source code is available from the CMUnited-99 page. You may also run ATT-CMUnited-2000 as it ran in Melbourne. Download the tarred, gzipped executables for Linux. A README file with instructions on how to start the clients is included. Additional packages are available for download from the CMUnited-99 page.