Construction of Players’ Action for Robocup Soccer
Using Graph Structured Program Evolution
Yasuaki Horima, Shinichi Shirakawa, Noriko Yata, and Tomoharu Nagao
Graduate School of Environment
and Information Sciences
Yokohama National University
Yokohama, Japan
Email: horima@nlab.sogo1.ynu.ac.jp

Abstract—In recent years, many researchers addressed multiagent system. Multi-agent system is the system consisted of multiple robots that have only limited capability. Robocup simulatedsoccer is proposed as a test bed of multi-agent system. It has asubtask called keepaway soccer. Automatic construction of thestrategy of multi-agent system is required because it is difficult.
Therefore, we purpose construction of the strategy for multiagent system by graph structured program evolution (GRAPE)
in keepaway soccer. GRAPE is the method of construction ofgraph-structured programs automatically.
Index Terms—Multi-agent system, Robocup soccer, Keepawaysoccer.

II. R ELATED WORKS
A. Keepaway soccer
Robocup simulated soccer has a subtask called keepawaysoccer. This is a task that robocup simulated soccer is simplified and a test bed for machine learning[3][4]. In keepawaysoccer, keepers try to keep possession of the ball for as longas possible. On the other hand, takers try to get possession of
the ball. Agents play in the limited rectangular area. Figure 1
shows overview of keepaway soccer.

I. I NTRODUCTION
Recently, autonomous robots have been put to practicaluse in our lives. In the future, multiple autonomous robots
will run in our environment. When multiple robots run,cooperation of multiple robots is important. It is called multiagent system that the system working by multiple agents suchas autonomous robots. Cooperative action enables robots towork more efficiently and to do tasks that are too hard to
do by a single robot. However, it is difficult to construct thecooperative action in an environment with multiple robots.
Therefore, it is required the method for automatic constructionof the cooperative action of robots.
Many researchers have acquired strategies of agents bymachine learning (e.g. genetic programming (GP)[15], reinforcement learning (RL)[16]). GP constructs tree structured strategies. Tree structure cannot construct algorithmsof reusing nodes but graph structure can do that. Therefore, it is proposed that methods automatically constructgraph-structured algorithm (e.g. GRAph structured Program
Evolution (GRAPE)[5][6], genetic network programming(GNP)[8]).
Robocup simulated soccer is proposed as a test bed formachine learning of multi-agent system[1][2]. This presents
the environment with simulated real elements. Soccer players
on the field are multiple agents. Agents using noisy and limited
data play soccer in the simulated field. Actions of agents andmovement of the ball are uncertain and unpredictable. Agents
must cooperate in these environments. In this paper, we aim toconstruct soccer actions of agents by using GRAPE in robocup
soccer.

Fig. 1.

Overview of keepaway soccer.

B. Methods of constructing graph-structured algorithms
Various methods of automatic construction of graphstructured algorithms was proposed such as GRAPE, GNP and
Genetic Automata Generation(GAUGE)[12] and so on. Graphstructured algorithms by them represented better expression
ability than tree structured algorithms by standard GP.
GNP and GAUGE are used for dynamic problems like thecontrol of agents. GAUGE selects pass and output by using
the value of memory. On the other hand, GNP selects different
output in the same situation by using the process of transitionof nodes as a memory. In addition, GNP has been proposed
various versions like adding RL[9], applying Automatically
Generated Macro Nodes (AGMs)[10] like automatically defined functions (ADFs)[11] and so on.
GRAPE is aimed at constructing arbitrary directed graphstructure, handling multiple data types using a data set andconverting phenotype of graph structure to genotype of an
integer string. It succeeded in constructing some programs forstatic problems like sorting[7], the computations of factorial,
Fibonacci sequence and exponentiation[5] et al. GRAPE and
GNP are expressly similar about some points. First, bothmethods define the number of available nodes and modify
combination of those nodes for searching better combination.
Second, a graph structure is able to convert a linear string ofintegers and evolution progress by modifying it. Moreover, theprocess of transition of nodes is important to construct more
effective algorithms. In this paper, using GRAPE construct algorithms for controlling agents as a dynamic problem because
GRAPE can control agents like GNP.
C. Graph structured program evolution
GRAPE constructs graph-structured algorithms automatically by combination of prepared nodes and alteration ofnodes. GRAPE is able to reuse nodes and construct thestructure of loops by reusing nodes. GRAPE consists ofphenotype that is graph structure, genotype that is a linear
string of integers and dataset that includes various types ofdata and is referred by nodes of graph structure. Figure 2
shows an example of the structure of GRAPE.
Structure of GRAPE
No.1

