Re: Scheduling

[Sven N. Thommesen]

At 08:19 AM 11/21/97 -0600, you wrote:
>>On Wed, 19 Nov 1997, Thai Dinh Nguyen wrote:
>>
>>> Dear fellow Swarm users:
>>>
>>> I need help on Swarm's schedule:
>>>
>>> 1.  In the application Heatbugs, what will happen if there are two bugs
>>> at (2,4) and (2,5) and both bugs pick out (2,3) as the next best spot to
>>> move to?  Will only one of the bug moves to this spot?  If so, will this
>>> be determined by which bug was first (or last) added to the bugList?
>>
>>>From the Heatbug.m file:
>>
>>  // Part of the heatbug simulation is that two bugs cannot be in the
>>  // same spot. The code to enforce that is done here: if the site we
>>  // want is occupied by another heatbug, move randomly. Note that
>>  // this code does not parallelize properly, it requires that each
>>  // bug be set a "step" method in sequence. This is a design flaw in
>>  // heatbugs: proper conflict resolution is difficult.
>>  // Also note we only look for 10 random spots - if we don't find an
>>  // unoccupied spot by then, assume it's too crowded and just don't move.
>>
>
>
>What is "the proper conflict resolution"?  Is there a way to do this sshort
>of resorting to spin glasses?
>
>Trey

I suppose 'proper' conflict resolution involves something like what we
economists do all the time: just *assume* that all bugs can read each
other's minds and hence know each other's intentions so you never have two
bugs moving to the same spot; or, *assume* the existence of that mythical
Walrasian auctioneer who magically coordinates things behind the scenes,
telling every bug where to go next! [This is where Swarm models of the
economy get very different from standard economic ones: in Swarm you have
to be able to program the code that tells each bug what to do, so making
those magical assumptions is not open to us ...]

Don't know about spin glasses, but current heatbugs/Grid2d code does this:
Grid2d only has a single pointer at each location to hold a pointer to a
bug, yet it is possible for two bugs to move themselves to the same
location. When the second one does, Grid2d 'forgets' the first one. (But of
course the bugs themselves know where they think they are.) As a result,
any code that accesses the bugs via the bug list in the model swarm will
find all the bugs, but code that scans the world grid will miss that first
bug because the pointer is 'lost'. So one solution is to have extra code in
the bugs:

a) If the movement is done as a result of goal-seeking
(disutility-minimization), you *could* make a list of all spots in the
agent's neighborhood (i.e. his range of movement), sort the list on your
search criterion, and move to the first spot on the list that's not occupied;

b) Or if the movement is random rather than goal-seeking, randomize the
list instead of sorting it;

The code to do this may be left in the agents, or some of it may be
generalized and moved into the Grid2d object.

Note that either of these options requires the bugs to move sequentially,
and so the code does not parallellize. (Short of having the bugs negotiate
with each other before anyone moves, I don't see what 'proper conflict
resolution' would look like here ...)

OR, you could make a version of the world grid that allows more than one
agent to occupy a given spot; then the bug code would not need to check for
occupancy before moving and hence could be parallellized. (If you really
only wanted single occupancy, you could of course walk through the grid
afterwards and tell doubled-up bugs to move elsewhere.)

On the user contribution section of the Swarm web site there's in fact two
different implementations of such an enhanced Grid2d, mine and Erik
Nelson's. Give them a try!

Cheers,
Sven Thommesen


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