View Original PDF

Team Description Of SoccerTeam 35 ½

Bora I. Kumova

Dokuz Eyl l University; Department of Computer. Engineering

http://cs.deu.edu.tr/~kumova

Abstract The CEVOP methodology is a co−evolutionary approach for planning co−operative/competitive team strategies for homogeneous/ heterogeneous agents. In this paper we describe CEVOP as the planning module of the SoccerTeam prototype.

1 Introduction

Evolutionary techniques in multi−agent systems [1] are mainly utilised for reducing exhaustive search in problem domains, such as in planning or learning through exploring the a search space randomly. For instance for co−operative learning [4]. Co−evolutionary algorithm enable further to simulate co−operative and/or competitive structures [3], [11]. However, all approaches consider either co− operation or competition. We have developed the Co−evolutionary Planning (CEVOP) methodology that combines both in a single co−evolutionary algorithm [7], [8]. In the following we describe the co−evolutionary planning approach with the CEVOP methodology as it is implemented in the SoccerTeam prototype.

2 Planning With CEVOP In SoccerTeam

The principle structures, co−operation, competition, and co−ordination, found in Soccer game, have explicitly been mapped onto the principle interaction structures of the co−evolutionary algorithm.

2.1 Populations

The homogeneous/heterogeneous and co−operation/competition structures of SoccerTeam are depicted in (Figure 1). The co−evolutionary algorithm operates according this schema of populations and relationships.

Figure 1: Co-operative/Competitive Evolution Of The Four Homogeneous/Heterogeneous Plan Populations
Figure 1: Co-operative/Competitive Evolution Of The Four Homogeneous/Heterogeneous Plan Populations

2.2 Phenotype Structure

A phenotype represents 11 combined game strategies $S_{p,i}$, one for each player. Where p=1,...,11. Each of them consists of i=1,2,3 primitive game strategies $S_{p,1},...,S_{p,3}$ with their relative locations $\Delta x_{1,1},\Delta y_{1,1},...,\Delta x_{11,3},\Delta y_{1,3}$, one for each player. The following tuple represents the combined game strategy for player $p:(S_{1,p},\Delta x_{1,p},\Delta y_{1,p},S_{2,p},\Delta x_{2,p},\Delta y_{2,p},S_{3,p},\Delta x_{3,p},\Delta y_{3,p})$.

3 The Generic Co-evolutionary Algorithm

Following algorithm co-evolves the n = 4 populations according their m interaction types:

    1. For all n=4 populations
  • 1.1) Randomly pickup plan steps from Pi for Ai
    1. For all n=4 populations
  • 2.1) Cross-over inside $A_i$
    1. For all n=4 populations
  • 3.1) Mutate distance values inside $A_i$
    1. For all n=4 populations
  • 4.1) Calculate Fitness $F_i$ of Population $A_i$
  • 4.2) For all m interaction relationships of $A_{\rm i}$
  • 4.2.1) Calculate fitness $F_{ij}$ for interaction of $A_i$ with $A_j$ ($i \neq j$)
  • 4.2.2) $F_c = F_c + F_{ij}$
  • 4.3) $F_i = (F_i + F_c / m) / 2$ and $F_c = 0$
    1. IF fitness $F_1 \ AND \ \dots \ AND \ F_m$ satisfied OR other termination THEN STOP
    1. For all n populations
  • 6.1) Fitness selection on A
  • 6.2) GO TO 2

$A_i$ is the plan population to be optimised. $P_i$ is the set of all possible plan steps of agent i. Fitness $F_i$ of population $A_i$ is determined by accumulating all m fitness values for interrelationships $F_{ij}$: $F_i = F_{i1} + F_{im}$. $F_{im}$ represents the co-operation and/or competition strengths of agent i with the others.

3.1 Overall Algorithmic Steps

