pdftohtml_folder/2009_ETDP_CMDragons-html.html

CMDragons 2009 Extended Team Description

Stefan Zickler, James Bruce, Joydeep Biswas,

Michael Licitra, and Manuela Veloso

Carnegie Mellon University

{

szickler,jbruce,veloso

}

@cs.cmu.edu

{

joydeep,mlicitra

}

@andrew.cmu.edu

Abstract.

In this paper we present an overview of CMDragons 2009,

Carnegie Mellon’s entry for the RoboCup Small Size League. Our team
builds upon the research and success of RoboCup entries in previous
years. Our team’s success can be contributed to a well-balanced combi-
nation of sophisticated robot hardware and a layered, intelligent software
architecture consisting of computer vision, multi-robot play selection, as
well as single robot tactics and navigation.

Introduction

Our RoboCup Small Size League entry, CMDragons 2009, builds upon the on-
going research used to create the previous CMDragons teams (1997-2003,2006-
2008) and CMRoboDragons joint team (2004, 2005). Our team entry consists of
five omni-directional robots controlled by an offboard computer. Sensing is pro-
vided by two overhead mounted cameras linked to the offboard computer. The
software then sends driving commands to the individual robots. This first half
of this paper describes the robot and vision hardware of the system. The second
half of this paper describes the overall architecture and individual components
of the offboard control software required to implement a robot soccer team.

Hardware

The modern Small Size League has brought along many challenging demands
on hardware. To perform well as a team, robots need to be reliable, fast, and
accurate in their actuations. Similarly, global vision sensing needs to not only
be low-latency, but also needs to have sufficient resolution to accurately localize
the robots and the ball on the relatively large field. This Section describes these
hardware components of our system.

2.1

Vision

In previous years, the CMDragons team has relied heavily on traditional off-the-
shelf camcorders in conjunction with low-cost capture cards as its vision system.
Our previous hardware delivered a 640

240 pixel video stream at 60Hz. The

Each motor has a reflective quadrature encoder for accurate wheel travel and
speed estimation. The kicker is a large diameter custom wound solenoid attached
directly to a kicking plate, which offers improved durability compared to designs
using a standard D-frame solenoid. The kicker is capable of propelling the ball
at speeds up to 15

m/s

, and is fully variable so that controlled passes can also be

carried out. The CMDragons robot also has a chip-kicking device in the style of
FU-Fighter’s 2005 robot design. It is a custom-made flat solenoid located under
the main kicker, which strikes an angled wedge visible at the front bottom of
the robot. The wedge is hinged and travels a short distance at a 45% angle from
the ground plane, driving the ball at a similar angle. It is capable of propelling
the ball up to 4

before it hits the ground. Both kickers are driven by a bank

of three capacitors charged to 200

. The capacitors are located directly above

the kicker and below the electronics, leading to our unusual mechanical design
which lacks a single connected “midplate”. By using a slightly thicker baseplate,
and several partial midplates with multiple standoffs for support, we were still
able to design a highly robust robot.

Ball catching and handling is performed by a motorized rubber-coated drib-

bling bar which is mounted on an hinged damper for improved pass reception.
The dribbling bar is driven by a brushless motor so that it can achieve a high
speed without sacrificing torque. The hinged damper can also be retracted us-
ing a small servo. This is used during certain kicking maneuvers, so that the
dribbling bar does not interfere with speed or accuracy.

Fig. 2.

Top view of the robot drive system, kicker, and dribbler.

Fig. 4.

The general architecture of the CMDragons offboard control software.

Software

The software architecture for our offboard control system is shown in Figure 4.
Our entire software architecture has been written in C++ and currently runs
under Linux. It follows the same overall structure as has been used in the previous
year, outlined in [1, 2]. The major organizational components of the system are
a server program which performs vision and manages communication with the
robots, and two client programs which connect to the server via UDP sockets.
The first client is a soccer program, which implements the soccer playing strategy
and robot navigation and control, and the second client is a graphical interface
program for monitoring and controlling the system. The details of the soccer
program are described in the following Sections.

The server program consists of vision, tracker, radio, and a multi-client server.

In past years, the vision system used CMVision2 for low-level image segmenta-
tion and connected region analysis [3, 4] with an efficient and accurate algorithm
for pattern detection described in [5]. This year, however, we are intending to
transition to the new, and still experimental, SSL shared vision system. Some
of the integration details are described in Section 3.1 of this paper. Tracking is
achieved using a probabilistic method based on Extended Kalman-Bucy filters
to obtain filtered estimates of ball and robot positions. Additionally, the filters
provide velocity estimates for all tracked objects. Further details on tracking are
provided in [6]. Final commands are communicated by the server program using
a radio link as described in Section 3.2. Alternatively to running the server which
observes and interfaces with the actual robots, it is also possible to employ the
simulator which appears semantically identical to the server, but uses an inter-
nal, physics-based world model. The details of this simulator are described in
Section 3.3.

