Amorphous Computing

Cells with identical DNA cooperate to create complex structures, from fruitflies to humans, with incredible reliability in the face of cell death, variations in cell numbers, and changes in the environment. Even after development, multicellular organisms show amazing abilities to repair and regenerate. Yet colonies of cells are not the only living things that create complex structure. Even colonies of social insects ("superorganisms") show the ability to create complex large-scale structures that is self-repairing, for example millimeter size termites cooperate to create mounds with complex architecture and army ants create nests (bivouacs) out of their own bodies.

Our group uses inspiration from these systems to study Programmable Self-Assembly: how global structure, repair, and adaptation can be achieved through simple local behaviors. Our early work was done in the context of Amorphous Computing, where we looked at global-to-local compilers for pattern formation and showed how one could automatically create scale-invariant and self-repairing patterns (Nagpal's PhD Thesis at MIT) with applications to origami-inspired foldable programmable materials. Our later work was done in the context of Self-reconfigurable Modular Lattice Robots (joint work with Prof. Kasper Stoy, SDU/ITU, Denmark) and Robot Swarms (see AAAI shapebugs paper). The work above was mainly algorithmic and theory-oriented, but laid the algorithmic ground for two of our best known collective robotic systems - the Termes and Kilobot projects - that bring the early concepts of amorphous computing to life.

A key focus of all of this foundational work was the design of global-to-local compilers, where the goal is described using a high-level shape language and the compiler automatically translates the user-specified global goal into a provable agent ("cell") program. We showed that such compilers could be created by composing smaller bio-inspired primitives, and that through smart compositions, one could encode scale-independence or self-repair or error-correction into the compiler itself.

Selected Publications