View Original PDF

Fractals2019: Guiding Self-Organisation of Intelligent Agents

Mikhail Prokopenko, Peter Wang

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

https://osdn.net/projects/rctools/releases/p4887

Abstract Fractals2019 is a new experimental entry in the RoboCup Soccer 2D Simulation League, based on Gliders2d, which extended agent2d code base. In developing Fractals we use elements of evolutionary computation, within the framework of Guided Self-Organisation. The evolution is guided by generic universal objective functions that relate information-processing and thermodynamic properties of collective action (i.e., collective distributed computation). Tactical tasks provide constraints on control parameters, varying which is the subject of the evolutionary process. Examples include evolving dash power rates, levels of pressing and risktaking, as well as action evaluation weights, to optimise thermodynamic efficiency of collective behaviours, in addition to standard competition performance measures.

1 Introduction

The RoboCup Soccer 2D Simulation League continues to inspire fundamental research and development efforts in Artificial Intelligence, as well as general studies of complex systems and self-organisation. Simulated teams created over the years have demonstrated a number of advances in collective behaviour, which self-organises within a distributed environment of the RoboCup Soccer Simulator (RCSS), as a result of teamwork interactions and in response to opponents' actions [1–11].

Typically, self-organisation of complex behaviours is underpinned by low-level skills and dynamic world models of simulated autonomous agents, standardised over the years by several important base code releases. These include CMUnited team (USA) [12], UvA Trilearn" team (The Netherlands) [13], HELIOS team (Japan) [14], and MarliK team (Iran) [15]. In particular, we note the release in 2010 of the base code of HELIOS team, agent2d-3.0.0, later upgraded to agent2d-3.1.1. About 80% of the League's teams adopted agent2d as their base code, including our champion team, Gliders2016 [16, 11], which also utilised fragments of MarliK source code [15].

While developing Gliders, we augmented artificial evolution with human innovation, using Human-based Evolutionary Computation (HBEC) [17]. HBEC enabled optimisation of several components which we introduced and investigated between 2012 and 2016: an action-dependent evaluation function [18], a particle-swarm based self-localisation method and tactical interaction networks [19–22], dynamic tactics with Voronoi diagrams [23], bio-inspired flocking behaviour [24], and diversified opponent modelling [16].

The main factor which allowed Gliders to demonstrate a high tactical proficiency was the increased mobility of players, resulting in a better control over the field. Recently, we released the code base Gliders2d [25], version v1, with six sequential changes, from v1.1 to v1.6, mapping to six evolutionary HBEC steps (version Gliders2d-v1.0 is identical to agent2d-3.1.1). In that release we traced improvements in the team performance, with respect to the achieved goal difference and attained points, along the following steps:

  • Gliders2d-v1.1: stamina management with higher dash power rates (less conservative usage of the available stamina balance; strategy.cpp);
  • Gliders2d-v1.2: pressing behaviour (more intense pressing of the opponents in possession of the ball; bhv_basic_move.cpp);
  • Gliders2d-v1.3: action-dependent evaluator (selecting more diversified actions aiming to stretch the opposition most; sample_field_evaluator.cpp);
  • Gliders2d-v1.4: positioning of attacking players using Voronoi diagrams (maximising the potential of ball reachability; strategy.cpp);
  • Gliders2d-v1.5: defensive formations (positioning defenders and midfielders closer to own goal; *.conf);
  • Gliders2d-v1.6: modelling risk in intercept behaviours (enabling risky passes in specific situations; strict_check_pass_generator.cpp).

As noted in [25], Gliders2d is a separate evolutionary branch, different from the (Gliders2012 — Gliders2016) branch, and hence, Gliders2d-v1.6 is not a subset of any of Gliders2012 — Gliders2016 teams, although it approaches the strength of Gliders2013 [19].

Fractals2019 is a new team which is partially based on Gliders2d, while retaining some elements of the champion team Gliders2016. To a large extent, Fractals2019 is an experimental entry, motivated by a new set of aims. Specifically, we intend to redefine the fitness landscape used by evolutionary computation in terms of universal objective functions, rather than in terms of the performance metrics alone. Our overall approach attempts to achieve guided self-organisation of tactical behaviour, as described in the next section.

2 Methodology: designing thermodynamically efficient behaviours

Typically, self-organisation is defined as the evolution of a system into an organised form and/or functionality in the absence of external pressures. Guided Self-Organisation (GSO) integrates two alternatives: (i) the process of self-organisation which explores the available search space (implying autonomy), and (ii) the process of designing a desirable outcome by providing a "blueprint" (implying control) [26]. The GSO framework has been applied to several robotic scenarios, where such an integration is proposed by (i) setting task-independent universal objective functions, while (ii) placing task-dependent constraints and feedbacks on the system dynamics, so that the combination implicitly guides the resultant behaviors and interactions towards the desirable outcomes [27–35].