3.1

Vision

Coincidental with the improvement of vision hardware, CMDragons 2009 has
also switched its image processing software to the new Small Size League Shared
Vision System,

SSL-Vision

. This vision system is currently under heavy devel-

opment by volunteers from several teams, including CMDragons. SSL-Vision is
released as open source and is therefore available to all teams. In order to use
SSL-Vision, the “Vision” component in Figure 4 is effectively being replaced
with a network client that receives packets from the SSL-Vision system. These
packets will contain the locations and orientations of all the robots, as well as
the location of the ball. However, data fusion of the two cameras and motion
tracking will continue to be performed within our system, as SSL-Vision does
not currently support such functionality.

For competing in RoboCup 2009, SSL-Vision should provide several advan-

tages compared to CMDragons past year’s system. One major improvement is
the geometry calibration of the cameras. Our previous system required the use of
paper calibration patterns to be carefully placed on the field for calibration pur-
poses. SSL-Vision does not require any such calibration patterns and can be fully
calibrated through its user interface. Another improvement is that SSL-Vision
provides direct access to all DCAM parameters of our Firewire cameras, thus
allowing configuration of settings such as exposure, white balance, or shutter
speed, during runtime. Finally, SSL-Vision contains a very open and extendible
architecture, allowing the interchangeability of different image processing “plug-
ins”. This will allow teams to develop their own improvements and extensions to
the system, such as faster image processing algorithms or improved calibration
routines. It furthermore allows quick switching and performance comparisons
between such plugins.

Even though these improvements sound very promising, there is a poten-

tial risk of transitioning to SSL-Vision: the system is still very new, its source
base is still under heavy development, and has had little real-world testing. We
feel however, that the benefits of SSL-Vision greatly outweigh its risks, and we
furthermore hope that our early adoption of the system will provide a positive
example and impact on the Small Size League, leading to a quick maturation of
the system.

3.2

Wireless Communication

Wireless communication with the robots is performed in the 902-927 MHz fre-
quency range through the Linx HP3 module connected via a standard serial port.
The CMDragons robots are fully equipped with both receivers and transmitters
which provides them with bi-directional communication abilities, thus not only
allowing the central software to control the robots, but also allowing the con-
trol software to receive IR sensor feedback and battery status from the robots.
However, due to the added latency of these robot observations, the system relies
mostly on one-way communication for control only. Sensor observations however,
are used if vision data becomes unavailable (e.g. in case of occlusion).

3.3

Simulator

Being able to accurately simulate robot behaviors is an integral part of our
team’s development cycle. Simulation allows rapid testing of new code without
the need to impose drain on our robotic hardware. Additionally, it allows us to
simulate scenarios which we are unable to recreate by our limited number of
physical robots, such as full five-on-five RoboCup games. In recent years, our
ball-manipulation capabilities and behaviors have become very sophisticated.
Our strategies often rely on complex dynamics interactions such as deflecting a
ball off from opponents. The introduction of chip-kicks has added the additional
requirement of three-dimensional simulation. Finally, many of our most recent
behaviors rely heavily on our robots’ ball-dribbling capabilities, and thus should
also be accommodated in a simulated model.

In order to model such behaviors, we use a simulator that is able to compute

complex rigid body dynamics. Various free and commercial simulation engines
exist to perform this task. We chose NVIDIA’s PhysX as our simulation engine
of choice due to its performance and ease of use, but other candidates such as
e.g. the Open Dynamics Engine (ODE) might be equally suited. The concept
of such simulation engines is that, given a scene of rigid-bodies and a set of
initial positions and velocities, we can apply forces and torques to arbitrary
objects in the scene. The engine will then integrate the scene forward in time,
automatically resolve any rigid-body interactions (such as collisions) using basic
Newtonian physics, and finally provide us with a new state of positions and
velocities. Our simulator is able to act as a full replacement of the standard
server depicted in Figure 4, thus processing the soccer-system’s commands and
returning the newly observed state of the world.

Fig. 5.

A diagram of the simulated dribbling model and its parameters.

Our robots are modeled using a convex triangulated shell in combination with

other convex rigid-body primitives. The golf-ball is approximated by using a sim-
ple sphere. In order to achieve accurate dynamics simulations, it is important

