Embodied EvolutionRichard A. Watson, Sevan G. Ficici
The vision of a population of robots evolving autonomously, articulated by Harvey,
1995, (Vision) describes a method for evolving robot controllers that
we will call Embodied Evolution (Definition). There are several
advantages for this approach to evolutionary robotics
(Motives/Background) especially in the study of multi-agent
interaction. But, it is immediately apparent that there are several
problematic technological requirements for Embodied Evolution (see
Tupperbots, Continuous Untethered Power), and there is considerable
algorithmic detail that must be added to this vision before EE is
workable (Evolutionary Algorithm). However, this work reports initial
experiments (Task Environment) that have realized this vision
successfully (Experimental Results) -- providing proof of concept for
Imagine a warehouse full of robots, clambering over each other, attempting to perform some task - say collecting objects representing food or energy. Imagine, these robots can mate with each other, i.e. exchange genetic material, producing control programs that become resident in other members of the robot population. Naturally, the likelihood of producing offspring is regulated by the ability to perform the task, or the 'energy' collected. Ideally there will be no need for human intervention either to evaluate, breed or reposition the robots for new trials. Thus the population of robots evolve hands-free - an artificial population that evolves autonomously.
c.f. Harvey, 1995.
Definition of Embodied Evolution
We define embodied evolution (EE) as evolution taking place in
a population of embodied robots [Brooks, 1990]. Natural evolution is indeed an
example of embodied evolution - but in our present context we will be
referring to EE that takes place in populations of artificial
creatures. Since our definition specifies embodied individuals we
exclude simulated creatures, and so for our purposes EE is evolution
taking place in a population of robots. We will also stipulate that the
evolutionary algorithm is distributed in the population as it is in
natural evolution. That is, an architecture that maintains and
manipulates the specifications of the individuals in the population in
a centralized manner is excluded. Evaluation and reproduction must be
carried out by the robots and between the robots in an autonomous
Other Evolutionary Robotics work has used a single robot that evaluates many controllers in serial [Harvey, Husbands & Cliff 1993, Floreano and Mondada 1996]. This method avoids all problems of transference that evolving controllers in simulation can suffer from [Mataric & Cliff, 1996]. But serial evaluations are time consuming even if they can be performed hands-free. It is conceivable that the process could be speeded-up by using many robots evaluated in parallel together with some centralised algorithm coordinating reproduction and download of new controllers (although, this would require the duplication of the task environment). Our EE experiments so far are essentially embodied evaluations carried out by a population of robots in a shared environment (avoiding duplication of the task environment). However, the EA is also fully-decentralised (Evolutionary Algorithm) and therefore avoids potential bottleneck problems that may arise if a centralised algorithm were scaled to hundreds of robots.
More importantly, EE provides a platform for evolving group behaviours. EE is ideal for experiments investigating cooperation/competition, coevolution, group formation, self-organisation, etc. in multi-robot domains. For these areas of research it is highly unlikely that simulators could model the physical interactions accurately enough for successful transference, and it is arguable that the complexities of modeling the environment, especially for high resolution sensory apparatus (e.g. vision), would make simulation slower than real time.
Whilst building our power floor we learned of two other groups that have built floors of a similar construction [Keating 1998, Billeter 1998].
This quite trivial task and
control architecture were chosen for our first proof of concept
experiments and were sufficient to illustrate the overall architecture
of the experiment and technology.
The figure below shows the frequency with which the light is successfully reached by the robot population ('hit rate') over time. All experiments used a population of eight Tupperbots. The embodied evolution experiment evolves the weights from an initial condition where all weights are zero. We also tested a hand-designed solution which (after considerable 'tuning') achieves approximately 10 hits per minute. Embodied evolution produces a population with a performance that exceeds the hand-designed solution after about one hour. Interestingly, the evolved solutions exhibit qualitatively different behavior from our hand-designed solution: we designed a Braitenberg-style  'swagger,' but evolution favoured a spiraling solution.
Billeter 1998, Jean-Bernard Billeter, personal communication, Laboratoire de microinformatique (LAMI), Switzerland.
Braitenberg, V. (1984) Vehicles: experiments in synthetic psychology. MIT Press.
R. Brooks. (1990) "Elephants don't play chess." Robotics and Autonomous Systems, 6(1-2):3-15.
Floreano, D. and Mondada, F. (1996) "Evolution of Homing Navigation in a Real Mobile Robot". IEEE Transactions on Systems, Man, and Cybernetics--Part B: Cybernetics, 26(3), 396-407.
Harvey, I. (1995) University of Sussex, U.K., Personal communication.
Harvey, I: The Microbial Genetic Algorithm, Submitted, under review.
Harvey, P. Husbands and D. Cliff. (1992) "Issues in evolutionary robotics." From Animals to Animats 2, J.-A. Meyer, H. Roitblat and S. Wilson (eds.), MIT Press/Bradford Books, Cambridge MA, 364-373.
Keating (1998), Dave Keating, personal communication, D.A.Keating@reading.ac.uk
M. Mataric and D. Cliff (1996) "Challenges in Evolving Controllers for Physical Robots." Robotics and Autonomous Systems, special issue on Evolutional Robotics.
Martin 1998, see http://fredm.www.media.mit.edu/people/fredm/projects/cricket/