Basic Blob Movement

Advisor:

Frédéric Gruau [LRI], Philippe Reitz (co-advisor) [LIRMM/INFO/DOC]

Laboratory:

LIRMM

Subject:

This subject is part of the Blob Computing project. We have selected a coherent, self contained task, appropriate for a master thesis.

We consider the problem of establishing membrane-like object called "blob" in a cellular automata modeling physical space. In particular, cellular automata states can be partitioned into empty, particle, and wall types. The following animation shows a blob's division :

A blob is a spatially extended object distributed over many cells. It is composed of a sequence of adjacent wall-cell forming a circular wall enclosing a set of n particles, plus a variable number of empty cells. Each particle has a unit mass, and a discrete bounded velocity. The density d is the proportion of particle versus empty cell within a blob. The blob quantity of movement p is the sum of all its n particles speed vectors. The walls need not have a mass nor a speed, their function is to distinguish the outside from the inside of the blob.
We want to design rules that will make the particles and walls move locally from cell to neighbor cell over the cellular automaton and interact, so that :

1. the blob remains a blob (the wall remain circular, and particles do not escape)
2. the blob, as a whole, behaves like a membrane, i.e. an elastic physical object of weight n , volume n/d and quantity of movement p.

More precisely, the following requirements should be checked:

1. The blob center of gravity should move at a speed vector of p/n cells per time step
2. The blob density should have a lower bound .
3. The blob diameter D should remain proportional to the square root of n. In other words, the blob should maintain a round shape. To be precise (D*D) /n should be upper bounded. This will be ensured by controlling the blob perimeter, i.e. the wall length.
4. The quantity of movement p should remain constant. Furthermore, the two following criteria must be optimized to ensure good performance:
5. The number of bits required to store a cell state should be kept minimal
6. The transition function of the cellular automaton should need as little computations as possible

In general, these requirements are contradictory: For example not enough bits per state will over-deteriorate the precision of the computation. If we use only 2 bits to store four possible speed vectors, either the conservation of p or D or the blob uniform movement will be compromised. A good compromise should be found. Under any setting, due to the bounded speed of particle (they can move at most one cell per time step), the blob speed will also be bounded and only a fraction of possible physical systems can be successfully simulated. The region where simulation is valid should be identified.

Bibliography:

Blob Computing project