that we have an adequate model of our robot’s ball-handling capabilities. One
particularly challenging issue is to correctly model the robots’ dribbler-bar. One
approach is to model the dribbler implicitly, by defining a motorized, rotating,
high-friction cylinder which is connected to the robot by using a rotary joint. In
practice however, this approach failed to accurately model the dribbling behav-
ior, possibly due to the accumulation of joint-error and an insufficient simulated
torque transfer between the bar and the ball. The approach we took instead
was to model the dribbling action explicitly: if the ball is in contact with the
dribbler-bar then we directly apply a torque to the ball facing towards our robot.
The exact dribbling behavior can be controlled by modifying the various vari-
ables that affect the ball’s dynamics. A diagram of the dribbling model is shown
in figure 5. The applied torque is depicted as

. Variables that affect our ball,

are the friction in relation to the floor

and in relation to the dribbler bar

The dribbler bar uses an anisotropic friction model, defining low friction against
the vertical direction of the bar (thus, roughly simulating a freely spinning bar),
and higher friction against the horizontal direction of the bar (thus modeling
the high friction of the bar’s rubber). In addition to friction, we can control the
ball’s coefficient of restitution against the dribbler and the floor respectively.
Naturally

will have a fairly low coefficient, thus roughly modeling the drib-

bler’s softness and dampening, whereas

will have slightly higher coefficient to

model the bounciness of the carpet. Additional constants in our physics model
are angular and linear damping of both the robot and ball, thus simulating air-
drag. The robot’s motions are simulated explicitly as well. Instead of modeling
the wheels which will impose friction on the floor, we model the robot as having
a flat, low-friction base-plate. We then directly apply forces and torques to the
robot to simulate its motions. Kicks and chip-kicks are simulated in a similar
fashion, by exerting linear impulses directly on the ball. A simulated sequence
of one of our robots performing a “dribble and fling”-maneuver can be found in
figure 6.

Fig. 6.

A simulation sequence of a “dribble-and-fling” behavior.

It should be noted that currently, all of the variables have been tweaked

experimentally to obtain a relatively accurate model of the robot. In the future,
it will be interesting to employ supervised learning techniques to automate this
task.

3.4

Behavior

The three major components of the soccer behavior control system are: (1) world
state evaluation and play selection; (2) skills and tactics; (3) navigation.

1. World state evaluation involves determining high level states about the

world, such as whether the team is on offense or defense. This allows us
to select among a set of possible plays [7]. It also involves finding and rank-
ing possible subgoals, such as evaluating a good location to receive a pass.

2. Tactics and skills implement the primitive behaviors for a robot, and can

range from the simple “go to point” skill, up to complex tactics such as “pass”
or “shoot”. A

role

in our system is defined as a tactic with all parameters

fully specified, which is then assigned to a robot to execute. The executed
tactic generates a navigation target either directly or by invoking lower level
skills.

3. The navigation module takes the targets specified by tactics and plans a path

using a randomized path planner. The path is then processed by motion con-
trol and dynamic obstacle avoidance to generate robot velocity commands.
These resulting commands are sent to the robots by a radio link.

In order to take advantage of opportunities as they arise in the dynamic

environment of a competitive soccer game, the entire control system executes at
60 times a second, synchronously with the vision system. This requires all of the
cooperating components to run within a real-time constraint.

Teamwork

Multi-robot domains can be categorized according to many different

factors. One such factor is the underlying parallelism of the task to be achieved.
In highly parallel domains, robots can complete parts of the task separately,
and mainly need to coordinate to achieve higher efficiency. In a more serialized
domain, some part of the problem can only be achieved by one robot at a time,
necessitating tighter coordination to achieve the objective efficiently. Robotic
soccer falls between parallel and serialized domains, with brief periods of joint
actions. Soccer is a serialized domain primarily due to the presence of a single
ball; At any given time only one robot from a team should be actively handling
the ball. In a domain such as soccer, multi-robot coordination methods need
to reason about the robot that actively addresses the serial task and to assign
supporting objectives to the other members of the team. Typically, there is one

active

robot with multiple robots in

supporting

roles. These supporting roles add

a parallel component to the domain, as supporting robots can execute actions
in a possibly loosely coupled way to support the overall team objective.

Multi-Robot Role Assignment

A large number of methods exists for task

assignment and execution in multi-agent systems. [8] provides an overview and
taxonomy of task assignment methods for multi-robot systems. [9] points out
the direct conflicts that can arise between multiple executing behaviors, as well
as complications arising when the number of tasks does not match the number
of robots. [10] present a cooperation method that handles tight coordination in
robot soccer using messaging between the behaviors controlling each agent. The
STP architecture [6] describes another method of cooperation using centralized
plays and communicating single-robot behaviors.

In addition to the assignment of tasks to agents, their still lies the problem of

