What I've learned about decentralized scheduling and floating point schedules

[Paul E Johnson]

This is really a note for Marcus D and Doug D, but I figure there may be
some people interested in decentralized scheduling that will join in a
discussion if I send it to the list.

Doug Donalson has mentioned several times in this list "floating point
schedules" and asynchronous scheduling and I've always been eager to
understand it more clearly.  He has shown me some code for his model
that uses floating point time and I think I understand it now.  Is this
correct?

Ordinarily, imagine a schedule that is empty at times 
0
1
2
3
etcetera.  Now we are just talking about the default kind of schedule,
with the default way of handling the insertion of actions.  If an agent
adds "anAction" at time 2, the Map which is the schedule adds one object
there:
0
1
2  "anAction"
3
Actually, more than that happens.  The Schedule creates a container
"action group" to hold this action and other actions that may be
inserted at time 2.  So after that is created, then the second action
"anAction2" can be scheduled at that time, meaning it is simply inserted
into the collection, and we have something like this:
0
1
2  {"anAction", "anAction2"}
3

By default the actions listed there are executed in order of insertion
when time 2 comes.

The bad thing about this is that, since the actions are executed in
order, then the agent behaviors can occur in a repetitive pattern that
can affect the simulation.  So what are the alternatives?

Now, we have the variant, which works in Swarm-2.1.4.2000-07-21 or
thereabouts, in which the treatment of actions scheduled at the same
time can be customized so that actions are randomized, not executed in
the default order.  When a swarm (or, as need may dictate, a schedule
within a swarm) is created with a customized setup for concurrent group
management, these actions will be randomized.  There are examples of
that approach in the "pjrepeater4-5-6" code in
http://lark.cc.ukans.edu/~pauljohn/SwarmFaq/WorkingExampleCode/objc. 
I've verified that these do indeed give the randomized actions at each
time step.

This randomization works because of this magical setup:

    groupProto = [ConcurrentGroup customizeBegin: self];
    [groupProto setDefaultOrder: Randomized];
    groupProto = [groupProto customizeEnd];

    theSchedule = [Schedule createBegin: self];
    [theSchedule setConcurrentGroupType: groupProto];
    [theSchedule setAutoDrop: YES];
    theSchedule = [masterSchedule createEnd];

This works if you are only worried about randomizing actions in a
specific schedules. If you want to randomize all actions that merge into
the schedule of a Swarm, say from several sub swarms, then you've got to
create that Swarm and set its concurrent group type. These are in the
examples I refer to above.


Before this recent Swarm edition to which I refer, there was an
alternative way of dealing with the problem of "mixing up" the actions
that are inserted onto the schedule at a particular time.  This way, I
think, may run faster and, I think, has some clear intuition.I gather
from what Doug told me, that Roger B worked this out sometime between
the fifth and sixth days of creation. Here is the way I understand it
from Doug's information.

Suppose you want agents to be able to schedule themselves, but you don't
want their actions to happen in an identical lockstep sequence.  You
want the agent actions, as much as possible, to be executed without
reference to each other.  If agent 1 wants to go to the store, we don't
want it to wait for agent 2 every time they both decide to go.  Treat
time as a floating point variable, and suppose it is meaningful to say
that two agents are scheduling things to happen at times like 2.15  and
2.99.  Here is what happens.  Each agent first of all has to have a
"handle" on an action group that exists on the schedule at time 2. If
there is no action group there yet, then one has to be created and
returned.  That's what this method in the Schedule class does:

- (id <ActionGroup>)insertGroup: (timeval_t)tVal 

If the agent catches the return from that, ie with   

mySubSchedule=[theSchedule insertGroup: 2];

Then the agent can insert its action into the action group at a
particular point within that time period (2) by sending messages to
mySubSchedule.  That's where the fractional point comes in.  The part
after the decimal is used to hang actions into "mySubSchedule" at 
particular instants.

For example, an agent can say 

[mySubSchedule at: 15 createActionTo: self message: M(doWhatever)];

And the other agent can say

[mySubSchedule at: 99 createActionTo: self message: M(doWhatever)];

You may wonder why mySubSchedule even answers to a method like
at:createActionTo:message:, but the secret is right here in the way
"theSchedule" is created:

        concGroupType = [ConcurrentSchedule customizeBegin: [self getZone]];
        [concGroupType setAutoDrop: 1];
        concGroupType  = [concGroupType customizeEnd];

        theSchedule = [Schedule createBegin: [self getZone]];
        [theSchedule setAutoDrop: 1];
        [theSchedule setConcurrentGroupType: concGroupType];
        theSchedule = [theSchedule createEnd];

Because ConcurrentSchedule adopts the Schedule protocol, and
"theSchedule" uses that as its concurrent group type, then one can treat
"mySubSchedule" like a regular Swarm schedule.

Since the floating point numbers can be assigned at random, and with a
high amount of precision, there is almost no chance that any two actions
will be inserted at the same exact instant in the sub schedule.  If they
do, I think that this sub schedule will just treat the same-instant
actions according to whatever concurrent group scheme is in place for
the Swarm in which that schedule was created.  It will not automatically
use the customized concurrent schedule that "theSchedule" adopts.

If I understand this correctly, and somebody here tells me so, or
corrects me, I'll make a small example program to complete my
decentralized scheduling odyssey that is pjrepeater.

I hasten to add that I don't think scheduling alone makes a model truly
asynchronous, because there are other design aspects required to truly
achieve an asynchronous design.  Thinking along the lines of that
exchange between Huberman and Glance and May and Nowak, it is also
important to have the "system" digest the impact of each agent's action
and make that environmental information available to the other agents in
order to justify the title of an asynchronous model.

-- 
Paul E. Johnson                       email: address@hidden
Dept. of Political Science            http://lark.cc.ukans.edu/~pauljohn
University of Kansas                  Office: (785) 864-9086
Lawrence, Kansas 66045                FAX: (785) 864-5700

                  ==================================
   Swarm-Support is for discussion of the technical details of the day
   to day usage of Swarm.  For list administration needs (esp.
   [un]subscribing), please send a message to <address@hidden>
   with "help" in the body of the message.