Computer Evolution of Buildable Objects
Inhaltsverzeichnis
Reference
Pablo J. Funes and Jordan B. Pollack: Computer Evolution of Buildable Objects. Evolutionary Design by Computers, pp. 387-403, Morgan Kaufmann, 1999.
DOI
Abstract
This chapter describes our work in evolution of buildable designs using miniature plastic bricks as modular components. Lego1 bricks are well known for their flexibility when it comes to creating low cost, handy designs of vehicles and structures. Their simple modular concept make toy bricks a good ground for doing evolution of computer simulated structures which can be built and deployed. Instead of incorporating an expert system of engineering knowledge into the program, which would result in more familiar structures, we combined an evolutionary algorithm with a model of the physical reality and a purely utilitarian fitness function, providing measures of feasibility and functionality. Our algorithms integrate a model of the physical properties of Lego structures with an evolu- tionary process that freely combines bricks of different shape and size into structures that are evalu- ated by how well they perform a desired function. The evolutionary process runs in an environment that has not been unnecessarily constrained by our own preconceptions on how to solve the prob- lem. The results are encouraging. The evolved structures have a surprisingly alien look: they are not based in common knowledge on how to build with brick toys; instead, the computer found ways of its own through the evolutionary search process. We were able to assemble the final designs manu- ally and confirm that they accomplish the objectives introduced with our fitness functions. This chapter discusses background and related work first (section 2), then goes on to describe our methods; first the model we use to simulate Lego structures (sections 3-4), then the representa- tion and evolutionary algorithms (section 5). The results sections (6-7) discuss applications, show- ing the results of several evolutionary runs and illustrating with pictures of the final assembled Lego artifacts. Finally, on sections 8-9, current and future lines of work and conclusions are drawn.
Extended Abstract
Bibtex
Used References
Angeline, P. J. and Pollack, J. B. (1994). Coevolving High-Level Representations. In C. Langton, (ed.) Proceedings of the Third Artificial Life Meeting.
Chapman, C. D., Saitou, K. and Jakiela, M. J. (1993) Genetic Algorithms as an Approach to Con- figuration and Topology Design, in Proceedings of the 1993 Design Automation Conference, DE-Vol. 65-1. Published by the A.S.M.E., Albuquerque, New Mexico, p. 485-498.
Cliff, D., Harvey, I., Husbands, P. (1996). Artificial Evolution of Visual Control Systems for Robots. From Living Eyes to Seeing Machines. M. Srinivisan and S. Venkatesh (eds.), Oxford University Press.
Cormen, T. H., Leiserson, C. E. and Rivest, R. L. (1989). Introduction to Algorithms. MIT press - McGraw Hill.
Darwen, P. J. (1996) Co-evolutionary Learning by Automatic Modularisation with Speciation. Uni- versity of New South Wales, 1996.
Floreano, D. and Mondada, F. (1994). Automatic Creation of an Autonomous Agent: Genetic Evo- lution of a Neural Network Driven Robot. In D. Cliff, P. Husbands, J.-A. Meyer, and S. Wil- son (Eds.), From Animals to Animats III, Cambridge, MA. MIT Press.
Forbus, K. (1984). Qualitative process theory. In Artificial Intelligence 24, 85-168.
Funes, P. and Pollack, J. (1997). Computer Evolution of Buildable Objects. Fourth European Con- ference on Artificial Life. P. Husbands and I. Harvey, eds., MIT Press. pp 358-367.
Gardin, F. and Meltzer, B. (1989). Analogical Representations of Naive Physics. Artificial Life 38, pp 139-159.
Goldberg, David E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley.
Iusem, A. and Zenios, S. (1995). Interval Underrelaxed Bregman’s method with an application. In Optimization, vol. 35, iss. 3, p. 227.
Jakobi, N., Husbands, P. and Harvey, I. (1995). Noise and the Reality Gap: The use of Simulation in Evolutionary Robotics, in Advances in Artificial Life: Proceedings of the 3rd European Con- ference on Artificial Life, Moran, F., Moreno, A., Merelo, J., Chacon, P. (eds.) Springer-Ver- lag, Lecture Notes in Artificial Intelligence 929. pp. 704-720.
Koza, John R. (1992). Genetic Programming: On the Programming of Computers by Means of Nat- ural Selection. Cambridge, MA: The MIT Press.
Lee, W., Hallam, J. and Lund, H. (1996). A Hybrid GP/GA Approach for Co-evolving Controllers and Robot Bodies to Achieve Fitness-Specified Tasks. In Proceedings of IEEE 3rd Interna- tional Conference on Evolutionary Computation. IEEE Press.
19Leighton, T., Makedon, F., Plotkin, S., Stein, C., Tardos, E. and Tragoudas, S. (1995). Fast Approx- imation Algorithms for Muticommodity Flow Problems. Journal of Computer and Syst. Sci- ences 50. p. 228-243.
Lund, H., (1995). Evolving Robot Control Systems. In J. T. Alander (ed.) Proceedings of 1NWGA, University of Vaasa, Vaasa.
Lund, H., Hallam, J and Lee, W. (1997). Evolving Robot Morphology. Invited paper in Proceedings of IEEE Fourth International Conference on Evolutionary Computation. IEEE Press, NJ.
Mataric, M and Cliff, D. (1996). Challenges In Evolving Controllers for Physical Robots. In Evolu- tional Robotics, special issue of Robotics and Autonomous Systems, Vol. 19, No. 1. pp 67-83.
Ngo, J.T., and Marks, J. (1993). Spacetime Constraints Revisited. In Computer Graphics, Annual Conference Series. p. 335-342.
Pollack, J. B., Blair, A. and Land, M.(1996). Coevolution of A Backgammon Player. Proceedings Artificial Life V, C. Langton, (Ed), MIT Press.
Shoenauer, M. (1996). Shape Representations and Evolution Schemes. In L. J. Fogel, P. J. Angeline and T. Back, Editors, Proceedings of the 5th Annual Conference on Evolutionary Program- ming, MIT Press, to appear.
Sims, K. (1994). Evolving Virtual Creatures. In Computer Graphics, Annual Conference Series.
Sims, K. (1994b). Evolving 3D Morphology and Behavior by Competition. In Artificial Life IV Proceedings, MIT Press.
Tesauro, G. (1995) Temporal difference learning and TD-Gammon. Communications of the ACM, 38(3): 58-68.
Zienkiewicz, O.C. (1977). The Finite Element Method in Engineering Science. McGraw-Hill, New York, 3rd edition.
Links
Full Text
http://www.demo.cs.brandeis.edu/papers/edc98.pdf
