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 the second DES (event-driven) version. The first DES version schedules patch change events and then brings all of the turtles up to the time of the patch color change. This version schedules patch change color events and turtle movement.
See HOW IT WORKS, below.

This simulation uses the Array extension to keep a list of event times and it uses the Table extension to map an event time to a list of agents that will perform an action at that time. In most cases, the list consists of a single agent, either patch or turtle. Sometimes, for example when a patch has turned red with a turtle on it, there will be more than one agent scheduled to act at the same time.

The array is used to implement a binary heap structure. See https://www.geeksforgeeks.org/binary-heap/ for a desription.

## HOW IT WORKS

Instead of time-steps, the simulation jumps to the time of the next event. The next event is when a patch changes color or a turtle can move. When a turtle moves, it moves as far as it can and then stops until an event for that turtle allows it move again.

The run method extracts the lowest event time in the event-time array (heap). Then it extracts the associated event list from the event table. The event list consists of a list of agents: patches and turtles. Each agent is called, in turn, to perform its action (doPatchStuff, doTurtleStuff).

## HOW TO USE IT

The only input is the number of turtles. The number of ticks is the number of event lists that have been extracted from the event queue. The sim-time shows the time of the last event to be executed.

## THINGS TO NOTICE

It is instructive to single step the simulation. In this simulation, there is one tick each time a list of agents is removed from the event queue. The time is represented as a real number and is shown in the interface. All of the turtles that are not created in a red patch have an initial event scheduled at time 0. Turtles in red patches schedule an event at the patch change time. If you look at the properties of a turtle, the turtle age is the time the turtle reached its current position. Usually, this is in advance of sim-time.

Notice that the turtles move one at a time and patches change colors one at a time. In a discrete event simulation, the state of the turtles and patches are at different times. They advance their state only when an event occurs that affects them. Looking at the states can be misleading, because the position may be for some time in the past or in the future.

The time paradox can be seen in turtles that do not move, even though they appear to be in a green patch. The turtle has calculated that it cannot move farther because the patch it is on is going to change to red before the turtle can exit the patch. By single stepping, you can see when the patch changes to red. When the patch changes back to green, the next event should be for a turtle that was waiting for the patch color change.
Notice that all of the turtles, except those stuck in a red patch, move at the beginning of the simulation. Many of the turtles move all the way to the edge because they know that none of the patches between them and the edge are going to be red when they get there.

**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

In this model, every agent has at most one event scheduled for it. Events are never cancelled or changed. This makes it easy to implement an event queue. In some DES models, events can be cancelled or changed. In these cases, the event queue can be more complicated, often requiring an agent to keep a list of events (indices in the heap array) so they can be easily found. Additional methods for a heap can remove or change values. See the reference below for code examples.

## NETLOGO FEATURES

Examine how the event queue is implemented by a table and an array. The array is used to implement a binary heap. A heap is a complete tree (all of the levels are full except, possibly the last level, and the last level hass all values as far left as possible) with the property that the children of a node are always greater than the parent. Thus, the smallest value in the tree is always the root node, which is found in the first location of the array at index 0.

The event time is used as a key in the events table. The value associated with the key is a list of turtles and patches that will perform an action at the event time.

## RELATED MODELS

See also ExampleABM_EventDriven_1.nlogo and ExampleABM_TimeStepped.nlogo for different implementations of this model. ExampleABM_TimeStepped is a classical agent-based time stepped simulation. ExampleABM_EventDriven_1.nlogo schedules patch color changes and checks every turtle to see if it can move at every patch color change.

## 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