Embodied Evolution

Richard A. Watson, Sevan G. Ficici

{richardw, sevan}@cs.brandeis.edu

Details

Read Summary

Introduction

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 Embodied Evolution.

Vision

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 manner.

Motives/Background

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.

Experimental Setup

Tupperbots

Continuous Untethered Power

  • stainless steel tape fixed to modular tongue and groove flooring strips connected to DC power supply
  • alternate strips to positive and negative
  • each robot has four contact points on the underside (made of thumb tacks)
  • geometry of contacts provides circuit in any orientation or position
  • generalised rectifier provides DC to robot
  • Tupperware body and contact springs made in one piece
  • rechargeable cell delivers power when contact with floor is lost, and charges from floor when contact is good
  • Whilst building our power floor we learned of two other groups that have built floors of a similar construction [Keating 1998, Billeter 1998].

    Robot underside showing the four contact points that collect power from the floor.

    Task Environment

    The robot pen for the phototaxis experiments: showing eight Tupperbots, the power-floor and the light in the center. Our eight robots are hardly a 'warehouse full' (Vision) -- but, they have been sufficient to illuminate a significant number of issues in this endeavor.

    Control Architecture

    Evaluation

    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.

    Evolutionary Algorithm

    Experimental Results

    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 [1984] 'swagger,' but evolution favoured a spiraling solution.

    Mean hit rate over time for embodied evolution and two control experiments; hand-designed weights, and random weights. EE and designed data is averaged over six runs, random averaged over two runs. The dotted lines are +/- one standard deviation. A time window of 20 minutes is used to compute the instantaneous hit rate for each data point on the graph.

    Conclusions

    Our experiments provide the first proof-of-concept for Embodied Evolution as an approach to the evolution of robotic controllers. The evolving network architecture, though minimally complex, provides surprisingly novel solutions for phototaxis while simultaneously keeping the solution space too sparse for random search to be effective. We are in the process of developing more complex task environments and control architectures for our experiments. Nevertheless, though the phototaxis task described in this report appears simple and not to involve any aspect of robot interaction, there are, in fact, strong interactive forces implicit in the EE approach; the "reproductive" process and physical robot-to-robot interference are two types of interaction that we are currently investigating. Indeed, the simplicity of our task environment provides more transparency with regard to the dynamics of interaction than a more complex task might.

    References

    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/