View Original PDF

"Infographics" team: Selecting Control Parameters via Maximal Fisher Information

Siddharth Pritam

Alumni Group of Indian Institute of Technology Kharagpur, India

Abstract "Infographics" is a very new RoboCup Soccer Simulation League 2D team, based on the released source code of agent2d and Gliders. This paper describes an approach to utilize Fisher information in interaction networks, produced by dynamics of RoboCup Simulation games. This approach is based on methods for computing interaction networks and methods for determining Fisher information in complex networks. It guides optimization of control parameters used by "Infographics".

1 Introduction

"Infographics" is a very new RoboCup Soccer Simulation League 2D team, based on the released source code of agent2d [1] and Gliders [2,3]. It also uses librcsc (a base library for The RoboCup Soccer Simulator, RCSS [4]); soccerwindow2: a viewer program for RCSS; fedit2: a formation editor for agent2d; and GIBBS: in-browser log-player for 2D Simulation League logs [5].

The Soccer Simulation 2D League is one of the oldest RoboCup leagues which still presents a significant challenge for Artificial Intelligence, Machine Learning, Autonomous Agents and Multi-Agent Systems, Cognitive Robotics and Complex Systems [6,7,8,9,10,11,12].

In this paper we describe an approach to utilize Fisher information in interaction networks, produced by dynamics of RoboCup Simulation games. This approach is based on (a) methods for computing interaction networks, introduced in [13] and verified by Gliders [3], and (b) methods for determining Fisher information in complex networks, described in [14]. It guides optimization of control parameters used by "Infographics".

2 Background

Information theory [15] is an increasingly popular framework for the study of complex systems and their phase transitions [16,17,18,19]. In part, this is because complex systems can be viewed as distributed computing systems, and information theory is a natural way to study computation, e.g. [20,21]. Information theory is applicable to any system, provided that one can define probability distribution functions for its states.

One particular information-theoretic measure, Fisher information, has been extensively used in many fields of science, providing insights that can be directly compared across different system types. It measures the amount of information that an observable random variable has about an unknown parameter, and can also be intuitively interpreted as a measure of the sensitivity of the random variable to changes in the parameter. For example, a recent study [14] explicitly related elements of the Fisher information matrix to the rate of change in the corresponding order parameters, and identified, in particular, second-order phase transitions via divergences of individual elements of the Fisher information matrix.

In parallel, our recent research has also focused on phase transitions between ordered and chaotic behaviour, analyzed from the perspective of distributed computation: specifically, in small-world Random Boolean Networks (RBNs) [22,23]. These studies characterized the distributed computation in terms of its underlying information dynamics: information storage and information transfer, and gave us a good insight on the behavior of the networks and flow of information near critical regimes.

Furthermore, in the context of RoboCup and team sports in general, several new techniques were recently developed for quantifying dynamic interactions in simulated football games [13]. This study not only involved computation of information transfer and storage, but also related the information transfer to responsiveness of the players, and the information storage within the team to the teams rigidity and lack of tactical flexibility [13].

We intend to bring these results together, by computing Fisher information within the interaction networks obtained by the techniques introduced in [13], and characterising critical behaviour and phase transitions via Fisher information, following methods of [14]. The results promise to advance research in complex multi-agent systems, as well as contribute to development of new behaviours, implemented within our RoboCup team, "Infographics" (India).

3 Methods

The first step (1) of the proposed algorithm is computation of "information-base diagram", i.e. interaction networks [13]. It has the following sub-steps, reproduced from [13]:

(1.1) The average conditional transfer entropy [24] between any two agents from opposing teams X and Y is computed for a game g with N time steps:

$$T_{Y_i \to X_j \mid B}^g = \frac{1}{N} \sum_{n=0}^{N-1} \lim_{k \to \infty} \log_2 \frac{p(x_{n+1} \mid x_n^{(k)}, y_n, b_n)}{p(x_{n+1} \mid x_n^{(k)}, b_n)} ,$$

where Yi is the process tracing the change in the position yn of agent i (2 ≤ i ≤ 11) from team Y at time n (1 ≤ n ≤ N); Xj is the process tracing the change xn in the position of agent j (2 ≤ j ≤ 11) from team X at time n; B is the process tracing the change in current ball position bn; and x (k) n = {xn−k+1, . . . , xn−1, xn} is the past of the process Xj (semi-infinite past as k → ∞).

(1.2) The responder agent JX(Yi) in team X is identified as the mode of the series

$${J_X(Y_i,1),\ldots,J_X(Y_i,G)}$$

for G games, where

$$J_X(Y_i, g) = \underset{2 \le j \le 11}{\arg \max} \ T_{Y_i \to X_j | B}^g .$$

