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 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.
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.
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.
; 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. ;