Multi-Agent Systems (MASs) are a widely used paradigm for modeling agents that interact with each other to solve problems. Genetic algorithms represent methods mimicking natural evolution and have been successfully applied in various domains, including MASs. While evolving controllers for homogeneous agents can be considered a relatively trivial task, evolving a collective ability in a group of heterogeneous agents strongly depends on the individual's characteristics. In a genetic algorithm, the selection of the individuals forming the MAS is random and the evaluation of the group performance is afected by both the agent's ability and the environmental complexity. Consequently, the emergent dynamics of the system can be highly unpredictable, and the success or failure of the MAS may be inaccurately evaluated. To mitigate the efect of chance, we proposed a novel technique - called which allows for a better estimation of each individual's efectiveness and its contribution to the final performance of the MAS. Results collected from three diferent cooperative benchmark tasks indicate that the proposed method is efective and outperforms a traditional genetic algorithm.
CEUR ceur-ws.org
Multi-agent systems (MASs) have emerged as a significant research area that has found
applications in various fields, including industrial applications, robotics, economics, social sciences, and
more. MASs ofer flexible and decentralized approaches to problem-solving, allowing adaptation
to changes in dynamic and complex environments [
Genetic algorithms (GAs) [
In particular, multi-agent simulations aim to study emergent behavior arising from interactions between agents. Thus, GAs provide a means to uncover patterns of emergent behavior and study their underlying mechanisms. Furthermore, since MASs often require agents to adapt to dynamic environments and diverse situations, GAs furnish the opportunity to evolve agents that learn optimal strategies over time, improving their performance in response to changing conditions, taking into account multiple objectives and constraints. This is particularly beneficial in complex scenarios where solutions are based on various factors, leading to improved cooperation, coordination, and conflict resolution within multi-agent systems. Examples of genetic algorithms applied to MASs can be found in [18–23].
As pointed out in [24, 25], the use of heterogeneous agents in MASs remains an open question. Moreover, the evolution of collective behaviors in groups of heterogeneous agents is afected by two main factors: (i) the ability of each individual in the MAS and (ii) the variability of the environmental conditions. This implies that groups formed by skilled individuals acting in a simple environment are more likely to be selected compared to groups containing individuals with less capable partners in complex scenarios. In other words, randomness and chance could alter the evaluation of the individual’s capability, ultimately hindering the discovery of truly efective individuals [ 19, 26, 27]. To deal with such issues, we introduce a new method - called n-mates evaluation - allowing us to better estimate the individual’s capability within a MAS. Specifically, we designed three evolutionary scenarios involving a simple two-agent MAS, in which individuals have to collaborate in order to solve the problems. The considered problems represent benchmark tasks in the areas of swarm and evolutionary robotics. Diferently from traditional methods evaluating random pairs, the n-mates evaluation technique evaluates each individual with diferent partners sampled from the population and computes its performance as the average of the evaluations. In this work, we empirically set = 5 and combined our method with a standard genetic algorithm. We then compared its performance with the genetic algorithm, which serves as our baseline. Based on our experiments, the results indicate that the former approach outperforms the latter algorithm. Furthermore, evolved individuals are more adaptive to both the partner’s capability and the diferent environmental conditions.
Genetic algorithms (GAs) [
For the experiments reported in this work, we employed the Generational Genetic Algorithm
(GGA) [
= ∗ ∗ 2.0 (1) where is the generic gene value (integer), = 255 is the maximum gene value and
= 5.0 represents the weight range. We used the same settings as in [
We used the n-mates evaluation technique to improve the performance of the GGA. The resulting algorithm is described in Fig. 3. As it can be observed, the n-mates evaluation method only afects the agent’s evaluation (i.e., the computation of the fitness value).
In this section, we describe the evolutionary tasks we used. We consider three benchmark
problems largely employed in the fields of swarm and evolutionary robotics [
The foraging task is considered a benchmark problem in robotics and MASs [
Although the task is quite trivial, it does not necessarily require the collaboration of the two agents. In fact, the problem can be solved simply if the two agents reach a food element in distinct time steps. There is no pressure on explicit coordination of the robots. Nonetheless, an individual capable of reaching quickly the food item might be penalized if evaluated with an unable partner.
In this scenario, we designed a variant of the “Pursuit and Evasion” problems [42, 44] in which three E-puck robots are randomly placed in the environment, with one acting as a predator (Fig. 4(b)). All the agents have the same capabilities. The goal for the evolving agents (acting as preys, blue in Fig. 4(b)) is to avoid being captured by the predator (green in Fig. 4(b)). This can be achieved by staying as close as possible. More specifically, the minimum distance that guarantees the agents cannot be captured by the predator corresponds to the diameter of a robot. This design choice was made considering that this value prevents the predator from standing between the agents. The fitness function for the problem is reported in Eq. 3: (2) (3) = 1 ∑ (1.0 − =1 _ _ ) where is the number of episodes, _ is the distance of the agents at the end of the episode and _ is the maximum distance of the robots in the environment. Specifically, _ corresponds to the diagonal of the arena. The fitness value is bounded in the range [0.0, 1.0].
In order to solve this task, the agents may develop two potential capabilities:
2. they may escape from the predator in order to avoid being captured.
It is worth noting that the predator moves according to a predefined routine computing its direction of motion based on the closest detected prey. A possible solution for the agent under evaluation is to move rapidly and reach the partner before the arrival of the predator. This implies that a very fast individual can solve the problem even if the mate is an unable agent that stays still or turns on the spot.
Aggregation represents a very simple example of self-organized behavior in various species of
animals [54] and typically comes from a shared decision among the members of the group [55].
Several works demonstrated how an aggregation behavior can emerge through the interaction
of multiple agents in a MAS [
Here, we consider two E-puck robots placed in the arena. A red circular area of 30 diameter is randomly located in the environment (Fig. 4(c)). There is a cylinder object (with a diameter of 2.5 ) placed at the center of the area indicating its presence. The goal for the agents is to reach the aggregation area and spend as much time as possible within it. The fitness function is given by Eq. 4:
= 1 ∑=1 _ _ _ (4) where is the number of episodes, indicates the number of steps of each episode and _ _ _ represents the number of steps the two agents spent together over the aggregation area. Similarly to the “escaping from predator” task, the fitness value is bounded in the range [0.0, 1.0].
Diferently from the other evolutionary problems, in this case, the robots are equipped with an additional ground sensor allowing the agents to recognize the presence of the area when they pass over it.
In order to solve the evolutionary problem, the agents must develop the following capabilities:
2. stay on the area as much time as possible.
Similar to the foraging problem, the agents are not required to explicitly coordinate their arrival at the aggregation area, nor do they need to detect the other mate. However, only when both agents are over the area the fitness increases. This implies that a robot capable of detecting and remaining within the area will not receive a fitness score if its partner is an incapable agent that remains stationary or rotates in place. Consequently, this task is considerably more challenging than the other two problems since the agent’s evaluation is strongly dependent on the mate’s capabilities.
The network architecture employed for the experiments described above is depicted in Fig. 5.
We adopted the controller used in [
Figures 6-8 show the performance of the two algorithms we used. As it can be seen, the n-mates evaluation technique allows us to obtain better performances on average than the GGA algorithm at the end of the evolutionary process in all the considered scenarios. Specifically, results are statistically significant for both the “foraging” and the “escaping from predator” problems (Mann-Whitney U test, < 0.05 ), while there is no diference concerning the “aggregation” task (Mann-Whitney U test, > 0.05 ). This indicates that our method is able to discover solutions generalizing with respect to the capabilities of the partner. To further support this claim, we run a post-evaluation phase in which evolved individuals are tested with 25 diferent partners randomly drawn from the final population. Diferently from evolution, the test phase is deterministic, i.e. individuals experience the same initial conditions at the beginning of each episode. Overall, we evaluated 2000 individuals. The results of the post-evaluation (see Fig. 9) demonstrate how the n-mates evaluation technique evolved better generalizing individuals than the GGA algorithm in all three problems (Mann-Whitney U test, < 0.05 ). This implies that the former method leads to the discovery of truly efective and adaptive solutions. It is worth noting that this outcome has been obtained at no computational cost.
Figures 6-8 indicate that the n-mates evaluation method requires a bootstrap phase during the first part of the evolution before reaching performances comparable to those of the GGA. Specifically, it requires 108 evaluation steps in the case of the “foraging” and the “escaping from predator” problems (Figures 6 and 7) and 2 × 108 evaluation steps in the case of the “aggregation” task (Fig. 8). This is not surprising: at the beginning of the evolution, individuals are generally bad at dealing with the task. In collective problems involving the cooperation of heterogeneous agents, evaluating each individual with random mates is more likely to produce lower performance than the GGA, which evaluates an agent with a single peer. Notwithstanding this initial slow convergence, the n-mates evaluation procedure is able to evolve efective and generalizing agents, which adapt their behavior based on the partners’ capabilities.
Our analyses reveal diferences among the evolutionary problems. Specifically, both the n-mates evaluation method and the GGA algorithm obtain good performances on the “foraging” and the “escaping from predator” problems, while their fitness is quite low in the case of the “aggregation” task. This diference might be partially ascribed to the diferent stimuli agents perceive. In fact, in the former problems, the robots may only receive two types of visual inputs provided by both the peer (blue input of the linear camera sensor) and another object that can be either the food item or the predator. Conversely, in the latter task, the agent has to deal simultaneously with both visual stimuli provided by the camera (one from the mate and one from the cylinder inside the area) and the information obtained through the ground sensor. Put in other words, the agent has to properly manage two diferent types of inputs and map them into an efective behavior. Therefore, the “aggregation” problem is more complex than the other tasks. In addition, this task is strongly more dependent on the partner’s capabilities than the other problems. Indeed, given the limited dimension of the cylinder object (see section 3.3), the agents must develop an exploratory capability in order to look for the aggregation area and reach it. However, if the peer does not display the same ability, the performance of the evolving agent will be low even if it succeeds in quickly arriving at the target area.
MAS is a well-established paradigm across various domains, due to features like flexibility, decentralization and adaptation to environmental changes. Extensive research has demonstrated the efectiveness of applying MAS to diferent fields. However, exploiting the potentiality of MASs in dealing with heterogeneous agents presents some challenges, mainly dependent on the individual’s characteristics and the specific environmental conditions. In this work, we presented the n-mates evaluation technique, a novel method able to improve the performance of a genetic algorithm and, at once, estimate better the actual capability of an individual in heterogeneous MASs. Specifically, we designed three scenarios in which two agents have to collaborate so as to solve the evolutionary problems. We demonstrated how our approach is efective and outperforms a standard genetic algorithm. Moreover, the evolved individuals represent truly efective solutions, i.e., they exhibit an adaptive behavior regardless of the capability of the partners they are evaluated with. Notably, the proposed method allows the discovery of adaptive agents without adding computational complexity to the genetic algorithm it is combined with since it only afects the agent’s evaluation. However, the technique leads to the evolution of a population of flexible agents experiencing diferent environmental conditions, where the partner’s capabilities are unknown. This, in turn, allows for the optimization of the exploration-exploitation trade-of because the evolved individuals can immediately adapt to new random mates without incurring additional costs. As a result, the search space exploration is reduced, and the evolutionary process can benefit from the solutions found thus far.
The results of our analysis are promising, but further research is needed to validate the approach more comprehensively. In the future, we plan to extend our study to larger groups of agents, similarly to the experiments reported in [21, 22]. We are also interested in evaluating the technique in more challenging domains, in which the capability of each individual is paramount. Moreover, the parameter has been set empirically. Future work should be devoted to the analysis of the relationship between the value of and the final performance. In addition, we are investigating the possibility to adapt the parameter based on the individual’s fitness, without any need to fix it a priori. Finally, we are considering the use of the n-mates evaluation procedure in combination with modern evolutionary algorithms, such as OpenAI-ES [20, 57, 58], which proved their eficacy in many problems including a swarm robotics scenario [ 21]. via a modified genetic algorithm, IEEE Transactions on Neural Networks and Learning Systems (2022). [12] J. Zhou, X. Zhao, X. Zhang, D. Zhao, H. Li, Task allocation for multi-agent systems based on distributed many-objective evolutionary algorithm and greedy algorithm, Ieee Access 8 (2020) 19306–19318. [13] D. E. Golberg, Genetic algorithms in search, optimization, and machine learning, Addion wesley 1989 (1989) 36. [14] M. Mitchell, Genetic algorithms: An overview., Complex. 1 (1995) 31–39. [15] J. McCall, Genetic algorithms for modelling and optimisation, Journal of Computational and Applied Mathematics 184 (2005) 205–222. [16] I.-K. Jeong, J.-J. Lee, Evolving multi-agents using a self-organizing genetic algorithm,
Applied Mathematics and Computation 88 (1997) 293–303. [17] J.-P. Vacher, T. Galinho, F. Lesage, A. Cardon, Genetic algorithms in a multi-agent system, in: Procs. IEEE International Joint Symposia on Intelligence and Systems, 1998, pp. 17–26. [18] W. Gruszczyk, H. Kwasnicka, Coalition formation in multi-agent systems—an evolutionary approach, in: International Multiconference on Computer Science and Information Technology, IEEE, 2008, pp. 125–130. [19] P. Pagliuca, S. Nolfi, Robust optimization through neuroevolution, PLOS ONE 14 (2019) 1–27. [20] P. Pagliuca, N. Milano, S. Nolfi, Eficacy of modern neuro-evolutionary strategies for continuous control optimization, Frontiers in Robotics and AI 7 (2020) 98. [21] P. Pagliuca, A. Vitanza, Self-organized aggregation in group of robots with OpenAI-ES, in:
Int. Conf. on Soft Computing and Pattern Recognition, Springer, 2022, pp. 770–780. [22] P. Pagliuca, A. Vitanza, Evolving aggregation behaviors in swarms from an evolutionary algorithms point of view, in: Applications of Artificial Intelligence and Neural Systems to Data Science, Springer, 2023, pp. 317–328. [23] J. Yang, Z. Luo, Coalition formation mechanism in multi-agent systems based on genetic algorithms, Applied Soft Computing 7 (2007) 561–568. [24] M. Dorigo, G. Theraulaz, V. Trianni, Reflections on the future of swarm robotics, Science
Robotics 5 (2020) eabe4385. [25] M. Dorigo, G. Theraulaz, V. Trianni, Swarm robotics: Past, present, and future [point of view], Proceedings of the IEEE 109 (2021) 1152–1165. [26] J. T. Carvalho, S. Nolfi, The role of morphological variation in evolutionary robotics:
Maximizing performance and robustness, Evolutionary Computation (2023) 1–18. [27] N. Milano, J. T. Carvalho, S. Nolfi, Environmental variations promotes adaptation in artificial evolution, in: IEEE Symposium Series on Comput. Intell. (SSCI), 2017, pp. 1–7. [28] D. E. Goldberg, J. Richardson, et al., Genetic algorithms with sharing for multimodal function optimization, in: Genetic algorithms and their applications: Proceedings of the Second International Conference on Genetic Algorithms, volume 4149, Hillsdale, NJ: Lawrence Erlbaum, 1987. [29] T. Alam, S. Qamar, A. Dixit, M. Benaida, Genetic algorithm: Reviews, implementations, and applications, arXiv preprint arXiv:2007.12673 (2020). [30] H. Dawid, Adaptive learning by genetic algorithms: Analytical results and applications to economic models, Springer Science & Business Media, 2011. [31] C. García-Martínez, F. J. Rodriguez, M. Lozano, Genetic algorithms, in: Handbook of heuristics, Springer, 2018, pp. 431–464. [32] A. Ghaheri, S. Shoar, M. Naderan, S. S. Hoseini, The applications of genetic algorithms in medicine, Oman medical journal 30 (2015) 406. [33] I. Gómez-Vargas, J. B. Andrade, J. A. Vázquez, Neural networks optimized by genetic algorithms in cosmology, Physical Review D 107 (2023) 043509. [34] S. Nolfi, O. Miglino, D. Parisi, Phenotypic plasticity in evolving neural networks, in:
Proceedings of PerAc’94. From Perception to Action, IEEE, 1994, pp. 146–157. [35] V. Trianni, E. Tuci, M. Dorigo, Evolving functional self-assembling in a swarm of autonomous robots, From Animals to Animats 8 (2004) 405–414. [36] S. Tung Ngo, J. Jafreezal, G. Hoang Nguyen, A. Ngoc Bui, A genetic algorithm for multiobjective optimization in complex course timetabling, in: 2021 10th International Conference on Software and Computer Applications, 2021, pp. 229–237. [37] A. P. Wieland, Evolving neural network controllers for unstable systems, in: International
Joint Conference on Neural Networks, volume 2, IEEE, 1991, pp. 667–673. [38] A. Liu, Y. Zhang, H. Zhao, S. Wang, D. Sun, Neural network control system of cooperative robot based on genetic algorithms, Neural Computing and Applications 33 (2021) 8217–8226. [39] T. Salloom, X. Yu, W. He, O. Kaynak, Adaptive neural network control of underwater robotic manipulators tuned by a genetic algorithm, Journal of Intelligent & Robotic Systems 97 (2020) 657–672. [40] X. Yao, A review of evolutionary artificial neural networks, International journal of intelligent systems 8 (1993) 539–567. [41] J. J. Grefenstette, et al., Genetic algorithms for changing environments, in: Ppsn, volume 2,
Citeseer, 1992, pp. 137–144. [42] F. Gomez, R. Miikkulainen, Incremental evolution of complex general behavior, Adaptive
Behavior 5 (1997) 317–342. [43] Q. Lu, G. M. Fricke, J. C. Ericksen, M. E. Moses, Swarm foraging review: Closing the gap between proof and practice, Current Robotics Reports 1 (2020) 215–225. [44] G. F. Miller, D. Clif, Protean behavior in dynamic games: Arguments for the co-evolution of pursuit-evasion tactics, From animals to animats 3 (1994) 411–420. [45] E. H. Ostergaard, G. S. Sukhatme, M. J. Matari, Emergent bucket brigading: a simple mechanisms for improving performance in multi-robot constrained-space foraging tasks, in: Proc. of the fith international conference on Autonomous agents, 2001, pp. 29–30. [46] A. F. Winfield, Towards an engineering science of robot foraging, Distributed autonomous robotic systems 8 (2009) 185–192. [47] G. Massera, T. Ferrauto, O. Gigliotta, S. Nolfi, FARSA: An Open Software Tool for Embodied Cognitive Science, in: Proceedings of the 12th European Conference on Artificial Life (ECAL 2013), 2013, pp. 538–545. [48] G. Massera, T. Ferrauto, O. Gigliotta, S. Nolfi, Designing adaptive humanoid robots through the farsa open-source framework, Adaptive Behavior 22 (2014) 255–265. [49] J. T. Carvalho, S. Nolfi, Behavioural plasticity in evolving robots, Theory in Biosciences 135 (2016) 201–216. [50] J. de Greef, S. Nolfi, Evolution of implicit and explicit communication in mobile robots, in: Evolution of communication and language in embodied agents, Springer, 2009, pp. 179–214. [51] P. Pagliuca, S. Nolfi, Integrating learning by experience and demonstration in autonomous robots, Adaptive Behavior 23 (2015) 300–314. [52] V. Sperati, V. Trianni, S. Nolfi, Evolving coordinated group behaviours through maximisation of mean mutual information, Swarm Intelligence 2 (2008) 73–95. [53] F. Mondada, M. Bonani, X. Raemy, J. Pugh, C. Cianci, A. Klaptocz, S. Magnenat, J.-C.
Zuferey, D. Floreano, A. Martinoli, The e-puck, a Robot Designed for Education in Engineering, in: Proceedings of the 9th conference on autonomous robot systems and competitions, IPCB: Instituto Politécnico de Castelo Branco, 2009, pp. 59–65. [54] R. Jeanson, C. Rivault, J.-L. Deneubourg, S. Blanco, R. Fournier, C. Jost, G. Theraulaz,
Self-organized aggregation in cockroaches, Animal behaviour 69 (2005) 169–180. [55] S. Garnier, C. Jost, R. Jeanson, J. Gautrais, M. Asadpour, G. Caprari, G. Theraulaz, Aggregation behaviour as a source of collective decision in a group of cockroach-like-robots, in: European conference on artificial life, Springer, 2005, pp. 169–178. [56] F. Silva, L. Correia, A. L. Christensen, Evolutionary online behaviour learning and adaptation in real robots, Royal Society open science 4 (2017) 160938. [57] P. Pagliuca, S. Nolfi, The dynamic of body and brain co-evolution, Adaptive Behavior 30 (2022) 245–255. [58] T. Salimans, J. Ho, X. Chen, S. Sidor, I. Sutskever, Evolution strategies as a scalable alternative to reinforcement learning (2017).