Being Kevin Bacon NetLogo Model
Produced for the book series "Artificial Intelligence";
Author: W. J. Teahan; Publisher: Ventus Publishing Aps, Denmark.
powered by NetLogo
view/download model file: Being-Kevin-Bacon.nlogo
WHAT IS IT?
This model applies various algorithms to the problem of searching for a specific goal node in a network. The problem is that you do not know where the node is, or how the network is configured. To solve this problem, search needs to be employed to try out the different paths that might lead to the goal node. This model implements some multi-agent based solutions where knowledge is shared between agents in a dynamic way. These can be applied to this problem separately to see how they perform against each other.
The model uses "Kevin Bacon" in its title as Kevin Bacon has been chosen as the "centre" of the Hollywood Universe based on the catch-phrase "degrees of separation from Kevin Bacon". This catch-phrase is based on the related mathematical pastime of measuring the degrees of separation of mathematicians from Paul Erdos, a well-known Hungarian mathematician who was prolific at publishing papers. Paul Erdos has been chosen as the focal point for measuring how well connected a person is amongst the mathematical community. The degrees of separation measure is based on whether as person has published a paper with Paul Erdos (which equates to an Erdos number of 1), or if not then published a paper with someone who has published a paper with Paul Erdos (an Erdos number of 2), or if not then published a paper with someone who has published a paper with someone who has published a paper with Paul Erdos (an Erdos number of 3), and so on.
The model allows the user to select either Paul Erdos or Kevin Bacon as the "centre of the universe". Then it can measure the average degree of separation using Dijkstra's algorithm, or it can search for the node associated with these persons using various distributed algorithms for sharing of knowledge between agents, such as word-of-mouth.
WHAT IS ITS PURPOSE?
The purpose of this model is to demonstrate some important concepts in relation to communication amongst agents in a network such as the small world phenomenon, degrees of separation, super-nodes in peer to peer networks and communication via word-of-mouth.
HOW IT WORKS
The model implements the search algorithms in a novel way by making use of an agent-oriented approach which is relatively easy to implement in NetLogo. The model adopts a purely agent-oriented solution where the information is distributed amongst NetLogo agents. Unlike the traditional search algorithms (such as uninformed searches like Breadth-first Search, and Depth-first Search, or the informed searches such as Greedy Best-first Search and A* that are implemented in the Searching for Kevin Bacon model), these agents conduct the search by sharing knowledge with other agents that are concurrently conducting the search. In the word-of-mouth knowledge sharing method, if agents have found the goal, then they share their knowledge with other agents they meet while returning to their start destination. With the blackboard method, the agents share their knowledge by writing what they know into communal "blackboards" that are found at each node. This can then subsequently be read by agents who visit the node latter on. Two further knowledge sharing methods combine these two approaches - word-of-mouth and blackboard - in slightly different ways to create two new hybrid knowledge sharing schemes.
A breed of walker turtle agents is used for the agents that move throughout the maze trying to get to the goal. These searcher agents maintain information about the current state of the search such as the path they have taken. Each searcher agent expands the search by following the outgoing paths that lead out of the current node that were suggested as a result of the method of knowledge sharing they adopt.
A breed of dwalker agents are used to walk the network during the execution of Dijkstra's algorithm. This can be used to calculate the degree of separation for every node in the network from the goal node.
HOW TO USE IT
To initialise the search and create a random network (whose type is specified by the network-type chooser), press the setup-network button in the Interface. To setup a walker agent to search the network, first press the reset-blackboards and reset-walkers buttons to clear blackboards and remove any existing walkers, then press the setup-walkers button to create new ones. Several walker turtle agents (whose number is specified by the new-walkers-per-tick slider) will then be created and randomly located through the network. The setup-walkers button can be pressed multiple times if you wish more walkers to start the search.
To start the simulation, either press the go-walkers once button to make the search proceed one step at a time, or press the go-walkers button to make the search proceed continuously. The walkers will continue walking the network until they find the goal node or they expire without success if they have exceeded the time-to-live slider value. The links that the walker agents traverse across are briefly thickened to show the paths the agents are taking as they proceed in their search.
To plot the shortest path distances and find the average degree of separation from the goal node using Dijkstra's algorithm, press the go-dijkstra button.
THE INTERFACE
The model's Interface buttons are defined as follows:
- setup-network: This will clear the environment and all variables, and create a random network, whose type is specified by the network-type chooser. Its layout is specified by the layout-type chooser. The four sliders no-of-nodes, no-of-super-nodes, links-per-node and links-per-super-node control the number of nodes and super-nodes, and the number of links between them.
- change-layout: If the layout is of type spring, then this may help to remove some of the clutter.
- go-dijkstra: This plots the shortest path distances and find the average degree of separation from the goal node using Dijkstra's algorithm. The goal node is specified using the centre-of-the-universe chooser.
- reset-blackboards: This resets the blackboards that are associated with each node in the network. This is used by the Blackboard knowledge sharing mechanism.
- setup-walkers: This creates new walkers as specified by the number in the slider new-walkers-per-tick. These walkers will then start walking around the network trying to find the goal node.
- go-walkers-once: This will make the simulation proceed one step at a time.
- go-walkers-forever: This will make the simulation proceed continuously until it has reached the goal node or it gets stuck.
- reset-walkers: This kills off all existing searchers and creates new ones to restart the search as specified by the number in the slider new-walkers-per-tick.
- dump-blackboards: This will dump the contents of all the blackboards in the network (this can be used for debugging purposes).
- load-blackboards: This pre-loads the blackboards for each node using the shortest paths found using the Dijkstra algorithm. (This will improve the performance of the Blackboard knowledge sharing mechanism).
The model's Interface choosers, sliders, and switches are defined as follows:
- animate-dijkstra: This will animate the execution of Dijkstra's algorithm (that runs when the go-dijkstra button is pressed).
- revisits-allowed: If set to On, this will allow the agents to revisit already visited nodes.
- centre-of-the-universe: This sets the goal node that the agents are trying to find. It can be set to either Paul Erdos or Kevin Bacon. (These nodes are randomly created when the network is created).
- knowledge-sharing: This specifies the type of knowledge sharing the agents employ while walking around the network. The types of knowledge-sharing is as follows:
"None": The agents do not exchange any knowledge with other agents. As a result, the agents end up randomly walking around the network.
"Word-of-mouth": If the agents have found the goal, then they share their knowledge with other agents they meet while returning to their start destination.
"Blackboard": The agents share their knowledge by writing what they know into communal "blackboards" that are found at each node. This can then subsequently be read by agents who visit the node latter on.
"Combined 1" and "Combined 2": These combine the knowledge of the word-of-mouth and blackboard approaches in slightly different ways to create two new hybrid knowledge sharing schemes. The first scheme checks the blackboard first, then defaults to the word-of-mouth scheme if no knowledge exists in the blackboard. The second scheme does the reverse - it will apply word-of-mouth knowledge first before defaulting to the blackboard knowledge.
- network-type: This selects the type of network that is created when the setup-network button is pressed. The type of networks are as follows:
"P2P-no-super-nodes": This simulates a peer-to-peer network with no super-nodes.
"P2P-has-super-nodes": This simulates a peer-to-peer network with super-nodes.
"P2P-random-single-link": This simulates a peer-to-peer network where each node has only one link with another random node.
"P2P-incremental": This creates the simulated peer-to-peer network by incrementally building the links to other random nodes one at a time.
"P2P-incremental-1": This creates the simulated peer-to-peer network by incrementally building links to other random nodes.
"Star-central-hub": This creates a network with one node (the Kevin Bacon node; i.e. the goal node) as the central hub and all other nodes linked to it and not to any other node.
"Hierarchical": This creates a tree network with the Kevin Bacon goal node at the root.
- layout-type: This specifies how the network should be laid out when it is visualised.
- no-of-nodes: This is the number of nodes to place in the network.
- no-of-super-nodes: This is the number of super-nodes to place in the network. (These are nodes that usually will have significantly more links than standard nodes as specified by links-per-super-node slider).
- links-per-node: This specifies the maximum number of links a standard node will have. The actual number chosen for a particular node will be a random number between 1 and this number.
- links-per-super-node: This specifies the maximum number of links a super-node will have. The actual number chosen for a particular super-node will be a random number between 1 and this number.
- simulation-ticks: This specifies how long the simulation should run for.
- network-update: If non-zero, this will cause the network to be updated at an interval according to a random number from 0 up to the value of this slider.
- nodes-to-add: The number of nodes specified by this slider will be added to the network when the next update occurs according to the network-update slider.
- nodes-to-delete: The number of nodes specified by this slider will be deleted from the network when the next update occurs according to the network-update slider.
- new-walkers-per-tick: This sets the number of walker agents that are added each tick of the simulation.
- time-to-live: This sets how long the walker agents should remain active if they have not found the goal node before being killed off.
- new-walkers-per-node: This sets the number of walkers that are created to continue the search in multiple different directions when each walker visits each node. Setting this number higher than 1 will quickly flood the network in most circumstances.
- percent-in-both: When the network is created, a number of nodes will be created that are connected to the Paul Erdos node (i.e. a path exists that will eventually lead to Paul Erdos), and a number will be created that are connected to Kevin Bacon. This slider controls how many of the nodes will be doubly connected (i.e. paths exist from the node that will lead to both the Paul Erdos and Kevin Bacon nodes).
The model's Interface plots monitors (shown on the right) are defined as follows:
- Number of walkers: This plot shows the number of walkers per tick.
- Successful searches: This plot shows the number of successful searches (i.e. walkers that have found the goal node) per tick.
- Shortest path distances: This plot is plotted when the go-dijkstra button is pressed. It plots the shortest path distances from each node to the goal node.
- #Nodes: This monitor reports the number of nodes in the network. It will change if the network is updated when the network-update, nodes-to-add and nodes-to-delete sliders are all non-zero.
- #Walkers: This monitor reports the number of active walker agents in the network.
- #Visited: This monitor reports the number of nodes visited by the walker agents.
- %Success: This monitor reports the percentage of walker agents that have been successful in reaching the goal node.
THINGS TO NOTICE
Notice how well the agents perform at finding the goal node when the knowledge sharing method is set to None. Compare this with the other knowledge sharing methods.
Notice that the blackboard knowledge sharing mechanism usually outperforms the word of mouth mechanism in terms of the percentage of successful searches.
Notice that pre-loading the blackboards with shortest path information gained from execution of Dijkstra's algorithm can significantly improve the search.
Notice that when there is a learning effect due to the knowledge sharing mechanism, the Successful Searches plot will start to curve upwards rather then continue as a straight line. Why is this? What settings and type of networks does this occur for? Can you get the curve to bend downwards instead of upwards? (Hint: Try changing the value of one or two of the sliders mid-stream).
Notice how the effectiveness of the search deteriorates as the network changes when nodes are either added or deleted. Which type of knowledge sharing method seems to cope best with a dynamic network?
Notice the effect of turning the flag allow-revisited-states? On and Off. Why is turning it Off so effective at dramatically reducing the search for the different search behaviours?
Notice how the agents shown when the Dijkstra's algorithm is animated seem to jump all around the network. Why is this?
THINGS TO TRY
Which knowledge sharing behaviour seems to be the best at this problem? Which seems to be the worst? Try out each of the different knowledge sharing behaviours to see which one is the most effective.
Try setting low and high values for the time-to-live slider. How does this affect the percentage of successful searches and the number of nodes visited as a result?
Try pressing the setup-walkers button multiple times. This will start the search with more than one walker.
Try out all the different types of networks with different slider settings. Which types of network causes problems for the various knowledge sharing methods, and which do not? i.e. Which seem to be more difficult to search?
Try switching the knowledge sharing behaviour mid-stream to see if there is any noticeable effect. For example, try switching from a Word-of-Mouth sharing method to a Blackboard sharing method then back again.
EXTENDING THE MODEL
Try adding other knowledge sharing mechanisms, or adding your own variations to the ones implemented in the model.
Try adding your own type of network, either randomly created or with a correspondence to a network in real-life. You will need to add input routines to create the network layout for the latter.
Instead of having the walker agents searching for a single node in the network, try adding resources to each node so that the simulation is similar to the resource discovery problem where a resource (such as an MP3 file) might appear at multiple nodes throughout the network, and each node will have many resources (up to tens of 1000s). You will need to add a resources variable to the nodes-own field where the resources is a table that contains the names of the resources that the node holds locally.
Try turning off the visualisation of the network by using the hide-turtle command to hide all agents and links. This will allow you to run much larger simulations - up to 100,000s of nodes.
NETLOGO FEATURES
Note the use of the hatch and die commands to create new child walkers at each node and terminate all existing walkers. Note also how the next-locations-list parameter for the expand-walkers command determines the knowledge sharing strategy being used that defines the different searches.
RELATED MODELS
See the Searching for Kevin Bacon model.
CREDITS AND REFERENCES
This model was created by William John Teahan.
To refer to this model in publications, please use:
Being Kevin Bacon NetLogo model.
Teahan, W. J. (2010). Artificial Intelligence. Ventus Publishing Aps.
PROCEDURES
; Being Kevin Bacon model.
;
; Demonstrates communication in a network, Dijkstra's algorithm and the small world
; phenomenon.
;
; Copyright 2010 William John Teahan. All Rights Reserved.
extensions [ array table ]
breed [nodes node]
breed [walkers walker]
breed [dwalkers dwalker] ;; for performing the Dijkstra algorithm
nodes-own
[link-type ;; link type: erdos, bacon and both
blackboard ;; table used when the knowledge-sharing of the walkers = "Blackboard"
net-depth] ;; used when building some of the networks
walkers-own
[location ;; the node where the walker is located
path ;; the path taken by the walker
wom-path ;; the path suggested by another walker by "word-of-mouth"
goal ;; the goal node that the walker wants to reach
ticks-alive] ;; the number of ticks the walker has been alive
globals
[erdos-set ;; nodes linked with Paul Erdos node
bacon-set ;; nodes linked with Kevin Bacon node
paul-erdos ;; node associated with Paul Erdos
kevin-bacon ;; node associated with Kevin Bacon
paul-erdos-no ;; node number associated with Paul Erdos node
kevin-bacon-no ;; node number associated with Kevin Bacon node
network-update-count ;; used for controlling when the network gets updated
dijkstra-distances ;; shortest path distance from initial node to all other nodes
dijkstra-directions ;; which direction to head in for shortest path
nodes-visited ;; total number of nodes visited by all walkers
successful-searches ;; number of successful searches completed by the walkers
unsuccessful-searches ;; number of unsuccessful searches not completed by the walkers
max-distance ] ;; a number that exceeds the maximum possible distance in the network
to reset-counts
;; Resets the counts used in some of the plots.
set nodes-visited 0
set successful-searches 0
set unsuccessful-searches 0
end
to create-network [number-of-nodes]
;; Creates number-of-nodes new nodes in the network.
create-nodes number-of-nodes
[
set blackboard table:make ;; used by walkers if applying the blackboard knowledge sharing method
ifelse (random 100 < percent-in-both)
[ set link-type 0 ;; both erdos and bacon node
set color red
set label (word "eb" who " ") ]
;else
[ ifelse (random 2 = 0)
[ set link-type 1 ;; erdos node
set color lime
set label (word "e" who " ") ]
[ set link-type 2 ;; bacon-node
set color blue
set label (word "b" who " ") ]]
]
set erdos-set nodes with [link-type = 1 or link-type = 0] ;; erdos nodes
set bacon-set nodes with [link-type = 2 or link-type = 0] ;; bacon nodes
end
to setup-network
clear-all
set-default-shape nodes "circle 2"
set-default-shape dwalkers "person"
;; create a random network
reset-counts
set max-distance 9999999 ;; this number must be greater than maximum path length in the network
if (network-update > 0) [ set network-update-count random network-update ]
create-network no-of-nodes
set paul-erdos min-one-of erdos-set [ who ]
set kevin-bacon min-one-of bacon-set [ who ]
ask paul-erdos [ set color magenta set paul-erdos-no who ]
ask kevin-bacon [ set color orange set kevin-bacon-no who ]
create-network-links
reset-layout
end
to create-network-links
;; creates the network links for the nodes that have none
;; according to the network-type
ifelse (network-type = "P2P-no-supernodes")
[ create-network-P2P-no-super-nodes ]
[ ifelse (network-type = "P2P-has-super-nodes")
[ create-network-P2P-has-super-nodes ]
[ ifelse (network-type = "P2P-random-single-link")
[ create-network-P2P-random-single-link ]
[ ifelse (network-type = "P2P-incremental")
[ create-network-P2P-incremental ]
[ ifelse (network-type = "P2P-incremental-1")
[ create-network-P2P-incremental-1 ]
[ ifelse (network-type = "Star-central-hub")
[ create-network-star-central-hub ]
[ create-network-hierarchical]]]]]]
end
to reset-layout
clear-drawing
layout
;; leave space around the edges
ask nodes [ setxy 0.95 * xcor 0.95 * ycor ]
end
to change-layout
ask walkers [ die ] ;; kill off all current walkers as where their current location may no longer be a correct node position
reset-layout
end
to layout
ifelse layout-type = "spring"
[ ifelse (network-type = "P2P-no-supernodes" or network-type = "P2P-has-super-nodes")
;;incremental" or network-type = "P2P-incremental-1" or network-type = "hierarchical")
[ repeat 500 [ layout-spring nodes links 0.1 9 5 ]]
[ repeat 500 [ layout-spring nodes links 0.5 2 1 ]]]
;;else
[ ifelse layout-type = "circle"
[ let radius ifelse-value (max-pxcor <= max-pycor) [max-pxcor - 1] [max-pycor - 1]
layout-circle nodes radius ]
[ ifelse (centre-of-the-universe = "Paul Erdos")
[ layout-radial nodes links paul-erdos ]
[ layout-radial nodes links kevin-bacon ]]
]
end
to update-network
;; updates the network by adding or deleting nodes
if (network-update > 0)
[
ifelse (network-update-count > 0)
[ set network-update-count network-update-count - 1 ] ;; count down to next update
[ ;; delete some random nodes first
if (nodes-to-delete > 0) and (nodes-to-delete < count nodes)
[ ask n-of nodes-to-delete nodes
[ if self != paul-erdos and self != kevin-bacon ;; don't delete Paul Erdos or Kevin Bacon
[ ask my-links [ die ]
ask walkers-here [ die ]
die ]]]
;; now add in new nodes at random
if (nodes-to-add > 0)
[ create-network nodes-to-add
create-network-links ]
set network-update-count random network-update ;; reset count down to next update
]
]
end
to create-network-P2P-no-super-nodes
;; creates a P2P (peer-to-peer) layout without "super-nodes"
let erdos-count count erdos-set
let bacon-count count bacon-set
let erdos-links ifelse-value (links-per-node < erdos-count) [links-per-node] [erdos-count]
let bacon-links ifelse-value (links-per-node < bacon-count) [links-per-node] [bacon-count]
let n 0
ask erdos-set
[ if count my-links = 0
[ set n random (erdos-links - 1) + 1
create-links-with n-of n other erdos-set ]];; create at least one link, but not to itself
ask bacon-set
[ if count my-links = 0
[ set n random (bacon-links - 1) + 1
create-links-with n-of n other bacon-set ]];; create at least one link, but not to itself
end
to create-network-P2P-has-super-nodes
;; creates a P2P (peer-to-peer) layout without "super-nodes"
let erdos-count count erdos-set
let bacon-count count bacon-set
let erdos-links ifelse-value (links-per-node < erdos-count) [links-per-node] [erdos-count]
let bacon-links ifelse-value (links-per-node < bacon-count) [links-per-node] [bacon-count]
let erdos-slinks ifelse-value (links-per-super-node < erdos-count - 1) [links-per-super-node] [erdos-count - 1]
let bacon-slinks ifelse-value (links-per-super-node < bacon-count - 1) [links-per-super-node] [bacon-count - 1]
let n 0
ask erdos-set
[ if count my-links = 0
[ set n random erdos-links + 1
create-links-with n-of n other erdos-set ]];; create at least one link, but not to itself
ask bacon-set
[ if count my-links = 0
[ set n random bacon-links + 1
create-links-with n-of n other bacon-set ]];; create at least one link, but not to itself
;; now create super-nodes, making sure paul erdos and kevin bacon are included
ask paul-erdos
[ if count my-links = 0
[ set n random erdos-slinks + 1 ;; create at least one link
create-links-with n-of n other erdos-set ]] ;; but not to itself
ask kevin-bacon
[ if count my-links = 0
[ set n random bacon-slinks + 1 ;; create at least one link
create-links-with n-of n other bacon-set ]] ;; but not to itself
ask n-of (no-of-super-nodes - 1) erdos-set
[ if count my-links = 0
[ set n random erdos-slinks + 1 ;; create at least one link
create-links-with n-of n other erdos-set ]] ;; but not to itself
ask n-of (no-of-super-nodes - 1) bacon-set
[ if count my-links = 0
[ set n random bacon-slinks + 1 ;; create at least one link
create-links-with n-of n other bacon-set ]] ;; but not to itself
end
to create-network-P2P-random-single-link
ask erdos-set
[ if count my-links = 0
[ create-link-with one-of other erdos-set ]]
ask bacon-set
[ if count my-links = 0
[ create-link-with one-of other bacon-set ]]
end
to create-network-P2P-incremental
let erdos-set1 (list paul-erdos)
let bacon-set1 (list kevin-bacon)
foreach but-first sort erdos-set
[ ask ?
[ if count my-links = 0
[ create-link-with one-of erdos-set1
set erdos-set1 fput ? erdos-set1 ]]]
foreach but-first sort bacon-set
[ ask ?
[ if count my-links = 0
[ create-link-with one-of bacon-set1
set bacon-set1 fput ? bacon-set1 ]]]
end
to create-network-P2P-incremental-1
ask nodes [ set net-depth 0 ]
ask paul-erdos
[ create-link-with one-of other erdos-set
ask link-neighbors [set net-depth 1 ]]
ask erdos-set
[ if (net-depth = 0) and (count my-links = 0)
[
create-link-with one-of erdos-set with [net-depth = 1]
set net-depth 1
]
]
ask kevin-bacon
[ create-link-with one-of other bacon-set
ask link-neighbors [set net-depth 1 ]]
ask bacon-set
[ if (net-depth = 0) and (count my-links = 0)
[
create-link-with one-of bacon-set with [net-depth = 1]
set net-depth 1
]
]
end
to create-network-star-central-hub
let erdos-count-1 count erdos-set - 1
let bacon-count-1 count bacon-set - 1
ask paul-erdos
[ if count my-links = 0
[ create-links-with n-of erdos-count-1 other erdos-set ]]
ask kevin-bacon
[ if count my-links = 0
[ create-links-with n-of bacon-count-1 other bacon-set ]]
end
to create-network-hierarchical
ask nodes [ set net-depth 0 ]
ask paul-erdos ;; root of Paul Erdos sub-network
[ set net-depth 1
ifelse (count other erdos-set < links-per-node)
[ create-links-with other erdos-set ]
[ create-links-with n-of links-per-node other erdos-set ]
ask link-neighbors [ set net-depth 2 ]]
let depth 2
let this-links 0
let this-count 0
while [count erdos-set with [net-depth = 0] > 0] ;; while still more nodes to place in network
[ ask erdos-set with [net-depth = depth]
[ set this-count count erdos-set with [net-depth = 0]
set this-links ifelse-value (links-per-node < this-count) [links-per-node] [this-count]
create-links-with n-of this-links erdos-set with [net-depth = 0]
ask link-neighbors [ set net-depth depth + 1 ]]
set depth depth + 1]
ask nodes [ set net-depth 0 ]
ask kevin-bacon ;; root of Kevin-Bacon sub-network
[ set net-depth 1
ifelse (count other bacon-set < links-per-node)
[ create-links-with other bacon-set ]
[ create-links-with n-of links-per-node other bacon-set ]
ask link-neighbors [ set net-depth 2 ]]
set depth 2
set this-links 0
set this-count 0
while [count bacon-set with [net-depth = 0] > 0] ;; while still more nodes to place in network
[ ask bacon-set with [net-depth = depth]
[ set this-count count bacon-set with [net-depth = 0]
set this-links ifelse-value (links-per-node < this-count) [links-per-node] [this-count]
create-links-with n-of this-links bacon-set with [net-depth = 0]
ask link-neighbors [ set net-depth depth + 1 ]]
set depth depth + 1]
end
to reset-blackboards
;; resets the blackboards at each node
ask nodes [ table:clear blackboard ]
end
to dump-blackboards
;; dumps out the blackboards at each node
ask nodes [ type "Blackboard at " print self print table:to-list blackboard ]
end
to setup-walkers
;; creates some new walkers
create-walkers new-walkers-per-tick
[
set color red
set goal one-of nodes
set location one-of nodes
move-to location
set path (list location)
set wom-path []
set ticks-alive 0
]
end
to reset-walkers
;; resets the walkers by first killing off all existing ones, then
;; creating new ones, and resetting related counts and plots
ask walkers [ die ] ;; kill off existing walkers
ask links [ set thickness 0 ] ;; reset all network links to uncrossed
reset-counts
setup-walkers
set-current-plot "Number of walkers"
clear-plot
set-current-plot "Successful searches"
clear-plot
reset-ticks
end
to expand-walkers [new-locations-list]
let new-walkers-count length new-locations-list
let new-location 0
hatch-walkers new-walkers-count
[ ;; create a new walker at location to continue the search
;; and move to new location
set ticks-alive ticks-alive + 1
; print ticks-alive
set new-location first new-locations-list ;; pop off the next location to visit
set new-locations-list but-first new-locations-list
ifelse (not revisits-allowed and member? new-location path)
[ die ] ;; don't revisit nodes already visited unless allowed to
[
if (new-location != nobody) and ([link-with new-location] of location != nobody)
[
ask [link-with new-location] of location [ set thickness 0.4 ] ;; highlight link I am crossing
face new-location ;; not strictly necessary, but improves the visuals a bit
move-to new-location
set location new-location
set path fput new-location path
if new-location = goal ;; success - no need to hang around any longer
[ set successful-searches successful-searches + 1
update-along-path self "S" ;; update information along path if necessary; "S" means success
die ] ;; die happy
]
]
]
end
to go-walkers
;; make the walkers continue the search
if (simulation-ticks > 0) and (ticks > simulation-ticks)
[ stop ]
update-network
setup-walkers
ask links [ set thickness 0 ]
ask walkers
[
set nodes-visited nodes-visited + 1
ifelse (ticks-alive >= time-to-live) ;; lived too long without success - kill it off
[ set unsuccessful-searches unsuccessful-searches + 1
update-along-path self "F";; update information along path if necessary; "F" means failure
]
[ ;; create new walkers to move to new location(s)
expand-walkers (next-locations location)
]
die ;; always die - the minions have already been sent out to continue the search for me
]
plot-walkers
tick
end
to-report next-locations [this-location]
;; find out the new locations to search for this-location
;; apply the search method using the knowledge sharing method or none e.g. choose randomly
if (knowledge-sharing = "Word of mouth")
[ ;; Word of mouth knowledge sharing method
report next-locations-word-of-mouth this-location
]
if (knowledge-sharing = "Blackboard")
[ ;; Blackboard knowledge sharing method
report next-locations-blackboard this-location
]
if (knowledge-sharing = "Combined 1")
[ ;; Blackboard knowledge sharing method
report next-locations-combined-1 this-location
]
if (knowledge-sharing = "Combined 2")
[ ;; Blackboard knowledge sharing method
report next-locations-combined-2 this-location
]
;; Default method is No knowledge sharing; i.e. knowledge-sharing = "None"
report next-locations-no-knowledge-sharing this-location
end
to-report next-locations-no-knowledge-sharing [this-location]
;; returns the new locations to search for this location
;; uses random choices; no knowledge sharing
let new-locations [link-neighbors] of this-location
if count new-locations > new-walkers-per-node
[ set new-locations n-of new-walkers-per-node new-locations ]
report sort new-locations
end
to-report next-locations-word-of-mouth [this-location]
;; returns the new locations to search for this location
;; using the word-of-mouth knowledge sharing method
if empty? wom-path
[ ask walkers-here
[ ;; does any of them know where the goal is?
if (this-location = first path) and (member? [goal] of myself path)
[ ask myself
[ set wom-path but-first path ]
;; type "asked " type who type " goal = " type [goal] of myself type " this-loc = " type this-location type " path = " print path
stop ]
]
]
if not empty? wom-path
[ ;; we have been told where to go
;; head back along the word of mouth path
let this-loc first wom-path
set wom-path but-first wom-path
;; type "found goal " type goal type " at " type this-loc type " in path " print wom-path
report (list this-loc)
]
;; no word of mouth path; default to random choices (i.e. same as no knowledge sharing)
report next-locations-no-knowledge-sharing this-location
end
to-report next-locations-blackboard [this-location]
;; returns the new locations to search for this location
;; using the blackboard knowledge sharing method
;;type "Blackboard for location " type this-location type " = " print [blackboard] of this-location
let dist 0
let this-path nobody
let key-dist (word ([goal] of self) " dist")
let key-path (word ([goal] of self) " path")
ifelse (not table:has-key? [blackboard] of this-location key-path)
[ set dist max-distance ] ;; no blackboard path
[ set dist table:get [blackboard] of this-location key-dist
set this-path table:get [blackboard] of this-location key-path ]
ifelse (dist >= max-distance)
[ ;; no blackboard path; default to random choices (i.e. same as no knowledge sharing)
report next-locations-no-knowledge-sharing this-location ]
[ ;; follow the blackboard path that has been found to be shortest
report (list this-path) ]
end
to-report next-locations-combined-1 [this-location]
;; returns the new locations to search for this location
;; using the combined-1 knowledge sharing method
let dist 0
let this-path nobody
let key-dist (word ([goal] of self) " dist")
let key-path (word ([goal] of self) " path")
ifelse (not table:has-key? [blackboard] of this-location key-path)
[ set dist max-distance ] ;; no blackboard path
[ set dist table:get [blackboard] of this-location key-dist
set this-path table:get [blackboard] of this-location key-path ]
ifelse (dist >= max-distance)
[ ;; no blackboard path; default to word-of-mouth
report next-locations-word-of-mouth this-location ]
[ ;; follow the blackboard path that has been found to be shortest
report (list this-path) ]
end
to-report next-locations-combined-2 [this-location]
;; returns the new locations to search for this location
;; using the combined-2 knowledge sharing method
if empty? wom-path
[ ask walkers-here
[ ;; does any of them know where the goal is?
if (this-location = first path) and (member? [goal] of myself path)
[ ask myself
[ set wom-path but-first path ]
;; type "asked " type who type " goal = " type [goal] of myself type " this-loc = " type this-location type " path = " print path
stop ]
]
]
if not empty? wom-path
[ ;; we have been told where to go
;; head back along the word of mouth path
let this-loc first wom-path
set wom-path but-first wom-path
;; type "found goal " type goal type " at " type this-loc type " in path " print wom-path
report (list this-loc)
]
;; no word of mouth path; default to blackboard
report next-locations-blackboard this-location
end
to update-along-path [this-walker value]
;; updates information along the path when the knowledge sharing method
;; is "Blackboard" or combined
let p 0
let val 0
let val1 0
let key-dist ""
let key-path ""
if knowledge-sharing = "Blackboard" or
knowledge-sharing = "Combined 1" or
knowledge-sharing = "Combined 2"
[
ask this-walker
[
;;type "goal = " type goal type " path = " show path
let this-goal goal
let prev first path
foreach but-first path
[
set key-dist (word this-goal " dist")
set key-path (word this-goal " path")
ifelse (value = "F")
[ set val max-distance ] ;; failure - node was not found
[ set val p + 1 ] ;; calculate the position in the path
;;type "putting into blackboard for node " type ? type " : " type key-dist type " val: " print val
if is-turtle? ? ;; does the node exist? (it may have been deleted)
[
ask ? ;; update blackboards along the path if path to goal is shorter
[ ifelse (not table:has-key? blackboard key-dist)
[ set val1 max-distance + 1 ] ;; no entry exists - make sure new entry is added
[ set val1 table:get blackboard key-dist ]
if (val < val1)
[ table:put blackboard key-dist val
table:put blackboard key-path prev ]]
]
set prev ?
set p p + 1
]
]
]
end
to plot-walkers
;; Reports results from data gathered by the walkers.
set-current-plot "Successful searches"
;;let total successful-searches + unsuccessful-searches
;;let s ifelse-value (total = 0) [0] [100 * successful-searches / total]
;;plot s
plotxy successful-searches + unsuccessful-searches successful-searches
set-current-plot "Number of walkers"
plot count walkers
end
to-report report-nodes
report count nodes
end
to-report report-walkers
report count walkers
end
to-report report-nodes-visited
report nodes-visited
end
to-report report-success-rate
report 100.0 * successful-searches / (successful-searches + unsuccessful-searches)
end
to initialise-distances [initial-node]
;; initialises the shortest path distances between nodes in the network to 0
let number-of-nodes max [who] of nodes + 1
set dijkstra-distances array:from-list n-values number-of-nodes [number-of-nodes + 1] ;; "infinity"
set dijkstra-directions array:from-list n-values number-of-nodes [nobody]
array:set dijkstra-distances initial-node 0 ;; set distance to 0 for initial node
end
to perform-dijkstra [initial-node nodes-to-visit]
;; calculates the distance array for the Dijkstra algorithm using the initial node
;; as the focal point
set nodes-visited 0
initialise-distances [who] of initial-node
let visited-set [] ;; this is the list of nodes that have been visited
let unvisited-set nodes-to-visit ;; this is the list of nodes yet to have been visited
let this-dwalker nobody
if (animate-dijkstra)
[ create-dwalkers 1 [ set color white set size 2 set this-dwalker who ]]
let current-node initial-node
while [count unvisited-set > 0]
[
if (animate-dijkstra)
[ ask dwalker this-dwalker [ setxy [xcor] of current-node [ycor] of current-node display wait 0.1 ]]
ask current-node
[
set nodes-visited nodes-visited + 1
set visited-set fput who visited-set
set unvisited-set other unvisited-set
ask link-neighbors
[
let dist-thru-here (array:item dijkstra-distances [who] of current-node) + 1
let dist-thru-to-there array:item dijkstra-distances who
if (dist-thru-here < dist-thru-to-there)
[ array:set dijkstra-distances who dist-thru-here
array:set dijkstra-directions who [who] of current-node ]
]
;; set the current-node to the remaining unvisited node that has the smallest distance to the initial node
set current-node min-one-of unvisited-set [array:item dijkstra-distances who]
]
]
;; print array:to-list dijkstra-distances
if (animate-dijkstra)
[ wait 0.2 ask dwalker this-dwalker [ die ]]
end
to go-dijkstra
;; Run directly by the interface button - calculates the distance array for the Dijkstra algorithm
let initial-node nobody
ifelse (centre-of-the-universe = "Paul Erdos")
[ set initial-node paul-erdos ] ;; set the initial node to the node associated with Paul Erdos
[ set initial-node kevin-bacon ] ;; set the initial node to the node associated with Kevin Bacon
initialise-distances [who] of initial-node
let nodes-to-visit [] ;; this is the list of nodes yet to have been visited
ifelse (centre-of-the-universe = "Paul Erdos")
[ set nodes-to-visit erdos-set ]
[ set nodes-to-visit bacon-set ]
perform-dijkstra initial-node nodes-to-visit
dump-dijkstra-directions
plot-dijkstra
end
to dump-dijkstra-directions
let i 0
foreach array:to-list dijkstra-directions
[
if (? != nobody) [ type " from: " type i type " thru: " type ? type " dist: " print array:item dijkstra-distances i ]
set i i + 1
]
end
to plot-dijkstra
;; Reports results from data gathered by execution of the dijkstra
;; algorithm.
set-current-plot "Shortest path distances"
clear-plot
let number-of-nodes report-nodes
let d array:to-list dijkstra-distances
let dmin number-of-nodes + 1
let dmax 0
let cnt 0
let avg-total 0
foreach d
[ ;; find min and max of x and y ranges for the plot first
;; also calculate cumulative total for average
if (? <= number-of-nodes)
[
set cnt cnt + 1
set avg-total ? + avg-total
if (? > dmax) [ set dmax ? ]
if (? < dmin) [ set dmin ? ]
]
]
set-plot-x-range 0 cnt
set-plot-y-range dmin dmax
foreach d
[ ;; now plot it
if (? <= number-of-nodes)
[ plot ? ]
]
user-message (word "The average path length to " centre-of-the-universe " is " (avg-total / cnt))
end
to load-blackboards-using-shortest-paths
;; pre-loads the blackboards for each node using the shortest paths
;; found using the Dijkstra algorithm
let i 0
let this-node nobody
let key-dist ""
let key-path ""
foreach sort nodes
[
set this-node ?
perform-dijkstra this-node nodes
set i 0
foreach array:to-list dijkstra-directions
[
if (? != nobody)
[ ;; type "goal: " type this-node type " from: " type i type " thru: " type ? type " dist: " print array:item dijkstra-distances i
set key-dist (word this-node " dist")
set key-path (word this-node " path")
table:put [blackboard] of node i key-dist (array:item dijkstra-distances i)
table:put [blackboard] of node i key-path node ?
ask node i
[
]
]
set i i + 1
]
]
end
;
; Copyright 2010 by William John Teahan. 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.
; b) this model will not be redistributed for profit without permission
; from William John Teahan.
; Contact William John Teahan for appropriate licenses for redistribution for
; profit.
;
; To refer to this model in publications, please use:
;
; Teahan, W. J. (2010). Being Kevin Bacon NetLogo model.
; Artificial Intelligence. Ventus Publishing Aps.
;