NetLogo Project Prototype: Exit III

From Backspaces Wiki

NetLogo Tutorial Home Modeling Overview Command Center Buttons Model Fooling Around Project Prototype: Setup Project Prototype: Go Project Prototype: Behavior Bag Of Tricks

We finish our Exit prototype by exploring more interesting agent behavior to eliminate the crowd stalemates/clumping, and the agents trapped by obstacles.

The obstacle problem is solved using a flood-fill, similar to the one used in the Grid example. The idea is to start at an agent's goal, and work outward from there, marking patches as to how far they are from the goal. This is done by finding the neighbor patches to the edge of already marked patches. Obstacles are avoided, and the distance remains correct, taking into account the additional distance needed to circle the obstacle.

More importantly, this method mimics a very human behavior. The agents do not just appear within the inside patches. Instead, they arrive there by entering an exit (entrance), threading through the inside patches to the point at which the model starts. The flood-fill similarly starts at the exit and naturally enters into the inside area, marking the way it entered.

The stalemated agents .. those who cannot move due to other agents blocking their way, headed in the opposite direction .. become frustrated over time. We introduce frustration, which at a certain point induces different behavior. The one we'll use is simply swapping positions, squeezing by each other. A complementary idea is for frustrated agents who are at the edge of the crowd headed for an exit to decide to go to a different exit which appears less crowded.

Contents 1 Flood Fill Procedure 2 Testing flood-fill 3 Using the Flood Fill: Patches 4 Using the Flood Fill: Turtles 5 Using the Flood Fill: Move 6 Stalemates and Frustration 7 Summary 8 Notes

Flood Fill Procedure

We'll start with writing a flood-fill procedure. It will need a patch variable for the distance to its initial starting patch. We'll call this "flood". Update the patches-own entry to include it:

patches-own [exit? inside? flood]

The procedure will:

• Require an input variable, pset, specifying where the flood-fill starts. It can be a patch-set or a single patch.
• Insure pset is a patch-set, for the case the input is a single patch. (As in our case where the exits are single patches.)
  • In production versions of the model, we used multiple patches for each exit.
• Initialize all the patch flood variables to an invalid value. We'll arbitrarily choose 9999, a pretty unlikely number.
• Initialize the input patch/patches flood variable to 0.
• While there are un-processed patches
  • Set pset to the "edge" un-processed patch-set (those with flood unmodified and inside).
  • Set their flood value to be the minimum distance to a processed neighbor. Note the use of 9999 insures the minimum neighbors exclude unprocessed patches.

to flood-fill [pset]
  set pset patch-set pset
  ask patches [set flood 9999]
  ask pset [set flood 0]
  while [count pset > 0]
  [ set pset patch-set [neighbors with [flood = 9999 and inside?]] of pset
    ask pset [set flood min [flood + distance myself] of neighbors] ]
end

Lookup: patch-set, while, min, of.

There are some subtleties in the last two lines:

• of: We often use the of command on a single agent or patch. In this case, we use it on a patch-set in both lines.
  • Line 1 - [neighbors with [flood = 9999 and inside?]] of pset: This returns all the neighbors of pset that are unprocessed (9999) and inside .. as a list. Thus we apply patch-set to this result to convert it back to a set of patches.
  • Line 2 - min [flood + distance myself] of neighbors: Again, of is applied to a set, thus returns a list. Fortunately, min expects a list. Again, note the potential 9999 entries are innocuous because we are looking for the min which 9999 will not be.
• ask: When we are done, we will have line 1 set pset to an empty patch set. Fortunately ask does not mind, it will simply not apply its procedure block to any patches.

Testing flood-fill

As you can imagine, it took several attempts to get this right! The Command Center, as usual, was used a lot.

Set the obstacles slider to its max: 500
Click setup
observer> clear-turtles
observer> flood-fill one-of exits
observer> ask patches with [flood != 9999] [set pcolor flood]

Lookup: clear-turtles (ct). (We remove the turtles to see the patches/obstacles more clearly)

Repeat the last two lines several times to see what the flood looks like from the various exits .. you can combine them into one line to make it easier:

observer> flood-fill one-of exits ask patches with [flood != 9999] [set pcolor flood]

The radial color pattern gives us some assurance that the distances are increasing from the exit. Ditto that the 9999 patches are where we think they are. See Notes for an alternative way to visualize the flood.

Lets actually try using the flood values in our model. In the move procedure, add a line that flips move from the distance approach to using flood:

;    [ (not any? turtles-here) and (inside? or exit?) and (flood < [flood] of myself)]