During self-organisation within a system, interactions among the system's elements produce a spontaneous increase in order. On one hand, in terms of distributed computation, the system increases its information-processing capabilities [36, 37, 21], manifested in statistical regularities that can be observed and measured information-theoretically [38– 42]. On the other hand, in terms of thermodynamics, this increase must be balanced by entropy production, exported to the system's exterior [43–47].

In the Fractals branch we identify several important control parameters, varying which allows us to measure the universal fitness levels via order parameters. Among the control parameters which prominently feature in Gliders2d-v1.6 we note: dash power rates used in stamina management; level of pressing (more precisely, pressure) applied to the opponents in proximity to the ball; weight factor(s) scaling the action evaluation, as well as players positioning, towards different sectors of the field; and level of risk taken in considering passes. Of course, other rates and factors can be added: the important point is that these control parameters must affect the global team behaviour, and have a sufficiently broad (preferably, continuous) range, within which they may make a transition through a critical point, separating phases with different energy profiles. Considering the corresponding energy behaviour and the overall thermodynamics is crucial to the analysis of phase transitions, and so we focus on how our control parameters affect the thermodynamic balance in Fractals. In general, the control parameters may be further constrained dependent on a specific task (e.g., defensive play, offside trap, free-kicks, and so on).

On the other hand, the order parameters are chosen to represent task-independent objectives: maximisation of spatiotemporal coordination [28, 29], maximisation of information flows [22, 42], maximisation of thermodynamic efficiency [47], etc. In particular, we focus on thermodynamic efficiency of collective computation defined, for a given value of the control parameter, as the ratio of the generated order (i.e., the reduction of uncertainty, measured as Shannon information) to the required thermodynamic work. The latter is closely related to the sensitivity of collective computation, measured as Fisher information [47]. For example, the collective motion (which is a result of distributed computation) may undergo a transition from a disordered to a coherent phase in response to changes in the number of nearest neighbours affecting an individual's alignment. The reduction in uncertainty (derivative of Shannon information) and the cumulative sensitivity (integrated Fisher information) are balanced in both disordered and coherent phases, so that their ratio, i.e., the thermodynamic efficiency, is steady. However, during a kinetic phase transition, or in other words, at the critical point, this balance is broken and the thermodynamic efficiency abruptly increases.

Evolving control parameters to critical points, where the order parameters approach the "edge of chaos", is the main goal of the Fractals team, designed within a GSO framework. Our conjecture is that at such critical regimes the resultant tactical behaviour is the most complex and diverse, and therefore, the most challenging for the opponents. In other words, we aim to evolve the behaviours that maximise the thermodynamic efficiency of collective computation underlying the teamwork.

3 Conclusions

Team Fractals2019 is based on recently released Gliders2d code base [25], built up on agent2d-3.1.1 [14]. Its development follows the methodology of Guided Self-Organisation in an attempt to evolve strong tactical performance, described by universal objective functions and restricted by task-dependent constraints. The primary universal objective that we consider is the thermodynamic efficiency of collective action, where the latter is seen, in the most generic sense, as collective distributed computation. For a specific value of a control parameter (e.g., dash power rate, risk level, and so on), the thermodynamic efficiency relates the reduction of uncertainty, measured by changes in Shannon information, to the expenditure of thermodynamic work, measured by integrated Fisher information [47]. Fractals2019 is an experimental entry aimed to verify the extent of applicability of the GSO approach, set specifically in terms of contrasting information-processing and thermodynamic factors, to RoboCup simulation.

4 Acknowledgments

We thank David Budden for developing a new self-localisation method introduced in Gliders2013 [20, 19] and Oliver Cliff for developing a new communication scheme adopted by Gliders from 2014 [23]. We are grateful to Gliders team members: Oliver Obst, particularly for establishing the tournament infrastructure supporting the team's performance evaluation on CSIRO Accelerator Cluster (Bragg) in 2012–2013, and Victor Jauregui, for several important insights on soccer tactics used in Gliders2016 [16].

