Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Challenges in cooperative coevolution of physically heterogeneous robot teams

  • Published:
Natural Computing Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. 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.

  2. http://cs.gmu.edu/~eclab/projects/mason/.

  3. https://cs.gmu.edu/~eclab/projects/ecj/.

  4. http://neat4j.sourceforge.net/.

  5. 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

    Article  MATH  Google Scholar 

  • 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

    Chapter  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Duan HB, Liu SQ (2010) Unmanned air/ground vehicles heterogeneous cooperative techniques: current status and prospects. Sci China Technol Sci 53(5):1349–1355

    Article  Google Scholar 

  • Ducatelle F, Di Caro G, Pinciroli C, Gambardella L (2011) Self-organized cooperation between robotic swarms. Swarm Intell 5(2):73–96

    Article  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Chapter  Google Scholar 

  • 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

    Chapter  Google Scholar 

  • Mouret JB, Doncieux S (2012) Encouraging behavioral diversity in evolutionary robotics: an empirical study. Evol Comput 20(1):91–133

    Article  Google Scholar 

  • Nelson AL, Barlow GJ, Doitsidis L (2009) Fitness functions in evolutionary robotics: a survey and analysis. Robot Auton Syst 57(4):345–370

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Nitschke GS, Eiben AE, Schut MC (2012a) Evolving team behaviors with specialization. Genet Program Evol Mach 13(4):493–536

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Nolfi S, Floreano D (2000) Evolutionary robotics. MIT Press, Cambridge

    Google Scholar 

  • Panait L (2010) Theoretical convergence guarantees for cooperative coevolutionary algorithms. Evol Comput 18(4):581–615

    Article  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • Potter MA, Jong KAD (2000) Cooperative coevolution: an architecture for evolving coadapted subcomponents. Evol Comput 8(1):1–29

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Stanley K, Miikkulainen R (2002) Evolving neural networks through augmenting topologies. Evol Comput 10(2):99–127

    Article  Google Scholar 

  • Trianni V, López-Ibáñez M (2015) Advantages of task-specific multi-objective optimisation in evolutionary robotics. PLoS one 10(8):e0136406

    Article  Google Scholar 

  • Uchibe E, Asada M (2006) Incremental coevolution with competitive and cooperative tasks in a multirobot environment. Proc IEEE 94(7):1412–1424

    Article  Google Scholar 

  • 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

    Google Scholar 

  • Yong CH, Miikkulainen R (2009) Coevolution of role-based cooperation in multiagent systems. IEEE Trans Auton Mental Dev 1(3):170–186

    Article  Google Scholar 

Download references

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

  1. BioMachines Lab, Lisbon, Portugal

    Jorge Gomes & Anders Lyhne Christensen

  2. Instituto de Telecomunicações, Lisbon, Portugal

    Jorge Gomes & Anders Lyhne Christensen

  3. BioISI, Faculdade de Ciências, Universidade de Lisboa, Lisbon, Portugal

    Jorge Gomes & Pedro Mariano

  4. Instituto Universitário de Lisboa (ISCTE-IUL), Lisbon, Portugal

    Anders Lyhne Christensen

Authors
  1. Jorge Gomes
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pedro Mariano
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Anders Lyhne Christensen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jorge Gomes.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11047-016-9582-1

Keywords

Search

Navigation