Kondacs, Biologically-inspired Self-Assembly of 2D Shapes, Using Global-to-local Compilation, International Joint Conference on Artificial Intelligence (IJCAI), 2003. (pdf)
Nagpal, Kondacs, Chang, Programming
Methodology for Biologically-Inspired Self-Assembling Systems,
in the AAAI Spring Symposium on Computational Synthesis: From
Basic Building Blocks to High Level Functionality, March 2003.
(pdf)
Overview
By what mechanisms do biological cells replicate to form highly complex structures? How might one use such an insight to engineer robust systems comprised of aggregate elements? To investigate such questions, this work addresses the problem of programming cell-like computing units to achieve specified three-dimensional conformations. Modeling cells as distributed, identically-programmed structures, we explore methods for instructing these elements to attain a globally-described shape relying solely on their ability to replicate and engage in limited, local communication. These attributes are central to a computing paradigm known as Amorphous Computing.
This project has two major components. The first part addresses the task of converting a predetermined global shape into a representation which is efficient and conducive to amorphous growth. The next task involves linking the representation with a set of instructions that, when executed by every "cell", generates the growth of the specified shape.
Finding an appropriate shape representation is essential to the compilation phase, which translates a global shape into a corresponding individual cell program. Key work has been done by Radhika Nagpal, who presents an origami-inspired language for instructing a two-dimensional sheet of cells to assemble into global structures. Additionally, the question of efficiently representing three-dimensional shapes is prevalent in computer graphics research. This project seeks to represent three-dimensional shapes in terms of an efficient sphere-packing, motivated by the fact that spheres are very easily grown in an amorphous fashion.
This sphere-representation permits the actual cell program to consist, at the highest level, of only a few basic primitives. Namely, a cell must (1) initiate the growth of a sphere and/or exist as a member of a sphere, and (2) exude gradient-like signals to accomplish the triangulation of sphere-originating cells. Because the cells are subject to limited communication and random point or regional death, it is crucial that the cell program incorporate a high degree of strength and flexibility. Accordingly, the cell program is based on relative, rather than absolute, information provided by the sphere representation, and the delegation of tasks among cells is such that successor cells are automatically designated in the event of sudden cell death.
Our current focus is to implement the amorphous growth of arbitrary shapes in two dimensions, which will subsequently be extended to 3D.