Funnycells assignment: CS 374, Winter and Fall 2010

This is an assignment about funny cells. There are three kinds of cells: susceptible, infected, and antibodies. The infected and antibody cells try to convert their opposite kinds and induct them into their workforce. Students will divide themselves into groups, some groups will program the infected cells, other groups will program the antibody cells, and they will be pitted against each other at the end of the semester! The goal is simple -- for the infected cells it is to infect everybody, and for the antibody cells it is to immunise everybody. But there are some rules:

Molecular communication: The cells cannot directly talk to one another. They can manufacture molecules and dump these molecules into the medium. The medium is assumed to be sufficiently viscous so that the molecules do not diffuse away. Other cells in the neighborhood can sense these molecules. Note that sensing consumes the molecule, so if a cell has to send some information to two other cells, it has to produce two molecules. Communication can thus happen by producing different kinds of molecules, as long as the different cells know what the information encoded on the molecules means.
Alphabet: The molecules can only use a finite alphabet of a, t, c, g protein sequences. So, any information to be communicated has to be encoded into this 4-letter alphabet.
Energy and lifetime: Molecules have a finite lifetime, and the lifetime depends upon their size. The larger the molecule, the greater its lifetime. But there is also an energy cost to manufacturing molecules -- the larger a molecule, the greater its energy cost. If a cell runs out of energy, it becomes completely ineffective. Energy reservoirs are available, but the cells have to make sure they travel to the reservoirs before they run out of energy since there is energy cost to movement as well.
Quorum: A single cell cannot infect another cell, but a sufficient quorum is required. This is similar to how quorum sensing is necessary in bacterial infections.
Movement: Infected and antibody cells can move around to infect other cells. But since infections can only happen with a sufficient quorum, it is necessary for a group to move together. Or, at least to arrive at target cells at the same time to launch a successful infection.

This is what it looks like. Susceptible cells are yellow, infected ones are red, and the antibodies are green. The infected cells in my reference implementation also leave pheromone trails, marked with an 'i'. You can see that the infected and antibody cells are moving around in small armies!

And since the infected cells are smarter, they win at the end!

Although an effort has been made to preserve molecular communication semantics as those available in real cellular networks or projected to happen in futuristic nanonetworks, the mapping is in no way accurate or exhaustive. This is purely meant to serve as an exciting assignment.

Before we move to the details, just a note about the different counters reported on the cellular map. The susceptible, infected, and antibody counters give a current count of the number of different types of cells. The infections and immunisations counters give the number of conversions that were made so far. The infected energy and antibody energy counters give an exponentially weighted moving average of the amount of energy consumed per cell per sec by the infected and antibody cells. The infected coord and antibody coord metrics are updated only upon clicking the Update button, and indicate the level of synchrony with which the infected and antibody cells move together. More about the metric later, but this is just to give an indication of whether the cells are able to form groups and move in groups, rather than just moving randomly.

Running funnycells

The source code and binaries (compiled on Java 1.6.0_10) for the simulator can be downloaded here. Note that only binaries are available for my reference implementation of the antibody and infected cells. Instructors can drop me an email for the source code. The code is also available through SVN on Google Code.

The simulator runs in a client-server mode. Each cell runs as a separate Java program, and connects to the server. To run the server, navigate to the funnycells directory and type:

java -cp "lib/java-getopt-1.0.13.jar;build" assg.funnycells.server.Coordinator -c [config file] -l [log level] -x [terminate upon infection] -v [display ON/OFF] -w [walls ON/OFF]

-c [config file]: The default file is funnycells.conf, picked up from the current directory. This is explained in more detail later.
-l [log level]: This can be 0 (no logging), 1 (info), or 2 (debug)
-x [terminate upon infection]: This is just a termination condition to end the simulation. If marked as 1, the server will terminate when all susceptible cells have been infected or immunized, ie. the number of susceptible cells goes to zero. 0 indicates that the server will keep running
-v [display ON/OFF]: This can be 0 (no display) or 1 (display active)
-w [walls ON/OFF]: This can be 0 for a toroid topology where the cells rolls over to the other side on hitting the edge, or 1 for a finite grid topology

Note that you have to change the ; in the classpath to : depending upon whether you run the command in Linux or Windows or Cygwin.

To create a cell, type:

java -cp "lib/java-getopt-1.0.13.jar;build" assg.funnycells.cells.FunnyCell -c [config file] -x [x-coord] -y [y-coord] -t [type] -i [cell-id] -l [log level]