The move procedure now looks like this:

to move
  ifelse inside?
  [ let d distance exit
    let n neighbors with
    [ (not any? turtles-here) and (inside? or exit?) and (distance [exit] of myself < d)]
;    [ (not any? turtles-here) and (inside? or exit?) and (flood < [flood] of myself)]
    if any? n [face one-of n move-to patch-ahead 1] ]
  [ ifelse patch-ahead 1 = nobody [die] [move-to patch-ahead 1] ]
end

To test, use the Command Center again:

Use the above version of move (i.e. use the distance approach, not the flood)
Set num-exits slider to 1 (There is only one flood variable, thus only one exit to flood from.)
observer> setup repeat 1.5 * population [go]
Move the semicolon (comment) to the line above its current line (i.e. use flood, not distance)
observer> setup flood-fill one-of exits repeat 1.5 * population [go]

The distance approach leaves several stranded agents, blocked by obstacles (left, below). The flood approach completely empties the inside, with no obstacle blockage (right, below). See the random-seed Notes entry for how we achieved the same patch/obstacle layout for the two runs.

Using the Flood Fill: Patches

Now that we're comfortable with flood-fill, we're stuck in a dilemma: our flood-fill only works with a single exit, using the patch variable "flood", but we have multiple exits. How do we manage this? Our answer was to replace the single flood patch variable with a list patch variable, where each position in the list represents one of the exit floods:

• Create a list named "floods" in each patch.
• For each exit, perform a flood-fill.
• Append the "flood" variable created by flood-fill to the end of each patch's "floods" list.

It looks like this for 4 exits:

To use the floods list, each agent knows which level in the list is the one for its exit. Although this seems fairly complicated, it turns out to be fairly reasonable to implement. We'll need a new patch variable for the list of floods:

patches-own [exit? inside? flood floods]

The floods list will be created at the end of the setup-patches procedure. To do this, we create a list of the exits, using "sort exits", and use the foreach command (See Notes for details). Note that using sort has the advantage that the exits are flooded in "reading order" from top-left to bottom-right. Insert these two new lines at the end of setup-patches:

to setup-patches
  ...
  ask patches [set floods []]
  foreach sort exits [ flood-fill ? ask patches [set floods lput flood floods] ]
end

Lookup: foreach, sort, lput. You may want to review the difference between agent sets and lists.

Test the results by clicking setup, then right-click on patches to see the floods lists. In the sample below, the left is outside, thus has all 9999 entries. The middle is the third exit flood-filled (why?), thus has one 0 and the rest 9999's (why? .. don't forget that exits are also outside!). The right is an arbitrary inside patch.

Using the Flood Fill: Turtles

Each turtle needs to know which position within the floods list to use for its distance to its exit. We'll need a new turtle variable for that position, flood-index.

turtles-own [exit flood-index]

We'll set flood-index in the setup-turtles procedure as soon as we've set the exit for the turtle. Insert this:

set flood-index position 0 [floods] of exit

Lookup: position.

.. in the turtle setup block:

 ask n-of population inside [ sprout 1
 [ ifelse random-exit? 
   [ set exit one-of exits ]
   [ set exit min-one-of exits [distance myself] ]
   set flood-index position 0 [floods] of exit
   set color [pcolor] of exit
   set size agent-size ]]

Test the results by inspecting a turtle near its exit:

• Right-click on an exit patch to inspect it.
• Right-click on a nearby turtle, and inspect the turtle (not the patch)

In this case:

• The exit patch was the first to be flood filled (0 is in the first (0th) position).
• The turtle's flood-index is 0, as expected.
• Its turtle's exit is the same patch number as the exit's, also expected.
• To see how far the turtle is from its exit:

observer> ask turtle 1351 [show item flood-index floods]
(turtle 1351): 2.414213562373095

The small value, around 2.4, is as expected .. the turtle was close to its exit.

Using the Flood Fill: Move

Finally, the move procedure will have to take the floods lists into account. It fits in fairly easily .. much like the single flood (see Testing flood-fill above). In that section we used the single flood:

    [ (not any? turtles-here) and (inside? or exit?) and (flood < [flood] of myself)]

In our new move procedure, we set a variable "i" to be the flood-index of the current turtle, then use:

    [ (not any? turtles-here) and (inside? or exit?) and (item i floods < item i [floods] of myself)]

This results in:

to move
  ifelse inside?
  [ let i flood-index
    let n neighbors with
    [ (not any? turtles-here) and (inside? or exit?) and (item i floods < item i [floods] of myself)]
    if any? n [face one-of n move-to patch-ahead 1] ]
  [ ifelse patch-ahead 1 = nobody [die] [move-to patch-ahead 1] ]
