E-Coli, A Game Of Life?

By
Peter Asenov Ruevski
E-mail:ruevs@drexel.edu
Drexel University
College of Engineering
Department of Electrical and Computer Engineering

ECE-C 501 "Principles of Computer Engineering"

Abstract

The problem of finding an optimal survival behavior for E-coli bacteria.

  1. Definition of the problem

The E-coli cell is put in a container full of water and somewhere in the container there is a piece of sugar. The dissolving sugar creates a potential "field" of sugar concentration around it. The goal of the e-coli cell is by "orienting" itself by the field and using it's limited propulsion abilities to reach the sugar as fast as possible.

The cell can be viewed as an autonomous robot. The robot and its environment can be represented by means of the <whatever-you-call-the-A-W-S-SP-WM-BG-system> model.

Figure .1

A description of the different parts of this model for the e-coli case follows.

    1. Actuators

The e-coli cell has rather rudimentary and stochastic propulsion system. It can execute only two actions:

    1. World
    2. The world is defined by the potential field created by the dissolving sugar. The sugar is presumed to be a point source. For simplicity I'll accept also that the intensity of the field decreases linearly with distance i.e.

      Equation .1

      Where:

      R - Current distance from the sugar (the origin)

      I0 - Intensity at the origin (the sugar). I presume that it's constant and is known (by the cell)

      IR - Intensity at the current distance. Intensity in effect is the concentration of the sugar solution.

      Figure .1 - A plot of the field around the sugar (I0=1)

      The e-coli cell is defined by its length H and one end is denoted Head and the other Tail. When the cell "jumps" it jumps in the direction of its head.

      The position of the cell in the world is specified in polar coordinates.

      R - Distance of the center of the cell from the origin (length of the cell vector)

      g - Positive angle between the vector of the cell and the positive direction of the X axis

      a - Orientation of the cell - the angle between the vector defining the cell's position (R, g ) and the heading of the cell (i.e. the direction tail->head) (a Î [-180,180], a =0 ó facing sugar)

      Figure 1.2.2 shows the e-coli cell and the sugar and all the parameters that were mentioned above.

      Figure .2 - The "world"

    3. Sensors
    4. The e-coli cell has only one very simple sensor. It can measure the difference between the sugar concentration at its head and it's tail D I. from Figure 1.2.2 it is a matter of simple trigonometry to find an expression for D I.

      Equation .1

      Equation .2

      Equation .3

      therefore

       

      Equation .4

      Equation 1.3.4 expresses the "reading" of the difference sensor as a function of the current distance to the goal R and the orientation of the cell a . The next figure is a 3D plot of D I against the distance R and the orientation a . The length of the cell H and I0 are assigned 1.

      Figure .1 - D I plotted against the distance R and the angle a

    5. Sensory processing
    6. Since the ultimate goal of the robot/cell is reaching the sugar it would be good if the sensory processing system can calculate the distance to the sugar R. But if we look at Equation 1.3.4 we see that there are two unknown variables in it, the distance R and the heading a . If we could perform a jump with a known length and measure D I before and after the jump then it is possible to calculate R and a . But the cell can only make jumps with a random length!

      Calculating a is also extremely important because it is much easier to discuss the problem in terms of Alpha instead in terms of D I. Yet for the same reasons as with R we can not calculate a .

      Further analysis of this problem is directly connected with the world model and behavior generation systems and will be discussed in the next parts. The important thing to point out is that our sensory system is extremely "crippled" and complicates the problem, much more than the "stochastic" propulsion system.

    7. The world model
    8. An ideal world model would consist of the current coordinates of the cell (g and R) and it's heading a . Yet g is not relevant to the problem because it does not matter at all from which direction we will approach the sugar. On the other hand the other two parameters a and R are critical for the system to work. But unfortunately they can not be easily calculated from the sensory input we get. For this reason later I will discuss the problem with two situations in mind. One in which we only have the sensor described in 1.3 giving us D I and one in which we can measure R and a . I consider the later to be interesting because it is easier to analyze analytically and also permits to develop some nice learning algorithms. It also provides some clues as to how the original problem should be addressed.

      A world model that relies only on D I can be an array of a certain number of previous states (i.e. values of D I) and the actions that were taken to go from each state to the next (i.e. a rotation or a translation at each step).

    9. Behavior generation (BG)

The function of the BG subsystem is to decide at each step whether the cell should rotate or jump and feed the appropriate command to the actuators. It can be said that on each step the BG module should generate one bit of information:

0 - rotate

1 - jump