References

  1. Stone, P., Veloso, M.: Task decomposition, dynamic role assignment, and low-bandwidth communication for real-time strategic teamwork. Artificial Intelligence 110(2) (June 1999) 241– 273
  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. 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
  4. 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
  5. Stone, P., Kuhlmann, G., Taylor, M.E., Liu, Y.: Keepaway soccer: From machine learning testbed to benchmark. In Noda, I., Jacoff, A., Bredenfeld, A., Takahashi, Y., eds.: RoboCup-2005: Robot Soccer World Cup IX. Volume 4020. Springer Verlag, Berlin (2006) 93–105
  6. 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
  7. Riedmiller, M., Gabel, T., Trost, F., Schwegmann, T.: Brainstormers 2d team description 2008. In: RoboCup2008. (2008)
  8. Akiyama, H., Shimora, H.: Helios2010 team description. In: RoboCup2010. (2010)
  9. Bai, A., Chen, X., MacAlpine, P., Urieli, D., Barrett, S., Stone, P.: WrightEagle and UT Austin Villa: RoboCup 2011 Simulation League Champions. In: RoboCup 2011: Robot Soccer World Cup XV. Lecture Notes in Artificial Intelligence. Springer (2012)
  10. Bai, A., Wu, F., Chen, X.: Online planning for large Markov decision processes with hierarchical decomposition. ACM Transactions on Intelligent Systems and Technology 6(4) (July 2015) 45:1–45:28
  11. Prokopenko, M., Wang, P.: Disruptive Innovations in RoboCup 2D Soccer Simulation League: From Cyberoos'98 to Gliders2016. In Behnke, S., Sheh, R., Sariel, S., Lee, D.D., eds.: RoboCup 2016: Robot World Cup XX [Leipzig, Germany, June 30 - July 4, 2016]. Volume 9776 of Lecture Notes in Computer Science., Springer (2017) 529–541
  12. Stone, P., Riley, P., Veloso, M.: The CMUnited-99 champion simulator team. In Veloso, M., Pagello, E., Kitano, H., eds.: RoboCup-99: Robot Soccer World Cup III. Volume 1856 of Lecture Notes in Artificial Intelligence. Springer Verlag, Berlin (2000) 35–48
  13. Kok, J.R., Vlassis, N., Groen, F.: UvA Trilearn 2003 team description. In Polani, D., Browning, B., Bonarini, A., Yoshida, K., eds.: Proceedings CD RoboCup 2003, Padua, Italy, Springer-Verlag (July 2003)
  14. Akiyama, H.: Agent2D Base Code. https://osdn.net/projects/rctools/ releases/p4887 (2010)
  15. 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)
  16. Prokopenko, M., Wang, P., Obst, O., Jaurgeui, V.: Gliders2016: Integrating multi-agent approaches to tactical diversity. In: RoboCup 2016 Symposium and Competitions: Team Description Papers, Leipzig, Germany, July 2016. (2016)
  17. Kosorukoff, A.: Human based genetic algorithm. In: Systems, Man, and Cybernetics, 2001 IEEE International Conference on. Volume 5., IEEE (2001) 3464–3469
  18. 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)
  19. Prokopenko, M., Obst, O., Wang, P., Budden, D., Cliff, O.M.: Gliders2013: Tactical analysis with information dynamics. In: RoboCup 2013 Symposium and Competitions: Team Description Papers, Eindhoven, The Netherlands, June 2013. (2013)
  20. 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)
  21. Lizier, J.T., Prokopenko, M., Zomaya, A.Y.: Coherent information structure in complex computation. Theory in Biosciences 131 (2012) 193–203
  22. Cliff, O.M., Lizier, J., Wang, R., Wang, P., Obst, O., Prokopenko, M.: Towards quantifying interaction networks in a football match. In Behnke, S., Veloso, M., Visser, A., Xiong, R., eds.: RoboCup 2013: Robot Soccer World Cup XVII, Springer (2013) 1–12
  23. 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)
  24. 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)
  25. Prokopenko, M., Wang, P.: Gliders2d: Source Code Base for RoboCup 2D Soccer Simulation League. CoRR abs/1812.10202 (2018)
  26. Prokopenko, M.: Guided self-organization. HFSP Journal 3(5) (2009) 287–289
  27. Nehaniv, C., Polani, D., Olsson, L., Klyubin, A.: Evolutionary information-theoretic foundations of sensory ecology: Channels of organism-specific meaningful information. Modeling Biology: Structures, Behaviour, Evolution (2005) 9–11
  28. Prokopenko, M., Gerasimov, V., Tanev, I.: Measuring spatiotemporal coordination in a modular robotic system. In Rocha, L., Yaeger, L., Bedau, M., Floreano, D., Goldstone, R., Vespignani, A., eds.: Artificial Life X: Proceedings of The 10th International Conference on the Simulation and Synthesis of Living Systems, Bloomington IN, USA (2006) 185–191
  29. Prokopenko, M., Gerasimov, V., Tanev, I.: Evolving spatiotemporal coordination in a modular robotic system. In Nolfi, S., Baldassarre, G., Calabretta, R., Hallam, J.C.T., Marocco, D., Meyer, J.A., Miglino, O., Parisi, D., eds.: From Animals to Animats 9: 9th International Conference on the Simulation of Adaptive Behavior (SAB 2006), Rome, Italy, September 25-29 2006. Volume 4095 of Lecture notes in computer science. (2006) 558–569
  30. Martius, G., Herrmann, M., Der, R.: Guided self-organisation for autonomous robot development. In Almeida e Costa, F., Rocha, L., Costa, E., Harvey, I., Coutinho, A., eds.: Advances in Artificial Life: 9th European Conference on Artificial Life (ECAL-2007), Lisbon, Portugal, September 10-14. Volume 4648 of Lecture Notes in Artificial Intelligence., Springer (2007) 766–775
  31. Klyubin, A.S., Polani, D., Nehaniv, C.L.: Representations of space and time in the maximization of information flow in the perception-action loop. Neural Computation 19(9) (2007) 2387–2432
  32. Ay, N., Bertschinger, N., Der, R., Guttler, F., Olbrich, E.: Predictive information and explorative behavior of autonomous robots. The European Physical Journal B - Condensed Matter 63 (2008) 329–339(11)
  33. Der, R., Martius, G.: The Playful Machine Theoretical Foundation and Practical Realization of Self-Organizing Robots. Springer (2012)
  34. Prokopenko, M.: Guided self-organization: Inception. Volume 9. Springer Science & Business Media (2013)
  35. Hamann, H., Khaluf, Y., Botev, J., Divband Soorati, M., Ferrante, E., Kosak, O., Montanier, J.M., Mostaghim, S., Redpath, R., Timmis, J., Veenstra, F., Wahby, M., Zamuda, A.: Hybrid societies: Challenges and perspectives in the design of collective behavior in self-organizing systems. Frontiers in Robotics and AI 3 (2016) 14
  36. Polani, D., Sporns, O., Lungarella, M.: How information and embodiment shape intelligent information processing. In Lungarella, M., Iida, F., Bongard, J., Pfeifer, R., eds.: Proceedings of the 50th Anniversary Summit of Artificial Intelligence, New York. Volume 4850 of Lecture Notes in Computer Science., Berlin / Heidelberg, Springer (2007) 99–111
  37. Wang, X.R., Lizier, J.T., Prokopenko, M.: Fisher information at the edge of chaos in random Boolean networks. Artificial Life 17(4) (2011) 315–329
  38. Klyubin, A.S., Polani, D., Nehaniv, C.L.: Empowerment: A universal agent-centric measure of control. In: Proceedings of the IEEE Congress on Evolutionary Computation, Edinburgh, Scotland. Volume 1., IEEE Press (2005) 128–135
  39. Klyubin, A.S., Polani, D., Nehaniv, C.L.: Keep your options open: An information-based driving principle for sensorimotor systems. PLoS ONE 3(12) (2008) e4018
  40. Prokopenko, M., Boschietti, F., Ryan, A.J.: An information-theoretic primer on complexity, self-organization, and emergence. Complexity 15(1) (2009) 11–28
  41. Salge, C., Polani, D.: Empowerment as replacement for the three laws of robotics. Frontiers in Robotics and AI 4 (2017) 25
  42. Cliff, O.M., Lizier, J.T., Wang, X.R., Wang, P., Obst, O., Prokopenko, M.: Quantifying longrange interactions and coherent structure in multi-agent dynamics. Artificial Life 23(1) (2017) 34–57
  43. Parrondo, J.M., Horowitz, J.M., Sagawa, T.: Thermodynamics of information. Nature Physics 11(2) (2015) 131
  44. Prokopenko, M., Einav, I.: Information thermodynamics of near-equilibrium computation. Physical Review E 91 (Jun 2015) 062143
  45. Spinney, R.E., Lizier, J.T., Prokopenko, M.: Transfer entropy in physical systems and the arrow of time. Physical Review E 94 (Aug 2016) 022135
  46. Spinney, R.E., Lizier, J.T., Prokopenko, M.: Entropy balance and information processing in bipartite and nonbipartite composite systems. Physical Review E 98 (Sep 2018) 032141
  47. Crosato, E., Spinney, R.E., Nigmatullin, R., Lizier, J.T., Prokopenko, M.: Thermodynamics and computation during collective motion near criticality. Physical Review E 97 (Jan 2018) 012120