View Original PDF

Photon 2D Soccer Simulation Team Description Paper

Morteza Barati, Zahra Hakimi, Amir Homayoun Javadi*

17 Queen Square, WC1N 3AR, London, UK

https://sites.google.com/site/ahjavadi/photon2drcss

Abstract Photon is a 2D soccer simulation team which is going to participate in international competitions for the first time. This paper gives a brief overview of current and future efforts of Photon. We have used Genetic Algorithm (GA) to optimise our fitness functions. Using this method we optimised two tasks: ball-possession and passing, and through-pass interception. The results of our simulations show promising and we are aiming to further our method to other tasks such as marking.

Keywords: Robocup, Soccer, Simulation, 2D, Genetic Algorithm

1 Introduction

Photon is a 2D soccer simulation team. Although Photon is going to participate in international competitions for the first time, the members of the team have expertise necessary in the 2D soccer simulation league such as artificial intelligence and decision making. We began our research on soccer simulation two years ago basing our team on UvA Trilearn [1,2], freely available online [3]. Recently we migrated to HELIOS base code (called Agent2D) [4], which is also freely available.

Due to the complexity of the soccer simulation, application of adaptive and intelligent methods can improve the performance to a great extent and helps the team to deal with unforeseen situations and changes to the system. Different methods of artificial intelligent have been previously successfully used in soccer simulation [5- 11]. We have used genetic algorithm (GA), a biologically inspired method, to optimise our decision making by evaluating different options in two tasks: ballpossessing and through-pass interception.

Here we first give an overview of the method of genetic algorithm and then we discuss the two skills to which we applied GA. In the last section we discuss the currently achieved results and future directions.

2 Genetic Algorithms

Genetic Algorithm (GA) is an adaptive method that is inspired by biological systems and may be used for search and optimisation purposes. The basic idea behind it is the "survival of the fittest", which was first formulated by Charles Darwin [12,13]. GA is based on the natural selection of the fittest members of a population and production of offspring inheriting from current members. It has proved to be a highly effective method for several control engineering and optimisation problems in which explicit description of the dynamics of the system is difficult, if not impossible. We have successfully applied it to different problems such as civil engineering [14], biomechanics [15], robotics and control engineering [16,17]. Considering the difficulty of modelling of a soccer game, application of GA seems promising. A GA approach is therefore adopted to determine the coefficient of the contributing factors in two tasks in order to achieve the most effective or close to optimised performance.

This method has been implemented for two tasks: Ball-possession and passing, and through-pass interception. We have considered several factors in each task and have used GA to give an importance coefficient to each factor to quantify the appropriateness of each decision to finally select the most effective one.

In the following we first give an overview of GA method and then we explain the two tasks that we have applying GA to.

Fig. 1. General method of genetic algorithm (GA).
Fig. 1. General method of genetic algorithm (GA).

2.1 Basics of Genetic Algorithms

Fig. 1 shows the method of genetic algorithm. Each repetition of GA works on a population of members (generation). Each member (chromosome) represents a possible solution to the problem. Each chromosome is consisted of several values that are called 'genes'. Each gene represents a value regarding a parameter or factor in the system. GA begins the algorithm with an initial population, which is usually generated randomly. Using a 'fitness function', each chromosome is evaluated and a fitness value will be assigned to each of them. This numbers shows how much the considered chromosome is appropriate for the problem. Then, using a few operations such as 'selection', 'mutation' and 'crossover', it creates the next generation [13]. These operations usually use a probabilistic method to select the more appropriate chromosomes with a higher possibility. The process continues either to a certain number of repetitions or until a set of criteria is met.

Fig. 2. A sample scenario showing considered parameters in the implemented GA optimisation method. Player γ is considered as the agent who is evaluating the appropriateness of teammate λ for passing the ball.
Fig. 2. A sample scenario showing considered parameters in the implemented GA optimisation method. Player γ is considered as the agent who is evaluating the appropriateness of teammate λ for passing the ball.

2.2 Ball-Possession and Passing

Ball-possessing and successful passing are two crucial factors for strategy planning and effective playing. Due to the complexity of the soccer game, it is difficult to build an optimum model using explicit description of the system. We have used GA to overcome the difficulty of modelling the dynamics of the system by running the simulation for a fairly long time and extract the most efficient values for close to optimum ball-possessing and successful passing.

