Robot Bodies and how to Evolve them

Evolutionary robotics has been around for about 20 years: it's about 15 years since Stefano Nolfi and Dario Floreano published their seminal book on the subject. Yet, surprisingly the number of real, physical robots whose bodies have been evolved can be counted on the fingers of one hand. The vast majority of ER research papers are concerned with the evolution of robot brains - the robot's control system. Or, when robot bodies are evolved often the robot is never physically realised. This seems to me very odd, given that robots are real physical artefacts whose body shape - morphology - is deeply linked to their role and function.

The question of how to evolve real robot bodies and why we don't appear to have made much progress in the last 15 years was the subject of my keynote at the IEEE International Conference on Evolvable Systems (ICES 2014) in Orlando, a week ago. Here are my slides:

The talk was in three parts.

In part one I outlined the basic approach to evolving robots using the genetic algorithm, referring to figure 18: The four-stage process of Evolutionary Robotics, from chapter 5 of my book:

I then reviewed the state-of-the-art in evolving real robot bodies, starting with the landmark Golem project of Hod Lipson and Jordan Pollack, referencing both Henrik Lund and Josh Bongard's work on evolving Lego robots, then concluding with the excellent RoboGen project of Josh Auerbach, Dario Floreano and colleagues at EPFL. Although conceptually RoboGen has not moved far from Golem, it makes the co-evolution of robot hardware and controllers accessible for the first time, through the use of 3D-printable body parts which are compatible with servo-motors, and a very nice open-source toolset which integrates all stages of the simulated evolutionary process.

RoboGen, Golem and, as far as I'm aware, all work on evolving real physical robot bodies to date has used the simulate-then-transfer-to-real approach, in which the whole evolutionary process - including fitness testing - takes place in simulation and only the final 'fittest' robot is physically constructed. Andrew Nelson and colleagues in their excellent review paper point out the important distinction between simulate-then-transfer-to-real, and embodied evolution in which the whole process takes place in the real world - in real-time and real-space.

In part two of the talk I outlined two approaches to embodied evolution. The first I call an engineering approach, in which the process is completely embodied but takes place in a kind of evolution factory; this approach needs a significant automated infrastructure: instead of an manufactory we need an evofactory. The second approach I characterise as an artificial life approach. Here there is no infrastructure. Instead 'smart matter' somehow mates then replicates offspring over multiple generations in a process much more analogous to biological evolution. This was one of the ambitious aims of the Symbrion project which, sadly, met with only limited success. Trying to make mechanical robots behave like evolving smart matter is really tough.

Part three concluded by outlining a number of significant challenges to evolving real robot bodies. First I reflect on the huge challenge of evolving complexity. To date we've only evolved very simple robots with very simple behaviours, or co-evolved simple brain/body combinations. I'm convinced that evolving robots of greater (and useful) complexity requires a new approach. We will, I think, need to understand how to co-evolve robots and their ecosystems*. Second I touch upon a related challenge: genotype-phenotype mapping. Here I refer to Pfeifer and Bongard's scalable complexity principle - the powerful idea that we shouldn't evolve robots directly, but instead the developmental process that will lead to the robot, i.e. artificial evo-devo. Finally I raise the often overlooked challenge of the energy cost of artificial evolution.

But the biggest challenge remains essentially what it was 20 years ago: to fully realise the artificial evolution of real robots.

---

Some of the work of this talk is set out in forthcoming paper: AFT Winfield and J Timmis, Evolvable Robot Hardware, in Evolvable Hardware, eds M Trefzer  and A Tyrrell, Springer, in press.

*I touch upon this in the final para of my paper on the energy cost of evolution here.

The Triangle of Life: Evolving Robots in Real-time and Real-space

At the excellent European Conference on Artificial Life (ECAL) a couple of weeks ago we presented a paper called The Triangle of Life: Evolving Robots in Real-time and Real-space (this links to the paper in the online proceedings).

As the presenting co-author I gave a one-slide one-minute pitch for the work, and here is that slide.

The paper proposes a new conceptual framework for evolving robots, that we call the Triangle of Life. Let me outline what this means. But first a quick intro to evolutionary robotics. In my very short introduction to Robotics I wrote:

