1. The complete title of the paper published in the open literature describing the work that the author claims describes a human-competitive result: Grammar-based cooperative learning for evolving collective behaviours in multi-agent systems. 2. The name, complete physical mailing address, e-mail address and phone number of each author of the paper: • Dilini Samarasinghe The School of Engineering and Information Technology The University of New South Wales at the Australian Defence Force Academy Northcott Dr, Campbell ACT 2612 d.samarasinghe@adfa.edu.au +61 4 1503 2140 • Erandi Lakshika The School of Engineering and Information Technology The University of New South Wales at the Australian Defence Force Academy Northcott Dr, Campbell ACT 2612 e.henekankanamge@adfa.edu.au +61 2 6268 8817 • Michael Barlow The School of Engineering and Information Technology The University of New South Wales at the Australian Defence Force Academy Northcott Dr, Campbell ACT 2612 m.barlow@adfa.edu.au +61 2 6268 8955 • Kathryn Kasmarik The School of Engineering and Information Technology The University of New South Wales at the Australian Defence Force Academy Northcott Dr, Campbell ACT 2612 k.kasmarik@adfa.edu.au +61 2 6268 8023 3. The name of the corresponding author: Dilini Samarasinghe 4. The abstract of the paper: This paper presents a novel grammar-based evolutionary approach which allows autonomous emergence of heterogeneity in collective behaviours. The approach adopts a context-free grammar to describe the syntax of evolving rules, which facilitates an evolutionary algorithm to evolve rule structures without manual intervention. We propose modifications to the genome structure to address the requirements of heterogeneity, and two cooperative learning architectures based on team learning and cooperative coevolution. Experimental evaluations with four behaviours illustrate that both architectures are successful in evolving heterogeneous collective behaviours. Both heterogeneous architectures surpass a homogeneous model in performance for deriving a flocking macro behaviour, however the homogeneous model is superior for evolving micro behaviours such as cohesion and alignment. The results infer that by placing the entire set of agent rules and their syntax under evolutionary control, effective solutions to complex problems can be evolved when human knowledge and intuition becomes insufficient. 5. A list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria that the author claims that the work satisfies: (D) The result is publishable in its own right as a new scientific result independent of the fact that the result was mechanically created. (E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions. (F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered. (G) The result solves a problem of indisputable difficulty in its field. 6. A statement stating why the result satisfies the criteria that the contestant claims: The multifaceted nature of many real-world requirements of multi-agent systems (MASs) could be addressed by employing heterogeneity. It facilitates adaptation to dynamic and complex conditions with maximum robustness. Nevertheless, designing heterogeneous MASs is challenging due to the inherent complications associated with human bias in exploring and tuning a substantially diverse search space of different rules and parameters. Mere intuition is insufficient to foresee which combination of parameters, rules and/or their components will result in the desired behaviour at the emergent level [1]. We propose a grammatical evolution (GE)-based approach which generates the entire set of agent rules and their syntax automatically, thus making a significant step forward in mitigating human bias and limitations of human knowledge and intuition in complex problem solving. (D) The result is publishable in its own right as a new scientific result independent of the fact that the result was mechanically created. The existing mechanisms on automatic synthesis of agent behavioural rules require significant human involvement in designing the rule structure. As a first step towards mitigating the bias associated with this, we introduced a GE-based mechanism to synthesise multi-agent behaviours for a homogeneous system, which can reduce human intervention in the rule generation process in a previous study [2]. However, in contrast to homogeneous agents, heterogeneous agent rules can complicate the process of learning as the search space for rules becomes proportional to the number of agents in the system increasing the complexity [3]. In this paper, we propose a novel model to allow autonomous emergence of heterogeneity in collective behaviours with the following contributions: - We propose a GE-based approach for synthesis of heterogeneous multi-agent behavioural rules. Unlike the existing mechanisms which require the rule structure to be pre-defined, this approach can evolve the entire rule structure from their atomic components based on a grammar which outlines the syntax of rules. - We propose a novel encoding mechanism for GE which can encode multiple behavioural rules (corresponding to different agents) in a single genome. This facilitates the representation of rules required for cooperative learning. - We introduce two cooperative learning architectures based on team learning (TL) and cooperative coevolution (CCE) for implementation of the grammar-based model. These mechanisms explore means to reduce computational costs associated with expanding agent group sizes and to avoid the evolution process getting stuck in sub-optimal solutions. - Further, we evaluate the effectiveness of the proposed models through comparisons against our previous homogenous model and state-of-the-art methods in the field which include genetic programming (GP), and particle swarm optimisation (PSO). As the above are all novel contributions to the field they can be published in its own right as a new scientific result. (E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions. Multiple computational methods such as reinforcement learning, particle swarm optimisation, evolutionary algorithms including genetic algorithms, estimation of distribution algorithms, and evolution strategy algorithms are often used to improve emergent behaviour of MASs. Nevertheless, these methods have only be used in exploring the space of states and behaviour parameters of agents [4] rather than the space of behaviour rule structures. They often either focus on evolving parameters related to pre-designed rules or on finding the best subset from a pool of manually generated behaviours to result in required emergent behaviours. They are limited in their capacity to incorporate the structure of a programme in the evolution process. As a result, autonomous emergence of heterogeneity in a MAS is difficult to achieve due to the need for pre-designed rule structures for individual agents. Manual configuration of behaviour rule structures limits the exploration of full potential of MASs in solving complex problems. In contrast to the existing models that rely on human knowledge and intuition for generating the behaviour rule structures, we automate the process by letting a GE algorithm define the syntax of the rules based on their atomic components (control structures, parameters, preliminary actions, and logical/relational connectives). Although in a typical GE model, each rule is represented by a single genome, we propose a novel mode of encoding multiple heterogeneous agent rules in the same genome to reduce computational complexity associated with population size. The GE algorithm thus designed with two learning architectures based on TL and CCE and the comparative results with GP and PSO demonstrated that our proposed model shows statistically significant performance improvement against both methods. The proposed heterogeneous model also performs better than our previous model that can only tackle homogeneous models in deriving flocking behaviour. Hence, it is a significant achievement over the existing models for generating multi-agent behaviours. (F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered. The evaluations for the proposed GE-based approach are conducted with a boids simulation. The boids model was first proposed by Reynolds [5] and it is considered one of the seminal achievements in the field of simulation of complex behaviours. Reynolds achieved emergent flocking behaviour by handcrafting 3 rules for cohesion, alignment, and separation. The model has since been used, modified, and extended in multiple research work in the area to explore complex problem solving in simulation environments; however, with significant manual intervention in the rule generation process. With our proposed approach, we achieve the same behaviours that Reynolds handcrafted, through an automatic synthesis of behaviour rule structures. We only define the atomic components of the rules which are then fed to the GE-model that automatically generates the individual rule structure, rule components, parameters, and parameter values for each agent in the heterogeneous agent system. As such, human intervention is significantly limited from the rule synthesis process which unveils potential to use such systems in complex environments where human intuition is insufficient to identify the required agent behaviour rules. (G) The result solves a problem of indisputable difficulty in its field. Limiting human intervention, and thus, the bias associated with human intervention in designing MASs, to better address complex problem requirements has been a topic of discussion for decades [1]. Although it is difficult to completely eliminate human bias, this problem has been approached through solutions such as automating the control/tuning of parameters and identifying the appropriate combinations of rule components to generate emergent complex behaviour. The model we propose is a significant milestone over the previous approaches as we focus on automating the entire process of designing the rule structures in addition to parameter tuning and identifying the appropriate combination of rule components. Specifically, automating rule structure generation for a heterogeneous agent system is challenging due to the limitations associated with scalability and the significantly large search space. Our work identifies solutions to these challenges through different learning architectures (TL and CCE). The significance of the approach lies in its ability to autonomously emerge heterogeneity within the system targeting a common goal. The significant reduction in human bias with this approach presents GE as a potential solution to shape future research on evolving complex emergent behaviours for solving real-world problems via MASs. 7. A full citation of the paper: Dilini Samarasinghe, Erandi Lakshika, Michael Barlow, and Kathryn Kasmarik. 2022. Grammar-based cooperative learning for evolving collective behaviours in multi-agent systems. In Swarm and Evolutionary Computation, 2022, 69(101017). https://doi.org/10.1016/j.swevo.2021.101017 8. A statement either that “any prize money, if any, is to be divided equally among the co-authors” OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors: Any prize money, if any, is to be divided equally among the co-authors. 9. A statement stating why the authors expect their entry would be the “best”: The contributions we have published are eminent in two primary directions. Firstly, it is a significant step forward in further reducing human bias and associated limitations in designing complex multi-agent behaviour rules. A common problem for designing MASs to solve real-world problems is the limitations in human cognitive capacity to fully explore the solution space. As a result, the generated solutions may not represent the ideal solutions to complex problems. Since our model is automated to explore the entire solution space, it can determine its own rule structures and parameter values for each individual agent. The rules generated by the model can also be extracted and re-used in similar environments. This can significantly enhance the performance of agents in complex and dynamic environmental conditions that make them more appropriate for real-world applications. Secondly, the results unveil GE as a tool to further explore the domain of MASs. GE is a relatively new branch of evolutionary computing of which the potential has not yet been fully explored. The modifications proposed here to the generic GE algorithm and the integration of GE with architectures such as TL and CCE emphasise that GE has the capacity to extend beyond its original form in addressing complex requirements which pave the path for future research. Therefore, our contributions can be used as insights into developing multi-agent-based solutions in domains that have not previously been considered. Our work is a steppingstone towards an advanced society where multi-agent systems are used across a range of tasks from menial factory jobs through to AI-based border protection models. 10. An indication of the general type of genetic or evolutionary computation used: Grammatical Evolution 11. The date of publication of the paper. If the date of publication is not on or before the deadline for submission, but instead, the paper has been unconditionally accepted for publication and is “in press” by the deadline for this competition, the entry must include a copy of the documentation establishing that the paper meets the "in press" requirement.: Published in volume 69 of the journal(Swarm and Evolutionary Computation) in March 2022; available online in the journal website since 27 November 2021 after acceptance. ------------------------------------------------------ References [1] P. Husbands, I. Harvey, D. Cliff, G. Miller. 1997. Artificial evolution: a new path for artificial intelligence? Brain Cognition. 34 (1). 130–159. https://doi.org/10.1006/brcg.1997.0910 [2] D. Samarasinghe, E. Lakshika, M. Barlow, and K. Kasmarik. 2018. Automatic synthesis of swarm behavioural rules from their atomic components. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '18). Association for Computing Machinery, New York, NY, USA. 133–140. https://doi.org/10.1145/3205455.3205546. [3] L. Panait, S. Luke. 2005. Cooperative multi-agent learning: the state of the art. Autonomous Agents and Multi-Agent Systems. 11 (3). 387–434. https://doi.org/10.1007/s10458-005-2631-2. [4] E. Conti, V. Madhavan, F.P. Such, J. Lehman, K. Stanley, J. Clune. 2018. Improving exploration in evolution strategies for deep reinforcement learning via a population of novelty-seeking agents. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (NIPS'18). Curran Associates Inc., Red Hook, NY, USA. 5032–5043. [5] C. W. Reynolds. 1987. Flocks, herds and schools: A distributed behavioural model. ACM SIGGRAPH Computer Graphics. 21. 4. 25–34.