Abstract
Heterogeneous multirobot systems have shown significant potential in many applications. Cooperative coevolutionary algorithms (CCEAs) represent a promising approach to synthesise controllers for such systems, as they can evolve multiple co-adapted components. Although CCEAs allow for an arbitrary level of team heterogeneity, in previous works heterogeneity is typically only addressed at the behavioural level. In this paper, we study the use of CCEAs to evolve control for a heterogeneous multirobot system where the robots have disparate morphologies and capabilities. Our experiments rely on a simulated task where a simple ground robot must cooperate with a complex aerial robot to find and collect items. We first show that CCEAs can evolve successful controllers for physically heterogeneous teams, but find that differences in the complexity of the skills the robots need to learn can impair CCEAs’ effectiveness. We then study how different populations can use different evolutionary algorithms and parameters tuned to the agents’ complexity. Finally, we demonstrate how CCEAs’ effectiveness can be improved using incremental evolution or novelty-driven coevolution. Our study shows that, despite its limitations, coevolution is a viable approach for synthesising control for morphologically heterogeneous systems.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
We compared the previous best strategy with choosing a random population individual as representative (Wiegand et al. 2001). The previous-best strategy outperformed the random strategy across all task setups. The results are available at http://dx.doi.org/10.5281/zenodo.47066.
The results of the preliminary experiments are available at: http://dx.doi.org/10.5281/zenodo.47066
References
Blumenthal HJ, Parker GB (2004) Co-evolving team capture strategies for dissimilar robots, vol 2. In: AAAI artificial multiagent learning symposium. AAAI Press
Candea C, Hu H, Iocchi L, Nardi D, Piaggio M (2001) Coordination in multi-agent RoboCup teams. Robot Auton Syst 36(2):67–86
Christensen AL, Dorigo M (2006) Incremental evolution of robot controllers for a highly integrated task. In: Nolfi S, Baldassarre G (eds) From animals to animats 9. Springer, Berlin, pp 473–484
Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197
Doncieux S, Mouret JB (2010) Behavioral diversity measures for evolutionary robotics. In: Congress on evolutionary computation (CEC). IEEE Press, pp 1–8
Doncieux S, Mouret JB (2014) Beyond black-box optimization: a review of selective pressures for evolutionary robotics. Evolu Intell 7(2):71–93
Dorigo M, Trianni V, Şahin E, Groß R, Labella TH, Baldassarre G, Nolfi S, Deneubourg JL, Mondada F, Floreano D et al (2004) Evolving self-organizing behaviors for a swarm-bot. Auton Robot 17(2–3):223–245
Dorigo M, Floreano D, Gambardella L, Mondada F et al (2013) Swarmanoid: a novel concept for the study of heterogeneous robotic swarms. IEEE Robot Autom Mag 20(4):60–71
Duan HB, Liu SQ (2010) Unmanned air/ground vehicles heterogeneous cooperative techniques: current status and prospects. Sci China Technol Sci 53(5):1349–1355
Ducatelle F, Di Caro G, Pinciroli C, Gambardella L (2011) Self-organized cooperation between robotic swarms. Swarm Intell 5(2):73–96
Gomes J, Christensen AL (2013) Generic behaviour similarity measures for evolutionary swarm robotics. In: Blum C, Alba E (eds) Genetic and evolutionary computation conference (GECCO). ACM Press, New York, pp 199–206
Gomes J, Mariano P, Christensen AL (2014a) Avoiding convergence in cooperative coevolution with novelty search. In: Bazzan ALC, Huhns MN, Lomuscio A, Scerri P (eds) International conference on autonomous agents and multiagent systems (AAMAS). IFAAMAS, pp 1149–1156
Gomes J, Mariano P, Christensen AL (2014b) Systematic derivation of behaviour characterisations in evolutionary robotics. In: Sayama H, Rieffel J, Risi S, Doursat R, Lipson H (eds) International conference on the synthesis and simulation of living systems (ALife). MIT Press, Berlin, pp 202–209
Gomes J, Mariano P, Christensen AL (2015a) Cooperative coevolution of morphologically heterogeneous robots. In: Andrews P, Caves L (eds) European conference on artificial life. MIT Press, pp 312–319
Gomes J, Mariano P, Christensen AL (2015b) Cooperative coevolution of partially heterogeneous multiagent systems. In: Weiss G, Yolum P, Bordini RH, Elkind E (eds) International conference on autonomous agents and multiagent systems (AAMAS). IFAAMAS, pp 297–305
Gomes J, Mariano P, Christensen AL (2015c) Devising effective novelty search algorithms: a comprehensive empirical study. In: Silva S, Esparcia-Alcázar AI (eds) Genetic and evolutionary computation conference (GECCO). ACM Press, pp 943–950
Gomes J, Duarte M, Mariano P, Christensen AL (2016a) Cooperative coevolution of control for a real multirobot system. In: Handl J, Hart E (eds) Parallel problem solving from nature – PPSN XIV. Springer, pp 591–601
Gomes J, Mariano P, Christensen AL (2016b) Novelty-driven cooperative coevolution. Evolutionary computation, (in press)
Gomez F, Miikkulainen R (1997) Incremental evolution of complex general behavior. Adapt. Behavior 5(3–4):317–342
Grabowski R, Navarro-Serment LE, Paredis CJ, Khosla PK (2000) Heterogeneous teams of modular robots for mapping and exploration. Auton Robots 8(3):293–308
Howard A, Parker LE, Sukhatme GS (2006) Experiments with a large heterogeneous mobile robot team: exploration, mapping, deployment and detection. Int J Robot Res 25(5–6):431–447
Hsieh MA, Cowley A, Keller JF, Chaimowicz L, Grocholsky B, Kumar V, Taylor CJ, Endo Y, Arkin RC, Jung B et al (2007) Adaptive teams of autonomous aerial and ground robots for situational awareness. J Field Robot 24(11–12):991–1014
Jones EG, Browning B, Dias MB, Argall B, Veloso M, Stentz A (2006) Dynamically formed heterogeneous robot teams performing tightly-coordinated tasks. In: Proceedings 2006 IEEE international conference on robotics and automation (ICRA). IEEE Press, pp 570–575
Jordan MI (1997) Serial order: a parallel distributed processing approach. In: Donahoe JW, Dorsel VP (eds) Neural-network models of cognition biobehavioral foundations, advances in psychology, vol 121. North-Holland, pp 471–495
Kistemaker S, Whiteson S (2011) Critical factors in the performance of novelty search. In: Krasnogor N, Lanzi PL (eds) Genetic and evolutionary computation conference (GECCO). ACM Press, pp 965–972
Knudson M, Tumer K (2010) Coevolution of heterogeneous multi-robot teams. In: Pelikan M, Branke J (eds) Genetic and evolutionary computation conference (GECCO). ACM Press, pp 127–134
Lacroix S, Le Besnerais G (2011) Issues in cooperative air/ground robotic systems. In: Kaneko M, Nakamura Y (eds) Robotics research, Springer tracts in advanced robotics, vol 66. Springer, Berlin, pp 421–432
Lehman J, Stanley KO (2011) Abandoning objectives: evolution through the search for novelty alone. Evol Comput 19(2):189–223
Mathews N, Christensen AL, O’Grady R, Dorigo M (2010) Cooperation in a heterogeneous robot swarm through spatially targeted communication. In: Dorigo M, Birattari M (eds) Swarm intelligence, LNCS, vol 6234. Springer, Berlin, pp 400–407
Mouret JB (2011) Novelty-based multiobjectivization. In: Doncieux S, Bredeche N, Mouret JB (eds) New horizons in evolutionary robotics, studies in computation intelligence, vol 341. Springer, Berlin, pp 139–154
Mouret JB, Doncieux S (2008) Incremental evolution of animats behaviors as a multi-objective optimization. In: Asada M, Hallam JCT, Meyer JA, Tani J (eds) From Animals to Animats 10. Springer, Berlin, pp 210–219
Mouret JB, Doncieux S (2012) Encouraging behavioral diversity in evolutionary robotics: an empirical study. Evol Comput 20(1):91–133
Nelson AL, Barlow GJ, Doitsidis L (2009) Fitness functions in evolutionary robotics: a survey and analysis. Robot Auton Syst 57(4):345–370
Nitschke GS, Schut MC, Eiben AE (2009) Collective neuro-evolution for evolving specialized sensor resolutions in a multi-rover task. Evol Intell 3(1):13–29
Nitschke GS, Eiben AE, Schut MC (2012a) Evolving team behaviors with specialization. Genet Program Evol Mach 13(4):493–536
Nitschke GS, Schut MC, Eiben AE (2012b) Evolving behavioral specialization in robot teams to solve a collective construction task. Swarm Evol Comput 2:25–38
Nolfi S, Floreano D (2000) Evolutionary robotics. MIT Press, Cambridge
Panait L (2010) Theoretical convergence guarantees for cooperative coevolutionary algorithms. Evol Comput 18(4):581–615
Parker L, Kannan B, Tang F, Bailey M (2004) Tightly-coupled navigation assistance in heterogeneous multi-robot teams. In: IEEE/RSJ international conference on intelligent robots and systems (IROS). IEEE Press, pp 1016–1022
Popovici E, De Jong K (2006) The dynamics of the best individuals in co-evolution. Nat Comput 5(3):229–255
Potter MA, Jong KAD (2000) Cooperative coevolution: an architecture for evolving coadapted subcomponents. Evol Comput 8(1):1–29
Potter MA, Meeden LA, Schultz AC (2001) Heterogeneity in the coevolved behaviors of mobile robots: the emergence of specialists. In: Nebel B (ed) International joint conference on artificial intelligence (IJCAI). Morgan Kaufmann, San Francisco, pp 1337–1343
Stanley K, Miikkulainen R (2002) Evolving neural networks through augmenting topologies. Evol Comput 10(2):99–127
Trianni V, López-Ibáñez M (2015) Advantages of task-specific multi-objective optimisation in evolutionary robotics. PLoS one 10(8):e0136406
Uchibe E, Asada M (2006) Incremental coevolution with competitive and cooperative tasks in a multirobot environment. Proc IEEE 94(7):1412–1424
Uchibe E, Nakamura M, Asada M (1998) Co-evolution for cooperative behavior acquisition in a multiple mobile robot environment. In: IEEE/RSJ international conference on intelligent robots and systems (IROS). IEEE Press, pp 425–430
Vanneschi L, Mauri G, Valsecchi A, Cagnoni S (2006) Heterogeneous cooperative coevolution: strategies of integration between GP and GA. In: Keijzer M, Cattolico M (eds) Genetic and evolutionary computation conference (GECCO). ACM Press, pp 361–368
Wiegand RP (2003) An analysis of cooperative coevolutionary algorithms. PhD thesis, George Mason University
Wiegand RP, Liles WC, De Jong KA (2001) An empirical analysis of collaboration methods in cooperative coevolutionary algorithms. In: Spector L, Goodman ED (eds) Genetic and evolutionary computation conference (GECCO). ACM Press, pp 1235–1245
Yang J, Liu Y, Wu Z, Yao M (2012) The evolution of cooperative behaviours in physically heterogeneous multi-robot systems. Int J Adv Robot Syst 9(253):1–10
Yong CH, Miikkulainen R (2009) Coevolution of role-based cooperation in multiagent systems. IEEE Trans Auton Mental Dev 1(3):170–186
Acknowledgments
This research was supported by Fundação para a Ciência e Tecnologia (FCT), under Grants SFRH/BD/89095/2012, UID/EEA/50008/2013, and UID/Multi/04046/2013.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gomes, J., Mariano, P. & Christensen, A.L. Challenges in cooperative coevolution of physically heterogeneous robot teams. Nat Comput 18, 29–46 (2019). https://doi.org/10.1007/s11047-016-9582-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11047-016-9582-1