end

Lookup: item.

We can test how well this works compared to the previous version not using flood-fill by setting num-exits to 1. We use one so as to eliminate stalemates, testing only the ability to avoid being trapped by obstacles. Our new version ran fine, with no trapped agents (below, left). Running the prior version with the same patches/obstacles (using random-seed 1) we get two stranded turtles (below, right), thus validating the new approach.

Run the new version several times (with random-exit? off) to convince yourself any turtles remaining after a run are blocked by other turtles, not trapped by obstacles.

Stalemates and Frustration

The second issue, solving the clumps of agents unable to move because they are in each others way, is fairly easy to solve, given our floods. We start by adding a last-move tick to each agent, and a new global, "swaps", the number of frustrated moves. Our complete set of global, patch, turtle variables is now (order changed .. globals now first):

globals     [population swaps]
patches-own [exit? inside? flood floods]
turtles-own [exit flood-index last-move]

Fine point: Neither swaps nor last-move need initialization, they will be set to 0 by default.

As their last move becomes several ticks ago, agents become impatient, and will consider alternative solutions to the steady flow toward their exit. We will make a few, fairly sophisticated changes to move. To make move a bit simpler, we introduce three new one-liners:

to-report frustrated? report (ticks - last-move) > 5 end
to go-to [a] face a move-to patch-ahead 1 set last-move ticks end
to swap [t] let p1 patch-here go-to t ask t [go-to p1] set swaps swaps + 1 end

Lookup: patch-here. Note that we did not use a slider for the frustration count, we simply used 5, see Notes. It did not seem to be important do do so, and its best to keep the interface as clean and simple as possible. (Similarly, we did not add a switch for using the random-seed, its easy to modify the code.)

We only need to modify the inside portion of the move command. Our strategy is:

• Create two patch-sets:
  • n0: Our neighbors that are inside and closer to our goal (a new neighborhood that does not exclude occupied patches).
  • n: The subset of n0 that is not occupied by any turtles (as in previous versions)
• Create one turtle-set:
  • frust: the turtles in n0 that have not moved recently and who would be closer to their goal if they switched positions.
• Implement the behavior:
  • If there are any patches available in n, go to one of them.
  • Else if I'm frustrated and I have any frustrated neighbors wanting to swap, do so with one of them.

to move
  ifelse inside?
  [ let i flood-index
    let n0 neighbors with [ (inside? or exit?) and (item i floods < item i [floods] of myself) ]
    let n n0 with [ (not any? turtles-here) ]
    let frust (turtle-set [turtles-here with [frustrated?]] of n0)
    set frust frust with [ item flood-index [floods] of myself < item flood-index floods ]
    ifelse any? n [go-to one-of n] [if frustrated? and any? frust [swap one-of frust]] ]
  [ ifelse patch-ahead 1 = nobody [die] [move-to patch-ahead 1] ]
end

Lookup: turtle-set.

Finally, we add a monitor for the swaps global variable.

Note the slight curve down in the middle of the plot. This implies the exiting actually improved part way through the run. Why do you think this is so? It was run with random-exits? on.

Summary

This completes our prototype for the RedFish Zozobra project. The final code is below. If you can browse over the code, feel comfortable with its use of agent sets, lists, procedures, commands, UI and so on, you're ready to start on your own models.

globals     [population swaps]
patches-own [exit? inside? flood floods]
turtles-own [exit flood-index last-move]

to setup
  ca ; random-seed 1 ; use any number you'd like for the seed.
  setup-patches
  set population int (( %-population * count inside ) / 100)
  setup-turtles
  set-plot-y-range 0 population
end
to go
  tick
  ask turtles [move]
  set population count turtles with [inside?]
  plot population
  if not any? turtles [set-plot-x-range 0 ticks stop]
end

to setup-patches
  ask patches
  [ set exit? false
    set inside? (abs pycor < (.7 * max-pycor)) and (abs pxcor < (.7 * max-pxcor)) ]
  
  ask inside [ ask neighbors4 with [not inside?] [set pcolor grey] ]

  let min-dist .5 * (count patches with [pcolor = grey]) / num-exits
  repeat num-exits
  [ ask one-of patches with [pcolor = grey and not any? patches in-radius min-dist with [exit?]] 
    [ set exit? true set pcolor (grey + 10 * count exits) ] ]

  ask n-of obstacles inside with [not any? neighbors4 with [exit?]] 
  [ set pcolor grey set inside? false ]
  
  ask patches [set floods []]
  foreach sort exits [ flood-fill ? ask patches [set floods lput flood floods] ]
