Searching for 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: Searching-for-Kevin-Bacon.nlogo
WHAT IS IT?
This model applies standard search 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 of the classic search algorithms and these can be applied to this toy problem to see how the different search strategies perform against each other.
WHAT IS ITS PURPOSE?
The purpose of this model is to show how some of the classic search algorithms such as breadth-first search and depth-first search can be implemented in NetLogo, and also how they can then be applied to solving a problem in order to compare how they perform.
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. Rather than use a queue data structure to implement the classic search algorithms (this is a standard solution; see, for example, Russell & Norvig's AI textbook), the model instead adopts a purely agent-oriented solution where the information is distributed amongst NetLogo agents. These agents conduct the search by transferring information to other agents that continue the search. Hence, an explicit queue data structure separate from what is happening in the search is not needed (although technically the information is still being stored in a queue behind the scenes, but the implementation of this is hidden behind the top-level commands that NetLogo provides).
The hope is that this "queueless" agent-oriented approach provides a more intuitive solution that makes it easier to grasp how the search strategies work. It uses a situated, embodied first person design perspective, therefore arguably making it easier to understand the essential differences between the search strategies.
The breed of searcher turtle agents is used for the searchers that move throughout the network trying to get to the goal. These searcher agents maintain information about the current state of the search such as the time taken and the path and estimated costs. Each searcher agent expands the search by following all outgoing paths that lead out of the current 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 searcher agent to search the network, press the reset-searchers button first, then press the setup-searcher button. A turtle agent with a shape of a person will be drawn at the node specified in the start-node input box.
To start the search, either press the go-searchers once button to make the search proceed one step at a time, or press the go-searchers button to make the search proceed continuously until it reaches the goal node or it gets stuck.
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.
- reset-searchers: This kills off all existing searchers and creates a new one as specified by the start-node-number Input box to restart the search.
- setup-searcher: This starts up a new searcher as specified by the start-node-number Input box (this can be used to create multiple searchers at the start of the search).
- go-searchers-once: This will make the search proceed one step at a time.
- go-searchers-forever: This will make the search proceed continuously until it has reached the goal node or it gets stuck.
The model's Interface choosers, sliders, switch and Input box are defined as follows:
- network-type: This selects the type of network that is created when the setup-network button is pressed. The types 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.
- search-behaviour: This specifies what search strategy the agents should employ when performing the search. A full description of the different search strategies can be found in Chapter 8 of the book Artificial Intelligence - Agent Behaviour I (see reference at the bottom of this Information).
- start-node-number: This is the node where the searcher agent is placed when it starts the search. Specifying 0 will mean that the searcher agent will be placed randomly in the network.
- heuristic: This specifies the heuristic to be used for the Informed searches - Greedy Best First Search and A* Search.
- max-agents-to-expand: This sets the maximum number of agents to expand the search each step. It is only used by the Multi-Agent Depth First Search.
- allow-revisited-states?: This is a flag that if set to On will allow the search to proceed to already visited states.
- max-depth: This sets the maximum depth of the search, for the depth-limited search and the Iterative Deepening Search only.
The model's Interface monitors are defined as follows:
- Active Searcher Agents: This shows the current number of active searcher agents still participating in the search.
- Maximum Active Searcher Agents: This shows the maximum value that the Active Searcher Agents monitor has achieved throughout the search.
- Total Searcher Agents: This shows the total number of searcher agents that the search has used.
- IDS Depth: This is the current depth during the execution of the Iterative Deepening Search.
THINGS TO NOTICE
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 that some of the searches if repeated with the same settings end up in different places. Why is this?
Notice that many of the behaviours result in the searching turtle agents getting stuck. When does this happen, and why?
THINGS TO TRY
Which search behaviour seems to be the best at this problem? Which seems to be the worst? Try out each of the different search behaviours to see which one is the most effective. Find out how well each search algorithm performs against the four evaluation criteria - time complexity, space complexity, optimality and complexity. Relate the theory to what happens in practice.
Try out all the different types of networks with different slider settings. Which types of network cause problems for the various searches, and which do not? i.e. Which seem to be more difficult to search?
Try switching the searching behaviour mid-stream. For example, try switching from a breadth-first search to a depth-first search then back again.
Try out the different heuristics for the informed searches (Greedy Best First Search and A* Search). Do they have any effect on how effective the search is?
EXTENDING THE MODEL
Try adding other search algorithms, 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.
NETLOGO FEATURES
Note the use of the hatch and die commands to clone child searchers and terminate parent searchers thus avoiding the need for a separate queue data structure to maintain the information during the search. Note also the variation in the ask command that determines the strategy being used that defines the different searches.
RELATED MODELS
For other search problems, see the Being Kevin Bacon model, the Missionaries and Cannibals model, and the Searching Mazes model. For an insight into the Manhattan distance and Euclidean distance metrics used as heuristics for the Informed searches, see the Manhattan Distance model.
CREDITS AND REFERENCES
This model was created by William John Teahan.
To refer to this model in publications, please use:
Searching for Kevin Bacon NetLogo model.
Teahan, W. J. (2010). Artificial Intelligence. Ventus Publishing Aps.
PROCEDURES
; Searching for Kevin Bacon model.
;
; Shows how agents can distribute information to aid network searches
; using word-of-mouth communication and blackboard communication.
;
; Copyright 2010 William John Teahan. All Rights Reserved.
breed [nodes node]
breed [searchers searcher]
nodes-own
[net-depth] ; used when building some of the networks
searchers-own
[location ; the node where the searcher is located
time ; time step
height ; used for hill climbing search
path-cost ; actual cost of search path so far (used for A-star search)
estimated-cost] ; estimated cost of cheapest path to goal
globals
[bacon-set ; nodes linked with Kevin Bacon node
kevin-bacon-node ; node associated with Kevin Bacon
kevin-bacon-xcor ; x co-ordinate of Kevin Bacon (goal node)
kevin-bacon-ycor ; y co-ordinate of Kevin Bacon (goal node)
search-time-step ; indicates what the current time step is during the search
visited-nodes ; indicates which nodes have aleady been visited - do not revisit them in that case
search-completed ; true when search is completed
searchers-used ; number of searcher agents used
max-active-searchers; maximum active searcher agents
path-found ; true if we have found a path to expand; e.g. used by DFS to signal a dead-end
person-colour ; colour of person shown doing the search in the visualisation
IDS-depth ] ; current depth limit for IDS (Iterative Deepening Search)
to create-network [number-of-nodes]
;; Creates number-of-nodes new nodes in the network.
create-nodes number-of-nodes
[ set color blue
set label (word "b" who " ") ]
set bacon-set nodes
end
to setup-network
clear-all
set-default-shape nodes "circle 2"
;; create a random network
create-network no-of-nodes
set kevin-bacon-node min-one-of bacon-set [ who ]
ask kevin-bacon-node
[ set color white
set size 3
set shape "star" ] ; Kevin Bacon is a star
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-super-nodes")
[ 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 ]
ask kevin-bacon-node ; recalculate Kevin Bacon's position
[ set kevin-bacon-xcor xcor
set kevin-bacon-ycor ycor ]
end
to change-layout
ask searchers [ die ] ;; kill off all current searchers 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-super-nodes" 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 ]
[ layout-radial nodes links kevin-bacon-node ]
]
end
to create-network-P2P-no-super-nodes
;; creates a P2P (peer-to-peer) layout without "super-nodes"
let bacon-count count bacon-set
let bacon-links ifelse-value (links-per-node < bacon-count) [links-per-node] [bacon-count]
let n 0
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 bacon-count count bacon-set
let bacon-links ifelse-value (links-per-node < bacon-count) [links-per-node] [bacon-count]
let bacon-slinks ifelse-value (links-per-super-node < bacon-count - 1) [links-per-super-node] [bacon-count - 1]
let n 0
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 kevin bacon is included
ask kevin-bacon-node
[ 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) 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 bacon-set
[ if count my-links = 0
[ create-link-with one-of other bacon-set ]]
end
to create-network-P2P-incremental
let bacon-set1 (list kevin-bacon-node)
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 kevin-bacon-node
[ 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 bacon-count-1 count bacon-set - 1
ask kevin-bacon-node
[ 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 kevin-bacon-node ;; 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 ]]
let depth 2
let this-links 0
let 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 setup-searcher
;; creates some new searchers
set search-completed false
if (visited-nodes = 0) ; not initialised yet
[ set visited-nodes []]
create-searchers 1
[
set size 2
set pen-size 3
set color magenta
set shape "person"
set person-colour magenta
ifelse (start-node-number = 0)
[ set location one-of nodes ] ; random start node
[ set location node start-node-number ]
set time search-time-step
move-to location
set height hill-height xcor ycor
]
set searchers-used searchers-used + 1
end
to reset-searchers
;; resets the searchers by first killing off all existing ones, then
;; creating new ones, and resetting related counts and plots
clear-drawing
ask searchers [ die ] ;; kill off existing searchers
set searchers-used 0
ask links [ set thickness 0 ] ;; reset all network links to uncrossed
setup-searcher
set search-completed false
set search-time-step 0
set max-active-searchers 1
set visited-nodes []
reset-ticks
end
to go-searchers
if (count searchers = 0)
[ user-message "Couldn't find Kevin Bacon:\nCan't find any more paths to search or no searchers to do search!"
stop ]
if search-completed
[ user-message "Found Kevin Bacon!"
stop ]
; uninformed search strategies (blind search)
if search-behaviour = "Breadth First Search"
[ expand-breadth-first-search ]
if search-behaviour = "Uniform Cost Search"
[ expand-depth-first-search ]
if search-behaviour = "Depth First Search"
[ expand-depth-first-search ]
if search-behaviour = "Multi-agent Depth First Search"
[ expand-MA-depth-first-search ]
if search-behaviour = "Depth Limited Search"
[ expand-depth-limited-search ]
if search-behaviour = "Iterative Deepening Search"
[ expand-iterative-deepening-search ]
; informed search strategies
if search-behaviour = "Greedy Best First Search"
[ expand-greedy-best-first-search ]
if search-behaviour = "A* Search"
[ expand-A-star-search ]
; local search strategies
if search-behaviour = "Hill Climbing Search"
[ expand-hill-climbing-search ]
set search-time-step search-time-step + 1
if (count searchers = 0)
[ user-message "No more searchers! Abort!"
stop ]
tick
end
to-report state [searcher-agent searcher-behaviour]
;; reports the state as a list of the current co-ordinates
report (list [xcor] of searcher-agent [ycor] of searcher-agent)
end
to-report goal-node [this-node]
;; returns true if the searcher agent has reached the goal
report this-node = kevin-bacon-node
end
to expand-breadth-first-search
; expand the search by adding more searcher-agents
ask searchers
[
expand-paths (searcher who)
die ; prune away parent agents used at lower time-steps
]
end
to expand-uniform-cost-search [curr-time]
; expand the search by adding more searcher-agents
set path-found false
ask first (sort-by [[path-cost] of ?1 < [path-cost] of ?2] searchers)
[
expand-paths (searcher who)
die ; this agent has done its work; it's children are now doing the work
]
end
to expand-depth-first-search
; expand the search by following newest path
; do not follow the other paths in parallel; just follow one of them
set path-found false
ask first (sort-by [[time] of ?1 > [time] of ?2] searchers)
[
expand-paths (searcher who)
die ; this agent has done its work; it's children are now doing the work
]
end
to expand-MA-depth-first-search
; expand the search by following longest path
; follow the other paths in parallel; but do not follow all of them
set path-found false
let agents ifelse-value (count searchers < max-agents-to-expand)
[ count searchers ]
[ max-agents-to-expand ]
ask n-of agents turtle-set (sort-by [[time] of ?1 > [time] of ?2] searchers)
[
expand-paths (searcher who)
die ; this agent has done its work; it's children are now doing the work
]
end
to expand-depth-limited-search
; expand the search by following longest path
; do not follow the other paths in parallel; just follow one of them
; limit the search depth to max-depth
expand-depth-limited-search-1 max-depth
end
to expand-depth-limited-search-1 [maxdepth]
; expand the search by following longest path
; do not follow the other paths in parallel; just follow one of them
; limit the search depth to maxdepth
set path-found false
ask first (sort-by [[time] of ?1 > [time] of ?2] searchers)
[
if (time <= maxdepth)
[ expand-paths (searcher who) ] ; only expand if not exceeded depth limit
die ; this agent has done its work; it's children are now doing the work
]
end
to expand-iterative-deepening-search
; expand the search by iteratively performing depth-limited-search
; to increasingly greater depths
set IDS-depth 1
set person-colour magenta
while [ IDS-depth <= max-depth ]
[
while [count searchers != 0]
[ expand-depth-limited-search-1 IDS-depth ]
set IDS-depth IDS-depth + 1
; change colour of person to reflect the increased maxdepth of search
if (person-colour > 5)
[ set person-colour person-colour - 5 ]
setup-searcher
]
set person-colour magenta ; restore default colour
end
to expand-greedy-best-first-search
; expand the search by adding more searcher-agents
set path-found false
ask first (sort-by [[estimated-cost] of ?1 < [estimated-cost] of ?2] searchers)
[
expand-paths (searcher who)
die ; this agent has done its work; it's children are now doing the work
]
end
to expand-A-star-search
; expand the search by adding more searcher-agents
set path-found false
ask first (sort-by [[estimated-cost + path-cost] of ?1 < [estimated-cost + path-cost] of ?2] searchers)
[
expand-paths (searcher who)
die ; this agent has done its work; it's children are now doing the work
]
end
to expand-hill-climbing-search
; expand the search using hill-climbing search method
set path-found false
ask searchers ; there should always be only one searcher at this stage
[ expand-paths (searcher who) ] ; look to see where I can go next
foreach but-first (sort-by [[height] of ?1 < [height] of ?2] searchers)
[ ; kill off all but the first
ask ? [ die ]; only let the best of the new searchers continue
]
end
to-report count-active-searchers
report count searchers
end
to-report maximum-active-searchers
let c count searchers
if (c > max-active-searchers)
[ set max-active-searchers c]
report max-active-searchers
end
to-report total-searchers
report searchers-used
end
to-report euclidean-distance [x y x1 y1]
;; reports the euclidean distance between points (x,y) and (x1,y1)
report sqrt ((x1 - x) ^ 2 + (y1 - y) ^ 2)
end
to-report manhattan-distance [x y x1 y1]
;; reports the euclidean distance between points (x,y) and (x1,y1)
report abs (x1 - x) + abs (y1 - y)
end
to-report heuristic-function [x y]
;; reports the heuristic evaluation function value
let goalx kevin-bacon-xcor
let goaly kevin-bacon-ycor
if (heuristic = "Zero")
[ report 0 ]
if (heuristic = "Euclidean distance")
[ report euclidean-distance x y goalx goaly ]
if (heuristic = "Manhattan distance")
[ report manhattan-distance x y goalx goaly ]
end
to-report hill-height [x y]
;; reports the "height" of the current search position
;; the zero height is the goal
report heuristic-function x y
end
to expand-paths [searcher-agent]
;; expands all the possible paths for the searcher-agent
foreach sort [link-neighbors] of [location] of searcher-agent
[ expand-path searcher-agent ? ]
end
to expand-path [searcher-agent node]
; the searcher-agent creates a new searcher-agent that draws a path in the network from its
; current position to the node
let xcor1 0
let ycor1 0
if not search-completed
[ ; create a new path by creating an agent to search it
; check to see if the path has already been visited
if allow-revisited-nodes? or not member? node visited-nodes
[
set path-found true
if not allow-revisited-nodes?
[set visited-nodes fput node visited-nodes] ; add to front of visited-nodes set
hatch-searchers 1
[ ; clone searcher
set searchers-used searchers-used + 1
set size 2
set pen-size 5
set color person-colour
set shape "person"
set xcor [xcor] of searcher-agent
set ycor [ycor] of searcher-agent
set xcor1 xcor ; copy xcor
set ycor1 ycor ; copy ycor
set heading [heading] of searcher-agent
set time [time] of searcher-agent + 1
set path-cost [path-cost] of searcher-agent
pen-down
; move to the node
set location node
move-to location
set xcor [xcor] of self
set ycor [ycor] of self
; increment path cost when executing the behaviour using Euclidean distance
set path-cost path-cost + euclidean-distance xcor1 ycor1 xcor ycor
set estimated-cost (heuristic-function xcor ycor)
set height hill-height xcor ycor
stamp
]
]
if goal-node node
[ set search-completed true ]
]
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). Searching For Kevin Bacon NetLogo model.
; Artificial Intelligence. Ventus Publishing Aps.
;