Re: Swarm: Asynchoronous schedules

[Chimera]

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