Tentative schedule:

9:00 – 10:30 Session on Self-organizing Biological Systems
9:00 – 9:45

Abstract

Cells use sophisticated, multiscale spatial patterns of chemical instructions to control cell fate and tissue growth. While synthetic formation of some types of spatial patterns have been well studied, it remains unclear how to build precise, repeatable patterns using chemical reaction-diffusion networks. Here we describe a scalable approach for the design of complex patterns, implemented in biocompatible networks of synthetic DNA. In our method, black-box reaction-diffusion "modules" are chained together into integrated "programs" for arbitrarily complex pattern formation. These programs can respond to input stimuli, process information, and ultimately produce stable output features that differ in size and concentration from the inputs. To build these programs, we break a target pattern into a set of patterning subtasks, design modules to perform these subtasks independently, and combine the modules into composite networks. We demonstrate how programs designed with our methodology can generate complex 1 and 2-dimensional patterns in response to a few localized inputs.

9:45 – 10:30

Abstract

Just as physics speaks the language of mathematics, the life sciences speak the language of algorithms. The difference lies in the loss of symmetry and the high descriptive and historical complexity of the systems commonly found in social and biological organisms. This talk will discuss the power of "natural algorithms" through the lens of "influence systems", a broad family of high-dimensional self-organizing systems for which algorithmic tools can do what differential equations cannot.

10:30 – 11:00 Open Discussion & Coffee break
11:00 – 12:30 Session on Self-organizing Robotic Systems
11:00 – 11:45

Abstract

Self-reconfiguring modular robots are electro-mechanical systems composed of repeated units that join together and can rearrange their connectivity to form a larger system. Over the past quarter century resarchers have designed dozens of systems and published thousands of papers on the topic. This presentation will include a review of some of the systems we have built, some issues in mechanical design, communications and power infrastructure and their implications on algorithms and vice-versa.

11:45 – 12:30

Abstract

Materials that think are enabled by recent advances in smart polymers, desktop manufacturing systems and miniaturization of computers. These materials tightly integrate sensing, actuation, computation and communication in a periodic, amorphous fashion, which might enable revolutionary new composites with fully programmable capabilities. The challenges in creating materials that think lie at the intersection of material science engineering and computer science, and — from a CS perspective — require advances in distributed algorithms for signal processing, control and routing of information.

I illustrate these challenges and recent advances by our group using three experimental case studies, all using identical computational infrastructure: (1) a soft robotic skin that can locate and classify textures by locally sampling, processing and classifying vibrations and route relevant information to a CPU using multi-hop networking; (2) A modular building block for creating intelligent walls and facade systems that can recognize complex gestures; and (3) variable-stiffness composites that can assume arbitrary shapes using simple actuation and local feedback control. Albeit serving different functions at different scales, material and computational properties can be designed using a unified mathematical framework based on abstracting the computer network as continuous amorphous medium.

12:30 – 14:00 Open Discussion & Lunch
14:00 – 15:30 Session on Amorphous Computing
14:00 – 14:45 Eric Klavins: "Engineering Multicelluar Systems"

Abstract

An engineering framework multicellular systems is crucial scientifically and practically. Evidence suggests that naturally occurring finite state machines control how cells switch states from stem cells to tissue specific cells according to chemical, mechanical, and logical cues from their local environments. However, many details remain unclear: How is state encoded by patterns of gene expression? How are states stabilized to avoid spontaneous switching? How do state-specific signals reliably cause transitions between states? Most importantly, can we build novel finite state machines in synthetic cells that control the process of differentiation and development? Such a capability would enable applications including multicellular diagnostic devices, division of labor in complex metabolic processes, pattern formation for tissue engineering, and possibly new approaches to understanding diseases such as cancer in which cell state is improperly regulated. Here, I describe theoretical results relating communicating finite state machines with gene regulatory networks and cell-cell signaling; a multicellular simulation tool called gro that enables exploration of designs; experimental work on programmed cell differentiation in E. coli that enables a division of labor scheme for complex feedstock digestion.

14:45 – 15:30 Andrea Richa: "Amoeba-inspired Self-organizing Particle Systems"

Abstract

Particle systems are physical systems of simple computational particles that can bond to neighboring particles and use these bonds to move from one spot to another (non-occupied) spot. These particle systems are supposed to be able to self-organize in order to adapt to a desired shape without any central control. Self-organizing particle systems have many interesting applications like coating objects for monitoring and repair purposes and the formation of nano-scale devices for surgery and molecular-scale electronic structures. While there has been quite a lot of systems work in this area, especially in the context of modular self-reconfigurable robotic systems, only very little theoretical work has been done in this area so far. We attempt to bridge this gap by proposing a model inspired by the behavior of amoeba that allows rigorous algorithmic research on self-organizing particle systems.

15:30 – 16:00 Open Discussion & Coffee break
16:00 – 17:30 Session on Self-Assembling DNA
16:00 – 16:45 John Reif: "Dynamic Self-Organization by Artificial and Physical Systems"

Abstract

In this talk, we describe our (done with Hongyan Wang) powerful and very general approach for distributed autonomous control of autonomous robots. We call this Social potential fields; it provides a distributed behavioral control for autonomous robots. We define simple artificial force laws between pairs of robots or robot groups. The force laws are sums of multiple inverse-power force laws, incorporating both attraction and repulsion. The force laws can be distinct and to some degree they reflect the 'social relations' among robots. Therefore we call our method social potential fields. The resultant artificial force imposed by other robots and other components of the system controls an individual robot’s motion. The approach is distributed in that the force calculations and motion control can be done in an asynchronous and distributed manner. We also extend the social potential fields model to use spring laws as force laws. We discuss applying potential fields to distributed autonomous multi-robot control, and the generic framework of our social potential fields method.

We also give complexity lower bounds for the complexity of n-body simulation (done with Stephen R. Tate) that indicate that is very unlikely that there is a deterministic polynomial time algorithm for n-body simulation. In the case we require a polynomial number of bits of accuracy and where the target time is polynomial in n, our complexity lower bounds are surprisingly PSPACE. We show that the reachability problem for a set of interacting particles in three dimensions is PSPACE-hard. All previous lower bound proofs required either artificial external forces or obstacles.

16:45 – 17:30 Erik Winfree: "Passive self-assembly with tiles and active self-assembly with motors"

Abstract

The study of simple models of computation based on the principles of molecular self-organization allows us to study the complexity of molecular self-organization tasks and to differentiate the capabilities of distinct mechanisms and architectures. Here, we examine the algorithmic fabrication task, inspired by biological developmental programs, as executed by two models of self-assembly. Passive self-assembly of tiles, a generalized form of crystal growth, is universal for computation and construction, but time for growth is lower bounded by the diameter of the object being constructed. Active self-assembly using molecular motors, allowing reconfigurable structures and mechanical interactions, is also universal for both computation and construction, but can be exponentially faster, taking time polylogarithmic in the diameter.

17:30 – 18:00 Open Discussion & Get Together