One of the most fascinating developments in robotics research in the last 20 years is evolutionary robotics. Evolutionary robotics is a new way of designing robots. It uses an automated process based on Darwinian artificial selection to create new robot designs. Selective breeding, as practised in human agriculture to create new improved varieties of crops, or farm animals, is (at least for now) impossible for real robots. Instead, evolutionary robotics makes use of an abstract version of artificial selection in which most of the process occurs within a computer. This abstract process is called a genetic algorithm. In evolutionary robotics we represent the robot that we want to evolve, with an artificial genome. Rather like DNA, our artificial genome contains a sequence of symbols but, unlike DNA, each symbol represents (or ‘codes for’) some part of the robot. In evolutionary robotics we rarely evolve every single part of a robot.

A robot consists of a physical body with an embedded control system - normally a microprocessor running control software. Without that control software the robot just wouldn't do anything - it would be the robot equivalent of a physical body without a mind. In biological evolution bodies and minds co-evolved (although the dynamics of that co-evolutionary process are complex and interesting). But in 20 years or so of evolutionary robotics the vast majority of work has focussed only on evolving the robot's controller. In other words we take a pre-designed robot body, then use the genetic algorithm to discover a good controller for that particular body. There has been little work on body-brain co-evolution, and even less work on evolving real robot bodies. In fact, we can count the number of projects that have evolved new physical robot bodies on the fingers of one hand*. Here is one of those very rare projects: the remarkable Golem project of Hod Lipson and Jordan Pollack.

This is surprising. When we think of biological evolution and the origin of species, our first thoughts are of the evolution and diversity of body shapes and structures. In the same way, the thing about a robot that immediately captures our attention is its physical body. And bodies are not just vessels for minds. As Rolf Pfeifer and Josh Bongard explain in their terrific book How the Body Shapes the Way We Think, minds depend crucially on bodies. The old dogma of Artificial Intelligence, that we can simply design an artificial brain without any regard to its embodiment, is wrong. True artificial intelligence will only be achieved by co-evolving physical bodies with their artificial minds.

In this paper we are arguing for a radical new approach in which the whole process of co-evolving robot bodies and their controllers takes place in real space and real time. And, as the title makes clear, we are also advocating a open-ended cycle of artificial life, in which every part of the robots' artificial life cycle takes place in real space and real time, from artificial conception, through to artificial birth, artificial infancy and development, then artificial maturity and mating. Of course these words are metaphors: the artificial processes are at best a crude analogue. But let me stress that no-one has demonstrated this. The examples that we give in the paper, from the EU Symbrion project, are just fragments of the process - not joined up in reality. And the Symbrion example is very constrained because of the modular robotics approach which means that the building blocks of these 'multi-cellular' robot organisms - the 'cells' - are themselves quite chunky robots; we have only 3 cell types and only a handful of cells for evolution to work with. Evolving robots in real space and real time is ferociously hard but, as the paper concludes: Our proposed artificial life system could be used to investigate novel evolutionary processes, not so much to model biological evolution – life as it is, but instead to study life as it could be.

Full reference:

Eiben AE, Bredeche N, Hoogendoorn M, Stradner J, Timmis J, Tyrrell A, and Winfield A (2013), The Triangle of Life: Evolving Robots in Real-time and Real-space, pp 1056-1063 in Advances in Artificial Life, ECAL 2013, proc. Twelfth European Conference on the Synthesis and Simulation of Living Systems, eds. Liò P, Miglino O, Nicosia G, Nolfi S and Pavone M, MIT Press.

---

*was surprised to discover this when searching the literature for a new book chapter I'm co-authoring with Jon Timmis on Evolvable Robot Hardware.

Related blog posts:
New experiments in embodied evolutionary swarm robotics
New video of 20 evolving e-pucks

Walterian Creatures

The Symbrion swarm-organism lifecycle

I've blogged before about the Symbrion project: an ambitious 5-year project to build a swarm of independently mobile autonomous robots that have the ability - when required - to self-assemble into 3D 'multi-cellular' artificial organisms. The organisms can then - if necessary - disassemble back into their constituent individual robots. The idea is that robots in the system can choose when to operate in swarm mode, which might be the optimal strategy for searching a wide area, or in organism mode, to - for instance - negotiate an obstacle that cannot be overcome by a single robot. We can envisage future search and rescue robots that work like this - as imagined on this ITN news clip from 2008.

Our main contribution to the project to date has been the design of algorithms for autonomous self-assembly and disassembly - that is the process of transition between swarm and organism. This video shows the latest version of the algorithm developed by my colleague Dr Wenguo Liu. It is demonstrated with 2 Active Wheel robots (developed at the University of Stuttgart - who also lead the Symbrion project) and 1 Backbone robot (developed at the Karlsruhe Institute of Technology).

