Automated assembly as situated development: using artificial ontogenies to evolve buildable 3-D objects

ABSTRACT

Artificial Ontogenies, which are inspired by biological development, have been used to automatically generate a wide array of novel objects, some of which have recently been manufactured in the real world. The majority of these evolved designs have been evaluated in simulation as completed objects, with no attention paid to how, or even if, they can be realistically built. As a consequence, significant human effort is required to transfer the designs to the real world. One way to reduce human involvement in this regard is to evolve how to build rather than what to build, by using prescriptive rather than descriptive representations. In the context of Artificial Ontogenies, this requires what we call Situated Development, in which an object's development occurs in the same environment as its final evaluation. Not only does this produce sufficient information on how to build evolved designs, but it also ensures that only buildable designs are evolved. In this paper we explore the consequences of Situated Development, and demonstrate how it can be incorporated into Artificial Ontogenies in order to generate buildable objects, which can be sequentially assembled in a realistic 3-D physics environment.

REFERENCES

• 1: J. Bongard and R. Pfeifer. Morpho-functional Machines: The New Species (Designing Embodied Intelligence), chapter Evolving complete agents using artificial ontogeny, pages 237--258. Springer-Verlag, Berlin, 2003.
• 2: J. C. Bongard and H. Lipson. Once More Unto the Breach: Automated Tuning of Robot Simulation using an Inverse Evolutionary Algorithm. In Proceedings of the Ninth Int. Conference on Artificial Life (ALIFE IX), pages 57--62, 2004.
• 3: C. A. C. Coello. An updated survey of evolutionary multiobjective optimization techniques: State of the art and future trends. In P. J. Angeline, Z. Michalewicz, M. Schoenauer, X. Yao, and A. Zalzala, editors, Proceedings of the Congress on Evolutionary Computation, volume 1, pages 3--13, Mayflower Hotel, Washington D.C., USA, 6-9 1999. IEEE Press.
• 4: E. D. De Jong, R. A. Watson, and J. B. Pollack. Reducing bloat and promoting diversity using multi-objective methods. In L. Spector, E. Goodman, A. Wu, W. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. Garzon, and E. Burke, editors, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2001, pages 11--18, San Francisco, CA, 2001. Morgan Kaufmann Publishers.
• 5: Pablo Jose Funes , Jordan B. Pollack, Evolution of complexity in real-world domains, 2001
• 6: M. Goldwasser, , J. Latombe, and R. Motwani. Complexity measures for assembly sequences. In Proc. IEEE Int. Conf. on Robotics and Automation, pages 1581--1587, Minneapolis, MN, Apr. 1996.
• 7: Gregory Scott Hornby , Jordan B. Pollack, Generative representations for evolutionary design automation, 2003
• 8: G. S. Hornby and J. B. Pollack. The advantages of generative grammatical encodings for physical design. In Proceedings of the 2001 Congress on Evolutionary Computation CEC2001, pages 600--607, COEX, World Trade Center, 159 Samseong-dong, Gangnam-gu, Seoul, Korea, 27-30 2001. IEEE Press.
• 9: Nick Jacobi , Phil Husbands , Inman Harvey, Noise and the Reality Gap: The Use of Simulation in Evolutionary Robotics, Proceedings of the Third European Conference on Advances in Artificial Life, p.704-720, June 04-06, 1995
• 10: Lydia Kavraki , Jean-Claude Latombe , Randall H. Wilson, On the complexity of assembly partitioning, Information Processing Letters, v.48 n.5, p.229-235, Dec. 10, 1993 [doi>10.1016/0020-0190(93)90085-N]
• 11: Maciej Komosinski , Szymon Ulatowski, Framsticks: Towards a Simulation of a Nature-Like World, Creatures and Evolution, Proceedings of the 5th European Conference on Advances in Artificial Life, p.261-265, September 13-17, 1999
• 12: J. D. Lohn, G. S. Hornby, and D. S. Linden. An Evolved Antenna for Deployment on NASA's Space Technology 5 Mission. In U.-M. O'Reilly, R. L. Riolo, T. Yu, and B. Worzel, editors, Genetic Programming Theory and Practice II. Kluwer, in press.
• 13: Samir W. Mahfoud, Niching methods for genetic algorithms, University of Illinois at Urbana-Champaign, Champaign, IL, 1996
• 14: Jordan B. Pollack , Hod Lipson , Gregory Hornby , Pablo Funes, Three generations of automatically designed robots, Artificial Life, v.7 n.3, p.215-223, Summer 2001 [doi>10.1162/106454601753238627]
• 15: J. Rieffel and J. Pollack. The Emergence of Ontogenic Scaffolding in a Stochastic Development Environment. In K. D. et al., editor, Genetic and Evolutionary Computation--GECCO 2004. Proceedings of the Genetic and Evolutionary Computation Conference. Part I, pages 804--815, Seattle, Washington, USA, June 2004. Springer-Verlag, Lecture Notes in Computer Science Vol. 3102.
• 16: J. Rieffel and J. B. Pollack. Artificial ontogenies for real world design and assembly. In M. B. et al., editor, Ninth International Conference on the Simulation and Synthesis of Living Systems (ALIFE9) Workshop: Self-Organization and Development in Artificial and Natural Systems (SODANS), pages 37--41. MIT Press, 2004.
• 17: Karl Sims, Evolving virtual creatures, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.15-22, July 1994 [doi>10.1145/192161.192167]
• 18: M. Toussaint. Demonstrating the evolution of complex genetic representations: An evolution of artificial plants. In Proceedings of the 2003 Genetic and Evolutionary Computation Conference (GECCO 2003). Springer-Verlag, New York, 2003.
• 19: J. Ventrella. Explorations in the emergence of morphology and locomotion behavior in animated characters. In R. A. Brooks and P. Maes, editors, Proceedings of the 4th International Workshop on the Synthesis and Simulation of Living Systems Artificial Life IV, pages 436--441, Cambridge, MA, USA, July 1994. MIT Press.
• 20: S. Viswanathan and J. B. Pollack. Towards an evolutionary-developmental approach for real-world substrates. In M. B. et al., editor, Ninth International Conference on the Simulation and Synthesis of Living Systems (ALIFE9), pages 45--41. MIT Press, 2004.
• 21: R. A. Watson, S. G. Ficici, and J. B. Pollack. Embodied evolution: Embodying an evolutionary algorithm in a population of robots. In P. J. Angeline, Z. Michalewicz, M. Schoenauer, X. Yao, and A. Zalzala, editors, Proceedings of the Congress on Evolutionary Computation, volume 1, pages 335--342, Mayflower Hotel, Washington D.C., USA, 6-9 1999. IEEE Press.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics

General Terms:
Algorithms, Design

Keywords:
artificial ontogeny, assembly, evolutionary design, fabrication