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:

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.

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:

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

  1. 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]

  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. The difference this time is that you have a toroid topology. [Assignment 2]

  3. 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:
  1. 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]

  2. Sense and find susceptible cells in the network. How many cells were you able to discover? [Assignment 2]

  3. 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]

  4. 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.

References