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: kt.nlogo
This is a model of a physics-based approach to provide a “sweep” of a region. The goal is to sweep a large group of robots through a long bounded region. This is especially useful for de-mining, searching for survivors after a disaster, and for robot sentries.
We use a very different form of physicomimetics, based on “kinetic theory.” In kinetic theory, particles are treated as possessing no potential energy. The system consists entirely of kinetic energy. In fact, kinetic theory does not typically deal with forces at all. Instead, increases in particle velocity are modeled as being caused by collisions and/or a system temperature increase. This is very different from the F = ma physics systems that we have examined earlier.
Our region is very simple - it is a vertical corridor. In the model, we treat the left boundary as an infinite-length wall that moves down, whereas the right boundary is an infinite-length wall that moves up. This creates an interesting sweep, where one-half of the corridor is swept in one direction while the other half is swept in the other direction. Chapter 4 discusses this particlar simulation in more detail. Chapter 7 provides a more sophisticated version of the simulator in which both walls move in the same direction and robots are modeled realistically. Chapter 7 also provides experimental and theoretical results.
Kinetic theory is a stochastic approach. The focus is on obtaining desirable bulk movement of the swarm. The movements of the individual agents are probabilistic and therefore unpredictable. This is desirable for applications where stealth is required.
If an agent senses another agent nearby, they both respond as if a virtual collision has occurred. If an agent senses a wall nearby, it changes its velocity in response to the virtual motion of the wall. In addition, the temperature T of the walls adds kinetic energy to the particles.
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.
Two sliders affect the simulation when it is running. The WALL_VELOCITY slider controls the velocity of both walls (i.e., the left wall moves down with velocity WALL_VELOCITY, and the right wall moves up with velocity WALL_VELOCITY). The TEMPERATURE slider controls the temperature T of both walls.
Two monitors show the x- and y-components of the linear momentum. These should remain close to zero because the particles are stationary when initialized, and kinetic theory conserves linear momentum.
A histogram shows the velocity distribution of the particles. The corridor is broken into
13 vertical columns, and the histogram shows 13 bars that indicate the average velocity of the particles in each column. The leftmost bar gives the average velocity in the leftmost column, and the rightmost bar gives the average velocity in the rightmost column. Since there is an odd number of columns, the central bar reflects the average velocity in the center column.
The velocity distribution is averaged during the running of the simulation. If you click RESAMPLE, the previous data is thrown away and the averages are (re-)computed using the data accumulated after RESAMPLE is clicked. Hence, the averages will fluctuate until enough new samples are accumulated.
Two additional monitors give quantitative information about the bars of the histogram. One monitor shows the slope of the bars. The other monitor gives the correlation coefficient - the maximum value is 1.0, indicating that the height of the bars has a relationship that is predicted by theory (see Chapters 4 and 7 for specifics).
Once you understand the behavior of the particles, 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? Can you guess why it has this particular form? Try guessing first, and then read Chapter 4 (or Chapter 7) to find the mathematical formula for the velocity distribution.
Both the WALL_VELOCITY and the wall TEMPERATURE are controllable by sliders. These parameters control the bulk movement of the robotic swarm.
Recall that a kinetic theory approach conserves linear momentum. The book explains how collisions are implemented in a way that ensures this conservation.
Trying running the simulation with 100 agents and try running with 1000 agents. What
difference does this make in the behavior?
Change the WALL_VELOCITY. For an extreme case, set it to zero.
Change the TEMPERATURE.
How do these changes (of the WALL_VELOCITY and TEMPERATURE, going from low to high values) affect behavior? Can you explain the differences in swarm behavior?
Try a wide variety of parameter settings and see if you can predict how the settings will affect the shape and slope of the histogram.
Figure out which parameter (slider) settings provide better horizontal corridor coverage, and which provide better vertical corridor coverage. How would you recommend balancing the two? Can you derive a formula for doing this?
Try adding obstacles, including obstacles of difference sizes and shapes. Observe what happens in the “shadow regions” (see Chapter 7) as you vary the parameters. Find the best settings for shadow region coverage, and determine how that affects the vertical and horizontal coverage of the corridor.
Create a button to add agents and a button to remove agents (you can get the code from prior simulations). Does the bulk swarm behavior change when you add or remove agents? If yes, how?
For a more challenging project, invent a hybrid physicomimetic algorithm consisting of both forces and collisions. Normal movement is driven by forces, whereas collisions are used to drive the particles out of enclosing “traps.” Start with code such as “formation_lj_goal_obs.nlogo” and add in some of the code from “kt.nlogo” as appropriate. Note that you will have to add software procedures for an agent to detect when it is trapped and then to switch from forces to collisions (e.g., by raising the wall TEMPERATURE inside a cul-de-sac) to pop out of the “trap.”
In order to change any NetLogo simulation, you must have the source code (i.e., “kt.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 compute the velocity distribution for the thirteen columns in the environment.
The “do-plot” procedure provides extensive detail on how to create a very useful histogram.
Spears, D. F., Kerr, W., and Spears, W. M. (2009) Fluid-like swarms with predictable macroscopic behavior. Lecture Notes in Computer Science, Volume 4324.
Spears, D. F., Kerr, W., and Spears, W. M. (2006) Physics-based robot swarms for coverage problems. International Journal on Intelligent Control and Systems, 11(3).
Kerr, W. and Spears, D. F. (2005) Robotic simulation of gases for a surveillance task. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems.
Garcia, A. (2000) Numerical Methods for Physics, Second Edition. New Jersey: Prentice Hall.
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, Wesley Kerr, and Diana F. Spears, September 2011
; Kinetic Theory Tutorial Code
; Based on code from "Numerical Methods for Physics" by
; Alejandro L. Garcia, 2nd edition, Prentice Hall, 2000.
; Especially see pages 388 and 393 of Garcia for details.
; For research and educational use only
extensions[array] ; This extension adds arrays to NetLogo
globals [vel_hist slope corr sum_vel sample] ; vel_hist is the velocity distribution histogram
turtles-own [v vx vy]
; Called by "Setup Agents"
to setup
clear-all ; Clear everything
set sample 0
set vel_hist array:from-list n-values 13 [0] ; Used to break the environment into 13 columns
crt Number_of_Particles ; Create and initialize particles throughout the environment
[set heading (random 360) set v (sqrt Temperature) * 1.2533 ; Constant is from theory (see Chapter 4)
set vx (v * cos heading) set vy (v * sin heading)
set color white set size 1.5
setxy (7 * random-xcor / 8) (7 * random-ycor / 8)]
ask patches [setup-patches] ; Ask patches to initialize two vertical walls
setup-plot ; Initialize the velocity distribution histogram
monitor ; Update the information for the histogram
compute-stats ; Compute slope and correlation coefficient of velocity histogram
reset-ticks
end
to setup-patches ; Setup two vertical walls
if ((pxcor = (max-pxcor - 0)) or (pxcor = (max-pxcor - 1)) or (pxcor = (max-pxcor - 2))) [set pcolor red]
if ((pxcor = (min-pxcor + 0)) or (pxcor = (min-pxcor + 1)) or (pxcor = (min-pxcor + 2))) [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]
tick
ask turtles [go-particles] ; All particles update their velocity
ask turtles [move] ; All particles move
monitor ; Update the information for the histogram
do-plot ; Redraw the histogram
compute-stats ; Compute slope and correlation coefficient of velocity histogram
end
to go-particles
let friends other turtles in-radius 2 ; Anyone near you?
if (any? friends) [ ; If so, assume a collision
let friend [who] of one-of friends ; For details, see Chapter 4 of the book
let rel_speed sqrt (((vx - ([vx] of turtle friend)) ^ 2 +
((vy - ([vy] of turtle friend)) ^ 2)))
let cm_vel_x 0.5 * (vx + ([vx] of turtle friend))
let cm_vel_y 0.5 * (vy + ([vy] of turtle friend))
let theta (random 360)
let costh (cos theta)
let sinth (sin theta)
let vrel_x (rel_speed * sinth)
let vrel_y (rel_speed * costh)
set vx (cm_vel_x + 0.5 * vrel_x) ; Figure out the new velocities for yourself and your neighbor
set vy (cm_vel_y + 0.5 * vrel_y)
ask turtle friend [set vx (cm_vel_x - 0.5 * vrel_x)
set vy (cm_vel_y - 0.5 * vrel_y)]
]
; Compute the effect of the walls on particle velocity
if (any? patches in-radius 1 with [pcolor = red]) ; The red wall moves up
[set vx (- (sqrt (2 * Temperature)) * (sqrt (- ln (random-float 1.0))))
set vy (((random-normal 0.0 1.0) * (sqrt Temperature)) + Wall_Velocity)]
if (any? patches in-radius 1 with [pcolor = yellow]) ; The yellow wall moves down
[set vx ((sqrt (2 * Temperature)) * (sqrt (- ln (random-float 1.0))))
set vy (((random-normal 0.0 1.0) * (sqrt Temperature)) - Wall_Velocity)]
if ((vx != 0) or (vy != 0)) [set heading atan vx vy]
end
to move ; The particles move with velocity v
set v sqrt (vx * vx + vy * vy)
fd v
end
to monitor ; Update the velocity distribution for the histogram
if (sample = 0) [set sum_vel 0]
foreach [0 1 2 3 4 5 6 7 8 9 10 11 12] [
if (sample = 0) [array:set vel_hist ? 0]
let column (turtles with [((xcor > (min-pxcor + (? * 2 * max-pxcor / 13))) and
(xcor < (min-pxcor + ((? + 1) * 2 * max-pxcor / 13))))])
if (any? column) [array:set vel_hist ? ((array:item vel_hist ?) + (mean [vy] of column))]
]
set sum_vel (sum_vel + (sum [v] of turtles))
set sample sample + 1
end
to setup-plot ; Setup the histogram
set-current-plot "Distribution of Velocities"
end
to do-plot ; Draw the histogram
clear-plot
set-plot-x-range 0 780 ; 540
set-plot-y-range (- Wall_Velocity) (Wall_Velocity + 0.001)
set-current-plot-pen "pen0"
plotxy 0 (array:item vel_hist 0) / sample
set-current-plot-pen "pen1"
plotxy 60 (array:item vel_hist 1) / sample
set-current-plot-pen "pen2"
plotxy 120 (array:item vel_hist 2) / sample
set-current-plot-pen "pen3"
plotxy 180 (array:item vel_hist 3) / sample
set-current-plot-pen "pen4"
plotxy 240 (array:item vel_hist 4) / sample
set-current-plot-pen "pen5"
plotxy 300 (array:item vel_hist 5) / sample
set-current-plot-pen "pen6"
plotxy 360 (array:item vel_hist 6) / sample
set-current-plot-pen "pen7"
plotxy 420 (array:item vel_hist 7) / sample
set-current-plot-pen "pen8"
plotxy 480 (array:item vel_hist 8) / sample
set-current-plot-pen "pen9"
plotxy 540 (array:item vel_hist 9) / sample
set-current-plot-pen "pen10"
plotxy 600 (array:item vel_hist 10) / sample
set-current-plot-pen "pen11"
plotxy 660 (array:item vel_hist 11) / sample
set-current-plot-pen "pen12"
plotxy 720 (array:item vel_hist 12) / sample
end
to compute-stats ; Compute slope and correlation coefficient of velocity histogram
let xbar 6.0 let ybar 0
let sxy 0 let sx 0 let sy 0
foreach [0 1 2 3 4 5 6 7 8 9 10 11 12] [
set ybar (ybar + (array:item vel_hist ?) / sample)
]
set ybar (ybar / 13)
foreach [0 1 2 3 4 5 6 7 8 9 10 11 12] [
set sxy (sxy + ((? - xbar) * (((array:item vel_hist ?) / sample) - ybar)))
set sx (sx + ((? - xbar) ^ 2))
set sy (sy + (((array:item vel_hist ?) / sample) - ybar) ^ 2)
]
set slope (sxy / sx)
set corr (sxy / ((sqrt sx) * (sqrt sy)))
end