A challenge in evolutionary robotics is the co-optimization of both the morphology and the controller of robots. Classically, a robot body is designed and its controller is afterwards optimized. However, it is not always known if the robot body causes an inherent issue that limits the effectiveness of the robot. Therefore, one can design algorithms that can change part of the robot bodies in simulation and only transfer the most efficient body plan to reality. Even more, the entire robot could be reconfigured which is done in the field of modular robotics. How these modules should be connected to one another is then optimized with the evolutionary algorithm. The computational requirements to optimize morphologies will be computationally heavy if all the specific requirements of hardware should be taken into account. Therefore it is usually good practice to evaluate the algorithms themselves in simulation environments that do not have a real world counterpart.
For projects regarding evolving robot morphologies one can look at (1) the evolutionary algorithm, (2) the type of modules (physical parts) that are used to create the robot morphologies, (3) the controllers, (4) the reality gap (5) the encodings used to map a genotype to a phenotype, and (6) the environment and objective functions. A master’s thesis can investigate any one of these elements or a combination of them depending on your interests.
Here are some examples of directions you could take within this project:
Bio-inspired encodings for morphological evolution
Nature has an abundance of interesting and qualitatively different creatures. Despite the large diversity of these creatures, they share the same mechanism for encoding their structure and traits, the DNA. We want to investigate whether aspects of this seemingly efficient encoding can be used to move us closer to the discovery of equally interesting and diverse virtual creatures. The objective of this project is to design robot encodings by drawing inspiration from biology, and to find out whether the chosen aspects from biology are useful when evolving robots or virtual creatures.
Morphological tree search algorithms
Powerful tree search algorithms, such as Monte-carlo tree search[1], have been applied to a variety of difficult problems. Board games such as go and chess, and path planning are examples of domains where the application of these algorithms have been a success. There have been attempts to apply tree search to morphology search in robotics[2]. However, this is still a largely unexplored field with many possibilities. We propose to explore either 1) how to design tree representation of the space of possible configurations for a modular robots, and comparing the representations using monte-carlo tree search, or 2) adapting a tree search algorithm to the domain of modular robots to make it more efficient.
[1] C. B. Browne et al., "A Survey of Monte Carlo Tree Search Methods," in IEEE Transactions on Computational Intelligence and AI in Games, vol. 4, no. 1, pp. 1-43, March 2012, doi: 10.1109/TCIAIG.2012.2186810.
[2] Zhao, Allan & Xu, Jie & Konaković-Luković, Mina & Hughes, Josephine & Spielberg, Andrew & Rus, Daniela & Matusik, Wojciech. (2020). RoboGrammar: graph grammar for terrain-optimized robot design. ACM Transactions on Graphics. 39. 1-16. 10.1145/3414685.3417831.
Decentralized controllers in morphological evolution
When the morphology of a robot changes, the number of inputs and outputs available can also change dramatically. Having a single neural network that is able to map all the inputs and outputs is possible, but having a control system that is composed of small controllers inside specific modules can allow for local computation to occur. Popular approaches can use oscillators as controllers as differential equations [1] or neural networks [2]. This project investigates what type of decentralized controllers are usually used to optimize robot behaviors and how they can be incorporated in robot evolution.
[1] Ijspeert AJ. Central pattern generators for locomotion control in animals and robots: a review. Neural Netw. 2008 May;21(4):642-53. doi: 10.1016/j.neunet.2008.03.014. Epub 2008 May 14. PMID: 18555958.
[2] Robin Thandiackal, Kamilo Melo, Laura Paez, Johann Herault, Takeshi Kano, Kyoichi Akiyama, Frédéric Boyer, Dimitri Ryczko, Akio Ishiguro and Auke J. Ijspeert (2021) Emergence of robust self-organized undulatory swimming based on local hydrodynamic force sensing
[3] Jelisavcic, Milan; Glette, Kyrre; Haasdijk, Evert; Eiben, AE, (2019) Lamarckian Evolution of Simulated Modular Robots
Example of a previous master project on this topic:
Quality diversity algorithms:
Evolutionary algorithms are a unique type of bio-inspired optimization method but are prone to getting stuck in local optima. To prevent this from happening, quality-diversity (QD) evolutionary algorithms have recently been introduced, which not only select for performance (quality or fitness) but also promote diversity in an evolving population. This multi-objective approach has been shown to be a promising adaptation that increases the overall performance of evolutionary algorithms. Although it is challenging to describe metrics of diversity and even though computational requirements can be high, this project will specifically investigate how QD algorithms can be used to evolve both the control systems and the morphologies of robots.
Lifetime learning
Evolving morphology and control is a difficult task, and the results so far have been relatively simple. Some of this lies in the difficult search space arising from the co-evolution of morphology and control. In a sense, the morphology of a robot can be seen as an “interface” between the controller of the robot and the environment, and when the morphology changes this interface is “scrambled” [1]. This impacts the efficiency of the search, and may lead to early convergence on (simple) morphologies. In this context, it would make sense to let the controllers have time to adapt to their new bodies. There could be many approaches to doing this, but one is to introduce a lifetime learning stage in the evolutionary process, using a data-efficient learning algorithm to adapt the controller.
Genetic assimilation is the process of learned traits being incorporated into the genome of biological organisms on an evolutionary time-scale. The theory is that if a behavioral trait can be incorporated in the genome of an organism the trait does not need to be learned during the life-time of an individual anymore. However, if the learning mechanism is lost for an individual as it was assimilated, the individual loses a bit of plasticity. In static environments, learning might not be necessary since individuals could evolve an optimal set of parameters for that environment. In a dynamic environment, where the objective for example might change, traits might need to continuously adapt, this would lead to an evolutionary pressure to keep learning. This pressure to adaptive learning is what is called ‘the baldwin effect’ in biology, where there is continuous pressure for individuals to keep their genes responsible for learning in the gene pool.
Research questions for this approach could be a) how lifetime learning affects the convergence of morphologies, or leads to more complex morphologies for solving tasks, b) what kind of learning algorithms make sense (e.g. reinforcement learning, bayesian optimization, simple greedy optimization methods, parameter sweeps), c) what kind of controllers are suitable for adaptation. In addition, it could be interesting to explore if a Lamarckian evolutionary approach could be relevant to implement in this case, compared to the typical Baldwinian evolution observed in nature [2].
[1] Cheney, N., Bongard, J., Sunspiral, V., & Lipson, H. (2016). On the Difficulty of Co-Optimizing Morphology and Control in Evolved Virtual Creatures. Proceedings of the Artificial Life Conference 2016 (ALIFE XV), 226--234.
[2] Jelisavcic, M., Glette, K., Haasdijk, E., & Eiben, A. E. (2019). Lamarckian Evolution of Simulated Modular Robots. Frontiers in Robotics and AI, 6. https://doi.org/10.3389/frobt.2019.00009