There are many factors that one might consider for a successful ball-possession. It is not, however, feasible to consider all possible contributing factors in the decision making as increasing the number of factors increases the duration of the convergence of GA dramatically. Among all possible parameters, we began our implementation with three parameters: 1. Distance to each of the teammates, say teammate λ , 2. Our confidence in the condition of considered teammate ( λ ), and 3. Distance of the closest opponent, say opponent α , to our closest teammate ( λ ). Fig. 2 shows one sample scenario with γ as 'the self'. Later we added a fourth parameter: the angle in between the agent ( γ ), the closest teammate ( λ ), and the closest opponent (α ) to our closest teammate ( λ ).

2.3 Through-Pass Interception

Through-passing is one of the most important tasks in attacking as it breaks through the defence players. Having the ability to intercept these passes, takes the team to a superior level, as it makes the team almost unbeatable. After considering ballpossession and successful passing, we considered optimisation of interception of through-passes. Here we explain the basics of through-passing and through-pass interception.

Assuming player $\alpha$ and $\beta$ move with constant velocity $\vec{v}{\alpha}$ and $\vec{v}{\beta}$ , respectively, the position of each player can be achieved as following

$$\bar{p}{\alpha}(t) = \bar{p}{\alpha,0} + t.\vec{v}_{\alpha} \tag{1}$$

$$\overline{p}{\beta}(t) = \overline{p}{\beta,0} + t. \vec{v}_{\beta} \tag{2}$$

in which $\overline{p}{\alpha,0}$ and $\overline{p}{\beta,0}$ are initial position of the two players. Bar above p shows that it is comprised of the (x,y) pair. Further, we assume players' speed is equal and set to maximum players' speed, $v_n$ :

$$\left|\vec{\mathbf{v}}{\alpha}\right| = \left|\vec{\mathbf{v}}{\beta}\right| = \mathbf{v}_{p} ,. \tag{3}$$

Velocity of the ball at the time t will be

$$\vec{v}b(t) = v{bd} \cdot \vec{v}_b(t-1),$$ (4)

in which $v_{b,d}$ is ball speed decay. So, velocity of the ball based on its initial velocity, $\vec{v}_{b,0}$ , will be

$$\vec{v}b(t) = v{bd}^{t} \cdot \vec{v}_{b0}. \tag{5}$$

Integrating the above equation gives the position of the ball at time t as following

$$\bar{p}b(t) = \bar{p}{b,0} + \ln(v_{b,d}).\vec{v}{b,0}.v{b,d}^{t}. \tag{6}$$

As $v_{b,d} < 1$ , the equation above goes towards zero, i.e. the ball stops at some point. Considering equations 1 and 6, the governing system of equations will be as following:

$$\begin{cases} \overline{p}{\alpha}(t) = \overline{p}{\alpha,0} + t.\overrightarrow{v}{\alpha} \ \overline{p}{b}(t) = \overline{p}{b,0} + \ln(v{b,d}).\overrightarrow{v}{b,0}.v{b,d} \end{cases}$$

$$\overline{p}{\alpha}(t) = \overline{p}{b}(t)$$ (7)

Solving this equation gives the time and the position that player $\alpha$ reaches to the ball, $t_{\alpha}$ and $\overline{p}{\alpha,t}$ , respectively. Solving similar equation for player $\beta$ gives corresponding time and position as $t{\beta}$ and $\overline{p}_{\beta,t}$ respectively. Converting velocity vectors from Cartesian into polar coordinates shows angle and absolute velocity more explicitly,

$$\begin{cases} v_x = |\vec{v}| \cos \theta \ v_y = |\vec{v}| \sin \theta \end{cases}$$ (8)

in which $|\vec{v}|$ for the ball is equal to maximum players' speed, $v_p$ . This value for the ball is calculated by Eq. 4.

Considering players $\beta$ and $\gamma$ as teammates, a successful pass requires $t_{\alpha} > t_{\beta}$ . Conversely, a successful interception by player $\alpha$ requires $t_{\alpha} < t_{\beta}$ .

Fig. 3. A fairly common situation for through-pass. Players γ and β belong to one team.
Fig. 3. A fairly common situation for through-pass. Players γ and β belong to one team.

