Jordan B. Pollack - Hod Lipson - Sevan Ficici - Pablo Funes - Greg Hornby - Richard A. Watson
Computer Science Dept., Brandeis University, Waltham, MA 02454, USA,
,
http://www.demo.cs.brandeis.edu
The field of Robotics today faces a practical problem: most problems in the physical world are too difficult for the current state of the art. The difficulties associated with designing, building and controlling robots have led to a stasis [1] and robots in industry are only applied to simple and highly repetitive manufacturing tasks.
Even though sophisticated teleoperated machines with sensors and actuators have found important applications (exploration of inaccessible environments for example), they leave very little decision, if at all, to the on-board software [2]. Hopes for autonomous robotics were raised high several times in the past -- the early days of AI brought us Shakey the robot [3], and the eighties the ``subsumption architecture'' [4]. Yet today, fully autonomous robots with minds of their own are not a reality.
The central issue we begin to address is how to get a higher level of complex physicality under control with less human design cost. We seek more controlled and moving mechanical parts, more sensors, more nonlinear interacting degrees of freedom -- without entailing both the huge costs of human design, programming, manufacture and operation. We suggest that this can be achieved only when robot design and construction are fully automatic and the constructions inexpensive enough to be disposable and/or recyclable.
The focus of our research is thus how to automate the integrated design of bodies and brains using a coevolutionary learning approach. Brain/body coevolution is a popular idea, but evolution of robot bodies is usually restricted to adjusting a few morphological parameters in an otherwise fixed, human-engineered automaton [5,6,7]. We propose that the key is to evolve both the brain and the body, simultaneously and continuously, from a simple controllable mechanism to one of sufficient complexity for a task. We then require a replication process, that brings an exact copy of the evolved machine into reality. Finally, the transfer between a simulated environment and reality -- the ``reality gap'' -- needs further embodied adaptation.
We see three technologies that are maturing past threshold to make this possible. One is the increasing fidelity of advanced mechanical design simulation, stimulated by profits from successful software competition [8]. The second is rapid, one-off prototyping and manufacture, which is proceeding from 3D plastic layering to stronger composite and metal (sintering) technology [9]. The third is our understanding of coevolutionary machine learning in design and intelligent control of complex systems [10,11,12].
Coevolution, when successful, dynamically creates a series of learning environments each slightly more complex than the last, and a series of learners which are tuned to adapt in those environments. Sims' work [13] on body-brain coevolution and the more recent Framsticks simulator [14] demonstrated that the neural controllers and simulated bodies could be coevolved. The goal of our research in coevolutionary robotics is to replicate and extend results from virtual simulations like these to the reality of computer designed and constructed special-purpose machines that can adapt to real environments.
We are working on coevolutionary algorithms to develop control programs operating realistic physical device simulators, both commercial-off-the-shelf and our own custom simulators, where we finish the evolution inside real embodied robots. We are ultimately interested in mechanical structures that have complex physicality of more degrees of freedom than anything that has ever been controlled by human designed algorithms, with lower engineering costs than currently possible because of minimal human design involvement in the product.
It is not feasible that controllers for complete structures could be evolved (in simulation or otherwise) without first evolving controllers for simpler constructions. Compared to the traditional form of evolutionary robotics [15,16,17,18,19] which serially downloads controllers into a piece of hardware, it is relatively easy to explore the space of body constructions in simulation. Realistic simulation is also crucial for providing a rich and nonlinear universe. However, while simulation creates the ability to explore the space of constructions far faster than real-world building and evaluation could, transfer to real constructions is problematic. Because of the complex emergent interactions between a machine and its environment, learning and readaptation must occur in ``embodied'' form as well [20,21,22].
We have four major thrusts in achieving Fully Automated Design (FAD) and manufacture of high-parts-count autonomous robots. The first is evolution inside simulation, but in simulations more and more realistic so the results are not simply visually believable, as in Sims' work, but also tie into manufacturing processes. Indeed, interfacing evolutionary computation systems to commercial off-the-shelf CAD/CAM systems through developer interfaces to mechanical simulation programs seems as restrictive as developing programming languages for 8K memory microcomputers in the middle 1970's. However, even though the current mechanical simulation packages are ``advisory'' rather than blue-print generating, and are less efficient than research code, as computer power grows and computer-integrated manufacturing expands, these highly capitalized software products will absorb and surpass research code, and moreover will stay current with the emerging interfaces to future digital factories. The second thrust is to evolve automatically-buildable machines, using custom simulation programs. Here, we are willing to reduce the universe of mechanisms we are working with in order to increase the fidelity and efficiency of the simulators and reduce the cost of building resulting machines. The third is to perform evolution directly inside real hardware, which escapes the known limitations of simulation and defines a technology supporting the final learning in embodied form. This is perhaps the hardest task because of the power, communication and other reality constraints. The fourth thrust addresses handling high part-count structures with realistically complexity. We have preliminary and promising results in each of these four areas, which we outline below.
We have been doing evolution of neural-network controllers inside
realistic CAD simulations as a prelude to doing body reconfiguration
and coevolution. Our lab is using CAD/CAM software package that
comprises a feature based solid-modeling system ![[*]](ices00html/foot_motif.gif)
. Widely used in
industry, it includes a mechanical simulation component that can
simulate the function of real-world mechanisms, including gears,
latches, cams and stops. This program has a fully articulated
development interface to the C programming language, which we have
used in order to interface its models to our evolutionary recurrent
neural network software.
To date, we have used this system with evolved recurrent neural controllers for one and two segment inverted pendulums and for Luxo (an animated lamp creature, figure 1). Many researchers have evolved such controllers in simulation, but no one has continuously deformed the simulation and brought the evolved controllers along, and no one else has achieved neural control inside commercial simulations. We believe this should lead to easy replication, extension, and transfer of our work.
We have successful initial experiments consisting of evolving recurrent neural network controllers for the double-pole balancing problem, where we slowly ``morphed'' the body simulator by simulating a stiff spring at the joint connecting the two poles and relaxing its stiffness.
![\begin{figure}\par\parbox[c]{ 0.49 \linewidth}{\centering\epsfig{file=two_pole.p...
...entering (a)}
\hfill
\parbox[c]{ 0.49 \linewidth}{\centering (b)}
\end{figure}](ices00html/img1.gif) |
Some of the ways to achieve continuous body deformation are:
Commercial CAD models are in fact not constrained enough to be buildable, because they assume a human provides numerous constraints to describe reality. In order to evolve both the morphology and behavior of autonomous mechanical devices that can be built, one must have a simulator that operates under many constraints, and a resultant controller that is adaptive enough to cover the gap between the simulated and real world. Features of a simulator for evolving morphology are:
One approach is to custom-build a simulator for modular robotic components, and then evolve either centralized or distributed controllers for them. In advance of a modular simulator with dynamics, we recently built a simulator for (static) Lego bricks, and used very simple evolutionary algorithms to create complex Lego structures, which were then manually constructed [23,24,25].
Our model considers the union between two bricks as a rigid joint between the centers of mass of each one, located at the center of the actual area of contact between them. This joint has a measurable torque capacity. That is, more than a certain amount of force applied at a certain distance from the joint will break the two bricks apart. The fundamental assumption of our model is this idealization of the union of two Lego bricks.
 |
The genetic algorithm reliably builds structures that meet simple fitness goals, exploiting physical properties implicit in the simulation. Building the results of the evolutionary simulation (by hand) demonstrated the power and possibility of fully automated design. The long bridge of figure 2 shows that our simple system discovered the cantilever, while the weight-carrying crane shows it discovered the basic triangular support.
The next step is to add dynamics to modular buildable physical components. We are experimenting with a new process in which both robot morphology and control evolve in simulation and then replicate automatically into reality. The robots are comprised of only linear actuators and sigmoidal control neurons embodied in an arbitrary thermoplastic body. The entire configuration is evolved for a particular task and selected individuals are printed pre-assembled (except motors) using 3D solid printing (rapid prototyping) technology, later to be recycled into different forms. In doing so, we establish for the first time a complete physical evolution cycle. In this project, the evolutionary design approach assumes two main principles: (a) to minimize inductive bias, we must strive to use the lowest level building blocks possible, and (b) we coevolve the body and the control, so that that they stimulate and constrain each other.
We use arbitrary networks of linear actuators and bars for the morphology, and arbitrary networks of sigmoidal neurons for the control. Evolution is simulated starting with a soup of disconnected elements and continues over hundreds of generations of hundreds of machines, until creatures that are sufficiently proficient at the given task emerge. The simulator used in this research is based on quasi-static motion. The basic principle is that motion is broken down into a series of statically-stable frames solved independently. While quasi-static motion cannot describe high-momentum behavior such as jumping, it can accurately and rapidly simulate low-momentum motion. This kind of motion is sufficiently rich for the purpose of the experiment and, moreover, it is simple to induce in reality since all real-time control issues are eliminated [26,27].
Several evolution runs were carried out for the task of locomotion. Fitness was awarded to machines according to the absolute average distance traveled over a specified period of neural activation. The evolved robots exhibited various methods of locomotion, including crawling, ratcheting and some forms of pedalism.
 |
Selected robots are then replicated into reality: their bodies are first fleshed to accommodate motors and joints, and then copied into material using rapid prototyping technology. Temperature-controlled print head extrudes thermoplastic material layer by layer, so that the arbitrarily evolved morphology emerges pre-assembled as a solid three- dimensional structure without tooling or human intervention. Motors are then snapped in, and the evolved neural network is activated (figure 4). The robots then perform in reality as they did in simulation.
 |
Once a robot is built, it may well be necessary to ``fine-tune'' adaptation in the real world. Our approach is to perform adaptation via a decentralized evolutionary algorithm that is distributed and embodied within a population of robots. The distributed and asynchronous operation of this evolutionary method allows the potential for being scaled to very large populations of robots, on the order of hundreds or thousands, thus enabling speedup that is critical when using evolution in real robots.
Technologically, this introduces two main problems: long-term power and reprogramming [28,29]. Many robots' batteries last only for a few hours, and robots typically have to be attached to a PC for new programs to be uploaded. In order to do large group robot learning experiments, we have designed a continuous-power floor system, and utilized infra-red (IR) communications to transfer programs between robots. We are thus able to run a population of learning robots battery-free and wire-free for days at a time (figure 5). Evolution is not directed by a central off-board computer that installs new programs to try out, but rather is distributed into the behavior of all the robots. The robots exchange program specifications with each other and this ``culture'' is used to 'reproduce' the more successful behaviors and achievement of local goals.
The control architecture is a simple neural network and the specifications for it are evolved online. Each robot tries parameters for the network and evaluates its own success. The more successful a robot is at the task, the more frequently it will broadcast its network specifications via its local-range IR communications channel. If another robot happens to be in range of the broadcast, it will adopt the broadcast value with a probability inversely related to its own success rate. Thus, successful robots attempt to influence others, and resist the influence of others, more frequently than less successful robots. We have shown this paradigm to be robust both in simulation and in real robots, allowing for the parallel, asynchronous evolution of large populations of robots with automatically developed controllers. These controllers compare favorably to human designs, and often surpass them when human designs fail to take all important environmental factors into account. Figure 6 shows averaged runs of the robots in a light seeking task, comparing evolved controllers to random and human-designed ones.
Our research goals in this area involve group interactive tasks based on multi-agent systems, such as group pursuit and evasion, box pushing, and team games. These domains have been out of reach of traditional evolutionary methods and typically are approached with hand-built (non-learning) controller architectures [30,31,32,33]. Work that does involve learning typically occurs in simulation [34,35,36,37], or in relatively simple physical domains [38,39,40,41,42].
Can evolutionary and coevolutionary techniques be applied to real physical systems? In this paper we have presented a selection of our work each of which addresses physical evolutionary substrate in one or more dimensions. We have overviewed research in handling high part-count static structures that are buildable, use of commercial CAD/CAM systems as a realistic simulated substrate, dynamic electromechanical systems with complex morphology that can be built automatically, and evolutionary techniques distributed in a physical population of robots.
Our long-term vision is that both the morphology and control programs for self-assembling robots arise directly through hardware and software coevolution: primitive active structures that crawl over each other, attach and detach, and accept temporary employment as supportive elements in ``corporate'' beings can accomplish a variety of tasks, if enough design intelligence is captured to allow true self-configuration rather than human re-deployment and reprogramming. When tasks cannot be solved with current parts, new elements are created through fully automatic design and rapid prototype manufacturing.
Our current research moves towards the overall goal down multiple interacting paths, where what we learn in one thrust aids the others. We envision the improvement of our hardware-based evolution structures, expanding focus from static buildable structures and unconnected groups to reconfigurable active systems governed by a central controller, and then the subsequent parallelization of the control concepts. We see a path from evolution inside CAD/CAM and buildable simulation, to rapid automatic construction of novel controlled mechanisms, from control in simulation to control in real systems, and finally from embodied evolution of individuals to the evolution of heterogeneous groups that learn by working together symbiotically. We believe such a broad program is the best way to ultimately construct complex autonomous robots who are self-organizing and self-configuring corporate assemblages of simpler automatically manufactured parts.
