EvoCAD: EVOLUTION-ASSISTED DESIGN
EvoCAD: EVOLUTION-ASSISTED DESIGN
Combining a simple evolutionary algorithm with a partial simulation of Lego (1) bricks statics we evolve designs that come out of the computer ready to build [1-6]. A simplified physical simulator introduces the buildability constraint.
To allow for recombination and crossover, Lego structures are represented as Lisp-like functions that have one or more "root" bricks with zero or more descendants attached at diverse points. Mutations can modify a brick's size or position, whereas recombinations allow for interchange of entire subparts between two parents.
Figure 1. Genetic Representation: Lego structures are represented as trees. Each brick has (x, y) coordinates, (relative to its parent), size, and a list of descendants. In this example a 6-brick located at (1,1) is the root, with two descendants: a 2-brick at (-1,1) and a 4-brick at (2,1).
Lego structures are simulated based on a simplified model that views the bricks themselves as rigid elements and their joints as axis of rotation which generate a reactive torque to compensate for external forces, up to a certain limit. A given structure generates a network of torque propagation which needs to be evaluated to find out whether or not the loads can be distributed without violating any of the constraints.
Figure 2. Simplified Simulation: To determine whether a Lego structure is capable of supporting its own weight, plus external loads, we look at the rotational torque at each brick-brick union. If a distribution of forces exists that does not violate the resistance of any unions, the structure is stable.
With a genetic representation and a physical simulation in hand, one has the basic elements for evolving structures in simulation. Just add a fitness function, put all elements together into a plain steady-state GA, and wait for the results.
With different fitness functions we have evolved and built many different structures, such as bridges, cantilevers, cranes, trees and tables.
Figure 3. Evolved Lego structures: cantilevered bridge (a); table, an example of 3D evolution (b); crane, early and final stages (c, d); tree, internal representation and built structure (e, f)
Today's commercial CAD systems may add a mechanical simulator to the usual 3D manipulation tools(2). But the new field of Evolutionary Design (ED) [7] has the potential to add a third leg to computer-aided design: A creative role. Not only designs can be drawn (as in CAD), or drawn and simulated (as in CAD+simulation), but also designed by the computer following guidelines given by the operator. Thus we envision future Evolutionary CAD systems, "EvoCADs".
An EvoCAD system has the human designer in the main role: the designer has an idea or concept for a required object. Some of the requirements of can be added to the 3D canvas, creating evolutionary targets than an ED engine uses for evolving a possible design. The output of this evolutionary engine can be modified, tested and re-evolved as many times as desired .
Figure 4. A conceptual EvoCAD system has two "creative minds", the human designer and the ED software. The human designer is in control, and calls upon the remaining elements as tools. A problem description language (PDL) allows CAD, evolutionary and simulation components to communicate with each other (bold arrows).
We have built a mini-CAD system to design 2D Lego structures. This application allows the user to manipulate Lego structures, and test their gravitational resistance using a simplified structural simulator. It also interfaces to an evolutionary algorithm that combines user-defined goals with simulation to evolve candidate solutions for the design problems. The results of evolution are sent back to the CAD front-end to allow for further re-design until a satisfactory solution is obtained.
To begin an evolutionary run, a starting structure is first received, consisting of one or more bricks, and "reverse-compiled" into a genetic representation that will seed the population. Mutation and crossover operators are applied iteratively to grow and evolve a population of structures. The simulator is run on each new structure to test for stability and load support, needed to calculate a fitness value. The simulation stops when all objectives are satisfied or when a timeout occurs.
We designed a "brick problem description language" (BDL), as an interface between the evolutionary algorithm, simulator, and the CAD front-end. BDL encodes at the same time, structures and evolutionary targets and restrictions.
The goals for the ED engine are deducted from user-defined Restrictions, Target Points and Target Loads. A structure will be fully satisfactory if it touches all the target points and target load points, whereas avoiding all the restricted points, and supports all the specified loads at each target load point.
(b)
(c)
(d)
Figure 5. Sample working session with the EvoCAD program: (a) The user has defined the problem using two grounds and nine 25g loads (arrows) (b) The evolutionary run designed a structure that fulfills all requirements (it looks a bit hairy though) (c) The user made cosmetic corrections (d) The structure has been built with Lego bricks, and tested with a 250g load.
Our Lego EvoCAD system demonstrates how this new kind of application can employ ED techniques to let the computer not only be a canvas and a simulation tool, but also to create its own designs following the users' specifications. Our system allows human and computer to create a design collaboratively, greatly reducing the human effort needed to create and optimize a design.
Generic Problem Descriptions. We used targets, loads and restrictions. What are general rules for describing design problems to a computer?
Generalized Fitness Functions. ED employs ad hoc fitness function for each particular problem. Generic problem descriptions and Fitness functions need to work together to translate user specification into evolutionary guidelines.
Simulator APIs. Today's simulators, such as those found in CAD packages, are geared towards visualization and user interface. AID needs simulators geared towards being used as subroutines in design software: fast simulators than can be called hundreds of times per second and run in parallel in hundreds of machines.
[1] P. Funes and J. B. Pollack. Computer evolution of buildable objects. In P. Husbands and I. Harvey, editors, Fourth European Conference on Artificial Life, pages 358-367, Cambridge, 1997. MIT Press.
[2] P. Funes and J. B. Pollack. Componential structural simulator. Technical Report CS-98-198, Brandeis University Department of Computer Science, 1998.
[3] P. Funes and J. B. Pollack. Evolutionary body building: Adaptive physical designs for robots. Artificial Life, 4(4):337-357, 1998.
[4] P. Funes and J. B. Pollack. Computer evolution of buildable objects. In P. Bentley, editor, Evolutionary Design by Computers, pages 387 - 403. Morgan-Kaufmann, San Francisco, 1999.
[5] J. B. Pollack, H. Lipson, P. Funes, S. G. Ficici, and G. Hornby. Coevolutionary robotics. In J. R. Koza, A. Stoica, D. Keymeulen, and J. Lohn, editors, The First NASA/DoD Workshop on Evolvable Hardware (EH'99). IEEE Press, 1999.
[6] J. B. Pollack, H. Lipson, S. Ficici, P. Funes, G. Hornby, and R. Watson. Evolutionary techniques in physical robotics. In J. Miller, editor, Evolvable Systems: from biology to hardware; proceedings of the third international conference (ICES 2000), Lecture Notes in Computer Science, pages 175-186. Springer, 2000.
[7] P. Bentley, editor. Evolutionary Design by Computers. Morgan-Kaufmann, San Francisco, 1999.
References