describing how each agent should implement its local behavior. [11] presents an
artificial potential field for local obstacle avoidance. There are limitations of di-
rect local execution of potential functions however [12], including local minima in
the potential field gradient and the inability to represent hard action constraints.
The SPAR algorithm [13], describes a method combining binary constraints with
linear objective functions to define a potential over the workspace, but is only
used for navigation target selection rather than direct actions.

Task allocation in our system follows the STP model [6]. Our systems adopts

a split of active and support roles and solves each of those subtasks with a
different method. Active roles which manipulate the ball generate commands
directly, receiving the highest priority so that supporting roles do not interfere.
Supporting roles are based on optimization of potential functions defined over
the configuration space, as in SPAR and later work. With these two distinct
solutions, part of our system is optimized for the serialized aspect of ball han-
dling, while another part is specialized for the loosely coupled supporting roles.
We address the need for the even more tight coupling that is present in passing
plays through behavior dependent signalling between the active and supporting
behaviors as in [10].

Objective Evaluation Functions

In our system, the navigation targets of

supporting roles are determined by world state evaluation functions defined over
the entire soccer field. Each function holds the world state external to a robot
constant, while varying the location of the robot to determine a real valued
evaluation of that state within the workspace. Hard constraints are represented
using multiplicative boolean functions, whereas soft constraints are modelled as
general real-valued functions.

Passing Evaluation

An example of the general form of the pass position eval-

uation function is given in Figure 7. There are several variables given the current
world state and a point

to evaluate:

–

is the reachable area, which is defined by the perpendicular distance the

robot can travel in the time it takes a pass to reach a perpendicular centered
on

–

is the subtended angle of

from the current ball location

Fig. 7.

An example demonstrating the pass evaluation function inputs. The input

values for evaluating a point

are the subtended angle

of the reachable area

, the

unobstructed goal angle

, and the angle

between the pass and shoot centerlines.

These are combined in specific evaluation functions to achieve the desired behavior.

–

is the angular width of the free angle toward the goal from point

–

is the angle between the pass from the ball to

, and the shot from

the center of the free angle on the goal

Using this general model, we can define several types of passes:

– A one-touch pass-and-shoot which intercepts the moving ball to kick it at the

goal. This estimates the a time

as the pass length divided by the pass speed,

plus the shot length divided by the shooting speed. An angular preference

(

) is calculated which increases linearly from 0 at

= 0 to 1 at

= 45

◦

It stays at 1 until

= 90

◦

, where is decreases rapidly to 0. The evaluation

is then [

(

) min (

a, b

)

– A pass-receive-turn-shoot which explicitly receives the ball and then aims

and shoots. The estimates the

as the sum of the pass time, turning time

for

, and shot time. The evaluation using this

is [min (

a, b

)

– Partial chip-pass variants of the above passing methods, where a chip shot

is used to pass partway to the receiver, but dropping soon enough that it
will roll by the time it reaches the receiver. These are used when a robots
blocks the direct passing path.

– A direct chip deflection “header”. Here a chip pass is calculated to a reachable

robot position (a part of

), with a target point that passes over

at a height

midway up the robot. The robot will deflect the ball directly into the goal,
so the pass and shoot speed are identical. The evaluation is then identical
to the one-touch pass-and-shoot evaluation.

The resulting plots from two example passing situations are shown in Fig-

ure 8, with the pass evaluation function for one-touch pass-and-shoot overlaid
on a field. The location of the ball and other robots causes very different target
locations to be selected by the supporting robot. Because large portions of the
field are covered by a continuous evaluation, the existence of an unobstructed
maximum is likely.

Fig. 8.

Two example passing situations are shown with the passing evaluation metric

overlaid. The values are shown in grayscale where black is zero and the maximum value
is white. Values less than 0.5% of the maximum are not drawn. The maximum value
is indicated by the line extending from the supporting robot.

Properties

While the exact parameters and weights applied in evaluation func-

tions are highly application dependent, and thus not of general importance, the
approach has proved of useful throughout many revisions of our system. In par-
ticular, with well designed functions, the approach has the useful property that
large areas have a nonzero evaluation. This provides a natural ranking of alter-
native positions so that conflicts can be resolved. Thus multiple robots to be
placed on tasks with conflicting actions, or even the same task; The calculation
for a particular robot simply needs to discount the areas currently occupied by
other robots. Direct calculation of actions, as is used for active roles, does not in-
herently provide ranked alternatives, and thus leads to conflicting actions when
other robots apply the same technique.

3.5

Action Execution

Numerous low level skills are required to implement a robot soccer team. Many
of the skills such as shooting on a goal and described in other work on robot

soccer, such as in [6]. Two of the more unique parts of our system are the delta-
margin metric for choosing when to kick a ball with aiming a shot, and the
one-touch pass-and-shoot method to achieve the robot soccer equivalent of the
“one-touch” goal shot from human soccer.

Delta-Margin Shooting Metric

The shooting metric is a skill that must de-

termine the appropriate time of energizing the kicking device to execute an aimed
shot. The input to the shooting metric is a range of angles [

, g

] representing

the target, along with the robot’s current angle

(

). This data is provided each

frame as a data stream, and the output of the metric is the a binary value of
whether to kick or not. During this time, the robot will position itself to aim
at the center of the angular range. This problem is similar to an automated
assembly task where a part is positioned and then dropped into place. In both
cases, there is a tradeoff between probability of correct placement (i.e. within
tolerance), and the time used in positioning. Ideally we would like something
that maximizes the probability of correct placement while minimizing the total
time taken in positioning. In the robot soccer environment, this is complicated
by the fact that the target angles can change as a function of time [

(

)

, g

(

)].

This situation is similar to an assembly task where both parts to be mated are
moving.

Our method for shooting relies on the assumption that the probability of

shooting within the tolerance is proportional to the margin, where the margin is
defined as the angular distance to the nearest edge of the target range. Formally,
we can define the margin function

(

) as shown in Equation 1, which in turn

depends on the angle normalization function

(

) = max [

(

)

−

(

))

, N

(

)

−

(

))]

