CoChat
Sign Up
Cited by 20Advanced Multi-Objective Optimization AlgorithmsEvolutionary Algorithms and ApplicationsMetaheuristic Optimization Algorithms Research

Evolving multimodal robot behavior via many stepping stones with the combinatorial multiobjective evolutionary algorithm

Open access
Huizinga, Joost, Clune, Jeff·2022·Evolutionary Computation
DOI 10.1162/evco_a_00301
Open this paper in CoChat — free accountOpen PDF

Abstract

An important challenge in reinforcement learning is to solve multimodal problems, where agents have to act in qualitatively different ways depending on the circumstances. Because multimodal problems are often too difficult to solve directly, it is often helpful to define a curriculum, which is an ordered set of subtasks that can serve as the stepping stones for solving the overall problem. Unfortunately, choosing an effective ordering for these subtasks is difficult, and a poor ordering can reduce the performance of the learning process. Here, we provide a thorough introduction and investigation of the Combinatorial Multiobjective Evolutionary Algorithm (CMOEA), which allows all combinations of subtasks to be explored simultaneously. We compare CMOEA against three algorithms that can similarly optimize on multiple subtasks simultaneously: NSGA-II, NSGA-III, and ε-Lexicase Selection. The algorithms are tested on a function-optimization problem with two subtasks, a simulated multimodal robot locomotion problem with six subtasks, and a simulated robot maze-navigation problem where a hundred random mazes are treated as subtasks. On these problems, CMOEA either outperforms or is competitive with the controls. As a separate contribution, we show that adding a linear combination over all objectives can improve the ability of the control algorithms to solve these multimodal problems. Lastly, we show that CMOEA can leverage auxiliary objectives more effectively than the controls on the multimodal locomotion task. In general, our experiments suggest that CMOEA is a promising algorithm for solving multimodal problems.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1162/evco_a_00301

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Classical RL and imitation learning approaches operate on primitive actions, which could be challenging for systematic exploration, interpretability, and generalization.

    “Classical approaches employ reinforcement learning (RL) [6, 7] and imitation learning [8-10] that operate on primitive actions, which could be challenging for systematic exploration [11-15], interpretability [16-18], and generalization [19-21].”

    From Voyager: An Open-Ended Embodied Agent with Large Language Models (2023) · cites this paper as [12]

    The Introduction says multimodal problems can be difficult to solve directly, and the paper describes CMOEA as exploring combinations of subtasks simultaneously. This supports an exploration challenge in reinforcement learning, but our copy does not say that classical RL and imitation learning operate on primitive actions or that primitive actions cause difficulties with systematic exploration, interpretability, or generalization. (LLM, conf=0.76)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

No citation lists for this paper

No citation lists for this paper yet — checked again daily.

References 60 · Cited by 20

