View Original PDF

Gliders2015: Opponent avoidance with bio-inspired flocking behaviour

Mikhail Prokopenko, Peter Wang, Oliver Obst

Complex Systems Research Group, Faculty of Engineering and IT The University of Sydney, NSW 2006, Australia; Data Mining, CSIRO Digital Productivity PO Box 76, Epping, NSW 1710, Australia

www.socsim.robocup.org/files/2D/binary/RoboCup2012/ · http://www.rctools.sourceforge.jp

Abstract To succeed in the RoboCup Soccer 2D Simulation League, team players need to show a high degree of coherent mobility. In this paper we describe a bio-inspired mechanism employed by our team, Gliders2015, during a dynamic positioning. The mechanism is based on elements of flocking behaviour and is sufficiently generic to be applicable to other RoboCup Soccer Leagues. The proposed approach has been successfully tested, leading to an improved performance against benchmarks.

1 Introduction

As pointed out in previous studies, successful performance of the top RoboCup Soccer Simulation 2D teams is characterised by dynamic tactical flexibility [1]. One element of tactical flexibility is the dynamic repositioning of players to avoid the opponents which employ marking or blocking. Systematic investigation of this topic dates back to 2001 [2], and the survey of this research is out of scope of this paper, which is devoted to describing a simple mechanism for a dynamic position refinement. Intuitively, the intention is to keep each player's position as close as possible to the selection suggested by a specific tactical scheme, but introduce slight variations in order to maximise the chances of receiving the pass and/or shoot at the opponent's goal. In doing so, we utilise a well-known element of flocking behaviour: repulsion or separation.

The flocking behaviour refinement is implemented in Gliders [3, 4, 1] — a simulated soccer team for the RoboCup soccer 2D simulator [5]. Gliders2012 and Gliders2013 reached semifinals in RoboCup tournaments of 2012 and 2013, while Gliders2014 became vice-champions of RoboCup tournament in 2014. The team code is written in C++ using agent2d: the wellknown base code developed by Akiyama et al. [6], and fragments of released source code of Marlik [7]. Other software packages are used as well:

  • librcsc: a base library for The RoboCup Soccer Simulator (RCSS) with various utilities describing relevant geometrical constructs, world model, etc.;
  • soccerwindow2: a viewer program for RCSS, working as a monitor client, a log player and a visual debugger;
  • fedit2: a formation editor for agent2d, allowing to design a team formation;
  • Gliders' in-browser basic soccermonitor (GIBBS): a log-player for viewing 2D Simulation League logs over web browser [8].

Most of the Gliders source code has been released in 2013, and can be downloaded from the Official Data Repository of RoboCup 2D Soccer Simulation League: www.socsim.robocup.org/files/2D/binary/RoboCup2012/.

2 Approach

Flocking behaviour used by Gliders allows the players to achieve a high degree of coherent mobility: on the one hand, the players are constantly refining their positions in response to opponent players within certain interaction zone (being sensitive to the opponent players), but on the other hand, the repositioning is not erratic and the players move in somewhat predictable ways. The balance between sensitivity and predictability is one of the hallmarks of guided self-organisation and coherent behaviour [9, 10, 11, 12].

Multiple biological examples of coherent behavior are given by swarms of animals, e.g. schools of fish, swarms of locusts, flocks of birds, etc. [13, 14, 15, 16, 17, 18, 19, 20, 21], in which complex large-scale patterns and cooridnated behaviours (e.g., collective predator avoidance) emerge through individual decisions based on perception of local conditions. Recent studies by [22] and [23] revealed several ways to quantify collective variables representing dynamic coordination within swarms.

Typically, swarming agents follow three different types of forces: repulsion (separation), attraction (cohesion), and orientation (alignment). Each agent responds to other agents located within a local interaction zone with the radius $r$.

The agent behaviour defined for repulsion is quite simple: to move directly away from neighbours. The repulsion of the agent X from opponent Q located within the radius $r$, at the distance $d_Q \leq r$, can be defined by the squared relative distance:

$$g_Q = \left(\frac{r - d_Q}{r}\right)^2. \tag{1}$$

The overall repulsion vector $\mathbf{X}$ is calculated as the (weighted) sum of all unit vectors from the "interacting" neighbours to the agent X:

$$\mathbf{X} = \sum_{Q: d_Q \le r} g_Q \frac{\mathbf{QX}}{d_Q},\tag{2}$$

where $\mathbf{QX}$ is the vector from Q to X.

