View Original PDF

Gliders2016: Integrating multi-agent approaches to tactical diversity

Mikhail Prokopenko, Peter Wang, Oliver Obst, Victor Jauregui

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

http://www.rctools.sourceforge.jp

Abstract We summarize approaches to tactical diversity, mobility and field control developed over the recent years in team Gliders, ranging from tactic-dependent evaluation and selection of players' actions, to dynamic tactics based on Voronoi Diagrams, to tactical analysis and opponent modeling with information dynamics, to a bio-inspired mechanism for dynamic repositioning. All these approaches are sufficiently generic to be applicable to other RoboCup Soccer Leagues and various team sports scenarios. The reviewed approaches have been integrated in Gliders2016 and successfully tested against benchmarks.

Introduction

Developers involved in RoboCup simulation leagues are able to focus their effort on multi-agent algorithms underlying collective distributed intelligence, and advance virtual Artificial Intelligence (AI) techniques at a much faster rate than fully-embodied robotic AI. It is well-accepted that tactical proficiency and diversity shown in the RoboCup Soccer 2D Simulation League stand out among all RoboCup leagues: the agents demonstrate autonomous decision-making under constraints, while adapting their tactics to different opponents. In this paper we summarise approaches to tactical diversity, mobility and field control developed over the recent years in team Gliders. These methods include tactic-dependent evaluation and selection of players' actions, tactical analysis and opponent modelling with information dynamics, dynamic tactics based on Voronoi Diagrams, and a bio-inspired mechanism for dynamic repositioning.

Gliders is a simulated soccer team developed for the RoboCup soccer 2D simulator. Gliders2012 and Gliders2013 reached the semi-finals of RoboCup in 2012 and 2013, while Gliders2014 became vice-champions of RoboCup tournament in 2014. Gliders2015 finished third in RoboCup-2015. The team code is written in C++ using agent2d: the well-known base code developed by Akiyama et al., and fragments of released source code of Marlik. Other software packages are used as well:

  • librcsc: a base library for the RoboCup Soccer Simulator (RCSS);
  • soccerwindow2 : a viewer and a visual debugger program for RCSS;
  • fedit2 : a team formation editor for agent2d.

Action-dependent evaluation

The approach introduced in Gliders2012 retained the advantages of a single evaluation metric (implemented in agent2d), but diversified the evaluation by considering multiple points as desirable states. The mechanism can be contrasted with some well known constructive models used by belief revision and belief update. More specifically, for any current state of the simulation $w \in W$ and a feasible agent action $a \in A$, there is a number of tactics represented by a set of desirable tactical states S. For example, a tactical state can be given by a target ball position on the field. The function mapping a state and an action to its tactic is given by

$$tactics: A \times W \to S$$

Then each feasible action is rated with respect to the corresponding desirable tactical state:

$$r(a, w) = D(S = result(a, w), S^* = tactics(a, w))$$

where D is a simple distance metric, identical for all actions. The selected action minimizes the distance between resultant and desirable tactical states:

$$a^*(w) = \arg\min_{a} r(a, w)$$

Importantly, the desirable tactical states that the player is trying to reach are not independent of actions, but rather are action-dependent, and this dependence is tactical. The definition allows for different desirable states $S_1 = tactics(a_1, w) \neq S_2 = tactics(a_2, w)$, where $a_1 \neq a_2$. Tactics are not imposed in a top-down fashion: instead, they suggest desirable states and guide self-organization of resultant behavior. Ultimately, the function tactics implements the mobility aspect of evaluation, by diversifying options of the player controlling the ball in continuing the game. The other teammates can also use this function in selecting a desirable state for their positioning. The diversification in positioning achieves both mobility (by enabling better passes to these teammates) and field control — by taking key points and blocking key directions.

Dynamic Tactics with Voronoi Diagrams

Better mobility and more comprehensive field control are critical to successful performance in RoboCup Soccer. This idea can be traced to a generic framework describing abstract spatio-temporal relationships, suggested by Dylla et al. with the use of Voronoi diagrams. A Voronoi diagram is the partitioning of a plane with n points into n convex polygons such that each polygon contains exactly one point and every point in the given polygon is closer to its central point than any other. This was further developed by Akiyama et al. who used a dual representation of Voronoi diagrams — the Delaunay triangulation. Voronoi diagrams are also known to emerge as a result of parallel computation, providing an optimal spatial configuration for a robust resource distribution and quick transportation.