-c [config file]: The configuration file, default being funnycells.conf present in the current directors
-x [x-coord]: The x coordinate at which to create the cell. The top left corner is (0, 0), and the size of the map is defined in funnycells.conf
-y [y-coord]: The y coordinate at which to create the cell
-t [type]: This can be 0 (susceptible cell), 1 (infectious cell), 2 (antibody cell), or 3 (energy cell)
-i [cell-id]: Any string for a cell-id. Each cell has to have a unique id
-l [log-level]: 0 (no logging), 1 (info), or 2 (debug)

Alternatively, to create a whole series of cells randomly launched in different squares:

perl randomlaunch.pl [map width] [map height] [energy cells] [infected cells] [antibody cells] [susceptible cells]

[map width]: The width of the map, should be the same as that defined in funnycells.conf
[map height]: The vertical length of the map
[energy cells]: The number of energy cells. They are placed at random locations
[infected cells]: The number of infected cells to start with. Placed randomly
[antibody cells]: The number of antibody cells to start with
[susceptible cells]: The number of susceptible cells

Similarly, to create a lot of cells with the susceptible cells organized in clusters:

perl clusterlaunch.pl [map width] [map height] [energy cells] [infected cells] [antibody cells] [susceptible cells] [probability of joining cluster]

Here, [probability of joining clusters] indicates the probability by which a new susceptible cell will be created in a random location, or next to another susceptible cell. A higher probability will result in a few large clusters, while a smaller probability will result in a lot of small clusters

The maps in the figures above were generated in the scenario randomlaunch.pl 30 30 0 15 15 40, that is on a 30x30 map with no energy reservoirs, 15 infected and antibody cells each, and 40 susceptible cells.

funnycells.conf

The configuration file is divided into different sections with the following parameters.

server: Entries for the IP address and port of the server
[server]
ip = 127.0.0.1
port = 8080
map: Entries for the height and width of the map, and the number of energy cells
[map]
height = 30
width = 30
numenergy = 10
classes: Classes for susceptible and energy cells will be supplied, and students will have to implement their own classes for infected and antibody cells. More on how to implement these classes in described later.
[classes]
energycell = assg.funnycells.cells.EnergyCellImpl
susceptiblecell = assg.funnycells.cells.SusceptibleCellImpl
infectedcell = assg.funnycells.cells.InfectedCellImpl
antibodycell = assg.funnycells.cells.AntibodyCellImpl
newinfectedcell = assg.funnycells.cells.InfectedCellImpl
newantibodycell = assg.funnycells.cells.AntibodyCellImpl

Here, the [infectedcell] class is instantiated for infected cells, and the [newinfectedcell] class is instantiated in place of a susceptible of antibody cell which gets infected. Since in the example shown above, both [newinfectedcell] and [infectedcell] are the same, therefore the same class is instantiated in both cases. But different classes can instead be used to simulate interesting effects and distinguish between newly infected cells and the originally infectious cells. For example, if the [newinfectedcell] field is left blank, then newly infected cells actually disappear from the map and do not add to the population to infected cells.
receptors: Each molecule that is produced by the cells has to start with a start sequence, end with an end sequence, and has to have receptors for the cell that is meant to sense the molecule. Infected cells can only sense molecules containing the infected sequence, antibody cells can only sense molecules containing the antibody sequence, and any cell (including susceptible cells) can sense molecules containing the any sequence. Thus, a null molecule would be something like gggc-agcg-cccg, consisting of the start sequence, destined for an infected cell, and ending with a valid end sequence. Of course, even null molecules can be used to convey information such as heartbeat status messages!
[receptors]
start = gggc
stop = cccg
any = atat
infected = agcg
antibody = taca
affectors: Cells can define their own affectors, but the following are recognized by the server. Infection and immunisation affectors are used to convert other cells into infected or antibody cells. The presence affector is produced by susceptible cells to signal their presence, and can be sensed by infected and antibody cells that would want to convert it. The energy affector is produced by energy cells, and can be picked up by any cell to gain energy. The pheromone affector is also recognized by the server as having a long lifetime, so that pheromone messages can persist in the network for longer times. Thus, an infection molecule targeted at any cell in the region would be gggc-atat-atga-cccg, composed of the start and end sequences, the any destination, and the infection sequence. Note that infections or immunization molecules affect cells in adjacent squares as well. So, if you dump an infection molecule in (x,y) and another one in (x+1,y+1), they can together cause infections in any of (x,y), (x+1,y), (x,y+1), and (x+1,y+1) squares.
[affectors]
infection = atga
immunisation = gata
presence = attt
energy = gaag
pheromone = ttta
params: A number of control parameters are provided to run the simulation.
[params]
senseradius = 1: Radius around a cell in which it can sense for molecules. Default of 1 means that the cell can only sense in the rectangle surrounding it.
moltimeout = 100: The time in milliseconds for a molecule of length 1 to expire. Thus, the null molecule mentioned above will expire in 12 times moltimeout duration.
ratetimeout = 5: The maximum rate at which a cell can move is ratetimeout times moltimeout.
droptimeout = 20: The maximum rate which a cell can produce infection or immunisation molecules is droptimeout times moltimeout.
pheromonetimeout = 500: The lifetime of a pheromone molecule is pheromonetimeout times moltimeout.
molenergy = 100: The energy consumed to produce a molecule consisting of only a single letter. Thus, the null molecule explained above will require 12 times molenergy energy
movenergy = 1000: The energy consumed to move one coordinate up or down or left or right or diagonally.
senseenergy = 200: The energy required to sense one molecule.
transferenergy = 10000: The energy supplied by one energy cell.
infectionenergy = 4000: The energy required to produce an infection molecule.
immunisationenergy = 4000: The energy required to produce an immunisation molecule.
maxenergy = 500000: The maximum energy a cell can store, and the energy it starts with.
quorumsize = 2: The quorum size necessary to launch a successful attack or immunisation.
dieprobability = 0.001: The probability for a random cell to die. To disable deaths, either uncomment or set it to a negative value.
colors: color is a misnomer here! Up to three molecules can be listed to be marked in the cellular map on the server. For example, a pheromone molecule for infected nodes starts with gggc-agcg-ttta, and whenever anybody produces this molecule, this will be show on the map marked with an 'i'.
[colors]
gggcagcgttta = i: For infected pheromones
gggctacattta = a: For antibody pheromones
gggcatatgaag = e: For energy cells
display: Defines the window size in pixels for the graphic shown on the server.
[display]
dispheight = 700
dispwidth = 700

