PROBE on Understanding and Harnessing Ensemble Behavior

Organized bySeth Copen Goldstein

This proposal aims to understand complex systems that arise both in nature and as a result of human engineering. Such systems range from human engineered systems such as the internet, the power system, and the telephone network to biological systems such as multicellular organisms, ant colonies, social organizations, and flocks of birds. Our long term goal is to develop a theory and method for efficiently creating such systems which possess provably correct properties. We believe that computational thinking holds the key to understanding and engineering these systems. Complex biological organisms are built from vast numbers of individual cells (e.g., there are 1014 cells in a person) and yet the number of unique types of cells is quite small (e.g., 400 different types in a human). Furthermore, the individual cells—all specialized versions of the same basic prototype which start from the same initial plan and carry the same “program”—have limited capabilities. Few can move on their own, none are capable of complex problem solving, and many of them are not capable of surviving without the support of other cells. But, when the cells are combined together in the proper way, the result is a complex living organism with capabilities far in excess of the sum of its parts. In contrast, most man made systems typically have large numbers of custom parts. A Boeing 777 airliner, for instance, has only 3 million parts but over 130,000 unique types of parts. The work in this proposal is intended to shed light on how we can construct interesting and robust systems which can use large numbers of similar, small, limited functionality, but programmable units to create complex systems. The key to exploring this possibility is to understand how to “program” the simple units to obtain the desired complex ensemble behavior. This idea is becoming even more important as microscale manufacturing processes (e.g. synthetic biology, nanotechnology) gain momentum. The systems we are interested in—which we call ensembles—share three important properties: (1) They are composed of massive numbers of interacting units, (2) Each unit has limited functionality, and (3) Each unit is capable of “running” a “program.” How do we understand such ensembles? How do we engineer them? How do we make ensembles which are flexible, robust, controllable, programmable, and cost effective? We believe that answering these questions is vital to future progress—and, that a combination of computational thinking and thermodynamics holds the answers.

Computational Thinking: Inspiration and Understanding

Computational thinking is an important concept in and of itself. Properly applied it should lead to radically new approaches to science and technology. In our group we are investigating programmable matter—in some sense, the ultimate expression of computational thinking—i.e., how to bring the power of computing to matter. We have used this as a basis for both teaching and inspiring students about computer science. Last year, we used Meld, a programming language for ensemble engineering, in the Microsoft sponsored OurCS program to teach a group of undergraduate women concepts in abstraction, programming, logic, ensemble engineering, and emergent behavior. For the last two years we have used programmable matter to teach high school students about abstraction, ensembles, self-organization, robotics, and programming.

Meld: An ensemble programming language

Our approach to understanding ensembles is based on developing a means of creating them. To this end we have developed Meld, a declarative, logic-based programming languages specifically for ensembles. With roots in Datalog and Prolog, Meld permits the programmer to specify rules for deriving ”facts” about the system. These facts are automatically distributed to the relevant nodes by means of an automatic messaging system. This provides the programmer the illusion of programming a single system without having to be enmeshed in the intricacies of the units. The Meld compiler and runtime handle all the details of distributing data and maintaining a coherent state across the ensemble. Among the research goals guiding our work on Meld is to develop concise, efficient, and provably correct programs for ensembles. Meld is a logic-based programming language and Meld programs are amenable to proof. We have been able to prove important properties about some of our Meld programs using a combination of paper proofs and a straightforward translation from Meld to theorem proving tools like Twelf. This permits us to prove correctness properties about algorithms and their actual implementations. For example, we have proven that our general shape planning algorithm written in Meld is complete (i.e., ...) and sound (ii.e., ...). We hope to expand on this area of our research by creating an tool which can automatically translate Meld to Twelf, thereby facilitating automatic theorem proving. To date we have used Meld, in simulation, to create concise and provably correct implementations of a generalized planner for claytronics as well as smaller programs to perform unit localization, message routing, etc. The most promising planner makes use of groups of modules, called meta-modules, to create a new abstraction where the programmer can ”create” and ”destroy” meta-modules without needing to worry about where the modules that make up the meta-module come from or go to, or how they move about. The localization program establishes a coordinate system on the ensemble for use in other algorithms such as the planner. These algorithms have been shown to work well in simulations, however the simulator used to date has some serious limitations: it only simulates claytronic ensembles and it lacks sufficient parallelism and real concurrency. The shortcomings of the simulator present two significant problems with simulating the execution of Meld programs. Firstly, the lack of parallelism creates limitations upon the size of the MD systems that experiments can be run upon. Even more importantly, the current simulator runs one ’tick’ on each node of the MD at a time, preventing any real concurrency. This lack of real concurrency has the potential to mask bugs and subtle design flaws calling into question the results of the existing simulator. More importantly it only allows us to investigate how Meld works for claytronic ensembles.

