Richard A. Watson, Sevan G. Ficici, Jordan B. Pollack
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, EE (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.
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.
We define embodied evolution, EE, as evolution taking place in an embodied population [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.
Other Evolutionary Robotics work has used a single robot that evaluates many controllers in serial (e.g., 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 8 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.
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 6 runs, random averaged over 2 runs. The dotted lines are +/- 1 standard deviation. A time window of 20 minutes is used to compute the instantaneous hit rate for each data point on the graph.
Our eight robots are hardly a 'warehouse full' (Vision) - but they have been sufficient to illuminate a significant number of issues in this endeavor.
Billeter 1998, Jean-Bernard Billeter, personal communication, Laboratoire de microinformatique (LAMI), Switzerland.
Braitenberg, V. (1984) Vehicles: experiments in synthetic psychology. MIT Press. Brooks 1990
R. Brooks. Elephants don't play chess. Robotics and Autonomous Systems, 6(1--2):3--15, 1990.
Floreano, D. and Mondada, F. Evolution of Homing Navigation in a Real Mobile Robot. IEEE Transactions on Systems, Man, and Cybernetics--Part B: Cybernetics, 26(3), 396-407, 1996.
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: "Issues in evolutionary robotics" in: J.-A. Meyer, H. Roitblat and S. Wilson (eds.), From Animals to Animats 2: Proc. of the Second Intl. Conf. on Simulation of Adaptive Behavior, (SAB92), pp. 364--373. MIT Press/Bradford Books, Cambridge MA, 1993.
Keating 1998, Dave Keating, personal communication, D.A.Keating@reading.ac.uk
M. Mataric and D. Cliff ``Challenges in Evolving Controllers for Physical Robots'' invited paper for Robotics and Autonomous Systems special issue on ``Evolutional Robotics'', 1996.
Martin 1998, see http://fredm.www.media.mit.edu/people/fredm/projects/cricket/