Writing your own infectious and antibody cells

You will have to implement the InfectedCellImpl and AntibodyCellImpl classes specified in funnycells.conf. The interface that you are provided is very simple. A dummy class will look as follows:

public class InfectedCellImpl implements CellularProcesses {

public SusceptibleCellImpl(Integer type, Integer energy, String cellId, RateLimBufferedReader in, RateLimPrintWriter out) {
}

public void startCell() {
}

}

The constructor is called with the type of cell (0, 1, 2), the energy you start with, the Id assigned to the cell, and java.io.BufferedReader and java.io.PrintWriter instances for reading and writing messages to communicate with the server. You are only allowed to use the in.readLine() and out.println() methods to receive and send data since these methods have been overridden to limit the rate at which cells can send messages. This is to protect the server from faulty cell implementations that may run into infinite loops because of bugs and cause too many writes on the socket, potentially bringing down the server.

If your cell gets taken over by an opponent, it will be destroyed and a new cell with the same cell-id will be created in its place. Note that this will be an instance of the class supplied by your opponent.

You can then communicate with the server through the following messages, by writing and reading from the PrintWriter and BufferedReader objects:

Move
MOVECELL
incx=[x-offset]
incy=[y-offset]
\n

Note that you do not know your location! You can only move one cell up or down or left or right or diagonally. Therefore, x-offset and y-offset can be {-1, 0, 1}. The server will respond with one of the following messages:

OK
MOVECELL
type=[type]
energy=[energy]
\n

... for a successful move. Your remaining energy will be reported back.

WALL
Illegal move
\n

... if you hit a wall.
ERROR
Not enough energy to move
\n

... if you run out of energy
ERROR
Bad arguments in cell move
\n

... if you sent illegal x and y movement offsets
ERROR
Malformed MOVECELL message
\n

... if you sent a bad message
Drop molecule
DROPCHEM
[molecule string]
offx=[x-offset]
offy=[y-offset]
color=[character]
\n

Here, x-offset and y-offset can be {-1, 0, 1} to drop the molecule at the assigned location. You can also convey a character that the server will display on the network map graphically, but you can do this for at most three colors. Please refer to the funnycells.conf description earlier to read more about this. The server will then respond with one of the following messages:

OK
DROPCHEM
type=[type]
energy=[energy]
\n

... for a successful drop.
ERROR
Malformed chemical
\n

... if your molecule did not have the appropriate start, drop, and one of {infected, antibody, any} receptors. Please refer to the funnycells.conf explanation earlier.
ERROR
Rapid infection or antibody drop
\n

... if you tried to produce infections or immunisations too fast.
ERROR
Not enough energy to produce chemical
\n

... if you run out of energy
ERROR
Bad arguments in drop chemical
\n