3 Conclusion and Future Directions

We used genetic algorithm (GA) to improve our decision making algorithms and considered two skills to optimise. Using this method we could improve our team and have achieved promising results against the teams that have previously participated in the Robocup competitions.

Application of GA seems to be able to solve all the problems of modelling, as it optimises the system by using the same simulator (soccer server) to adjust the values. Therefore, one might expect to achieve the best possible solution after enough repetition of GA. It is, however, not feasible to consider all possible contributing factors in a task. First of all, because it is fairly impossible to detect all possible factors. Secondly, as the duration of convergence increases exponentially with the number of considered factors, integrating too many factors increases the duration of the search to an unachievable extent. We ran the algorithm for several weeks to achieve acceptable values for our passing and through-pass interception skills and yet they need more time to achieve values suitable for the standards of the competitions. The idea behind GA is simple and fairly easy to implement, but selection of the contributing factors, boundaries and the fitness function is a challenging task. Incorrect selection of these values increases the duration of convergence and even in some cases instability of the selection process.

We are going to improve our decisions for the currently implemented skills by introducing new contributing factors in the algorithm and also extend our method to other skills such as marking. We should also consider other important factors such as the positioning of the players without ball in order to facilitate the process of passing and ball-possessing. In the ball-possessing algorithm we considered just the player who possesses the ball. It is, however, important to drive the teammate without the ball to an area that decreases the chance of losing the ball.

References

  1. Kok J, Vlassis N, Groen F (2003) UvA Trilearn 2003 team description. Proceedings CD RoboCup 2003
  2. de Boer R, Kok J (2002) The incremental development of a synthetic multi-agent system: The UvA Trilearn 2001 robotic soccer simulation team. Master's thesis, University of Amsterdam, The Netherlands
  3. Kok J, de Boer R (2003) UvA Trilearn Web Page. http://staff.science.uva.nl/~jellekok/robocup/index\_en.html. Accessed 2010
  4. Akiyama H Helios Robocup simulation league team. http://sourceforge.jp/projects/rctools/. Accessed 2010
  5. Zhou J, Zhu E, Zhang R (2010) AUA 2D Soccer Simulation Team Description Paper. 2D Soccer Simulation League.
  6. Reis LP, Lau N, Mota L (2010) FC Portugal 2D Simulation: Team Description Paper. 2D Soccer Simulation League.
  7. Igarashi H, Masaki J, Nagae N, Yoshimoto A (2010) Fifty-Storms: Team Description 2010. 2D Soccer Simulation League.
  8. Gao M, Zhang Y, Zhang C, Lin Q, Zhang Z, Zhao Y, Wang H, Fang B (2010) HfutEngine2010 Simulation 2D Team Description Paper. 2D Soccer Simulation League.
  9. Nakabayashi Y (2010) NCL10. 2D Soccer Simulation League.
  10. Norouzitallab M, Javari A, Noroozi A, Salehizadeh S, Meshgi K (2010) Nemesis Team Description 2010. 2D Soccer Simulation League.
  11. Uenishi T, Narimoto Y, Nakashima T (2010) Team Description of opuCI 2D 2010. 2D Soccer Simulation League.
  12. Darwin C (2003) The origin of species. Signet Classic,
  13. Goldberg D (1989) Genetic algorithms in search, optimization, and machine learning. Addison-wesley,
  14. Nadji Tehrani M, Javadi AH Optimisation of steel bridge design using Genetic Algorithms. In: 2nd Iranian congress on Civil Engineering, Iran, 2003.
  15. Javadi AH, Arshi AR, Shirzad E, Moeinzadeh M A genetic algorithm approach to singularity avoidance in the analysis of weight lifting performance. In: Annual conference of American society of biomechanics, USA, 2007.
  16. Javadi AH, Mojabi P A new approach to decentralized conflict resolution and utilizing GA in path planning for a novel map representation in evolutionary multi-agent systems based on team learning. In: 11th IEEE meditterranean conference on control and automation, MED03, Greece, 2003.
  17. Javadi AH Manipulation redundancy reduction as a tool for reinforcing motion planning using genetic algorithms. In: World Congress on Engineering, UK, 2008.