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