The following example illustrates this behaviour for a given player X, located at position (45.0,0.0), which chooses to follow the repulsion behaviour from two other players Y(47.0,2.0) and Z(46.0,-2.0) within the interaction zone with the radius $r=10.0$. The vector $\mathbf{YX}$ defines relative shift from Y to X, as $\mathbf{YX} = (45.0,0.0) - (47.0,2.0) = (-2.0,-2.0)$, with the distance $d_Y = |YX| = \sqrt{8}$, while vector $\mathbf{ZX}$ defines relative shift from Z to X, as $\mathbf{ZX} = (45.0,0.0) - (46.0,-2.0) = (-1.0,2.0)$, with the distance $d_Z = |ZX| = \sqrt{5}$. Then the squared relative distances are given by $g_Y \approx 0.514$ and $g_Z \approx 0.603$, yielding

$$\mathbf{X} = g_Y \frac{\mathbf{YX}}{d_Y} + g_Z \frac{\mathbf{ZX}}{d_Z} \approx 0.514 \frac{(-2.0, -2.0)}{\sqrt{8}} + 0.603 \frac{(-1.0, 2.0)}{\sqrt{5}}$$

$$\approx (-0.363, -0.363) + (-0.270, 0.540) = (-0.633, 0.177). \tag{4}$$

This means that, in order to avoid the two opponents, the agent X needs to refine its position by shifting backwards by 0.633, as well as slightly downwards by 0.177 (noting that in RoboCup Simulation 2D, the ordinate is positive in the downward direction), as shown by Fig. 1.

The C++ code implementing this simple behaviour, with an additional constraint on the number of interacting opponents set to 3, is shown below:

double rad = 10.0;
Vector2D tmp (0.0,0.0);
int c = 0;
for ( PlayerPtrCont::const_iterator
        o = wm.opponentsFromSelf().begin();
        o != wm.opponentsFromSelf().end();
        ++o )
{
     if (M_positions[unum-1].dist((*o)->pos()) > rad)
        continue;
     Vector2D grad = M_positions[unum-1] - (*o)->pos();
     double cf = ( rad - grad.r() ) / rad;
     tmp += grad * cf * cf / grad.r();
     c++;
     if (c >= 3)
        break;
}
M_positions[unum-1] = M_positions[unum-1] + tmp;
Fig. 1. Example with agent X and two opponents Y and Z. The repulsion vectors from each of the players Y and Z are shown as dashed red arrows. The overall repulsion vector is shown as solid red arrow. Kickable areas are approximately shown as shaded circles around the players.
Fig. 1. Example with agent X and two opponents Y and Z. The repulsion vectors from each of the players Y and Z are shown as dashed red arrows. The overall repulsion vector is shown as solid red arrow. Kickable areas are approximately shown as shaded circles around the players.

3 Conclusion

We described a mechanism of dynamic positioning based on elements of flocking behaviour (separation). The mechanism is utilised by Gliders, a simulated soccer team participating in the RoboCup 2D Simulation League. It is sufficiently generic and may be applicable to other soccer Leagues. The opponent avoidance approach has been successfully tested, improving performance against top Simulation League teams and other benchmarks, e.g. agent2d.

Acknowledgments We thank David Budden for developing new self-localisation method introduced in Gliders2013 [24], Oliver Cliff for developing tools for quantifying interaction networks and tactical analysis [25].

Some of the Authors have been involved with RoboCup Simulation 2D in the past, however the code of their previous teams (Cyberoos and RoboLog, see, e.g., [26, 27, 28]) is not used in Gliders.

