This page was automatically generated by NetLogo 5.0.
The applet requires Java 5 or higher. Java must be enabled in your browser settings. Mac users must have Mac OS X 10.4 or higher. Windows and Linux users may obtain the latest Java from Sun's Java site.
powered by NetLogo
view/download model file: uniform_mfpl.nlogo
This model is an attempt to provide “uniform coverage” of a region. The goal is to have one or more agents move throughout a region, exploring all parts with equal frequency.
Our region is very simple - it is a square divided into nine “cells.” The center cell is colored “red,” the corner cells are colored “blue,” and the remaining cells are colored “green.” The yellow boundary prevents agents from escaping the region.
This is our second attempt, which merges physicomimetics with the prior biomimetics approach. Our first approach is in “uniform.nlogo.”
If an agent moves a certain distance, or senses a wall or another agent in front of it, the agent makes a random turn. Otherwise the agent moves forward. This is motivated by similar behaviors used to model termites in NetLogo.
Every time step, if an agent is in a particular cell, a counter for that cell is incremented by one. This records the number of times that cell has been visited. A histogram displays how often all cells have been visited.
This approach adds a physics-based component to the prior biomimetics approach. In gases, molecules travel a distance referred to as the “mean free path” before they collide with another molecule. We can mimic this concept by having each agent note how far it has traveled between collisions with other particles and walls. If it has traveled far enough (the “mean free path” length), the agent makes a random turn.
The effect of this additional component is to prevent agents from simply moving across the region from one side to another. Hence, they will spend more time in cells with fewer walls. This provides coverage that is much more uniform. This simulation shows that sometimes we can obtain better solutions to problems by combining biomimetics with physicomimetics.
A monitor gives the theoretically derived value for the mean free path that will yield good uniform coverage (see Chapter 4 for details).
Click SETUP AGENTS to initialize the particles, and click MOVE AGENTS to have them move.
The NUMBER_OF_PARTICLES slider allows you to control the number of particles created at initialization. Changing this slider while the simulation is running will have no effect.
The MEAN_FREE_PATH_LENGTH slider controls the distance an agent will travel in a straight line before making a random turn. This slider is always monitored, so changing this slider will affect the simulation when it is running. If the slider is all the way to the right, this is equivalent to the prior simulation “uniform.nlogo.”
A histogram shows the distribution of the coverage as nine vertical bars, one bar for each cell. Higher bars represent larger frequencies of exploration. The bars are given the same color as the cell they represent. Qualitatively, the ideal model would yield a very “flat” histogram, showing that all cells have been visited equally often. In the perfect case, each bar would have height 1/9 = .1111… because there are nine cells.
A monitor called DEVIATION FROM UNIFORMITY provides a quantitative metric of how well the model works. The optimum value is 0.0, while the worst value is 0.9428. Chapter 4 provides an explanation of this metric.
Once you understand the behavior of an agent (or a set of agents), it is generally a good idea to speed up the simulation by moving the speed slider (at the top) to the right.
After running the simulation for a while, what does the histogram look like? Does this model favor certain cells over others? If so, why does this occur?
Is the performance better than the previous purely biomimetic approach?
Trying running the simulation with one agent and try running with 100 agents. What
difference does this make in the behavior?
Change the MEAN_FREE_PATH_LENGTH slider. How does this affect performance?
How could this model be improved, in terms of achieving better uniform coverage? Try different approaches.
Create a more interesting region (e.g., a rectangle or L-shaped region).
Create a button to add particles and a button to remove particles (you can get the code from prior simulations). Does the behavior change when you add or remove particles?
Note, in order to change any NetLogo simulation, you must have the source code (i.e., “uniform_mfpl.nlogo”) downloaded to your computer, as well as NetLogo itself. You can not change the code when you are running the simulation with your browser.
The “extensions[array]” command adds the ability to use arrays in NetLogo. An array is used to maintain the cell counts for the nine cells in the environment.
The “do-plot” procedure provides extensive detail on how to create a very useful histogram, using colored pens.
The NetLogo termite model is provided by:
Wilensky, U.: NetLogo termites model (1997). http://ccl.northwestern.edu/netlogo/models/Termites. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL
Our less sophisticated model for uniform coverage is in “uniform.nlogo.”
Maxim, P., and Spears, W. M. (2009) Robotic Uniform Coverage of Arbitrary-Shaped Connected Regions. Carpathian Journal of Electronic and Computer Engineering, 2 (1).
Maxim, P., Spears, W. M., and Spears, D. F. (2009) Robotic chain formations. In Proceedings of the IFAC Workshop on Networked Robotics.
If you mention this model in an academic publication, we ask that you include these citations for the model itself and for the NetLogo software:
- Spears, W. M. and Spears, D. F. (eds.) Physicomimetics: Physics-Based Swarm Intelligence, Springer-Verlag, (2011).
- Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.
Copyright 2011 William M. Spears. All rights reserved.
Permission to use, modify or redistribute this model is hereby granted, provided that both of the following requirements are followed:
a) this copyright notice is included, and
b) this model will not be redistributed for profit without permission from William M. Spears.
Contact William M. Spears for appropriate licenses for redistribution for profit.
; William M. Spears, September 2011
; Uniform Coverage Tutorial Code, Version 2
; For research and educational use only
extensions[array] ; This extension adds arrays to NetLogo
globals [boundary b1 b2 uhist] ; uhist is the uniform distribution histogram
turtles-own [steps]
; Called by "Setup Agents"
; Assumes max-pxcor = -min-pxcor, and max-pycor = -min-pycor
to setup
clear-all ; Clear everything
set uhist array:from-list n-values 9 [0] ; Used to break the environment into nine 3x3 cells
set boundary (max-pxcor - 2) ; Set the boundaries of the cells
set b1 ((2 * boundary) / 3) - boundary
set b2 ((4 * boundary) / 3) - boundary
crt Number_of_Particles ; Create and initialize particles throughout the environment
[setxy (15 * random-xcor / 16) (15 * random-ycor / 16)
set color white set size 2 monitor]
ask patches [setup-patches] ; Ask patches to color themselves
setup-plot ; Initialize the uniform distribution histogram
reset-ticks
tick
end
to setup-patches ; Use different colors for the three classes of cells
ifelse ((pxcor < b1) and (pycor < b1)) [set pcolor blue] [
ifelse ((pxcor < b1) and (pycor < b2)) [set pcolor green] [
ifelse (pxcor < b1) [set pcolor blue] [
ifelse ((pxcor < b2) and (pycor < b1)) [set pcolor green] [
ifelse ((pxcor < b2) and (pycor < b2)) [set pcolor red] [
ifelse (pxcor < b2) [set pcolor green] [
ifelse (pycor < b1) [set pcolor blue] [
ifelse (pycor < b2) [set pcolor green] [set pcolor blue]]]]]]]]
; Draw the yellow boundary for the environment
if ((pxcor = max-pxcor) or (pxcor = min-pxcor) or
(pycor = max-pycor) or (pycor = min-pycor))
[set pcolor yellow]
end
; Called forever by "Move Agents"
to go
if (count turtles < 1) [user-message "Please click HALT and then SETUP AGENTS first" stop]
ask turtles [go-particles] ; All particles try to move
do-plot ; Redraw the histogram
tick
end
to go-particles
let tries 1 ; The particles try 10 times to move forward
set steps steps + 1 ; They can move forward if there is nothing in the way
while [(tries < 10) and (([pcolor] of patch-ahead 1 = yellow) or
([pcolor] of patch-left-and-ahead 45 2 = yellow) or
([pcolor] of patch-right-and-ahead 45 2 = yellow) or
(any? other turtles in-cone 3 30) or
(steps = Mean_Free_Path_Length))]
[set heading random 360 set steps 0 ; If obstacle in the way or have traveled far enough,
; make a random turn and try again
set tries tries + 1]
if (tries < 10) [fd 1] ; If you can move forward, do so
monitor ; This updates the cell counts for the histogram
end
to monitor ; Update the histogram bins (cell counts)
let x 0
let y 0
; Left, center, or right column?
ifelse (xcor < b1) [set x 0] [
ifelse (xcor <= b2) [set x 1] [set x 2]]
; Bottom, center, or top row?
ifelse (ycor < b1) [set y 0] [
ifelse (ycor <= b2) [set y 1] [set y 2]]
array:set uhist (x + (3 * y)) (1 + array:item uhist (x + (3 * y)))
end
to setup-plot ; Setup the histogram
set-current-plot "Distribution of Coverage"
end
to do-plot ; The histogram, using pens of different colors
clear-plot
let temp (ticks * Number_of_Particles)
set-plot-x-range 0 540
set-plot-y-range 0 (1 / 9)
set-current-plot-pen "pen0"
plotxy 0 (array:item uhist 0 / temp)
set-current-plot-pen "pen1"
plotxy 60 (array:item uhist 1 / temp)
set-current-plot-pen "pen2"
plotxy 120 (array:item uhist 2 / temp)
set-current-plot-pen "pen3"
plotxy 180 (array:item uhist 3 / temp)
set-current-plot-pen "pen4"
plotxy 240 (array:item uhist 4 / temp)
set-current-plot-pen "pen5"
plotxy 300 (array:item uhist 5 / temp)
set-current-plot-pen "pen6"
plotxy 360 (array:item uhist 6 / temp)
set-current-plot-pen "pen7"
plotxy 420 (array:item uhist 7 / temp)
set-current-plot-pen "pen8"
plotxy 480 (array:item uhist 8 / temp)
end
to-report uniform ; Compute Euclidean distance metric for uniformity over nine cells
; 0.94280 is the worst value while 0.000 is the best
let my_sum 0 let temp (ticks * Number_of_Particles)
foreach [0 1 2 3 4 5 6 7 8]
[set my_sum my_sum + ((array:item uhist ? / temp) - (1 / 9)) ^ 2]
report sqrt my_sum ; See Chapter 4 for details
end