This is the most interesting part of the system and it is the one that can be implemented in different ways, giving the e-coli's different levels of intelligence and respectively different ability (probability) to come to the sugar in first (minimum time).

It is interesting that there is some probability, that even a cell with a totally stochastic behavior (i.e. the decision jump/rotate is random) can outperform a very "shrewd" cell using highly sophisticated decision making algorithm. Of coerce such a probability is very low.

The consideration of the BG algorithm will heavily depend on whether we use the "ideal" world model containing a and R at each step or the realistic one. In the next parts a number of different algorithms are discussed having different "intelligence" and learning abilities and built over the two different world models.

  1. Behavior generation using the {a , R} world model
  2. First I want to discuss the mathematical side of the problem. As we can see from Equation 1.3.4 in order to calculate a we need R and vice versa. R can be found if we had one additional sensor located in the geometrical center of the body of the cell that measures the absolute value of the sugar concentration IR. In this case given that I0 is known from Equation 1.2.1 follows:

    Equation .1

    Now we can substitute the expression for R in Equation 1.3.4 and after some (quite tedious) transformations it is possible to find an expression for a . I tried to use Maple to do this but the resulting equation is so clumsy that I would not even include it here. So from this point on I will accept that there is some "sensible" method of measuring a .

    The BG function should be a threshold function that compares a with a particular threshold value T and generates a jump if |a |<T and a rotation otherwise (a Î [-180,180],a =0ó facing sugar). This BG algorithm will be used in all cases except for the "dumb" ones 2.1 and Error! Reference source not found.. It looks like this:

    void BG(float T, float Alpha)
    {
    if (abs(Alpha)<T)
    then
    <JUMP>
    else
    <ROTATE>;
    <Calculate new Alpha and R>;
    }

    It is responsibility of the world model to provide a threshold value to the BG module at each step. The choice of this value is the only factor (apart from chance) that determines the "survivability" of the cell. Some definitions:

    Intelligence - I will use it as a synonym of the E-coli’s knowledge of how to dynamically change the threshold within one "race" to the sugar.

    Learning - in this case will be the "evolution" of the knowledge based on experience gathered through previous races.

    Memory – I do not intend to give a definition of memory. The important thing is that memory is absolutely necessary in order to have intelligence and/or learning or even a fixed behavior that provides any chance of survival.

    1. E-coli without memory (hence no "intelligence" and no learning)
    2. In this case we do not even need the world model, sensors and sensory processing, because we can not use them. We just have a BG module that generates a random sequence of jumps/turns. Such a "brainless" creature would not survive in any environment different from saturated sugar solution anywayJ

      In the rest of the cases we presume that there is memory available…as much as we need…

    3. E-coli with memory, but without learning and "intelligence"
    4. This is the case of fixed behavior that I mentioned earlier. The idea is that the world model contains a (genetically) fixed threshold which is used by the BG module. The particular value of the threshold will determine how successfully the cell will perform. I think (have not proven it) that there is an optimal threshold value for this case. A cell with (good) learning algorithm should eventually end up with the optimal threshold value (see 2.3).

      Next I will give some considerations about what the optimal threshold may be. First a threshold of 90° (which is D I>0) might not even give a solution, because using it the cell may actually go away from the sugar (see Figure 2.2.1). I would not try to prove this.

      Figure .1

      If on the other we want the cell to approach the sugar every time it jumps we should have R2£ R1. If the length of the jump J is the maximum possible Jmax and R2=R1 then we have

      Equation .1

      If the threshold is 60° the cell will constantly approach the sugar until it gets within a distance Jmax at which point it will start "wandering" around it in a circle of radius Jmax. I think this is the minimal "good survival behavior".

      If we take a simple assumption (not a very good one I admit) a better value of the threshold can be calculated. The assumption is that the cell is far from the sugar, i.e. R>>Jmax. In that case with each jump the cell approaches the sugar approximately by cos(a ) (see the picture).

      Figure .2

      If the threshold is T and the initial distance to the sugar is R0 then in the worst case we will reach the sugar in Nj=R0/cos(T) jumps. The total number of moves is N=Nj+Nr. On the other hand the probability of a jump is Pj=2T/360 therefore Nj=2NT/360. So we get:

      or

      Equation .2

      Equation .3

      We want to minimize N, which is to maximize the denominator of Equation 2.2.3. So we find its first derivative and make it equal zero cos(T)-Tsin(T)=0 ó cotan(T)=T and from here

      T» 49.29348360°

      The problem is that the assumption that we made is not very good when the E-coli starts approaching the sugar. I suspect that the exact solution is 45° which is pure abduction since I cannot prove it. A working simulation for the next case should show whether I am right or not.

      The algorithm for this case looks like this:

      float T=<CHOSEN CONSTANT>, R, Alpha;
      ………
      <initialize R, Alpha>;
      do
      BG(T, Alpha);
      while (R>Jmax); //until sugar reached

    5. E-coli with learning, but without "intelligence"
    6. The idea is to make many trials (to the sugar) with different thresholds and choose the best one by comparing the memorized costs. In order to minimize the error that may be introduced by the random propulsion system we should make many tests with each threshold and find the mean cost.

      A practical implementation of the last idea wold be to start with some threshold T0 – sixty degrees (see 2.2) may be a good starting point – and perform a kind of a binary search, memorizing only the best threshold we have found so far and the corresponding cost. The search need not end in a certain point, it may go on for the cells whole life.

      Here is the algorithm (some pseudo C code):

      int OptCost=FFFFFFFh; //max integer

      int Step=Topt/2; //searching step 30 degrees initially
      int CurrCost, CurrMeanCost;
      float T, R, Alpha;
      float Topt=60;
      int I;

      ………
      <initialize R=cost, Alpha>;
      do
      T=Topt-Step; //try decreasing the treshold
      CurrCost=0;
      CurrMeanCost=0
      for(I=0;I<1000;I++){
      do
      BG(T, Alpha);
      CurrCost++;
      while (R>Jmax); //go to the sugar
      CurrMeanCost=CurrMeanCost+CurrCost;
      }
      if (CurrMeanCost<OptCost) then {
      OptCost=CurrMeanCost;
      Topt=T
      }
      else {
      T=Topt+Step; //try increasing the treshold
      CurrCost=0;
      CurrMeanCost=0
      for(I=0;I<1000;I++){
      do
      BG(T, Alpha);
      CurrCost++;
      while (R>Jmax); //go to the sugar
      CurrMeanCost=CurrMeanCost+CurrCost;
      }
      if (CurrMeanCost<OptCost) then {
      OptCost=CurrMeanCost;
      Topt=T
      }
      }
      Step=Step/2; //Decrease the step
      while (alive);

      After the algorithm runs for some time the Step will become very small and Topt should converge to its optimal value. This algorithm can be viewed as a numerical solution for the problem that was solved with some simplifying assumptions in point 2.2.

      It is important to note that there is a hidden assumption that the turn and the jump have the same cost. We may of course say that the cost of the jump is for example K times the cost of the turn. The value of K will influence the optimal threshold. We may still accept that all the turns have the same cost and all the jumps have the same cost (i.e. the cost does not depend on the random factor) for the similar reason as in the footnote from page *. In the extreme case when K is infinite (or the cost of the turn is zero) the optimal threshold approaches 0

       

    7. E-coli with "intelligence", but without learning
    8. Choosing a single threshold angle may give good results, but I think that changing the threshold dynamically depending on the distance to the sugar R can give even better results. The problem is finding the appropriate relationship between R and T.

      An obvious solution is for each R to choose the maximum value of the threshold Tmax that will guarantee that after a jump we will be closer to the sugar. this is equivalent to Equation 2.2.1.

      Equation .1

      But later in point 2.2 I have showed that for R>>Jmax the optimal angle is 49.21 degrees, while for this case Tmax is 90 degrees. Since I have taken the worst case, I think that probably the optimal angle may be Topt.=Tmax/2. F R® ¥ , Tmax=90° , Topt.=45° . The graph Equation 2.4.1 is shown next.

      Figure .1 – Determining the threshold value as a function of the distance R

      The algorithm for this case looks like this:

      float T, R, Alpha;
      ………
      <initialize R, Alpha>;
      do
      T:=arccos(Jmax/(2*R)/2;
      BG(T, Alpha);
      while (R>Jmax); //until sugar reached

      Of course I may be wrong about the Topt.=Tmax/2. Bun I think that there should be some constant P so that Topt.=Tmax/P would be the optimal solution. A learning algorithm as described in the next part can determine this constant.

    9. E-coli with "intelligence" and learning

    The learning algorithm is in fact the same as in part 2.3 but this time instead of the threshold value we are searching for am optimal value of P. The oly difference would be in the two lines calculating T. A good initial value for P would be 2.

    int OptCost=FFFFFFFh; //max integer

    int Step=Popt/2; //searching step 30 degrees initially
    int CurrCost, CurrMeanCost;
    float P, T, R, Alpha;
    float Popt=2;
    int I;

    ………
    <initialize R=cost, Alpha>;
    do
    T:=arccos(Jmax/(2*R)/(P-Step);
    CurrCost=0;
    CurrMeanCost=0
    for(I=0;I<1000;I++){
    do
    BG(T, Alpha);
    CurrCost++;
    while (R>Jmax); //go to the sugar
    CurrMeanCost=CurrMeanCost+CurrCost;
    }
    if (CurrMeanCost<OptCost) then {
    OptCost=CurrMeanCost;
    Popt=P
    }
    else {
    T:=arccos(Jmax/(2*R)/(P+Step);
    CurrCost=0;
    CurrMeanCost=0
    for(I=0;I<1000;I++){
    do
    BG(T, Alpha);
    CurrCost++;
    while (R>Jmax); //go to the sugar
    CurrMeanCost=CurrMeanCost+CurrCost;
    }
    if (CurrMeanCost<OptCost) then {
    OptCost=CurrMeanCost;
    Popt=P
    }
    }
    Step=Step/2; //Decrease the step
    while (alive);

    Again this algorithm is supposed to converge to an optimal value of P.

    I think that this world model is the best I was able to think of in the case when R and a are measurable.

    In the next section I will try to explore the much more complicated case when we can only measure D I. I am not sure whether an algorithm exist for this case that will perform as good as the one just described.

  3. Behavior generation using the "realistic" world model
  4. In this section I will not pay attention to the simple cases without memory and without learning. They are trivial and do not differ from what was described in sections 2.1 and 2.2.

    1. E-coli with memory and learning, but without "intelligence"
    2. This case is quite similar to the case described in part 2.3 the only difference is that we are searching for an optimal threshold value of D I instead of a . This does not change the algorithm at all so I would not repeat it here. It is important to note that since D I depends on the distance there may be different optimal values for reaching the goal starting from different initial distances.

    3. E-coli with memory and "intelligence", but without learning
    4. The problem how to change the threshold difference while moving towards the sugar is complicated by the fact that D I depends both on the distance and the angle. In this case a threshold that gets the cell closer to the sugar after a jump at a longer distance may in fact lead the cell away if used at a closer distance. Even though I can not say what the algorithm for changing the threshold should be there are several important properties that it should have. First it should keep history of the biggest positive value of D I, which will increase as the sugar is getting closer. The threshold value should be chosen depending on this maximum value. In the beginning of the algorithm the cell should execute a number of turns in order to "orient" itself in the world (i.e. to find some initial maximum value from which to calculate the threshold value). Keeping the maximum value close to the reality (i.e. to the real maximum value for the particular distance R when a =0) is important so it may be good to introduce some overhead of turning (Z times for example) after each X jumps, which will help keep the maximum precise. The threshold can be calculated as D Imax/Y. Probably a good value of Y is 2 (just like in section 2.4). I have no idea whatsoever about the optimal values of X and Y, but they can be found by…

    5. E-coli with memory, "intelligence" and learning

A learning algorithm for the real life situation will have to find (using multiple trials) the optimal values of X, Y and Z. While the idea of such an algorithm is not different from the one described in section 2.5 the task is much heavier. Unlike the one from section 2.5 this one has to do a search in a space with three degrees of freedom, which greatly increases the set of possible solutions and therefore the complexity.

  • Using evolutionary algorithm to achieve learning in the E-Coli.
  • Apart from the algorithms described in sections 2.3, 2.5, 3.1 and 3.3 a totally different approach can be used to achieve learning. En evolutionary process can be simulated.

    We "put" a big number of cells, with different initial values of the parameter we want optimized in the sugar container. All cells are given an equal initial amount of energy reserve, which they can use to move. Each move consumes a unit of energy. All cells start at the same initial distance from the sugar. If a cell consumes its energy before reaching the sugar it dies. If however a cell reaches the sugar it splits in two new cells that are given a full load of energy and are put at the initial distance to start over their race to the sugar. If this is run for a while and the conditions (initial energy, initial distance) are chosen correctly (experimentally) only the best cells will survive the natural selection. These cells should have the optimal value of the parameters.

    A slightly different approach (and a better one) can be also used. Instead of generating a large number of initial species (which would be needed in order to have value close to the optimal in the initial generation) diversity can be introduced by mutation. Each time a cell splits its "genes" (holding the values being optimize) can be changed a small random value. This way, starting with a comparatively small initial variety and population size, a large variety of species can emerge. I such a "game of life" well-adapted organisms will eventually evolve and prevail.

    There are numerous works available on genetic/evolutionary algorithms. An overwhelming amount of information on the subject can be easily found on the WEB.

    And let thou E-Coli reach the sugar!