Research works printed but not linked: 65

  1. X. Li and R. Miikkulainen. Evolving multimodal behav- ior through subtask and switch neural networks. In Proc. Int. Conf. Synt. & Sim. Living Systems, 2014.
  2. J. Schrum and R. Miikkulainen. Evolving multimodal behavior with modular neural networks in Ms. Pac-Man. In Proc. Genetic & Evolutionary Comput. Conf, pages 325-332. ACM, 2014.
  3. L. Spector. Assessment of problem modality by dif- ferential performance of lexicase selection in genetic programming: a preliminary report. In Proc. Genetic & Evolutionary Comput. Conf, pages 401-408. ACM, 2012.
  4. B. F. Skinner. Reinforcement today. American Psychol- ogist, 13(3):94, 1958.
  5. G. B. Peterson. A day of great illumination: B. F. Skinner's discovery of shaping. Jour. Experimental Analysis of Behavior, 82(3):317-328, 2004.
  6. F. Gomez and R. Miikkulainen. Incremental evolution of complex general behavior. Adaptive Behavior, 5(3-4): 317-342, 1997.
  7. M. A. Lewis, A. H. Fagg, and A. Solidum. Genetic programming approach to the construction of a neural network for control of a walking robot. In Proc. IEEE Int. Conf. Robotics & Automation, pages 2618-2623. IEEE, 1992.
  8. M. A. Lewis, A. H. Fagg, and G. A. Bekey. Genetic algorithms for gait synthesis in a hexapod robot. In Recent trends in mobile robots, pages 317-331. World Scientific, 1993.
  9. T. Larsen and S. T. Hansen. Evolving composite robot behaviour-a modular architecture. In Proc. Int. Work. Robot Motion & Control, pages 271-276. IEEE, 2005.
  10. D. Lessin, D. Fussell, and R. Miikkulainen. Open-ended behavioral complexity for evolved virtual creatures. In Proc. Genetic & Evolutionary Comput. Conf, pages 335- 342. ACM, 2013.
  11. J.-B. Mouret and S. Doncieux. Incremental evolution of animats' behaviors as a multi-objective optimization. From Animals to Animats 10, pages 210-219, 2008.
  12. J. Bongard. Behavior chaining-incremental behavior integration for evolutionary robotics. In ALIFE, pages 64-71, 2008.
  13. J. Auerbach and J. C. Bongard. How robot morphology and training order affect the learning of multiple behav- iors. In Proc. IEEE Cong. Evolutionary Comput, pages 39-46. IEEE, 2009.
  14. B. G. Woolley and K. O. Stanley. On the deleterious effects of a priori objectives on evolution and represen- tation. In Proc. Genetic & Evolutionary Comput. Conf, pages 957-964. ACM, 2011.
  15. A. M. Nguyen, J. Yosinski, and J. Clune. Innovation engines: Automated creativity and improved stochastic optimization via deep learning. In Proc. Genetic & Evolutionary Comput. Conf, pages 959-966. ACM, 2015.
  16. J. Huizinga, J.-B. Mouret, and J. Clune. Does align- ing phenotypic and genotypic modularity improve the evolution of neural networks? In Proc. Genetic & Evolutionary Comput. Conf. ACM, 2016. doi: 10.1145/ 2908812.2908836. · DOI
  17. K. Deb, A. Pratap, S. Agarwal, and T. A. M. T. Meyari- van. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evolutionary Comput, 6(2):182- 197, 2002.
  18. K. Deb and H. Jain. An evolutionary many-objective optimization algorithm using reference-point-based non- dominated sorting approach, part I: solving problems with box constraints. IEEE Trans. Evolutionary Comput, 18(4):577-601, 2013.
  19. W. La Cava, L. Spector, and K. Danai. ε-lexicase selection for regression. In Proc. Genetic & Evolutionary Comput. Conf, pages 741-748. ACM, 2016.
  20. J. M. Moore and A. Stanton. Lexicase selection out- performs previous strategies for incremental evolution of virtual creature controllers. In Proc. European Conf. Artificial Life, pages 290-297. MIT Press, 2017.
  21. N. Justesen, R. R. Torrado, P. Bontrager, A. Khalifa, J. Togelius, and S. Risi. Illuminating generalization in deep reinforcement learning through procedural level generation. arXiv preprint arXiv:1806.10729, 2018. · arXiv
  22. R. S. Sutton. Integrated architectures for learning, planning, and reacting based on approximating dynamic programming. In Machine Learning Proceedings 1990, pages 216-224. Elsevier, 1990.
  23. S. Nolfi and D. Parisi. Evolving non-trivial behaviors on real robots: an autonomous robot that picks up objects. Topics in artificial intelligence, pages 243-254, 1995.
  24. J. Schrum and R. Miikkulainen. Evolving agent behavior in multiobjective domains using fitness-based shaping. In Proc. Genetic & Evolutionary Comput. Conf, pages 439- 446. ACM, 2010.
  25. A. G. Barto and S. Mahadevan. Recent advances in hier- archical reinforcement learning. Discrete Event Dynamic Systems, 13(4):341-379, 2003.
  26. J. Pieter and E. D. de Jong. Evolutionary multi-agent systems. In Parallel Problem Solving from Nature, pages 872-881. Springer, 2004.
  27. A. Agogino and K. Tumer. Efficient evaluation functions for evolving coordination. Evolutionary Computation, 16 (2):257-288, 2008.
  28. J. Lehman and K. O. Stanley. Abandoning objectives: Evolution through the search for novelty alone. Evolu- tionary Computation, 19(2):189-223, 2011.
  29. J.-B. Mouret and S. Doncieux. Encouraging behavioral diversity in evolutionary robotics: an empirical study. Evolutionary Computation, 1(20), 2012.
  30. A. Cully, J. Clune, D. Tarapore, and J.-B. Mouret. Robots that can adapt like animals. Nature, 521(7553):503-507, 2015.
  31. V. Khare, X. Yao, and K. Deb. Performance scaling of multi-objective evolutionary algorithms. In Int. Conf. Evolutionary Multi-criterion Optimization, pages 376- 390. Springer, 2003.
  32. H. Ishibuchi, N. Tsukamoto, and Y. Nojima. Evolu- tionary many-objective optimization: A short review. In IEEE World Cong. Comput. Intelligence, pages 2419- 2426. IEEE, 2008.
  33. T. Wagner, N. Beume, and B. Naujoks. Pareto- , aggregation-, and indicator-based methods in many- objective optimization. In Int. Conf. Evolutionary Multi- criterion Optimization, pages 742-756. Springer, 2007.
  34. P. J. Fleming, R. C. Purshouse, and R. J. Lygoe. Many- objective optimization: An engineering design perspec- tive. In Int. Conf. Evolutionary Multi-criterion Optimiza- tion, pages 14-32. Springer, 2005.
  35. K. Deb. Multi-objective optimization using evolutionary algorithms, volume 16. Wiley, 2001.
  36. K. Deb and H. Jain. Handling many-objective problems using an improved NSGA-II procedure. In Proc. IEEE Cong. Evolutionary Comput, pages 1-8. IEEE, 2012.
  37. M. Laumanns, L. Thiele, K. Deb, and E. Zitzler. Com- bining convergence and diversity in evolutionary mul- tiobjective optimization. Evolutionary Computation, 10 (3):263-282, 2002.
  38. P. J. Bentley and J. P. Wakefield. Finding acceptable solutions in the pareto-optimal range using multiobjective genetic algorithms. In Soft Comput. Engineering Design & Manufacturing, pages 231-240. Springer, 1998.
  39. N. Drechsler, R. Drechsler, and B. Becker. Multi- objective optimisation based on relation favour. In Int. Conf. Evolutionary Multi-criterion Optimization, pages 154-166. Springer, 2001.
  40. C. M. Fonseca, P. J. Fleming, et al. Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization. In Proc. Int. Conf. Genetic Algo- rithms, volume 93, pages 416-423. Citeseer, 1993.
  41. J. Horn, N. Nafpliotis, and D. E. Goldberg. A niched pareto genetic algorithm for multiobjective optimization. In IEEE Cong. Evolutionary Comput, pages 82-87. Ieee, 1994.
  42. N. Srinivas and K. Deb. Multiobjective optimization using nondominated sorting in genetic algorithms. Evo- lutionary Computation, 2(3):221-248, 1994.
  43. J. Lehman and K. O. Stanley. Evolving a diversity of virtual creatures through novelty search and local competition. In Proc. Genetic & Evolutionary Comput. Conf, pages 211-218. ACM, 2011.
  44. J. Clune, J.-B. Mouret, and H. Lipson. The evolutionary origins of modularity. Proc. Royal Society B, 280(1755): 20122863, 2013.
  45. H. Mengistu, J. Huizinga, J.-B. Mouret, and J. Clune. The evolutionary origins of hierarchy. PLoS Comput. Biol, 12(6):e1004829, 2016.
  46. K. O. Ellefsen, J.-B. Mouret, and J. Clune. Neural modularity helps organisms evolve to learn new skills without forgetting old skills. PLoS Comput. Biol, 11(4): e1004128, 2015.
  47. W. La Cava, T. Helmuth, L. Spector, and J. H. Moore. A probabilistic and multi-objective analysis of lexicase selection and ε-lexicase selection. Evolutionary Compu- tation, pages 1-28, 2018.
  48. K. O. Stanley and R. Miikkulainen. Evolving neural networks through augmenting topologies. Evolutionary Computation, 10(2):99-127, 2002.
  49. R. D. Beer and J. C. Gallagher. Evolving dynamical neu- ral networks for adaptive behavior. Adaptive behavior, 1 (1):91, 1992.
  50. K. O. Stanley, D. B. D'Ambrosio, and J. Gauci. A hypercube-based encoding for evolving large-scale neural networks. Artificial Life, 15(2):185-212, 2009.
  51. J. K. Pugh and K. O. Stanley. Evolving multimodal con- trollers with HyperNEAT. Proc. Genetic & Evolutionary Comput. Conf, page 735, 2013.
  52. P. Verbancsics and K.O. Stanley. Constraining connec- tivity to encourage modularity in hyperneat. In Proc. Genetic & Evolutionary Comput. Conf, pages 1483- 1490. ACM, 2011.
  53. M. Jaderberg, V. Mnih, W. M. Czarnecki, T. Schaul, J. Z. Leibo, D. Silver, and K. Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. arXiv preprint arXiv:1611.05397, 2016. · arXiv
  54. P. Mirowski, R. Pascanu, F. Viola, H. Soyer, A. J. Ballard, A. Banino, M. Denil, R. Goroshin, L. Sifre, K. Kavukcuoglu, et al. Learning to navigate in complex environments. arXiv preprint arXiv:1611.03673, 2016. · arXiv
  55. M. E. J. Newman. Modularity and community structure in networks. Proc. Nat'l Acad. Sciences, 103(23):8577- 8582, 2006.
  56. E. A. Leicht and M. E. J. Newman. Community structure in directed networks. Physical review letters, 100(11): 118703-118707, 2008.
  57. K. O. Stanley. Compositional pattern producing net- works: A novel abstraction of development. Genetic Programming and Evolvable Machines, 8(2):131-162, 2007.
  58. E. Meyerson, J. Lehman, and R. Miikkulainen. Learning behavior characterizations for novelty search. In Proc. Genetic & Evolutionary Comput. Conf, pages 149-156. ACM, 2016.
  59. AM Reynolds. Maze-solving by chemotaxis. Physical Review E, 81(6):062901, 2010.
  60. J. Lehman and R. Miikkulainen. Enhancing divergent search through extinction events. In Proc. Genetic & Evolutionary Comput. Conf, pages 951-958. ACM, 2015.
  61. T. Krink and R. Thomsen. Self-organized criticality and mass extinction in evolutionary algorithms. In IEEE Cong. Evolutionary Comput, volume 2, pages 1155- 1161. IEEE, 2001.
  62. N. Kashtan, M. Parter, E. Dekel, A. E. Mayo, and U. Alon. Extinctions in heterogeneous environments and the evolution of modularity. Evolution, 63(8):1964-1975, 2009.
  63. C. Stanton and J. Clune. Curiosity search: producing generalists by encouraging individuals to continually explore and acquire skills throughout their lifetime. PloS one, 11(9):e0162235, 2016.
  64. K. Deb. Multi-objective optimization using evolutionary algorithms, volume 16. John Wiley & Sons, 2001.
  65. J.-B. Mouret. Novelty-based multiobjectivization. In New horizons in evolutionary robotics, pages 139-154. Springer, 2011.

Authors
Huizinga, J., & Clune, J.
Affiliations
  • OpenAI (United States) (US)
  • University of British Columbia (CA)
ORCID
Venue
Evolutionary Computation
Publisher
MIT Press - Journals
Published
2022-04-25
Volume
30
Issue
2
Pages
131-164
ISSN
  • 1063-6560 (ISSN-L)
  • 1530-9304
DOI
10.1162/evco_a_00301
OpenAlex
W2860358344
Cited by
20
References
60
Citations by year
2026: 3 · 2025: 2 · 2024: 3 · 2023: 1 · 2022: 3 · 2021: 3 · 2020: 2 · 2019: 3
FWCI
1.31
Type
journal article
Language
en
Open access
Locations
  • Evolutionary Computation (publishedVersion)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
National Science Foundation (CAREER, 1453549)
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Multi-Objective Optimization Algorithms
  • Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
Keywords
curriculum learning, robot locomotion, NSGA-II, NSGA-III, auxiliary objectives, function optimization
MeSH terms
Algorithms, Biological Evolution, Learning, Problem Solving, Robotics

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review