Target Systems

Modular robots are an exemplar of most ensembles. Each robot, on its own, is limited in functionality and only as ensemble can they exhibit interesting behavior. Ensembles are generally made up of many modules, capable of moving around and communicating and can be programmed to do arbitrary things. The variety of possible modular robots, however, is quite broad. We believe that there are overarching ideas and methods that can be applied to programming all ensembles. To expand on our understanding and ensure that we hit upon these overarching methods we will investigate two very different ensembles: claytronics and Telecube style robots. The idea behind claytronics is to have spherical robots that are capable of rolling along the surface of other robots. These robots are programmatically sticky such that by controlling where they stick they can be made to roll. This model allows for fairly arbitrary packings of modules where the robots can move only along the surface (including internal surfaces) of the ensemble. The Telecube style robots (an early version of the robots we are constructing), on the other hand, are cube shaped robots that pack in a fairly strict lattice and move more internally. These robots are capable of extending arms on each of their surfaces, permitting them to push away from other robots or pull towards them. This leads to more constrained motion patterns than in the claytronics model with the benefit of a much stricter lattice in which the robots must be placed. By exploring both models we can verify and expand our methods. This will permit us to demonstrate that techniques work across various types of ensembles rather than being constrained to a specific model, helping to ensure that we develop general ensemble programming principles. Furthermore, if we can show how to implement Meld on such different systems, then we hope to have a recipe for implementing Meld on other ensembles, e.g., sensor networks, internets, etc.

Expanding Melds Domain Using Robotic Studio

To further our study of ensembles we need to expand the possible targets which can run Meld programs. The concurrency and scalability of Robotics Studio should provide us with a significantly more capable platform on which to test out our approach to engineering ensembles. Using Robotic Studio should permit us to run larger, more accurate simulations and gain a much better understanding of how well Meld truly works. Furthermore, with Meld working on Robotics Studio it could be run on any system that is also implemented in Robotics Studio. This would allow a larger range of test platforms for Meld as well as provide an alternative means for programming interacting robots, and general ensembles, in Robotics Studio. We propose to implement APIs for two very different ensembles (Claytronics and Telecube style modular robots) in Robotics Studio.1 Having done this we would interface Meld with these APIs (and other available APIs) to permit running Meld programs on Robotics Studio ensembles. With this working it would then be possible to run existing Meld programs on Robotics Studio and find any concurrency problems that were masked by the existing simulator. It would also permit us to better understand known concerns about Meld with real concurrency. Once all concurrency issues in Meld are addressed, the next step is to verify Meld on real hardware.

Developing a System for Research and Teaching

Concurrent with our implementation of Meld in Robotics Studio we are working on implementing the Telecube style robots. With the development of real hardware which is robust and reasonably inexpensive this will provide a platform for other researchers to explore ensemble engineering, both in simulation and in reality.

1 We have already had productive discussions about this with Tandy Trower, George Chrysanthakopoulos, and Stewart Tansley.

Papers:

A Language for Large Ensembles of Independently Executing Nodes
Michael P. Ashley-Rollman, Peter Lee, Seth Copen Goldstein, Padmanabhan Pillai, and Jason D. Campbell

Detecting Locally Distributed Predicates
Michael de Rosa, Seth Copen Goldstein, and Peter Lee