(1)

(

) =











(

+ 2

)

a <

−

π,

(

−

)

a >

π,

otherwise

(2)

Using the definition of

(

), we can define the binary shooting function

(

)

as shown in Equation 3. The first case will prevent shooting unless the margin is
within the tolerances The second case case will shoot when the margin is nearer
to the optimal margin than the constant fraction

(we use

= 0

9). The third

case, which is the primary contribution of this method, prevents shooting as long
as the margin is increasing with time. In all remaining cases the metric will elect
to shoot.

(

) =











(

)

(

)

> β

(

)

−

(

))

(

)

> m

(

−

otherwise

(3)

This method has worked extremely well in practice, as it appears to strike a

good balance between the conflicting options of shooting as early as possible (to
capture short-lived opportunities) and waiting to improve the aim (thus lower
the probability of missing the target.) Though simple to compute, the method
captures all of the following qualitative properties:

– Try to aim for the center of the target angular range.
– If an angular range is widening, delay shooting since the miss probability is

dropping with time.

– If an angular range is narrowing, take the shot since the miss probability is

increasing with time.

– If aiming past a moving object (such as a goalkeeper), delay shooting iff our

goal probability is improving faster than the opponent is decreasing it.

Two examples of the shooting method executing on a real robot are shown

in Figures 9 and 10, with the relevant variables plotted over time until the kick
is taken. The experiment setup was a single robot 1.5m from an open goal. In
the first example, the margin increases to the maximum, and the kick is taken
due to the zero crossing of the margin delta. In the second example, the margin
stops improving so the shot is taken before the maximum (the ball was rolling
away from the robot causing its aim to stop improving).

-1.0

-0.8

-0.6

-0.4

-0.2

0.0

0.2

0.4

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1.0

1.1

angular margin (rad)

time (sec)

optimal

minimum

margin delta

margin

Fig. 9.

An example plot of the delta-margin shooting metric reaching a maximum

margin. Shot is taken at

= 1

15.

One-touch Aiming

The one-touch pass-and-shoot skill is a method for inter-

cepting a moving ball to shoot it at the goal, and corresponds to a “one-touch”
strike in human soccer. This skill combines our existing ball interception and

-1.0

-0.8

-0.6

-0.4

-0.2

0.0

0.2

0.4

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1.0

1.1

angular margin (rad)

time (sec)

optimal

minimum

margin delta

margin

Fig. 10.

An example plot of the delta-margin shooting metric reaching a zero-crossing

of the margin delta. Shot is taken at

= 1

target selection routines with a method for determining the proper angle to aim
the robot to accurately redirect the ball to the target. In order to calculate the
proper aiming angle, a model of how interaction with the kicker will affect the
speed of the ball is needed. In particular, while the kicker adds a large forward
component to the ball velocity, effects from the ball’s original (incoming) velocity
are still present and non-negligible.

The system model is shown in Figure 11.

and

represent the normalized

robot heading and perpendicular, respectively. After exploring numerous options
to determine the final ball velocity (

), the model chosen was a weighted sum

of three components:

– Initial ball velocity

damped by the dribbling device. This is a tangential

velocity along

, or (

)

, which is scaled by a damping factor

∈

1].

– Initial ball velocity

reflected by the robot heading

. This is expressed

as vector reflection of

, scaled by a constant

∈

1].

– Additive velocity imparted by the kicker along