No.2

No.3

S

1

2

1

int

bool

list

x
x
x
1
1
…

0
0
0
1
1
…

list 0list 1list 2
list 3list 4
…

No.1
1

....

2

No.6
1

3

0

3

2

3

0

1

0

No.2

2

3

4

0

1

࣭Add data[0] to data[1] and write data[0]࣭Decide next node

࣭Go to node 2

ࠉusing data[0] and data[1]

int

0 x
1 y
… …

1

int

int

0 x+y
1 y
… …

0 x
1 y
… …

data set

data set3

2
if(data[0] > data[1])data set

Fig. 3.

Examples of processing (left) and branching nodes (right).

genotype of GRAPE is a linear string of integers. Therefore,
GRAPE is able to use a typical genetic algorithm (GA)[14].
GRAPE uses uniform crossover and mutation for a string ofintegers as genetic operators.
It uses the Minimal Generation Gap (MGG) model[13] asa generation alternation model. GRAPE with the MGG modelshows a higher performance than it with simple GA[5]. At the
MGG model, two individuals remain in parents and children
in a generation. One is the elitist individual and the other fromroulette-wheel selection. the MGG model can avoid initialconvergence and maintain the diversity of the population.

No.6

0

1

…

No.7

2

3

No.5

output: does not appear in phenotype
No.2
2

0

1

5

1

KEEPAWAY SOCCER
No.4

Genotype (integer string)
No.0
1

type connection argc

type connection argc

No.1

III. G RAPH STRUCTURED PROGRAM EVOLUTION FOR

start

data set
0
1
2
3
4
…

No.0

Examples of node

1

2

0

3

No.7
3

4

2

6

...

3

1

0

0

0

We need some modifications of GRAPE for the constructionof strategies in keepaway soccer. We allocate the perceptual
information to input data and action to “Output node”, branching by using input data to “Processing node” and “Branchingnode”. First, the name of objects in this paper shows in Fig4.
• Agent: the keeper in attention.
• K1: the nearest keeper form “Agent”.
• K2: the second nearest keeper form “Agent”.
• T1: the nearest taker form “Agent”.
• T2: the second nearest taker form “Agent”.

5

Fig. 2. Structure of GRAPE (phenotype) and the genotype, which denotes
a list of node types, connections and arguments. No.6 is the inactive node.

An algorithm that is constructed by GRAPE consists of“Start node”, “Processing node”, “Branching node” and “Output node”. “Start node” is the start of transition of nodes.
“Output node” is the end of transition of nodes and outputs
data. “Processing node” updates the data for problems by using
current that. “Branching node” branches by using that data.
Figure 3 shows example nodes in GRAPE. No.1 adds data[0]of an integer data type in dataset to data[1], the sum putsin data[0]. No.2 decides the next node using integer data[0]and data[1]. If data[0] is greater than data[1], connection 1 ischosen, else connection 2 chosen. Each node has information
about node types like “Processing” and “Branching node”,
operation of the node in each node type, arguments that decideusing data in dataset at the node. They are data of integers, so

Fig. 4.

Name of objects in this paper.

The total number of “Processing node” and “Branchingnode” is nine. “Processing node” and “Branching node” showsin Table I and Fig. 5. Those nodes branch by the operation ofeach node, so all prepared nodes of “Branching node” and“Processing node” are only “Branching node”. “BranchingTABLE I“P ROCESSING NODE ” AND “B RANCHING NODE ” FOR KEEPAWAY.

name
Keeper1 dist (K1D)
Keeper2 dist (K2D)
Taker1 dist (T1D)
Taker2 dist (T2D)
Keeper1 Taker dist (K1TD)
Keeper2 Taker dist (K2TD)
Keeper1 angle (K1A)
Keeper2 angle (K2A)
Random (Rnd)