(1.3) The pairs (i, JX), where 2 ≤ i ≤ 11, identified for each agent i in team Y , produce an "information-base diagram" D(Y, X) [13]. There is one outgoing link from each agent i in team Y , but there may be several incoming links to the agent i from team Y , or an agent j from team X. At this sub-step we select the agent JˆX in our team X which has the maximal number of incoming links. In other words, it is the responder agent to the maximal number of opponent agents, being a "hub" of the "information-base diagram".

The next step (2) is computation of Fisher information F(XJˆ|θ) of time series XJˆ, i.e., the process tracing the change in the hub-agent's position, with respect to some control parameter, θ. The control parameter may be chosen from a broad set of parameters used within the team. Varying the control parameter within its range Θ allows us to compute Fisher information F(XJˆ|θ) for different values of θ ∈ Θ, and select the value maximizing Fisher information:

$$\theta^* = \operatorname*{arg,max}{\theta \in \Theta} F(X{\hat{\jmath}} | \theta) .$$

As argued in [14], the value maximizing Fisher information corresponds to a critical point, pinpointing a phase transition.

In summary, this method leads to selection of critical values of control parameters, assisting in optimizing influence of hub-agents on the oppponent team.

4 Conclusion

The main motivation behind our approach is the study of phase transitions and relevant control parameters, using interaction networks of RoboCup teams and Fisher information.

We described a method for a selection of control parameters, driven by maximizing Fisher information of a hub-agent in an information-base diagram. The mechanism is utilized by "Infographics", our new simulated soccer team which intends to participate in the RoboCup Simulation 2D League in 2014.

Acknowledgments. We thank Hidehisa Akiyama and his colleagues for development of agent2d; Mikhail Prokopenko, Peter Wang, and Oliver Obst for their advices regarding the source code of Gliders and helpful discussions of this manuscript; as well as Joseph Lizier for assistance with his Java Information Dynamics toolkit.

References

  1. Akiyama, H.: Agent2D Base Code. http://www.rctools.sourceforge.jp (2010)
  2. 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)
  3. 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)
  4. 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)
  5. Moore, E., Obst, O., Prokopenko, M., Wang, P., Held, J.: Gliders2012: Development and competition results. CoRR abs/1211.3882 (2012)
  6. 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
  7. Balch, T.: Hierarchic social entropy: An information theoretic measure of robot group diversity. Autonomous Robots 8(3) (June 2000) 209–238
  8. 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)
  9. 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
  10. 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 (selected papers from the ECAI 2000 Workshop and additional contributions), London, UK, Springer (2001) 175–197
  11. 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
  12. 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 (2003) 89–101
  13. 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)
  14. Prokopenko, M., Lizier, J.T., Obst, O., Wang, X.R.: Relating Fisher information to order parameters. Physical Review E 84(4) (2011) 041116
  15. MacKay, D.J.: Information Theory, Inference, and Learning Algorithms. Cambridge University Press, Cambridge (2003)
  16. Foreman, M., Prokopenko, M., Wang, P.: Phase transitions in self-organising sensor networks. In Banzhaf, W., Christaller, T., Dittrich, P., Kim, J.T., Ziegler, J., eds.: ECAL. Volume 2801 of Lecture Notes in Computer Science., Springer (2003) 781–791
  17. Lizier, J.T., Prokopenko, M., Zomaya, A.Y.: The information dynamics of phase transitions in random Boolean networks. In Bullock, S., Noble, J., Watson, R., Bedau, M.A., eds.: Proceedings of the Eleventh International Conference on the Simulation and Synthesis of Living Systems (ALife XI), Winchester, UK, Cambridge, MA, MIT Press (2008) 374–381
  18. Prokopenko, M., Boschetti, F., Ryan, A.J.: An information-theoretic primer on complexity, self-organization, and emergence. Complexity 15(1) (2009) 11–28
  19. Prokopenko, M.: Information dynamics at the edge of chaos: Measures, examples, and principles. In: ALIFE, IEEE (2013) 140–144
  20. Lizier, J.T., Prokopenko, M., Zomaya, A.Y.: Local information transfer as a spatiotemporal filter for complex systems. Physical Review E 77(2) (2008) 026110
  21. Lizier, J., Prokopenko, M., Zomaya, A.: A Framework for the Local Information Dynamics of Distributed Computation in Complex Systems. In Prokopenko, M., ed.: Guided Self-Organization: Inception. Volume 9 of Emergence, Complexity and Computation. Springer Berlin Heidelberg (2014) 115–158
  22. Lizier, J.T., Pritam, S., Prokopenko, M.: Information dynamics in small-world Boolean networks. Artificial Life 17(4) (2011) 293–314
  23. Lizier, J.T., Pritam, S., Prokopenko, M.: Computational capabilities of small-world boolean networks. In: Advances in Artificial Life, ECAL 2011, Proceedings of The Eleventh European Conference on the Synthesis and Simulation of Living Systems (ECAL 2011), Paris, 2011, MIT Press (2011) 463–464
  24. Schreiber, T.: Measuring information transfer. Physical Review Letters 85(2) (2000) 461–464