. The kicker provides an

impulse that would propel a ball at rest to speed

(i.e.

= 0

→ k

). Because the kicker is attached to the moving robot,

is the sum of the

kicking device speed and the speed of the robot along

Using this model, we can estimate

as:

(

)

(

−

)

) +

(4)

We determined the model parameter values experimentally, by recording the

incoming and outgoing velocity at a variety of angles and kick speeds, and calcu-
lating the most likely values. We found that

= 0

1 and

= 0

5 best modelled

Fig. 11.

The model for one-touch pass-and-shoot. The final velocity of the ball

contains a component of the initial velocity

, and thus is not parallel to the robot

heading

the data, but these values are likely to be dependent on the exact robot de-
sign, and can even be affected by the field surface. The calibration procedure is
straightforward however, so we have not found this to be a major limitation.

Of course, the forward model alone is not sufficient, as the control problem

requires solving for the robot angle given some relative target vector

. To invert

the model, we use bisection search. The bounding angles for the search are the
original incoming ball angle (where the residual velocity component would be
zero) and the angle of target vector

(where we would aim for an ideal kicker

with total damping (

= 0

, γ

= 0). The actual solution lies between these limits,

and we can calculate an error metric

by setting up Equation 4 as a function of

the robot angle

(

) =

cos

α,

sin

(

) =

h−

sin

α,

cos

(

) =

(

)

(

) +

(

) +

(

−

(

))

(

))

(5)

(

) = ˆ

(

)

(6)

Thus when

(

)

0 the solution lies with

closer to

, while if

(

)

the solution is closer to

. A solution at the value of

where

(

) = 0, so

bisection search is simply terminated whenever

(

)

. While it is possible

to invert the model so that search is not required, using a numerical method
for determining

allowed rapid testing of different models and parameters. The

complexity of the approximation is

(log(1

)), which has proven adequately

fast in practice.

We have found the one-touch aiming method to work with passes between

m/s

and 4

m/s

, and has proven quite a bit faster than a more explicit receive-

turn-shoot approach. The main limitation of the approach is that the angle
between the pass and the shot on goal should generally lie between 30 and 90

degrees. The receive-turn-shoot approach can be used in cases where the angle
is not amenable to the pass-and-shoot approach.

We also adapted the 2D version of one-touch aiming to the 3D problem

of soccer “headers”. The chip kicker is used to kick the ball in the air, and
a dynamics model of the ball fit a parabolic trajectory to the observed ball
position. This allows a robot to intercept a ball while still in the air to deflect it
into a goal. Because the kicker is not used, the model for aiming is pure reflection
(

= 0

, γ

= 1

0). The interception method used is to drive to the point where

the ball will reach a particular height above the ground (halfway up the flat part
of the robot’s protective cover). Due to the decreased accuracy of chip kicks, this
type of pass normally does not allow the receiving robot to remain at a fixed
location, and depends heavily of the receiving robot adjusting to intercept the
ball. Despite the low probability of a successful pass compared to other methods

[success] = 0

3, when it succeeds it has a high chance of scoring as it leaves

little time for the receiving team to react.

Fig. 12.

An example header from the RoboCup 2006 semi-final match. Robot A passes

to robot B, which then deflects the ball into the goal. Robot B chooses its angle using
one-touch aiming in order to deflect into the gap left by the goalkeeper.

3.6

Navigational Planning

The motion planner adopted for our navigational system is based on the RRT
family of randomized path planners. Our latest variant adopts additional modi-
fied features from RRT-Connect, and is called

Bidirectional Multi-Bridge ERRT

[14]. A basic RRT planner search for a path from an initial state to a goal state
by expanding a search tree. Table 1 shows the pseudo-code for a basic RRT
motion planner. It relies on three primitives which are defined for the domain.
First, the

Extend

function calculates a new state that can be reached from the

target state by some incremental distance (usually a constant distance or time),
which in general makes progress toward the goal. If a collision with an obstacle
in the environment would occur by moving to that new state, then a default
value, EmptyState, of type state is returned to capture the fact that there is

no “successor” state due to the obstacle. Next, the function

Distance

needs to

provide an estimate of the time or distance (or any other objective that the
algorithm is trying to minimize) that estimates how long repeated application
of

Extend

would take to reach the goal. Finally,

RandomState

returns a state

drawn uniformly from the state space of the environment. For a simple example,
a holonomic point robot with no acceleration constraints can implement

Extend

simply as a step along the line from the current state to the target, and

Distance

as the Euclidean distance between the two states.

function

RRTPlan

(env:

Environment

, initial:

State

, goal:

State

) :

RRTTree

var

nearest,extended,target :

State

var

tree :

RRTTree