operation
branch by distance from “Agent” to “K1”.
branch by distance from “Agent” to “K2”.
branch by distance from “Agent” to “T1”.
branch by distance from “Agent” to “T2”.
branch by distance from “K1” to nearest taker from “K1”.
branch by distance from “K1” to nearest taker from “K2”.
branch by angle consisting of “K1”,“Agent”and nearest taker from “K1”.
branch by angle consisting of “K1”,“Agent”and nearest taker from “K1”.
branch by probability.

number of connection
4
4
4
4
2
2
2
2
2

TABLE II“O UTPUT NODE ” FOR KEEPAWAY.

name
Go To Ball (GB)Hold Ball (HB)
Near Pass (NP)Far Pass (FP)
Angle Pass (AP)Get Open (GO)Recieve Move (RM)
Last Action (LA)Fig. 5.

the action of output
intercept the ball.
remain stationary with the ball.
pass to K1.
pass to K2.
pass by using angle information(Fig. 6).
go to free area(Fig. 6).
get courses of pass(Fig. 6).
operate previous “Output node”.

The detail of “Branching node” and “Processing node”.

node” uses the perceptual information and random numbers
to decide to select connections of node.
“Output node” has assumptions for output. If this is not
fulfilled, the transition of nodes continues till this is fulfilled.
To set assumptions restrains ineffective actions. It is importantfor keepaway soccer because an ineffective action causes
failure like failing in holding the ball and so on. “Output
node” shows in Table II. The number of “Output node” iseight such as “Hold Ball”(Remain stationary with the ball),“Go To Ball”(Intercept a ball) and so on. “Near Pass”, “FarPass”, “Hold Ball” and “Go To Ball” output the simple action
for the intended target. On the other hand, “Angle Pass”,“Get Open” and “Receive Move” go through some procedures
before output the action. “Angle Pass” decides the target forassumption for output“Agent” is nearest from the ball.
“Agent” is able to kick the ball.
“Agent” is able to kick the ball.
“Agent” is able to kick the ball.
“Agent” is able to kick the ball.
“Agent” can’t output “Go To Ball”.
“Agent” can’t output “Go To Ball”.
depend on previous “Output node”

Fig. 6.

Outline of some “Output node”.

pass by the judgement of angle that is formed by “Agent”,“K1” or “K2”, and the nearest taker from them before pass.
“Get Open” evaluates areas that are parts of playing area
devided into nine at first. Then, “Agent” goes to the area that
got the minimum value of evaluation. The way to evaluationof areas is to add points to each area and to reduce points
from each area. Points that are equal to the double number of
agents that are keepers except “Agent” and takers are added
to the area including those agents. Points that are equal to thenumber of those agents are added to areas adjoining the area
including those agents. In addition, One point is subtracted
from the area including “Agent”. “Receive Move” gets thesegment from “Agent” to keeper having the ball. “Agent”
moves to the direction that is vertical against that segment forincreasing the angle that consists of “Agent”, a keeper holding from the ball intercepts the ball and the other cut in on thethe ball and the nearest taker from “Agent”. Combination of course for pass. The strategies were evaluated by the ten times
those prepared nodes constructs graph-structured algorithms. average of time of keeping the ball by keepers. The processing“Output node” shows in Fig. 6.
steps of the experiment were as follows:
GRAPE is a method for static problem but keepaway soccer Step.1 Generate individuals of the first generation and evaluate
is dynamic problem. Therefore, algorithms by GRAPE output
them.
repeatedly in keepaway soccer. Previous “output node” is set Step.2 Select two individuals as parents and generate children
up as the start of transition of nodes because that allow agent
by crossover and mutation.
to decide next output considering previous output and branch Step.3 Evaluate children and select two individuals in parents
on condition. Without miss, keepaway soccer continues proand children.
ceeding. It is effective for keepaway soccer that an algorithm Step.4 Replace parents by selected individuals in parents andwithout the end of transition of nodes continues the transitionchildren.
of nodes.
Step.5 Repeat from Step.2 to Step.4 until the end of generaIn addition, we prepare multiple connections of “start node”
tions.
for keepers and each connection corresponds to each area for
The strategy was constructed according to this process. The
keepers starting keepaway soccer in Fig. 7 It allows keepers parameters of GRAPE were shown in tableIII.
to be pseudo heterogeneous keepers. A keeper starting froman area of those areas is able to use only one of connections.
TABLE III
PARAMETER OF GRAPEIn Fig. 7(b), Keeper using “1” of connections has the graph
Generations
15000
structure of “B” and “D”. Keeper using “2” of connections has
Individuals
20
the graph structure of “B” and “C”, so two keepers share the
The model of alternation of generations
MGG
structure of “B”. However, two keepers do not share all nodes,
Offspring10
so they have different algorithms. On the other hand, Keeper
Genetic operation
Only mutation
using “3” of connections has the structure of “A”, so the keeper
Mutation rate
0.05
has a specific algorithm. Keepers use each graph-structured
Max of nodes
35
Max of number of times for transition of nodes
1000
algorithm because agents start different areas. When keepawaysoccer starts, a keeper has the clear task that depends on
the area of start. Therefore, the pseudo heterogeneous graphstructured algorithm can work effectively for this task.
For experiments, we used the soccer server of Robocupthat is version 13.2.2[18] and Agent2d of version 2.1.0[17]for making keepers and takers. Agent2d is the template fordeveloping the soccer team for Robocup simulated soccer.
V. R ESULT AND D ISCUSSION
Figure 8 shows transitions of the keeping time. They are
increasing as the number of generations increase. Figure 9shows the best structure constructed by GRAPE for homogeneous keepers at the last generation.