Voronoi diagrams have been naturally embedded into the tactical schemes of Gliders2014, providing desirable states for action-dependent evaluation. In other words, the function $S = tactics(a, w)$, utilizes (i) a Voronoi diagram, where the n points are given by n = 11 positions of the opponent players at the simulation state w; (ii) a set of possible attacking nodes $V(a, w)$, through which the team may develop an attack further, including the Voronoi vertices (nodes), i.e. the points equidistant to three (or more) points, as well as nodes located at intersections between Voronoi segments and specific lines, e.g., offside line; (iii) constraints on the set $V(a, w)$, i.e., $V'(a, w) \subset V(a, w)$ (e.g., considering only nodes within a certain radius to the possible resultant state); (iv) a mechanism selecting one of the vertices in $V'(a, w)$ as the most promising attacking node, by identifying $v^(w) = \arg\max_{v \in V'(a, w)} d(v)$, for some measure d(v). The field position of the selected node $v^(w)$ is the final outcome: $S^(a, w) = position(v^, w) = tactics(a, w)$.

An example and an illustration of this selection mechanism are detailed in the literature.

Information dynamics

Starting from 2013, Gliders utilized information dynamics for tactical analysis and opponent modeling. This analysis involves computation of information transfer and storage, relating the information transfer to responsiveness of the players, and the information storage within the team to the team's rigidity and lack of tactical richness.

The active information storage quantifies the information storage component that is directly used in the computation of the next state of a process: it is the average mutual information between the semi-infinite past of the process $x_n^{(k)} = {x_{n-k+1}, \ldots, x_{n-1}, x_n}$ (as $k \to \infty$) and its next state: $A_X = \langle a_X(n+1) \rangle_n$, where

$$a_X(n+1) = \lim_{k \to \infty} \log_2 \frac{p(x_n^{(k)}, x_{n+1})}{p(x_n^{(k)})p(x_{n+1})}$$

Transfer entropy is designed to detect asymmetry in the interaction of subsystems by distinguishing between "driving" and "responding" elements. The local information transfer, based on transfer entropy, captures information transmission from source Y to destination X, at a particular time-step n+1. Specifically, the local information transfer between a source and a destination agent is defined as the information provided by the source $y_n$ about the destination's next state $x_{n+1}$ that was not contained in the past of the destination $x_n^{(k)}$:

$$t_{Y \to X}(n+1) = \lim_{k \to \infty} \log_2 \frac{p(x_{n+1} \mid x_n^{(k)}, y_n)}{p(x_{n+1} \mid x_n^{(k)})}$$

Information transfer between two variables does not require an explicit communication channel, but rather indicates directional synchrony between the source and the destination.

Sometimes it is useful to condition the local information transfer on another contributing process W, considering the local conditional transfer entropy:

$$t_{Y \to X|W}(n+1) = \lim_{k \to \infty} \log_2 \frac{p(x_{n+1} \mid x_n^{(k)}, y_n, w_n)}{p(x_{n+1} \mid x_n^{(k)}, w_n)}$$

Computational experiments with Gliders2013 verified two conjectures:

  • (i) a higher information transfer $t_{Y \to X|W}$ from the source Y (e.g. dynamics of player Y) to the destination X (e.g., dynamics of another player X), in the context of some other dynamics W (e.g., the movement of the ball W), is indicative of a higher responsiveness of the process/player X to the process/player Y.
  • (ii) a higher rigidity $A_{\mathbb{X}}$ within the team is indicative of a higher dependence of players on each other, or a higher redundancy within the team's motion.

This allowed us to identify the areas of most intense one-on-one contests, as well as the extent of dynamic interactions constraining mobility. Several detailed examples of tactical analysis are provided in the literature.

Bio-inspired dynamic repositioning

Building on the information dynamics measures, it is possible to investigate group behavior in complex systems, such as swarms. Constraints on mobility, identified by information dynamics, were investigated and partially overcome with bio-inspired avoidance of opponents which employ marking or blocking. Gliders2015 utilized a well-known element of flocking behavior: repulsion or separation, attempting to keep each player's position as close as possible to that suggested by a specific tactical scheme, while incorporating slight variations in order to maximize the chances of receiving the pass and/or shoot at the opponent's goal.

The flocking behavior 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 a 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. This achieves a balance between sensitivity and predictability which is typical of guided self-organization and coherent behavior.

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 swarming behaviour defined for repulsion (separation) is quite simple: to move directly away from neighbors located within a local interaction zone with the radius r. 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$$

The overall repulsion vector 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}$$