Let me explain how this works. The docking faces of the robots have infra-red (IR) transmitters and receivers. When a 'seed' robot - in this case the Active Wheel robot on the left - decides to form an organism with a particular body plan, it broadcasts a 'recruitment' signal from its IR transmitters, with the 'type' of robot it needs to recruit - in this case a Backbone robot. The IR transmitters then act as a beacon which the responding robot uses to approach the seed robot, and the same IR system is then used for final alignment prior to physical docking.

Once docked, wired (ethernet) communication is established between robots, and the seed robot communicates the body-plan for the organism with the newly recruited Backbone robot. Only then does the Backbone robot know what kind of organism it is now part of, and where in the organism it is. In this case the Backbone robot determines that the partially formed organism then needs another Active Wheel and it recruits this robot using the same IR system. After the third robot has docked it too discovers the overall body plan and where in the organism it is. In this case it is the final robot to be recruited and the organism self-assembly is complete.

Using control coordinated via the wired ethernet intranet across its three constituent robots, the organism then makes the transition from 2D planar form to 3D, which - in this case - means that the 2 Active Wheel robots activate their hinge motors to bend and lift the Backbone robot off the floor. The 3D organism is now complete and can move as a single unit. The process is completely reversible, and the complete 'lifecycle' from swarm -> organism -> swarm is shown in this video clip.

It is important to stress that the whole process is completely distributed and autonomous. These robots are not being remotely controlled, nor is there a central computer coordinating their actions. Each robot has the same controller, and determines its own actions on the basis of sensed IR signals, or data received over the wired ethernet. The only external signal sent was to tell the first robot to become the 'seed' robot to grow the whole organism. Later in the project we will extend the algorithm so that a robot will decide, itself, when to become a seed and which organism to grow.

The Symbrion system is not bio-mimetic in the sense that there are (as far as I know) no examples in nature of cells that spontaneously assemble to become functioning multi-cellular organisms and vice-versa. It is, however, bio-mimetic in a different sense. The robots, while in swarm mode, are analogous to stem cells. The process of self-assembly is analogous to morphogenesis, and - during morphogenesis - the process by which robot 'cells' discover their position, role and function within the organism is analogous to cell-differentiation.

While what I have described in this blog post is a milestone following several years of demanding engineering effort by a very talented team of roboticists, some of the ultimate goals of the project are scientific rather than technical. One is to address the question - using the Symbrion system as an embodied model - of under what environmental conditions is it better to remain as single cells, or symbiotically collaborate as multi-celled organisms. It seems far fetched but perhaps we could model - in some abstract sense - the conditions that might have triggered the major transition in biological evolution of some 1000 million years ago which saw the emergence of simple multi-cellular forms.

New video of 20 evolving e-pucks

In June I blogged about Nicolas Bredeche and Jean-Marc Montanier working with us in the lab to transfer their environment-driven distributed evolutionary adaptation algorithms to real robots, using our Linux extended e-pucks. Nicolas and Jean-Marc made another visit in August to extend the experiments to a larger swarm size, of 20 robots; they made a YouTube movie and here it is:



In the narrative on YouTube Nicolas writes

This video shows a fully autonomous artificial evolution within a population of ~20 completely autonomous real (e-puck) robots. Each robot is driven by its "genome" and genomes are spread whenever robots are close enough (range: 25cm). The most "efficient" genomes end up being those that successfully drive robots to meet with each other while avoiding getting stuck in a corner.

There is no human-defined pressure on robot behavior. There is no human-defined objective to perform.

The environment alone puts pressure upon which genomes will survive (ie. the better the spread, the higher the survival rate). Then again, the ability for a genome to encode an efficient behavioral strategy first results from pure chance, then from environmental pressure.

In this video, you can observe how going towards the sun naturally emerges as a good strategy to meet/mate with other (it is used as a convenient "compass") and how changing the sun location affect robots behavior.

Note: the 'sun' is the static e-puck with a white band around it.

Morphogenetic Engineering at ANTS

I'm at the excellent Swarm Intelligence conference in Brussels, called appropriately ANTS. This morning there is a special session on morphogenetic engineering, chaired by René Doursat, of the complex systems institute in Paris. Morphogenetic engineering is the name coined for a new cross over between biology and engineering. Current engineered systems are designed and 'built'. Biological systems on the other hand grow from seeds or embryos. Morphogenetic engineering asks the question, might it be possible to 'grow' complex engineered systems, like robots?

Of course with current materials: metal and plastic, we can't grow robots so many of the ideas of morphogenetic engineering remain, for the time being, future concepts. But I think we'll see some exciting developments in this new sub-field as new materials become available.