Fig. 7.

Example of the pseudo heterogeneous graph structured algorithm.

IV. E XPERIMENTS
We constructed the strategy of keepers by GRAPE. Proposed method made two kinds of the strategies, one was forhomogeneous keepers, and the other was for pseudo heterogeneous keepers. Our experiments matched 3 keepers against
2 takers in a 20[m]×20[m] region. Keepers used strategies
constructed by GRAPE. Takers used a hand-coded strategy.
Two action patterns of takers were prepared. The nearest takerFig. 8.

Transition of time of keeping the ball.

In Fig. 9, “A” contains the main loop that consists of basic
output in keepaway soccer. Basic output is continually usedsome “output node” that are “Hold Ball”, “Get Open” and “GoFig. 9.

Graph-structured algorithm for homogeneous agents.
Fig. 10.

To Ball”. Then, the transition of “B” exits the main loop of“A” and connects to structure of “C”. Structure of “C” works
as searching a free keeper and passing the keeper the ball.
Keepers get the strategy about attracting takers and passing afree keeper the ball and getting free by Get Open.
In Fig. 10, “1” of connections of “Start node” for the nearest
keeper from the ball at the start of keepaway soccer uses
structures of “B” and “D”. “2” and “3” of connections of “Startnode” for keepers receiving the ball at the start of keepawaysoccer use structures of “B”, “C” and “D”. Structures thatare used by the transition from “2” and “3” of connections
contain structures that are used by the transition from “1”of connections. However, the difference of connecting to thestructure come to the difference of main available nodes.
“B” in Fig. 10 is the structure for pass. It is connected by“A” and “D” in Fig. 10. If the node transfers from “A” to“B”, two kinds of information, distance and angle, use forpass. On the other hand, if the node transfers from “D” to“B”, only a kind of information, distance, use for pass. In
addition, a nearer keeper from “Agent” is mainly selected as
the target for pass. Therefore, the number of failure at thestart of keepaway soccer reduces but failure occurs easily
as keepaway soccer proceed. In the observation of actionsof keepers, the pseudo heterogeneous keepers choose thegood target for a pass at the start of keepaway soccer but
at proceeding keepaway soccer, choose the bad target for apass. The keeping time of the pseudo heterogeneous keepers

Graph-structured algorithm for pseudo heterogeneous agents.