nearest

←

initial

tree

←

initial

while

Distance

(nearest,goal)

threshold

target

←

ChooseTarget

(goal)

nearest

←

Nearest

(tree,target)

extended

←

Extend

(env,nearest,target)

extended

EmptyState

then

AddNode

(tree,extended)

return

tree

function

ChooseTarget

(goal:

State

) :

State

var

p :

←

UniformRandom

(0,1)

∈

GoalProb]

then return

goal

else if

∈

[GoalProb

then return

RandomState

()

function

Nearest

(tree:

RRTTree

,target:

State

) :

State

var

nearest :

State

;

nearest

←

EmptyState

;

foreach

State

∈

tree

Distance

(s,target)

Distance

(nearest,target)

then

nearest

←

return

nearest;

Table 1.

The basic RRT planner stochastically expands its search tree to the goal or

to a random state.

The RRT-Connect variant of RRT has demonstrated high performance for

one-shot queries when compared to other motion planners [15]. It combines bidi-
rectional search with an iterated extension step. In RRT-Connect, a random
target is chosen just as with a base RRT planner. However, instead of calling
the extend operator once, the RRT-Connect repeats the extension until either

the target point is reached, or the extension fails (such as when it would hit an
obstacle). The search is performed bidirectionally, with a tree growing from both
the initial and goal configurations. In each step, after a random target point is
chosen, one tree repeatedly extends toward that target, reaching some final con-
figuration

. The second tree then repeatedly extends toward

(as opposed to

the random target), in an operation referred to as

Connect

. After each iteration,

the tree swaps roles for extending and connecting operations, so that both the
initial and goal trees grow using both operations.

5600

5800

6000

6200

6400

avg. plan length (mm)

maximum repeated extensions

mean

90% confidence

Fig. 13.

The effect of repeated extensions in ERRT on plan length.

While these improvements can markedly improve RRT’s one-shot planning

time, they do have an associated cost. While RRT, with its single extensions,
tends to grow in a fixed rate due to the step size, RRT-Connect has a much
higher variance in its growth due to the repeated extensions. As a result, when
planning is iterated, RRT-Connect tends to find more widely varying homotopic
paths. This is not an issue for one-shot planning, but can become a problem for
iterated planning with interleaved execution. Thus ERRT adopts the improve-
ments of RRT-Connect, but modified somewhat. First, ERRT supports repeated
extensions, but only up to some maximum constant, which can be tuned for the
domain. Figure 13 shows the effect of this parameter on the average plan length
for a domain. Each datapoint is includes the mean and confidence interval for
300 test runs, where each run represents 240 iterated plans in a small-size do-
main with 64 random rectangular obstacles. The initial and goal positions were
varied with sinusoidal motion. As the number of extensions increases, the plan
average length grows. While applications can apply smoothing to remove some
of the inefficiency of less optimal plans, a shorter plan is more likely to be in

6800

6900

7000

7100

7200

7300

7400

7500

7600

7700

avg. plan length (mm)

target number of bridges

mean

90% confidence

Fig. 14.

The effect of multiple connection points in ERRT on plan length.

the same homotopy class as the optimal plan. Thus plan length is at least one
indicator of the reachable length even after smoothing, and stability in the ho-
motopic path is important for interleaved execution of the plan. Thus repeated
extensions, while they may speed planning, may come at the expense of average
plan length. ERRT, by using a tunable constant to set the maximum number
of extensions, allows the system designer to trade off between the two. In most
applications, we have used a value of 4, and found it to represent a reasonable
compromise.

ERRT also adopts the notion of the connect operation from RRT-Connect,

however this can also cause plan length to suffer. ERRT again offers a way to mit-
igate this with a tunable parameter, which is the number of connections between
the initial and goal trees before planning is terminated. Thus, ERRT allows mul-
tiple connection points, and can choose the shortest path of those available when
planning terminates. Implementing such a feature represents an important de-
parture from RRT however; with multiple connections the connected planning
“tree” is actually now a graph. This does not pose any significant theoretical
problems to RRT, but requires the implementation to support graph operations
efficiently instead of the normally faster tree operations. When planning ter-
minates, A* search is used over the resulting graph. The effect of varying the
number of connection points is shown in Figure 14. The methodology is the same
as used for the maximum repeated extensions, but using the domain

RandCircle

As can be seen, increasing the number of connections improves the plan length,
although the effect decreases after 6-8 connection points. Multiple connection
points by definition increase planning execution time, since ERRT continues to
search even after a path has been found. However, after the first connection,

ERRT can operate in a purely any-time fashion, using up idle time in the con-
trol cycle to improve the solution, but able to terminate and return a valid
solution whenever it is needed. Again, by offering the number of connections as
a parameter, the tradeoff can be set by the system designer.

Supporting multiple extensions and multiple connection points give ERRT

the benefits of RRT-Connect, as well as the ability to tune the system as needed.
By supporting a graph representation instead of search trees, as well as planning
over the resulting roadmap graph, ERRT takes a step toward unification with the
PRM family of planners. The only differences that remain are in the sampling
strategies for building and maintaining the search graph or roadmap structure.

Conclusion

Competition

Result

US Open 2003

1st

RoboCup 2003

4th

RoboCup 2004

4th

RoboCup 2005

4th

US Open 2006

1st

RoboCup 2006

1st

China Open 2006 1st
RoboCup 2007

1st

US Open 2008

1st

RoboCup 2008

2nd

Table 2.

Results of RoboCup small-size competitions for CMDragons from 2003-08

This paper gave an overview of CMDragons 2009, covering both the robot

hardware and the software architecture of the offboard control system. The hard-
ware has built on the collective experience of our team and continues to advance
in ability. The software uses our proven system architecture with continued im-
provements to the individual modules. The CMDragons software system has been
used in three national and seven international RoboCup competitions, placing
within the top four teams of the tournament every year since 2003, and finishing
1st in 2006 and 2007. The competition results since 2003 are listed in table 2.
We believe that the RoboCup Small Size League is and will continue to be an
excellent domain to drive research on high-performance real-time autonomous
robotics.

Provided software component as part of a joint team with Aichi Prefectural Univer-
sity, called CMRoboDragons

References

1. Zickler, S., Vail, D., Levi, G., Wasserman, P., Bruce, J., Licitra, M., Veloso, M.:

CMDragons 2008 Team Description. In: Proceedings of RoboCup 2008

2. Bruce, J., Zickler, S., Licitra, M., Veloso, M.: CMDragons 2007 Team Descrip-

tion. Technical report, Tech Report CMU-CS-07-173, Carnegie Mellon University,
School of Computer Science (2007)

3. Bruce, J., Balch, T., Veloso, M.: Fast color image segmentation for interactive

robots. In: Proceedings of the IEEE Conference on Intelligent Robots and Systems,
Japan (2000)

4. Bruce, J.: CMVision realtime color vision system. The CORAL Group’s Color

Machine Vision Project

http://www.cs.cmu.edu/

jbruce/cmvision/

5. Bruce, J., Veloso, M.: Fast and accurate vision-based pattern detection and iden-

tification. In: Proceedings of the IEEE International Conference on Robotics and
Automation, Taiwan (May 2003)

6. Browning, B., Bruce, J.R., Bowling, M., Veloso, M.: STP: Skills tactics and plans

for multi-robot control in adversarial environments. In: Journal of System and
Control Engineering. (2005)

7. Bowling, M., Browning, B., Veloso, M.: Plays as effective multiagent plans enabling

opponent-adaptive play selection. In: Proceedings of International Conference on
Automated Planning and Scheduling (ICAPS’04). (2004)

8. Gerkey, B.P., Mataric, M.J.: A formal analysis and taxonomy of task allocation

in multi-robot systems. International Journal of Robotics Research

(9) (2004)

939–954

9. Uchibe, E., Kato, T., Asada, M., Hosoda, K.: Dynamic task assignment in a multi-

agent/multitask environment based on module conflict resolution. In: Proceedings
of the IEEE International Conference on Robotics and Automation. (2001) 3987–
3992

10. D’Angelo, A., Menegatti, E., Pagello, E.: How a cooperative behavior can emerge

from a robot team. In: Proceedings of the 7th International Symposium on Dis-
tributed Autonomous Robotic Systems. (2004)

11. Tilove, R.B.: Local obstacle avoidance for mobile robots based on the method of

artificial potentials. General Motors Research Laboratories, Research Publication
GMR-6650 (September 1989)

12. Koren, Y., Borenstein, J.: Potential field methods and their inherent limitations

for mobile robot navigation. In: Proceedings of the IEEE International Conference
on Robotics and Automation. (April 1991) 1398–1404

13. Veloso, M., Bowling, M., Achim, S., Han, K., Stone, P.: The CMUnited-98 cham-

pion small robot team. In: RoboCup-98: Robot Soccer World Cup II, Springer
Verlag (1999)

14. Bruce, J.R.: Real-Time Motion Planning and Safe Navigation in Dynamic Multi-

Robot Environments. PhD thesis, Carnegie Mellon University (Dec 2006)

15. James J. Kuffner, J., LaValle, S.M.: RRT-Connect: An efficient approach to single-

query path planning. In: Proceedings of the IEEE International Conference on
Robotics and Automation. (2000)