NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled because this model uses extensions.)

## WHAT IS IT?

Macal and North [WSC 2008] ABM Example written as a discrete event simulation (DES).
The model consists of a 12 x 12 grid of patches. Each patch is 100 feet by 100 feet square. Approximately 20% of the patches are red and 80% are green. Each red patch changes to green after 10-30 minutes. Each green patch changes to red after 70-90 minutes. There are a variable number of turtles. Each turtle is randomly placed on the grid with facing of north, east, south, or west. Turtle speed is 60 feet per minute. Ticks are one minute apart. On each tick, each patch determines if it is time for it to change color and each turtle moves, if it can. If a patch changes color, then it will calculate its next color change time (10-30 minutes if it is red, 70-90 minutes iof it is green). Each turtle uses the following rules for movement:
1. A turtle will begin moving at its specific heading if, and only if, it starts on a green patch.
2. If a turtle is on a red patch, it will wait until the patch turns gree to start moving.
3. If a turtle is moving through a patch and reaches the edge, it will only enter the next patch if it is green.
4. If a turtle is travelling through a patch when it turns red, it will stop immediately. It will not move again until the patch turns green.
5. When a turtle reaches one of the edges of the grid, it exits the system, and its total time spent in the simulation is recorded.
The simulation is run until all turtles have exited, at which time statistics are calculated.

This is a DES (event-driven) version. Instead of time-stepping, the simulation keeps a list of times that patches change colors and "jumps" from one patch color change time to the next. This simulation uses the Array extension to keep the times, organized as a binary heap. Each time is associated with one patch; the patch that changes color at that time. The association of patch to time is kept using the Table extension.

## HOW IT WORKS

Each cycle, the earliest time is removed from the heap, the patch associated with the time is retreived from event table (and removed from the table), and the patch doPatchStuff is called. As part of the doPatchStuff procedure, each turtle is checked to see if it can move and, if so, it is moved until
1. time reaches the event time
2. turtle reaches the edge of a red patch
3. turtle reaches the edge of the grid.
After all of the turtles are checked, the patch color is changed and the next color change time for the patch is calculated.

The Table extension does not allow for two keys with the same value. Therefor, before adding a time to the heap array and event table, the table is checked to see if the time already is in the table. If it is, then the time is incremented slightly, until a time not in the table is calculated, and this is the time that is used for the event. There is another implementation, ExampleABM_Event_Driven_2.nlogo, where agents are kept in a list, so that all agents performing an action at the same time are placed in the table.

## HOW TO USE IT

The only input is the number of turtles. Notice that doTurtleStuff is not directly called in the go procedure. Rather, it is called by the doPatchStuff procedure.

## THINGS TO NOTICE

It is instructive to single step the simulation. In this simulation, there is one tick when a patch changes color. Prior to the patch actually setting its new color, all of the turtles are moved to the time of the patch color change. Then the patch color is set. This process continues until all turtles have reached the edge of the grid.

The results from this simulation should be compared with ExampleABM_TimeStepped.nlogo simulation, where the same model is implemented with the traditional time-stepped simulation mechanism. There, one tick is one minute. The average turtle age and the total simulation time are the same for the same number of turtles, but the execution profile is different. In this implementation, about 2.88 doPatchStuff events occur in a simulated minute, where the time-stepped version does all 144 patches every minute. In the time stepped version, most of the patches do not change color during a tick (in fact about 2.88 change color per tick, on average). In the time-stepped simulation, every turtle is checked once per tick. In this version every turtle is checked for every patch color change event, or 2.88 times per minute. This means that for less than 50 turtles, this simulation will have fewer total doTurtleStuff and doPatchStuff calls, and for more than 50 turtles this simulation will have more total doTurtleStuff and doPatchStuff calls.

**Model Setup**
The simulation could be executed a few thousand times in order to randomize the patch colors. Many simulations execute a warm-up period to reach steady state. In this case, the expected distribution of color change times can be calculated and set. The calculation is described in a paper, _NetLogo Meets DES_, submitted to the Computational Social Science 2018 annual conference.

## THINGS TO TRY

## EXTENDING THE MODEL

Try implementing the list of event times using a sorted list or a sorted array instead of a heap.

## NETLOGO FEATURES

This model uses the Array and Table extensions to implement an event queue.

## RELATED MODELS

See also ExampleABM_EventDriven_2.nlogo and ExampleABM_TimeStepped.nlogo for different implementations of this model. ExampleABM_TimeStepped is a classical agent-based time stepped simulation. ExampleABM_EventDriven_2.nlogo schedules both patch color changes and turtle moves and is nearly 50 times more efficient.

## CREDITS AND REFERENCES

See https://www.geeksforgeeks.org/binary-heap/ for information on heaps.

This model has been coded by Emmet Beeker, ebeeker@mitre.org. Feel free to contact me with comments or questions.
July 10, 2018