... if you sent illegal x and y movement offsets
ERROR
Malformed DROPCHEM message
\n

... if you sent a bad message
Sense molecules
This has two versions: directional and direction-less sensing. With directional sensing, you can specify the x- and y-offsets in which you want to sense. Direction-less sensing checks the entire neigborhood though. The direction-less command is as follows:
SENSECHEM
[molecule prefix]
max=[maximum to sense]
\n

You can specify the molecuar prefix for which you want to sense, and the maximum number of molecules that you want to sense for. Remember that if a match is found, the information will be conveyed to you and the molecule will be removed. Sensing consumes molecules it senses for.

The directional sensing command is as follows:
SENSECHEM
[molecule prefix]
max=[maximum to sense]
offx=[x-offset]
offy=[y-offset]
\n

The replies are the same for both versions, and will be one of the following messages:

OK
CHEMICALS=[number of matching molecules]
[molecule string 1]
offx=[x-offset]
offy=[y-offset]
[molecule string 2]
offx=[x-offset]
offy=[y-offset]
...
...
type=[type]
energy=[energy]
\n

... for a successful sense request. The server returns the number of matching molecules (< max), and details about each molecule including the molecule string, and its x and y offsets. The last two lines report back the remaining energy of the cell, and the type of the cell.
ERROR
Illegal receptor request
\n

... if your prefix match for molecules did not have the appropriate start and one of {infected, antibody, any} receptors that you can use. Remember that antibodies can only sense for molecules marked as antibody or any. Please refer to the funnycells.conf explanation earlier.
ERROR
Not enough energy to sense chemicals
\n

... if you run out of energy
ERROR
Sensing out of bounds
\n

... if you try to do directional sensing outside the grid
ERROR
Bad arguments in sense chemical
\n

... if you sent an illegal max request
ERROR
Malformed SENSECHEM message
\n

... if you sent a bad message

Strategy hints

Let your imagination run wild! There are many ways you can use to improve your performance. For a start, to capture cells you can do a leader election when some cells meet, and the leader can then lead its "army". This is what I do. You will have to think of request-response protocols for leader election, timeouts on when to leave a leader and go searching on your own, and extensive state management to work in cooperation with cells that may be in a completely different state at that time.

You can also use pheromone trails to indicate the path to susceptible cells so that your small armies of cells do not wander randomly in search of prey. Alternatively, you can establish a gradient to guide cells to the highest density of pheromones. You may even want to eat up your opponents pheromones for that matter! Try reading up on topics such as ant colonies and swarm intelligence for more ideas.

But remember that all these nice tricks come at the cost of energy and time. Your cells may need to replenish their energy periodically, but energy is available at only a few locations in the map. Think about how you can search for energy efficiently, or maybe even designate some cells as explicit energy transfer agents. You can get some ideas by reading up stuff on molecular biology -- how proteins are synthesized and energy is transfered across cells.

As you go along, you will also notice that some strateies will work well with certain density of cells, ratio to susceptible cells, and various other parameters. Think how you can make your algorithms dynamic enough to infer the environment and operate accordingly.

Assignments for Fall 2010

Count the number of susceptible cells in the network. Different cells should count susceptible cells in mutually exclusive parts of the map, and then sum their results. Cells can also die though, before they report their results! [Assignment 1]
Form groups, explore the network, and infect all susceptible cells. Contrast between search strategies for exploring a random layout of susceptible cells on the map, Vs a clustered layout. The difference this time is that you have a toroid topology. [Assignment 2]
Funny Cup round 2! [Assignment 3]

You must document your design choices, protocol, and architecture carefully. Marks will also be assigned based on your code quality, the neatness of your protocol, and the robustness of your state management methods.

Assignments for Winter 2010

We will build this step by step:

Start with being able to send instructions to the server to move. Your cells should be able to move vertically, horizontally, or diagonally, and reflect off walls. [Assignment 1]
Sense and find susceptible cells in the network. How many cells were you able to discover? [Assignment 2]
Form groups, explore the network, and infect all susceptible cells. Contrast between search strategies for exploring a random layout of susceptible cells on the map, Vs a clustered layout.[Assignment 3]
The Funny Cup begins! Develop strategies for your team and win! Do things like pheromones, swarms, molecule capture, and other interesting operations seen in cells and swarms. [Assignment 4]

Future enhancements

We may implement a diffusion process in the substrate at some point. Diffusion can serve as a mechanism for information transfer, for example, to create pheromone gradients, or to modulate the information on the amount and frequency of molecular production that diffuses to other parts of the substrate.