Evolving Multimodal Robot Behavior via Many Stepping Stones with the Combinatorial Multiobjective Evolutionary Algorithm

Joost Huizinga, Jeff CluneEvol. Comput 2022 · OpenReview

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.

Introduction: The Stepping Stone Problem

Multimodal problems in reinforcement learning require agents to perform qualitatively different behaviors depending on their environment or goals. Directly evolving these complex behaviors is often intractable. Instead, researchers use a "curriculum" of subtasks—stepping stones—to guide the learning process. However, traditional evolutionary algorithms often fail to preserve these stepping stones. If one subtask (e.g., running) is significantly easier to optimize than another (e.g., jumping), individuals that specialize in the harder task may be outcompeted and removed from the population before they can integrate both skills. Once these specialized lineages are lost, the path to the combined behavior is often closed forever.

Comparison of standard evolutionary populations versus CMOEA binning in preserving essential 'stepping stone' behaviors.

Methodology: The CMOEA Framework

The Combinatorial Multiobjective Evolutionary Algorithm (CMOEA) addresses the loss of stepping stones through a structural innovation called Combinatorial Binning. Rather than maintaining a single global population, CMOEA partitions individuals into separate "bins" based on every possible combination of subtasks.

In a scenario with $N$ subtasks, the algorithm maintains $2^N - 1$ bins. Competition is localized within these bins; an individual attempting to master "Jumping + Turning" only competes against others targeting that specific combination. This isolation ensures that specialists for difficult sub-combinations are protected from being prematurely discarded in favor of generalists or specialists in easier tasks.

Additionally, the authors introduce the Combined-Target (CT) Objective, a linear combination of all task performances. Integrating this objective into standard algorithms like NSGA-II and NSGA-III was found to significantly enhance their performance on multimodal problems by providing a clearer global optimization signal.

Experimental Evaluation

The efficacy of CMOEA was tested against several state-of-the-art controls, including NSGA-II, NSGA-III, and ε-Lexicase Selection, across two primary environments:

  1. Six-Task Locomotion: A simulated hexapod robot was tasked with learning six distinct behaviors: moving forward, moving backward, turning left, turning right, jumping, and crouching.
  2. 100-Maze Navigation: To test scalability, a wheeled robot navigated 100 procedurally generated mazes. To handle the exponential number of bins ($2^{100}$), the authors employed a bin sampling strategy, maintaining a representative subset of 1,000 bins.
The six distinct locomotion tasks (forward, backward, turn-left, turn-right, jump, and crouch) used to test multimodal behavior in a hexapod robot.

Key Results and Insights

The experimental results highlight several strengths of the CMOEA approach:

  • Rapid Convergence: On the locomotion task, CMOEA significantly outperformed all control algorithms during the initial 5,000 generations, demonstrating its ability to quickly find and preserve useful behavioral building blocks.
  • Scalability via Sampling: The maze navigation task proved that CMOEA's binning strategy remains effective even when the total number of subtask combinations is vast, provided a sampling strategy is used.
  • Synergy with Auxiliary Objectives: CMOEA proved uniquely capable of leveraging auxiliary objectives, such as selecting for neural network modularity. While such objectives often hindered traditional algorithms, they significantly boosted CMOEA's performance, leading to the highest overall scores in the study.
  • Addressing Pareto Stagnation: In high-dimensional objective spaces, standard Pareto-based methods like NSGA-II often suffer from a loss of selection pressure because most individuals become non-dominated. CMOEA's bin-based aggregation bypasses this "Pareto trap."

Conclusion

CMOEA offers a robust framework for evolving multimodal behaviors by explicitly protecting the stepping stones necessary for complex task mastery. By shifting the focus from global optimization to the preservation of specialized niches, it enables the discovery of sophisticated behaviors that traditional algorithms often overlook. Future work will focus on automating the decomposition of complex problems into the subtasks that CMOEA requires.

Summary updated

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.
BibTeX
@inproceedings{huizinga2022evolving,
  author = {Joost Huizinga and Jeff Clune},
  title = {{Evolving Multimodal Robot Behavior via Many Stepping Stones with the Combinatorial Multiobjective Evolutionary Algorithm}},
  booktitle = {Evol. Comput},
  year = {2022},
  url = {https://openreview.net/forum?id=2F3OsGAGfm},
}
Figure