Research Abstracts - 2006

Towards a Computational Model of Dictyostelium discoideum

Jonathan Bachrach & Tom Hsu

Overview

Swarm robotics rely on a large number of robots with identical algorithms to achieve global behaviors. This problem is analogous to biology in which cells communicate with each other and work together to sustain life. Our belief is that by constructing computational models of the behavior of biological cells, we will 1) gain insights into connections between individual and global behaviors, 2) begin to develop a computational theory for how biology operates, and 3) start to understand how we might program biology to accomplish tasks that we specify.

Problem Statement

Swarm robotics is becoming a reality as miniaturization and computerization continue to lower the cost and increase the functionality of robots. Utilizing a fleet of robots is becoming the main focus for many researchers. Researchers are interested in creating algorithms and frameworks to allow robots to work together efficiently. The study of how to use multiple robots effectively to achieve common goals is called swarm robotics [1].

Swarm robotics can be seen as a problem already solved by nature to sustain life for bacteria and multicellular organisms. Cells, analogous to robots, work together to achieve global objectives. While individual cells may perform different tasks than their neighbors, they share the same blueprint - the genetic code. Swarm robotics strives to achieve the same goal - to use a large number of robots with an identical algorithm to solve problems collectively. We want to learn from biology to create swarm robotic algorithms. A species of bacteria called Dictyostelium discoideum is our particular source of inspiration and focus of inquiry.

Dictyostelium discoideum are soil amoebae capable of many different techniques for survival. It is also known as the social amoebae or "cellular slime molds". These amoebae can form multicellular organisms in order to increase their chances for survival and reproduction. The mechanisms of such social behaviors are useful building blocks for distributed robotic control. In other words, knowledge can be gleaned from Dictyostelium bacteria to teach a swarm of robots to work together.

The goal of this project is to model the life of Dictyostelium discoideum. Programming the behaviors of the bacteria as swarm robots will grant insights on the connections between individual behaviors and global behaviors. The algorithms will be constructed to be reusable and composable. We will use the Proto programming language [5], a distributed stream processing language for sensor/actuator networks.

Related Work

McLurkin [1] has done pioneering work in swarm robotics. In particular, he has developed a C library of group behaviors inspired by ant colonies and deployed them on 128 small mobile robots. In contrast, this research aims to explain the Dictyostelium discoideum development cycle using a computational model built on top of a high level programming language. This computation model will allow us to better understand how nature has tackled the problem of programming a swarm of identical robots.

The behaviors of Dictyostelium discoideum have been intensely studied by biologists. The initial stages of development are well understood. The mechanism for the aggregation into a loose mound is explained well by Scott Camazine in his Self-Organization in Biological Systems [2]. Dictyostelium generates chemical waves through refractory period and digestion and release of the cAMP chemicals. The wave and aggregation model have been previously tested in simulation [4]. The simulation mirrors the experimental observations in laboratories. We will expand this work to include the whole development cycle of Dictyostelium and to do so out of composable and reusuable parts.

Proposed Work

The goal of the project is to describe all the developmental stages for Dictyostelium discoideum. Our project involves two major steps:

Step 1: Simulation environment. While the basic Proto language is fairly mature, its support for biological modeling is only preliminary. More low level building blocks need to be present in order to effective describe Dictyostelium bacteria. One of the major questions is how to express chemical diffusion in an abstract and composable manner. Other basic mechanisms include refractory periods, gradient sensing, chemotaxis, etc. The simulation will also need a graphical display to show the actual movements of the simulated bacteria. A graphical display will be invaluable in debugging and demonstrating the developmental algorithms quickly.

Step 2: Module library. The main purpose of this project will be to develop a library of composable modules that enable robots to work together efficiently. With the abstraction mechanisms provided by the Proto language, we will write each of the developmental algorithms in a concise and natural fashion. Basic movements include how to collect the bacteria together and differentiate them to have a head and a tail, etc.

Progress

To date, we have augmented the Proto language and runtime to include support for chemical channels and communication. Using this substrate, we have simulated the wave propagation and cell aggregation mechanisms. Finally, we have developed preliminary models for multicellular differentiation in the aggregated amoebae.

Chemical Wave Propagation	Cell Aggregation

Multicellular Differentiation

References

[1] J. McLurkin, "Stupid Robot Tricks: A Behavior-Based Distributed Algorithm Library for Programming Swarms of Robots," Master of Science Thesis, May 2004, Massachusetts Institute of Technology.

[2] S. Camazine, Self-Organization in Biological Systems, Princeton University Press: Princeton, 2003.

[3] R. Kessin, Dictyostelium, Developmental and Cell Biology Series, Cambridge University Press: New York, 2001.

[4] M. Resnick, StarLogo: An Environment for Decentralized Modeling and Decentralized Thinking Mitchel Resnick, CHI, 1996.

[5] J. Beal, J. Bachrach. “Infrastructure for Engineered Emergence on Sensor/Actuator Networks. IEEE Intelligent Systems. March/April 2006.