Here is an image from our talk* on autonomous distributed morphogenesis in the Symbrion project, presented during the special session. Here you see robots being recruited to join the 2D planar organism during its formation.



* Wenguo Liu and Alan FT Winfield, 'Autonomous morphogenesis in self-assembling robots using IR-based sensing and local communications', ANTS 2010.

Evolving e-pucks

Nicolas Bredeche and his graduate student Jean-Marc Montanier have spent the last two weeks working in the lab to test out work they had already done in simulation, onto real robots. Nicolas is interested in evolutionary swarm robotics. This is an approach, inspired directly by Darwinian evolution, in which we do not design the robots' controllers (brains) but instead evolve them. In this case the brains are artificial neural networks and the process of artificial evolution evolves the strengths of the connections between the neurons. Nicolas is especially interested in open-ended evolution, in which he - as designer - does not pre-determine the evolved robot behaviours (by specifying an explicit fitness function, i.e. what kinds of behaviours the robots should evolve). Thus, even though this is an artificial system, its evolution is - in a sense - a bit closer to natural than artificial selection.

Symbrion debates @Stuttgart

In Stuttgart, at the University, for a Symbrion project meeting. Its been a really tough meeting - which is hardly surprising given that we're one year in and - next month - have the big end-of-first-year review meeting in Prague. So a major part of the meeting has been a dress rehearsal for the review.

However, spending a day and a half with a group of very smart people is always a pleasure, and there were some really interesting issues to debate. One concerns the fundamental question of how much of the Symbrion system should be designed and how much evolved (using evolutionary computing techniques). One could take a purist view and aim to evolve every aspect. My own view is more pragmatic. I think that achieving the aims of the Symbrion project is going to be so difficult that we should resort to artificial evolution only for the parts of the system that we can't design, because we don't know how.

Also, I think there's a 'biological plausibility' argument for taking the pragmatic view. The Symbrion system will be both a swarm of individual robots, behaving like a swarm, and - following self-assembly - a multi-cellular organism, behaving as a single organism. Swarm and organism have, I think, radically different control paradigms; the former fully decentralised and dependent on mechanisms of emergence and self-organisation, the latter centralised and coordinated (by a central nervous system). Of course ant genes must both contain the instructions to build multi-cellular animals (the ants with CNSs and coordinated control, e.g. for walking), and their behaviours which give rise to the colony's collective swarm intelligence. However, Symbrion goes beyond anything seen in nature. We want the Symbrion robots to sometimes behave like complicated ant-like creatures, and sometimes behave like complicated cells in a complex body (that can perform useful coordinated functions). I think if such a thing were possible to be evolved it would have been (except for the fascinating but much-simpler-than-Symbrion case of the social amoeba Dictyostelium discoideum sometimes self-assembling into multicellular structures).

This is why I think engineering a single evolutionary process that can evolve both swarm intelligent control and centralised coordinated control is asking too much.

Just returned from the Symbrion Kick-off meeting

I just returned from an amazing meeting in Stuttgart with an amazing group of people: the project kick-off meeting for the Symbrion project. So what is Symbrion and what are we trying to achieve? Well, the idea is to build a swarm of mobile robots that can autonomously self-assemble into an artificial organism in which each individual robot becomes - in effect - a cell in a kind of artificial multi-cellular organism. The idea of self-assembling robots is not new, but in Symbrion the robots will be able to function as a swarm but then, if the situation demands, self-assemble into a 3 dimensional organism; then if required disassemble and form into a different kind of 3D organism. Imagine the swarm coming to a barrier too high to cross then autonomously forming an 'organism' to climb over the wall, then disassembling and reassembling into a different morphology to, for instance, collectively transport an object too large for a single robot to carry. In this way the Symbrion organism will be able to morph between different 3D forms as required by the situation.

No surprisingly, Symbrion is an extremely challenging project with very tough technical milestones. Our first task is to design and build the Symbrion robots - each robot will need to operate autonomously and have its own power, computation, sensing and motors for mobility but - in addition - have the ability to physically dock with other Symbrion robots on several sides. Furthermore the docking mechanism will need to be motorised so that once attached several robots will be able to bend in 3D. Thus a 2D swarm will be able to self-assemble into a 2D planar structure but then, once assembled, lift itself into a 3D shape - for instance from a X shape into a 4 legged walker.

-------------
Postscript: following the London press launch ITN posted the TV interview onto YouTube, see Robots with a mind of their own.