M.S. Thesis of Linge Bai:
Self-Organizing Primitives for Automated 2D Shape Composition

Motivated by the ability of living cells to form into specific shapes and structures, we present a new approach to automated 2D shape composition based on self-organizing primitives whose behaviors are derived via genetic programming. The key concept is to evolve local interaction rules that direct virtual cells to produce a self-organizing behavior that leads to the formation of a macroscopic, user-defined shape.

There are two levels of views. At the macroscopic level, a user-specified, pre-defined shape is given as input to the system. The system outputs local interaction rules that direct virtual cells to aggregate into the shape. At the microscopic level, cells take on prescribed behaviors, perform local interactions based only on local information. All cells are identical and do not know their position in the environment nor the final shape to be formed.

The interactions of the virtual cells, called Morphogenetic Primitives (MPs), are based on chemotaxis-driven aggregation behaviors exhibited by actual living cells. Cells emit a chemical into their environment. Each cell responds to the stimulus by moving in the direction of the gradient of the cumulative chemical field detected at its surface. MPs, though, do not attempt to completely mimic the behavior of real cells. The chemical fields are explicitly defined as mathematical functions and are not necessarily physically accurate. The explicit mathematical form of the chemical field functions are derived via genetic programming (GP), an evolutionary computing process that evolves a population of functions. A fitness measure, at the macroscopic level, based on the shape that emerges from the chemical-field-driven aggregation, determines which functions will be passed along to later generations.

This thesis describes the design of Morphogenetic Primitives(MP), cell-cell interaction rules as well as the GP-based method used to define the chemical field functions needed to produce user-specified shapes from simple aggregating primitives. In the fitness evaluation portion of genetic programming, a heuristic algorithm for calculating center of mass (COM) in a toroidal environment is proposed. This thesis also presents the self-alignment and self-organization process of MPs as well as analysis of the overall approach.

Last modified on September 17, 2008.