is shorter than that of the homogeneous keepers. Constructing
pseudo heterogeneous strategies, GRAPE destructs individual
strategies for keepers easily because keepers share nodes but
do not use all same nodes. Therefore, the strategy dose notstabilize and the keeping time of pseudo heterogeneous agentsis shorter.
VI. C ONCLUSION
In this paper, we constructed the strategy of keepers by
GRAPE. We verified that the constructed strategy is effective
to control of multiple agents from experiment. Some partsof the graph-structured algorithm acquired the particular roleand these are connected effectively. In future works, we aim
to get the strategy of achieving more difficult tasks instead of
keepaway soccer. In keepaway soccer, we have some future
work. In the observation of keepers’ actions, keeper often
takes no action when pass courses are completely blocked. The
reason is the behavior of “Get Open”. The behavior of “GetOpen” includes the tendency of staying at the same position, so
the keeping time increases by improving that tendency. In thispaper, we evaluate strategies by only using the keeping time.
We need the way of evaluation innovating the considerationof nodes related to misses.
R EFERENCES[1] Luke, S. and Hohn, C. and Farris, J. and Jackson, G. and Hendler, J., Coevolving Soccer Softbot Team Coordination with Genetic Programming,
Lecture notes in computer science, pp.398-411, 1998.

[2] Hsu, W. H. and Gustafson, S. M., Genetic programming and multiagent layered learning by reinforcements, Genetic and Evolutionary
Computation Conference, New York, NY, 2002.
[3] Stone, P. and Sutton, R. S., Reinforcement Learning for RoboCup Soccer
Keepaway, Adaptive Behavior, vol.13, num.3, pp.165-188, 2005.
[4] Stone, P. and Kuhlmann, G. and Taylor, M.E. and Liu, Y., Keepawaysoccer: From machine learning testbed to benchmark, Lecture Notes in
Computer Science, vol.4020, pp.93, 2006.
[5] Shinichi Shirakawa, Shintaro Ogino, and Tomoharu Nagao: Graph Structured Program Evolution, Proceedings of the Genetic and Evolutionary
Computation Conference 2007 (GECCO ’07), Vol.2, pp.1686-1693, London, England, 2007.
[6] Shinichi Shirakawa and Tomoharu Nagao: Graph Structured Program
Evolution: Evolution of Loop Structures, In Rick L. Riolo and Una-May
O’Reilly and Trent McConaghy editors, Genetic Programming Theory
and Practice VII, chapter 11, pp.177-194, Springer, 2009.
[7] Shinichi Shirakawa and Tomoharu Nagao: Evolution of sorting algorithm
using graph structured program evolution, Proceeding of the 2007 IEEE
International Conference on System, Man and Cybernetics (SMC 2007),
pp.1256-1261, 2007.
[8] Katagiri, H. and Hirasawa, K. and Hu, J. and Murata, J. andKosaka, M., Network Structure Oriented Evolutionary Model: Genetic Network Programming-Its Comparison with Genetic Programming,
TRANSACTIONS-SOCIETY OF INSTRUMENT AND CONTROL ENGINEERS, vol.38, num.5, pp.485-494, 2002.
[9] Shingo Mabu, Kotaro Hirasawa, and Jinglu Hiu, A Graph-Based Evolutionary Algorithm: Genetic Network Programming (GNP) and Its Extension Using Reinforcement Learning. Evolutionary Computation, Vol.15,
No.3, pp.369-398, 2007.
[10] H. Nakagoe, K. Hirasawa, and J. Hu. Genetic network programmingwith automatically generated variable size macro nodes. In Proceedingsof the 2004 IEEE Congress on Evolutionary Computation (CEC 2004),
pp.713-719, Portland, Oregon, 20-23 June 2004. IEEE Press.
[11] J. R. Koza, Genetic Programming II: Automatic Discovery of Reusable
Programs. MIT Press, Cambridge, MA, USA 1994.
[12] Hiroaki Kataoka, Akira Hara and Tomoharu Nagao: Genetic Automata
Generation; GAUGE, Information Processing Society of Japan, Vol.44,
No.12, pp.3232-3241, 2003. [In Japanese][13] H. Satoh, M. Yamamura, and S. Kobayashi. Minimal generation gap
model for considering both exploration and exploitations In Proceedingsof the IIZUKA ’96, pp.494-467, 1996.
[14] John H. Holland, Adaptation in Artificial and Natural Systems, The
University of Michigan Press, 1975.
[15] John R. Koza, Genetic programming: On the programming of computers
by means of natural selection, MIT Press, 1992.
[16] Sutton R. S. and Barto A. G., Reinforcement learning, MIT Press, 1998.
[17] Robocup tools, http://sourceforge.jp/projects/rctools.
[18] Soccer Server, http://sourceforge.jp/projects/sserver.