References

  1. Prokopenko, M., Obst, O., Wang, P.: Gliders2014: Dynamic Tactics with Voronoi Diagrams. In: RoboCup 2014 Symposium and Competitions: Team Description Papers, Joao Pessoa, Brazil, July 2014. (2014)
  2. Reis, L.P., Lau, N., Oliveira, E.: Situation based strategic positioning for coordinating a team of homogeneous agents. In: Balancing Reactivity and Social Deliberation in Multi-Agent Systems, From RoboCup to Real-World Applications, London, UK, Springer (2001) 175–197
  3. Prokopenko, M., Obst, O., Wang, P., Held, J.: Gliders2012: Tactics with action-dependent evaluation functions. In: RoboCup 2012 Symposium and Competitions: Team Description Papers, Mexico City, Mexico, June 2012. (2012)
  4. Prokopenko, M., Obst, O., Wang, P., Budden, D., Cliff, O.: Gliders2013: Tactical analysis with information dynamics. In: RoboCup 2013 Symposium and Competitions: Team Description Papers, Eindhoven, The Netherlands, June 2013. (2013)
  5. Chen, M., Dorer, K., Foroughi, E., Heintz, F., Huang, Z., Kapetanakis, S., Kostiadis, K., Kummeneje, J., Murray, J., Noda, I., Obst, O., Riley, P., Steffens, T., Wang, Y., Yin, X.: Users Manual: RoboCup Soccer Server — for Soccer Server Version 7.07 and Later. The RoboCup Federation. (February 2003)
  6. Akiyama, H.: Agent2D Base Code. http://www.rctools.sourceforge.jp (2010)
  7. Tavafi, A., Nozari, N., Vatani, R., Yousefi, M.R., Rahmatinia, S., Pirdir, P.: MarliK 2012 Soccer 2D Simulation Team Description Paper. In: RoboCup 2012 Symposium and Competitions: Team Description Papers, Mexico City, Mexico, June 2012. (2012)
  8. Moore, E., Obst, O., Prokopenko, M., Wang, P., Held, J.: Gliders2012: Development and competition results. CoRR abs/1211.3882 (2012)
  9. Prokopenko, M.: Guided self-organization. HFSP Journal 3(5) (2009) 287–289
  10. Lizier, J.T., Prokopenko, M., Zomaya, A.Y.: Coherent information structure in complex computation. Theory in Biosciences 131 (2012) 193–203
  11. Ay, N., Bernigau, H., Der, R., Prokopenko, M.: Information-driven self-organization: the dynamical system approach to autonomous robot behavior. Theory in Biosciences 131 (2012) 161–179
  12. Prokopenko, M., ed.: Guided Self-Organization: Inception. Volume 9 of Emergence, Complexity and Computation. Springer Berlin Heidelberg (2014)
  13. Lissaman, P.B.S., Shollenberger, C.A.: Formation flight of birds. Science 168(3934) (1970) 1003–1005
  14. Treherne, J.E., Foster, W.A.: Group transmission of predator avoidance behaviour in a marine insect: The trafalgar effect. Anim. Behav. 29(3) (1981) 911 – 917
  15. Aoki, I.: A simulation study on the schooling mechanism in fish. B. Jpn. Soc. Sci. Fish. 48 (1982) 1081–1088
  16. Partridge, B.L.: The structure and function of fish schools. Sci. Am. 246(6) (June 1982) 114–123
  17. Potts, W.K.: The chorus-line hypothesis of manoeuvre coordination in avian flocks. Nature 309 (May 1984) 344–345
  18. Huth, A., Wissel, C.: The simulation of the movement of fish schools. J. Theor. Biol. 156 (1992) 365–385
  19. Couzin, I.D., James, R., Croft, D.P., Krause, J.: Social organization and information transfer in schooling fishes. In C., B., Laland, K., Krause, J., eds.: Fish Cognition and Behavior. Fish and Aquatic Resources. Blackwell Publishing (2006) 166–185
  20. Lukeman, R., Li, Y.X., Edelstein-Keshet, L.: Inferring individual rules from collective behavior. Proc. Natl. Acad. Sci. USA 107(28) (June 2010) 12576–12580
  21. Katz, Y., Tunstrøm, K., Ioannou, C.C., Huepe, C., Couzin, I.D.: Inferring the structure and dynamics of interactions in schooling fish. Proc. Natl. Acad. Sci. USA (2011) in press.
  22. Wang, X.R., Miller, J.M., Lizier, J.T., Prokopenko, M., Rossi, L.F.: Quantifying and tracing information cascades in swarms. PLoS ONE 7(7) (07 2012) e40084
  23. Miller, J.M., Wang, X.R., Lizier, J.T., Prokopenko, M., Rossi, L.F.: Measuring information dynamics in swarms. In Prokopenko, M., ed.: Guided Self-Organization: Inception. Volume 9 of Emergence, Complexity and Computation. Springer Berlin Heidelberg (2014) 343–364
  24. Budden, D., Prokopenko, M.: Improved particle filtering for pseudo-uniform belief distributions in robot localisation. In: RoboCup 2013: Robot Soccer World Cup XVII, Springer (2013)
  25. Cliff, O., Lizier, J., Wang, R., Wang, P., Obst, O., Prokopenko, M.: Towards quantifying interaction networks in a football match. In: RoboCup 2013: Robot Soccer World Cup XVII, Springer (2013)
  26. Butler, M., Prokopenko, M., Howard, T.: Flexible synchronisation within RoboCup environment: A comparative analysis. In: RoboCup 2000: Robot Soccer World Cup IV, London, UK, Springer (2001) 119–128
  27. Prokopenko, M., Wang, P.: Evaluating team performance at the edge of chaos. In Polani, D., Browning, B., Bonarini, A., Yoshida, K., eds.: RoboCup 2003: Robot Soccer World Cup VII. Volume 3020 of Lecture Notes in Computer Science., Springer (2004) 89–101
  28. Obst, O., Boedecker, J.: Flexible coordination of multiagent team behavior using HTN planning. In Noda, I., Jacoff, A., Bredenfeld, A., Takahashi, Y., eds.: RoboCup 2005: Robot Soccer World Cup˜IX. Lecture Notes in Artificial Intelligence. Springer, Berlin, Heidelberg, New York (2006) 521–528