end
to setup-turtles
  set-default-shape turtles agent-shape
  
  ask n-of population inside [ sprout 1
  [ ifelse random-exit? 
    [ set exit one-of exits ]
    [ set exit min-one-of exits [distance myself] ]
    set flood-index position 0 [floods] of exit
    set color [pcolor] of exit
    set size agent-size ]]
end
to move
  ifelse inside?
  [ let i flood-index
    let n0 neighbors with [ (inside? or exit?) and (item i floods < item i [floods] of myself) ]
    let n n0 with [ (not any? turtles-here) ]
    let frust (turtle-set [turtles-here with [frustrated?]] of n0)
    set frust frust with [ item flood-index [floods] of myself < item flood-index floods ]
    ifelse any? n [go-to one-of n] [if frustrated? and any? frust [swap one-of frust]] ]
  [ ifelse patch-ahead 1 = nobody [die] [move-to patch-ahead 1] ]
end

;; One Liners
to-report inside report patches with [inside?] end
to-report exits  report patches with [exit?]   end
to-report frustrated? report (ticks - last-move) > 5 end
to go-to [a] face a move-to patch-ahead 1 set last-move ticks end
to swap [t] let p1 patch-here go-to t ask t [go-to p1] set swaps swaps + 1 end

;; Utilities
to flood-fill [pset]
  set pset patch-set pset
  ask patches [set flood 9999]
  ask pset [set flood 0]
  while [count pset > 0]
  [ set pset patch-set [neighbors with [flood = 9999 and inside?]] of pset
    ask pset [set flood min [flood + distance myself] of neighbors] ]
end

Notes

• visualizing flood-fill: we used the pcolor above to show the flood. An alternative way would be to use the patch's plabel. Try this:

Set the obstacles slider to its max: 500
Click setup
observer> clear-turtles
observer> flood-fill one-of exits
observer> ask patches with [flood != 9999] [set plabel precision flood 0]

Lookup: precision.

Unfortunately, the numbers will all run into each other! You can fix this in the View Settings panel by changing the font size from 10 to 8, and the Patch size from 7 to 12. For even more information, make the patches larger, and use a precision of 1. Using plabel is a common debugging technique.

• random-seed: The random-seed command is a way to insure that a model repeats itself on each run by having the random numbers it generates be the same sequence: the same numbers, and in the same order. A simple way to use this is to use the random-seed command at the beginning of the setup procedure:

to setup
  ca  random-seed 1 ; use any number you'd like
  ...

To return to standard usage (non-identical runs), comment out the random-seed command:

to setup
  ca  ; random-seed 1 ; use any number you'd like
  ...

• Alternate use of flood-fill: Rather than having a list of all the flood-fills, we could use our single flood only when needed. When an agent gets trapped, mark it as needing help, and every time it takes a turn, use a flood fill to help it take its next turn. It is a reasonable approach and avoids the floods lists which are a bit heavy weight. It does, however, have a few problems:
  • The performance could be quite bad if there are several agents needing assistance.
  • It would be more reasonable for the trapped agent to seek assistance from other agents, rather than magically change from the distance mode to the flood mode. A trapped agent would seek out a helper agent (cop) who would give the trapped agent "directions" as a flood-fill. This would considerably complicate the model.
  • Doing so would complicate the move procedure, handling some moves with the distance function, others with the flood-fill's flood variable. It would chose among the two methods discussed above:

[ (not any? turtles-here) and (inside? or exit?) and (distance [exit] of myself < d)]
.... or
[ (not any? turtles-here) and (inside? or exit?) and (flood < [flood] of myself)]

• Creating floods lists: Our first try was:

ask patches [set floods []]
ask exits [ flood-fill self ask patches [set floods lput flood floods] ]

.. but it produced the error:

Basically patches and turtles are not allowed to ask all the patches to do something. This could be solved by having our flood-fill only look at the exits and inside patches .. this seems to be allowed. But we used the foreach list enumerator ("sort exits" as well as "[self] of exits" creates a list of exits) which let us avoid calling flood-fill from within the exit patches.

• Frustration: Interestingly enough, increasing the frustration threshold from 5 to 10 reduces the number of swaps. This makes sense: it gives the agents more time to become freed to move. I guess patience really is a virtue!

• See ExitTutFloods.nlogo (just the flood fills) and ExitTutBehavior.nlogo (final version with floods and frustration) in the NetLogoTut download folder.