(movie of self-assembly)
Some Project Webpages:
NSF Grant Proposal
NSF Program on Quantum and Biologically Inspired Computing (QuBIC)
Amorphous Computing homepage
This research focuses on morphogenesis and developmental biology as a source of algorithms and general principles for organizing complex behavior from locally interacting individuals. We aim to design artificial systems that replicate biological robustness, and to use insights from these systems to understand the capabilities of biological systems. The goal is to be able to eventually formalize these general principles as programming languages --- with explicit primitives, means of combination, and means of abstraction --- thus providing a framework for the design and analysis of self-assembling systems.
We believe that the results from this research will have significant impact, not only on our engineering principles for robust design but also on our understanding of biological systems. These new programming models will impact the design of and approach to reconfigurable robotics, self assembly, and smart-matter applications. In the long run, these ideas may even help achieve coherent behavior from aggregates of biological cells. The biological comparisons will significantly improve our understanding of development and creation of morphology. Not only will this promote the use of computational models for understanding systems level biology, but it will also increase collaboration between computer science and biology in this area, where focus has traditionally been narrow.
Important organizational lessons can be learned from natural biological systems. Emerging technologies are making possible novel applications that integrate computation into the environment: smart materials, self-reconfiguring robots, self-assembling nanostructures. We are faced with the challenge of achieving coherent and robust behavior from the interactions of multitudes of elements and their interactions with the environment. These new environments fundamentally stress the limits of our current engineering and programming techniques, which depend on precision parts and strongly regulated environments to achieve fault-tolerance. By contrast, the precision and reliability of embryogenesis, in the face of constantly dying and replacing cells, variations in cell numbers, and changes in the environment, is enough to make any engineer green with envy. Our previous work demonstrated the potential of this approach with a programmable and robust process for shape formation on a sheet of identically-programmed ``cells'' using local primitives inspired by epithelial cell morphogenesis and Drosophila cell differentiation.
The goal of this project is twofold:
Lauren Clement won the 2003 Anna Pogosyants UROP (undergraduate Research) Award for her work on active gradients.
Stoy, Nagpal, Self-reconfiguration using Directed Growth, 7th International Symposium on Distributed Autonomous Robotic Systems (DARs), France, June23-25, 2004.
Werfel Building Blocks for Multi-Robot Constructionh, 7th International Symposium on Distributed Autonomous Robotic Systems (DARs), France, June23-25, 2004.
Nagpal, Mamei, Engineering Amorphous Computing Systems, invited chapter in Methodologies and Software Engineering for Agent Systems, editors Bergenti, Gleizes, Zambonelli, Kluwer Academic Publishing, (in press) 2003.
Bachrach, Nagpal, Salib, Shrobe, Experimental Results and Theoretical Analysis of a Self-Organizing Global Coordinate System for Ad Hoc Sensor Networks, Telecommunications Systems Journal, Special Issue on Wireless System Networks, Kluwer Academic Publishing, 2003.(pdf)
Beal, Near-Optimal Distributed Failure Circumscription, International Conference on Parallel and Distributed Computing and Systems (PDCS), CA, Nov 2003. paper
Beal, Robust Amorphous Hierarchy from Persistent Nodes, International Conference on Communication Systems and Networks, Spain, Sept 2003. paper
Nagpal, Towards a Catalog of Biologically-inspired Primitives, Workshop on Engineering Self-organising Applications, Autonomous Agents and Multiagents Systems Conference (AAMAS), 2003, LNAI 2977.
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)
Clement, Nagpal, Self-Assembly and Self-Repairing Topologies, Workshop on Adaptability in Multi-Agent Systems, RoboCup Australian Open, January 2003. (ps)
Selected Papers from graduate seminar on Biologically-inspired Programming Technology
Nagpal, Programmable Self-Assembly Using Biologically-Inspired Multiagent Control, Proceedings of the 1st International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), Bologna, Italy, July 2002. (ps)
Nagpal, Programmable Pattern-Formation and Scale-Independence, International Conference on Complex Systems (ICCS), June 2002. (ps)
Beal, An Algorithm for Bootstrapping Communications, International Conference on Complex Systems (ICCS), June 2002.
Also see the Amorphous Computing publications page.