NetLogo User Community Models
## WHAT IS IT?
Macal and North [WSC 2008] ABM Example written as a discrete event simulation (DES).
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.
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.
## 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, firstname.lastname@example.org. Feel free to contact me with comments or questions.
(back to the NetLogo User Community Models)