where QX is the vector from Q to X. A detailed example and C++ code implementing this simple behavior are provided in the literature.

Conclusion

This integrated approach has been successfully applied to opponent modeling and selection of the best available tactics in an opponent-specific way. The overall framework may be useful for analysis of tactical diversity, mobility and field control in different multi-agent team sports, where dynamic interactions shape performance both locally and globally, as well as for analysis of general distributed dynamics, e.g., decentralized coordination, optimal distributed decision making, swarm engineering, reconfigurable sensor networks, and modular robotics.

Acknowledgments We thank David Budden for developing new self-localization method introduced in Gliders2013, and Oliver Cliff for developing tools for quantifying interaction networks and tactical analysis. 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., references in literature) is not used in Gliders.

References

  1. Budden, D.M., Wang, P., Obst, O., Prokopenko, M.: Robocup simulation leagues: Enabling replicable and robust investigation of complex robotic systems. IEEE Robotics and Automation Magazine 22(3) (2015) 140–146
  2. Noda, I., Stone, P.: The RoboCup Soccer Server and CMUnited Clients: Implemented Infrastructure for MAS Research. Autonomous Agents and Multi-Agent Systems 7(1–2) (July–September 2003) 101–120
  3. Riley, P., Stone, P., Veloso, M.: Layered disclosure: Revealing agents' internals. In Castelfranchi, C., Lesperance, Y., eds.: Intelligent Agents VII. Agent Theories, Architectures, and Languages — 7th. International Workshop, ATAL-2000, Boston, MA, USA, July 7–9, 2000, Proceedings. Lecture Notes in Artificial Intelligence. Springer, Berlin, Berlin (2001)
  4. Stone, P., Riley, P., Veloso, M.: Defining and using ideal teammate and opponent models. In: Proceedings of the Twelfth Annual Conference on Innovative Applications of Artificial Intelligence. (2000)
  5. 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
  6. 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
  7. Prokopenko, M., Wang, P.: Relating the entropy of joint beliefs to multi-agent coordination. In Kaminka, G.A., Lima, P.U., Rojas, R., eds.: RoboCup 2002: Robot Soccer World Cup VI. Volume 2752 of Lecture Notes in Computer Science., Springer (2003) 367–374
  8. 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
  9. 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)
  10. 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)
  11. 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)
  12. 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)
  13. Prokopenko, M., Wang, P., Obst, O.: Gliders2015: Opponent avoidance with bio-inspired flocking behaviour. In: RoboCup 2015 Symposium and Competitions: Team Description Papers, Hefei, China, July 2015. (2015)
  14. 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)
  15. Akiyama, H.: Agent2D Base Code. http://www.rctools.sourceforge.jp (2010)
  16. 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)
  17. Peppas, P., Nayak, A.C., Pagnucco, M., Foo, N.Y., Kwok, R.B.H., Prokopenko, M.: Revision vs. update: Taking a closer look. In Wahlster, W., ed.: 12th European Conference on Artificial Intelligence, Budapest, Hungary, August 11-16, 1996, Proceedings, John Wiley and Sons, Chichester (1996) 95–99
  18. Prokopenko, M.: Guided self-organization. HFSP Journal 3(5) (2009) 287–289
  19. Dylla, F., Ferrein, A., Lakemeyer, G., Murray, J., Obst, O., Röfer, T., Schiffer, S., Stolzenburg, F., Visser, U., Wagner, T.: Approaching a formal soccer theory from the behavior specification in robotic soccer. In Dabnicki, P., Baca, A., eds.: Computers in Sport. Bioengineering. WIT Press (2008) 161–186
  20. Akiyama, H., Noda, I.: Multi-agent positioning mechanism in the dynamic environment. In Visser, U., Ribeiro, F., Ohashi, T., Dellaert, F., eds.: RoboCup 2007: Robot Soccer World Cup XI. Springer, Berlin, Heidelberg (2008) 377–384
  21. Akiyama, H., Shimora, H.: Helios2010 team description. In: RoboCup 2010: Robot Soccer World Cup XIV. Volume 6556 of Lecture Notes in Computer Science., Springer (2011)
  22. Adamatzky, A., Prokopenko, M.: Slime mould evaluation of Australian motorways. IJPEDS 27(4) (2012) 275–295
  23. Lizier, J.T., Prokopenko, M., Zomaya, A.Y.: Detecting non-trivial computation in complex dynamics. In Almeida e Costa, F., Rocha, L.M., Costa, E., Harvey, I., Coutinho, A., eds.: Proceedings of the 9th European Conference on Artificial Life (ECAL 2007), Lisbon, Portugal. Volume 4648 of Lecture Notes in Artificial Intelligence., Berlin / Heidelberg, Springer (2007) 895–904
  24. Lizier, J.T., Prokopenko, M., Zomaya, A.Y.: Local information transfer as a spatiotemporal filter for complex systems. Phys. Rev. E 77(2) (2008) 026110
  25. Lizier, J.T., Prokopenko, M., Zomaya, A.Y.: Information modification and particle collisions in distributed computation. Chaos 20(3) (2010) 037109
  26. Lizier, J.T., Prokopenko, M., Zomaya, A.Y.: Coherent information structure in complex computation. Theory in Biosciences 131 (2012) 193–203
  27. Lizier, J.T., Prokopenko, M., Zomaya, A.Y.: Local measures of information storage in complex distributed computation. Information Sciences 208 (2012) 39–54
  28. Schreiber, T.: Measuring information transfer. Phys. Rev. Lett. 85(2) (2000) 461–464
  29. Cliff, O.M., Lizier, J.T., Wang, X.R., Wang, P., Obst, O., Prokopenko, M.: Quantifying Long-Range Interactions and Coherent Structure in Multi-Agent Dynamics. IEEE Transactions on Cybernetics (submitted)
  30. 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
  31. 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
  32. Prokopenko, M., ed.: Guided Self-Organization: Inception. Volume 9 of Emergence, Complexity and Computation. Springer Berlin Heidelberg (2014)
  33. Mathews, G.M., Durrant-Whyte, H., Prokopenko, M.: Decentralised decision making in heterogeneous teams using anonymous optimisation. Robotics and Autonomous Systems 57(3) (2009) 310–320
  34. Mathews, G., Durrant-Whyte, H., Prokopenko, M.: Measuring global behaviour of multi-agent systems from pair-wise mutual information. In: Knowledge-Based Intelligent Information and Engineering Systems, Springer (2005) 587–594
  35. Mathews, G., Durrant-Whyte, H., Prokopenko, M.: Asynchronous gradient-based optimisation for team decision making. In: Decision and Control, 2007 46th IEEE Conference on, IEEE (2007) 3145–3150
  36. Foreman, M., Prokopenko, M., Wang, P.: Phase transitions in self-organising sensor networks. In Banzhaf, W., Christaller, T., Dittrich, P., KIm, J., Ziegler, J., eds.: Advances in Artificial Life - Proceedings of the 7th European Conference on Artificial Life (ECAL). Volume 2801 of Lecture Notes in Artificial Intelligence., Springer Verlag (2003) 781–791
  37. Prokopenko, M., Gerasimov, V., Tanev, I.: Measuring spatiotemporal coordination in a modular robotic system. In Rocha, L.M., Yaeger, L.S., Bedau, M.A., Floreano, D., Goldstone, R.L., Vespignani, A., eds.: Proceedings of the 10th International Conference on the Simulation and Synthesis of Living Systems (ALifeX), Bloomington, Indiana, USA, MIT Press (2006) 185–191
  38. Prokopenko, M., Gerasimov, V., Tanev, I.: Evolving spatiotemporal coordination in a modular robotic system. In Nolfi, S., Baldassarre, G., Calabretta, R., Hallam, J., Marocco, D., Meyer, J.A., Parisi, D., eds.: Proceedings of the Ninth International Conference on the Simulation of Adaptive Behavior (SAB'06), Rome. Volume 4095 of Lecture Notes in Artificial Intelligence., Springer Verlag (2006) 548–559
  39. 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)
  40. 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