Each CEVOP run returns usually several plans, all for one specific game constellation. The number of constellations, even for non-continues positions, is huge. Therefore, the planning process is iterated until the overall grade of success of SoccerTeam becomes satisfactory in simulation runs. The algorithmic steps of the CEVOP methodology are given below.

  • Apply the Co-evolutionary Algorithm for a Random/Desired Game Constellation
  • Store the Resulting Combined Game Strategies for Players in the Knowledge Base of each Player
    1. Store the Resulting Combined Game Strategies for Goal Keepers in the Knowledge Base of each Goal Keeper
    1. IF SoccerTeam is not Successful in a Simulation Run THEN GO TO 1

After a number of iterations, each found combined game strategy will look increasingly similar to the previously found strategies. Thus, the found set of combined game strategies will saturate with respect to its successfulness in simulation runs.

3.2 Combined Evaluated Structures

Implied by the properties plan diversity and interaction type, the structures evolve in some combinations. These combinations are recapitulated in the following:

  • Each primitive game strategy and its distance values evolve combined to one player strategy.
  • Three primitive game strategies with their distance values evolve to one combined game strategy for one player.
  • 11 combined game strategies evolve combined to one team strategy; one for each team member.
  • Two team strategies evolve combined to one solution for the current game constellation.

4 Conclusions

The CEVOP methodology produces team plans without explicit specifications of co−operation, competition, and co−ordination structures, since they are implied by the algorithm in the planning process. Our goal is to find a set of representative combined game strategies, which is as small as possible and covers all significant game constellations. The current weakness of SoccerTeam is that a number of supporting strategies are required, which must implement the smooth movements of the agents [10]. CEVOP is generic for dynamic planning in multi−agent systems.

References

  1. Bull, Lawrence; Fogarty, Terence C.; 1996; "Evolutionarey Computing in Cooperative Multi agent Environments ; Adapt ation, Coevolution and Learning in Multi a gent Syst ems; AAAI Press; Menlo Park
  2. Chen, Mao; Foroughi, Ehsan; Heintz, Fredrik; Zahn, Xiangh Huang; Kapetanakis, Spiros; Kostiadis, Kostas; Kummeneje, Johan; Noda, Itsuki; Obst, Oliver; Riley, Pat; Steffens, Timo; Wang, Yi; Yin; Xiang; 2001; RoboCup Soccer Server ; RoboCup Fe deration; http:// www.robocup.org/
  3. Grefenstette, John; Daley, Robert; 1996; "Methods for Competitive and Cooperative Coevolution ; Adaptation, Coevolution and Learning in Multiagent Systems; AAAI; Menlo Park
  4. Matsubara, Hitoshi; Noda, Itsuki; Hiraki, Kazuo; 1996; "Learning of Cooperative actions in multi-agent systems: a case study of pass play in Soccer"; Adaptation, Coe volution and Learning in Multi agent Syst ems; AAAI Press; Menlo Park
  5. Kumova, Bora .; 2000; "Software Design Patterns for Intelligent Agents"; SSGRR'00, lAquila; http:// www.ssgrr.it/ en/conferenza/index.htm
  6. Kumova, Bora .; 2000, "Object-oriented Design and Implementation of the Multi-agent System AgentTeam"; OOPSLA'00; ACM
  7. Kumova, Bora .; Imada, Akira; 2002; "Co-evolutionary Planning Game Strategies in SoccerTeam"; working paper for GECCO'02; AAAI
  8. Kumova, Bora I.; 2002; "Co-evolutionary Planning ; PhD thesis; Dokuz Eylul University
  9. Kumova, Bora I.; Imada, Akira; 2002; "Concepts of the SoccerTeam Prototype"; working paper for RoboCup'02; Fukuoka
  10. Kumova, Bora I.; 2002; "The Game Strategies of SoccerTeam"; TAINN'02; Istanbul University
  11. Potter, Mitchell A.; 1997; "The Design and Analysis of a Computational Model of Coop erative Coevolution"; dissertation; George Mason University; Virginia
  12. Rosin, Christopher Darrell; 1997; Coevolutionary search among adversaries ; University of California, San Diego; ISBN 0-591-42206-9