Evolutionary Machines & Interactive Toys
Evolutionary Machines...
Dateline: 09/14/99
Robotics researchers have traditionally focused on developing controller algorithms that could produce an adequate response when downloaded to an appropriate platform. New approach has been adopted more recently: it involves the process of adaptation through evolutionary search. Most such experiments rely on carefully designed simulations, and just a few apply evolution directly in the real robot. However, almost all of them use human designed robot machines and try to evolve control programs for them. Jordan Pollack and Pablo Funes, researchers from Brandeis University, have took an entirely different approach: evolution of morphology and control together. The evolution of a creatures brain is just one part of the problem of artificially evolving life forms. It cannot survive without an adequate body to inhabit.
Evolutionary approach could mean a first step toward robots capable of reworking their own hardware without any human guidance.
|
This idea is becoming popular very rapidly, because it could present a giant leap from today's CAD (Computer Aided Design) into the realm of fully automated design. Some earlier simulations (see the links listed below for more details) involve simultaneous evolution of a robot control program and some parameters of its morphology such as sensor number or positioning and body size. Pollack and Funes started from the other end by using evolutionary techniques to create structures and physical forms adapted to perform correctly in the physical world. They see it as the fist step toward the development of robots and brains with higher complexity than humans can engineer.
The general process of building evolutionary robots can be summarized as follows (much more detailed source of information can be found Brandeis DEMO - Dynamical & Evolutionary Machine Organization - site):
- Start with a set of simple bodies and set of random "brains"
- Evolve brains inside bodies
- If a satisfactory solution has been reached, stop and build the robot
- Else mutate, cross and evolve the bodies, and go to step 2
Guess what material was chosen for the implementation of building blocks for the rudimentary evolutionary hardware? An obvious choice for every robotics hobbyist, Lego ™ bricks are made of plastic material that has the resistance that far surpasses the force necessary to either join two blocks together or break their unions. This makes it possible to design a model that ignores the resistance of the material and evaluates the strain forces over a group of bricks only at their union areas. On the other hand, if evolved structure fails, it will do so at the joints, but the actual bricks will not be damaged. Another "breakable" material would make such experiments very expensive. However, building a thousand real structures with minor changes would still be a slow and expensive process. Simulation can bring in constraints from various sources - such as the specification, physical laws and manufacturability. Only the most successful artifacts will be actually built.
Pollack and Funes developed a patent-pending algorithm that analyzes torque in networks of the Lego blocks and provided it with a simple optimization goals, such as spanning a distance and carrying a weight. Their genetic representation borrows the standard tree mutation and crossover operators from genetic programming. Each node on the tree represents a brick and has a size parameter indicating the size of the brick and a list of descendants, and positional parameters that describe the position of the new brick relative to the parent. Mutation operates by either random modification of a bricks parameters (size, position and orientation) or addition of a random brick. The basic crossover operator involves two parent trees out of which random subtrees are selected. The offspring generated has the first subtree removed and replaced by the second. After mutation or crossover operators are applied, a new, possibly invalid specification tree is formed. Once a valid tree has been obtained, the physical model is constructed and the structure tested for stress stability. If approved, fitness is evaluated and the new individual is added to the population.
The resulting program is not a speed champion (it often needs more than a day to produce useful result), and the resulting creations are not engineering marvels. But if this relatively simple evolutionary program, paired with the right physics, can design such complex structures without any engineering expertise from humans, what should we expect from more complex algorithms and hardware, including modern CNC machines and 3D plastic layering systems? Remember that it took us many centuries to design similar sophisticated structures, like bridges and cranes...
You can see several evolved structures following the links listed below. Lego Bridge
obtained a solution for the problem of constructing a bridge structure fixed to one of the tables in a lab that spans the distance of 1.5m that separates it from a neighboring table. Crane was evolved by evolutionary Lego simulation system to lift a weight of 0.5 kg.
Table
was the first experiment in evolution of 3D lego structures. It satisfies multiple specifications as established in fitness functions (it is 10 blocks tall, with top covering a 9x9 square, supporting a load of 50 grams anywhere in its surface while using as few bricks as possible).
... and Interactive Bears
What toy can talk, solve math problems, recognize anyone's voice, play games, and wiggle around? Furby? I think it doesn't like math so much. Parents, prepare yourself for a new furry madness - Koby, The Interactive Bear by MGA Entertainment. Through the innovative use of progressive intelligence and speaker-independent voice recognition technology, Koby is able to have conversations with everyone he meets. Using an embedded speech recognition chip (RSC-264T) from Sunnyvale-based Sensory, Inc., Koby recognizes dozens of phrases, and speaks over 200 words. It features over 400 play sequences and 17 different activities, such as the Peek-a-boo and Buckle My Shoe song, and he'll even tell you when he wants a hug or when he wants to play. More details on Neural Networks and other technologies used in Koby and other similar voice-activated products can be found at Sensory's Web site. Robot builders and electronics professionals will be interested in Interactive Speech line of ICs, the associated software and development tools.
Still think this is just another toy? Think again, because the previous generation of Koby's RSC-264T chip, the RSC-164 is about to land on Mars to record Martian sound as part of the Planetary Society's Mars Microphone project.
Koby has a manufacturer's suggested retail price of $29.99 and will be available in stores starting October.
Will the research described above lay a groundwork for robots capable of reworking their own hardware without any human guidance? What do you think about new "smart" toys & artificial pets and how they influence young children?
Site(s) of interest: evolvable hardware, biologically inspired robots, genetic programming
- Evolvable Hardware
An area of research called evolvable hardware has recently emerged which combines aspects of evolutionary computation with hardware design and synthesis. This paper gives an excellent introduction to the field.
- Evolutionary Robotics at Sussex
Artificial evolution, such as a Genetic Algorithm, has many promising applications in electronics. These range from using it as an optimisation technique as part of a fairly conventional VLSI synthesis pathway, through to using it to design automatically circuits that could be of a very different nature to the way electronics is normally envisaged.
- Toward Evolware
The idea of evolving machines, whose origins can be traced to the cybernetics movement of the 1940s and the 1950s, has recently resurged in the form of the nascent field of bio-inspired systems and evolvable hardware. The inaugural workshop, Towards Evolvable Hardware, took place in Lausanne in October 1995, followed by the First International Conference on Evolvable Systems: From Biology to Hardware (ICES'96) held in Japan in October 1996 (proceedings of both conferences are available from Springer-Verlag). The session described on these pages was held in Indianapolis, Indiana, from April 13 to 16, 1997.
- Computer Evolution of Buildable Objects
Excellent research paper by Funes and Pollack.
- Henrik Hautop Lund
Home page with links to resources on Toybots - Evolving Adaptive LEGO Robots, Robot-cricket, and all kinds of fun stuff (including many excellent articles).
- Lego Lab
The aim of the LEGO Lab is to create a common space for interaction, an open experimentarium in the intersection between on the one hand information and communication technology and on the other children's play in a world of ubiquitous computing.
- Toybots
A strong limitation of traditional robot kits is the assumption that to build an intelligent toy-robot (toybot), it is better to program the robot as a sort of "computer with wheels". This project is based on a different point of view: it considers a mobile toy robot as a little pet.
- Papers
Great resource including a list of links on evolutionary robotics.
- Crickets
Research in the new field of 'Bio-Robotics' (Biologically inspired robotics), using a robotic model of a female cricket.
- MRG
The home page of Mobile Robots Group at the University of Edingburgh offers a welath of information on biologically inspired robots.
- POE
In analogy to nature, the space of bio-inspired hardware systems can be partitioned along three axes: phylogeny, ontogeny, and epigenesis, giving rise to the POE model, recently introduced by Sipper et al.
- EvoNet
EvoWeb, the Web site of EvoNet, the network of excellence in Evolutionary Computing.
- Evolvuton
A framework for evolutionary computation which allows other C++ objects to evolve.
- The Genetic programming Notebook
One of the best Web resources related to Genetic Programming.