Pseudo Non-determinisim in NetLogo

Determinism and Non-determinism in NetLogo
NetLogo is designed to mimic a parallel processing system, although it is fundamentally a serial processing one. For example, when a set of agents are asked to run a command, the agents must be sequentially asked because they cannot be asked simultaneously. This feature of NetLogo can be used to illustrate deterministic processes as well as to mimic non-deterministic ones.

The model below is a variation on Langton's Ant which includes four agents. The starting conditions of the model are the same every time. That is, the setup function places the agents at the origin and gives the headings of 0, 90, 180, and 270 degrees. The agents also all follow the same set of commands. Essentially, an agent moves forward 1 space; if the patch below is black it sets it to yellow and turns right; if the patch below is yellow it sets it back to black and turns left. After all agents have executed this set of commands, they do it again.

If the starting conditions are the same and each agent is following the same commands, then the pattern of black and yellow patches should be identical every time the model is run. If you run the model below several times (using the "go (non-deterministic)" button) you will notice that this in fact does not happen. The different outcomes are a result of using a pseudorandom number sequence which determines in what order the agents are called on to run the commands. With each iteration, NetLogo uses a "seed" number that generates a random sequence of numbers. This is then used to determine the order in which the agents are chosen to run the commands. This looks to the observer to be a non-deterministic process.

Click on setup to clear the model and/or setup the agents.

Use go (non-deterministic) to run the model with NetLogo's default of changing the sequence in which agents are called at every iteration. Or use go (deterministic) to run the model using the same seed (set by the seed slider) number used to call agents.

*The speed of the model can be adjusted using the slider at the top.

We can illustrate a deterministic process by specifying the seed number which outputs the same random number sequence every time, which in turn calls the agents in the same sequence every time. Running the model using the "go (deterministic)" button yields the same pattern everytime, just as it should. The seed number can be changed by using the "seed" slider. Changing the seed number generates a different sequence of numbers and hence the pattern created by the agents changes.


"Random"?
A serially operating computer is necessarily deterministic and cannot simulate a non-deterministic process. It can, however, generate outputs that are indistinguishable from those generated by non-deterministic processes. To mimic randomness (and hence indeterminancy), NetLogo uses a pseudorandom number generator to output a sequence of "statistically" random numbers which is then used to determine the order of agents called or whenever the appearance of non-determinism is needed. Statistically random in this case means that the sequence appears random in that the next number in the sequence cannot be accurately predicted, no matter how many previous numbers are known. Additionally, each single digit appears in the sequence with the same frequency as all others (in a binary sequence, 1's and 0's have a frequency of about 50%). Similarly, the frequency of pairs of digits are the same for others, and so on (00's, 01's, 10's, and 11's have a frequency of about 25%). The sequence is not truly random but is rather pseudorandom because using the same seed in the algorithm will always yield the same sequence.


The code

to setup
ca
crt 4 [set color sky]
ask turtle 0 [set heading 0]
ask turtle 1 [set heading 90]
ask turtle 2 [set heading 180]
ask turtle 3 [set heading 270]
end

to go-non-deterministic
ask turtles [
fd 1
ifelse [pcolor] of patch-here = black [set pcolor yellow rt 90] [set pcolor black lt 90]
]
end

to go-deterministic
random-seed seed
ask turtles [
fd 1
ifelse [pcolor] of patch-here = black [set pcolor yellow rt 90] [set pcolor black lt 90]
]
end

 

Posted by Laura Cyckowski 9 Feb 2008.

Comments

Post new comment

The content of this field is kept private and will not be shown publicly.