Re: Swarm: Asynchoronous schedules

[John W. Fondon III (Trey)]

This problem is very similar to a problem faced by molecular dynamics
modelers who try model very large systems with density dependent behaviors.
For example, when an atom is not close to any other atoms (i.e. low density)
then its trajectory can be fairly accurately described by Newtonian
mechanics and timesteps can be large, but if, as a result of too large a
time step, atoms get too close together (i.e. less than vdw radii apart)
huge repulsive forces dominate the equation, giving atoms so much energy
that the system flies apart.  If time is slowed down to the point that this
does not occur, then inordinate computational resources are consumed (mostly
wasted).  As with most hard problems in biology, we would be wise to see
what physicists can do and have done for us.


John W. Fondon III (Trey)
UT Southwestern Medical Center
Dallas, Texas
address@hidden
address@hidden
address@hidden
-----Original Message-----
From: Chimera <address@hidden>
To: Michael Whidden <address@hidden>; address@hidden
<address@hidden>
Date: Monday, August 03, 1998 6:54 PM
Subject: Re: Swarm: Asynchoronous schedules


>
>
>Michael Whidden wrote:
>
>> Hi there.  Sorry to bug you, but you seem to be a fellow with some
>> idea of what you are doing, so I was wondering if you wouldn't mind
>> briefly explaining to me what you mean by synchronous vs. asynchronous
>> schedules in swarm.  I am familiar with the term, but curious as to
>> how to construct the behavior.
>>
>> Thanks,
>>
>> -Mike
>
> The following is just my understanding of a very complex question.  I am
>posting this to swarm-modeling because we don't get much there.  I wrote
>this quickly, comments and responses are welcome.
>
>Hi Mike,
>
>   Take a very simple situation of say, a single type of agent who has a
>very boring life.  It simply reproduces until it dies.  There are two
>events that can happen to that agent "giveBirth" and "die".
>Now, there is nothing that happens to this agent in between these events,
>so we can take advantage of it.  Say the average birth rate is 5 and the
>average death rate is 0.1.  So, on average, 5 new individuals are created
>every day and, on average, an individual lives 10 days.  We can predict
>the time to the next events in an individuals life using the inverse of
>the rate and some appropriate random distribution.  A favorite
>distribution is exponential, so I'll use that in my example.
>
>timeToBirth=(1/5)*(-log(U[0,1])
>
>This just says make a draw from a uniforn random distribution between 0
>and 1.  Take the negative log of it and multiply it by the inverse of the
>of the birth rate.  Here is one of my Swarm calculations.
>
>   deathEvent.time=-log([myGenerator getDoubleSample])/deathRate;
>
>Now, we can also calculate the time to next birth in the same manner.
>
>Last
>
>   [myAsynchronousSchedule at: deathEventTime createActionTo: self
>message: M(die)];
>   [myAsynchronousSchedule at: birthEventTime createActionTo: self
>message: M(giveBirth)];
>
>myAsynchronousSchedule should have autoDrop set to 1;
>
>Within "giveBirth" a new individual is created, and then each is given a
>new "time to birth" and each of them are added to the schedule.  Within
>"die", if there is an impending birth event, it is removed from the
>schedule, and the agent is dropped.
>
>   if( birthEvent.eventId != nil )
>   {
>      nullEvent=[eventSchedule remove: birthEvent.eventId];
>      [nullEvent drop];
>   }
>   [self drop];
>
>Note that I created a structure to keep track of the various bits of the
>scheduled events.
>
>The real question is, why use this type of schedule.  Synchronous
>schedules bave a basic problem in that multiple events happen within a
>time step.  At a minimum, these should be ordered in a purly random
>sequence.  If that is not done, the execution sequence can strongly effect
>
>the outcome of the simulation.  For instance, in a simple predator/prey
>system, schedule predation before or after birth has a very different
>result.  The two ways to do this are either have such a small time step
>that only one thing can happen per time step.  Or, have a schedule that
>compleatly randomizes the order of the events.
>
>A very small time step has the problem that if there are few individuals,
>you end up executing lots of time steps with nothing in them.  (The time
>step must be small enough to handle the density of events at high numbers
>of agents.)  The difficulties of randomizing within a time step,
>especially if things are spatially distributed with movement, are self
>evident,
>
>The asynchronous discrete event simulation gets around the time step size
>issue because if there are few individuals there are few events scheduled
>and so the schedule just jumps over the unused time.  The ordering problem
>
>is taken care of by default.
>
>There are two problems with this type of simulation:
>
>1.)  The "ordering problem" is solved because each event is scheduled on
>its own.  You need to have enough resolution in your time so that the
>probability of scheduling two events at an identical time is small.  Of
>course, the chance will never be zero.
>
>2.)  Density dependence:  This one can be a bugger!
>
>Scheduling times into the future assumes that they are density
>independent.  In other words, that they don't depend on the system state.
>If this is not valid, then a change in system state may invalidate a
>previously scheduled event.  For example, in the simplest predator prey
>senerio, the predator feeds on prey at a rate equal to a constant
>multiplied by the density (or total number) of prey.  If a predation event
>
>is scheduled, and the number of prey either increases or decreases, that
>event time may become invalid and need to be recalculated.  This may
>depend on the magnitude of the change.  1,000,000+1 is not significant
>whereas 10+1 is.
>
>Well, that's enough (or too much) to start with.
>
>Cheers,
>
>   D3
>
>--
>*********************************************************************
>* Doug Donalson                 Office: (805) 893-2962
>* Ecology, Evolution,           Home:   (805) 961-4447
>* and Marine Biology            email address@hidden
>* UC Santa Barbara
>* Santa Barbara Ca. 93106
>*********************************************************************
>*
>*   The most exciting phrase to hear in science, the one that
>*   heralds new discoveries, is not "EUREKA" (I have found it) but
>*   "That's funny ...?"
>*
>*       Isaac Asimov
>*
>*********************************************************************
>
>
>
>
>                  ==================================
>   Swarm-Modelling is for discussion of Simulation and Modelling techniques
>   esp. using Swarm.  For list administration needs (esp. [un]subscribing),
>   please send a message to <address@hidden> with "help" in the
>   body of the message.
>                  ==================================



                  ==================================
   Swarm-Modelling is for discussion of Simulation and Modelling techniques
   esp. using Swarm.  For list administration needs (esp. [un]subscribing),
   please send a message to <address@hidden> with "help" in the
   body of the message.
                  ==================================