Searching for Kevin Bacon 2 NetLogo Model

Produced for the book series "Exercises for Artificial Intelligence";

Author: W. J. Teahan; Publisher: Ventus Publishing Aps, Denmark.

powered by NetLogo

view/download model file: Searching-for-Kevin-Bacon-2.nlogo

WHAT IS IT?

This NetLogo model is an extension to the Searching for Kevin Bacon model that has an Output box that provides an English description of the search problem, and provides a trace of how the search proceeds. Specific networks can also be saved to a file, and loaded latter into the application.

As with the Searching for Kevin Bacon model, 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 create your own network, set the network-type chooser to "User-specified". If the specify-coordinates? slider value is set to Off, then the user can then use the mouse to click on the points in the environment where they want the network nodes located. (The first point clicked will be designated as the goal node i.e. the Kevin Bacon node.) If the slider is set to On, then the user will be prompted for the x and y co-ordinates of the nodes. For each of the nodes in the network, the user will then be asked how many links there are from the node and which nodes link to it.

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

To save the network to a file, press the Save Network to a File button. To reload it at a letter date, press the Load Network from a File button. To generate a problem description (that could be used for an exam or test question, for example), then press the Generate Problem Description button. This will write the description into the Output box shown on the middle-right bottom of the Interface. To add further nodes to the network, press the Add to Network 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 specfied 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.

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

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

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

- change-layout: If the layout is of type spring, then this may help to remove some of the clutter.

- Generate Problem Description: This will generate a description in English of the search problem and write it into the Output box. The problem description is based on the values of the choosers and sliders in the Interface. It can be used for setting an exam or test question, or set an exercise for an assignment as course work.

- Add to Network: This will allow the user to add nodes to the network, including networks that have been generated randomly.

- Load Network from a File: This will load a network layout that has been previously saved to a file on disk.

- Save Network to a File: This will save the network layout to a file on disk. This can be loaded at a latter date using the Load Network from a File button.

The model's Interface choosers 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 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.
"Heirarchical": 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.

- search-behaviour: This specifies what search strategy the agents should emply when performing the search. A full description of the different search strategies can be found in Chapter 8 of Volume 1 of the Artificial Intelligence book (see reference at the bottom of this Information).

- heuristic: This specifies the heuristic to be used for the Informed searches - Greedy Best First Search and A* Search.

- start-node-number: This is the node where the searcher agent is placed when it starts the search. Specifying 0 will mean that the search agent will be placed randomly in the network.

The model's Interface sliders are defined as follows:

- node-size: This is the size used to draw the nodes in the network.

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

- max-depth: This sets the maximum depth of the search, for the depth-limited search and the Iterative Deepening Search only.

- link-thickness: This sets the thickness of the links that are drawn between the nodes in the network.

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

- spring-constant, spring-length, repulsion-constant: These sliders are used by the change-layout algorithm when the layout-type slider is set to spring and can be used to control how the network looks. For example, setting the spring-length to 0, then increasing it, will often unclutter the layout of the network.

The model's Interface switches are defined as follows:

- allow-revisited-states?: This is a switch that if set to On will allow the search to proceed to already visited states.

- specify-coordinates?: If this switch is set to On when the network-type slider is set to User-specified, then the user has to specify the precise co-ordinates of each node rather than using the mouse to point and click on a location.

- output-trace?: If this switch is set to On, then a trace of the search is written to the Output box (this is located to the middle-right at the bottom of the Interface).

The model's Interface monitors are defined as follows:

- IDS Depth: This is the current depth during the execution of the Iterative Deepening Search.

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


THINGS TO NOTICE

Notice the effect of turning the switch 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 aginst 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 causes 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 to follow how the informed searches, Greedy Best First and A*, search the various networks. Trace the searches as they proceed by turning the output-trace? switch to On. Work out how the path cost and estimated cost are calculated at each stage of the search. Try out the different heuristics. 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, Searching for Kevin Bacon 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 2 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
 searcher-that-found-goal
                     ; the searcher agent who found the goal
 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 init-node
;; initialises the node.

  set color white
  set size node-size
  ifelse (node-size <= 1)
    [ set label (word "n" who "   ") ]
    [ ifelse (node-size < 2)
      [ set label (word "n" who "      ") ]
      [ set label (word "n" who "        ") ]
    ]
end
  
to create-network [number-of-nodes]
;; Creates number-of-nodes new nodes in the network.

  create-nodes number-of-nodes [ init-node ]

  set bacon-set nodes
end

to init-network [num-nodes]
;; Initialises the network without the links.

  clear-all
  display
  set-default-shape nodes "circle 2"

  ;; create a random  or user-specified network
  create-network num-nodes

  set kevin-bacon-node min-one-of bacon-set [ who ]
  ask kevin-bacon-node
  [ set color white
    set size node-size + 1
    set shape "star 2"
  ] ; Kevin Bacon is a star
end

to setup-network
;; Sets up the network. (Called by the setup-network button)

  init-network no-of-nodes
    
  create-network-links
                
  if (network-type != "User-specified")
    [ reset-layout ]
end

to switch [this-case switch-list]
; pseudo switch statement (as NetLogo does not have one)  

  let p position this-case switch-list
  if (p + 1 < length switch-list)
    [ run (item (p + 1) switch-list) ]
end      

to create-network-links
;; creates the network links for the nodes that have none
;; according to the network-type

  switch network-type
    [ ; pseudo switch statement - execute the code on the right
      ; if network-type matches the string on the left
      "P2P-no-super-nodes"     "create-network-P2P-no-super-nodes"
      "P2P-has-super-nodes"    "create-network-P2P-has-super-nodes"
      "P2P-random-single-link" "create-network-P2P-random-single-link"
      "P2P-incremental"        "create-network-P2P-incremental"
      "P2P-incremental-1"      "create-network-P2P-incremental-1"
      "Star-central-hub"       "create-network-star-central-hub"
      "Heirarchical"           "create-network-hierarchical"
      "User-specified"         "create-network-user-specified"
    ]
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"
    [ repeat 500 [ layout-spring nodes links spring-constant spring-length repulsion-constant ]]
;;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 ]
    ]
  display
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
      [ set thickness link-thickness ]
    ] ;; 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
      [ set thickness link-thickness ]
    ] ;; 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
      [ set thickness link-thickness ]
    ] ;; 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
      [ set thickness link-thickness ]
    ] ;; 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
      [ set thickness link-thickness ]
    ]
  ]
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 thickness link-thickness ]
        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
    [ set thickness link-thickness ]
    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 thickness link-thickness ] 
      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
      [ set thickness link-thickness ]
    ]
  ]
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
        [ set thickness link-thickness ]
      ]
      [ create-links-with n-of links-per-node other bacon-set
        [ set thickness link-thickness ]
      ]
    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]
      [ set thickness link-thickness ]

      ask link-neighbors [ set net-depth depth + 1 ]]
    set depth depth + 1]
end

to-report enter-coordinate [x? node]
;; User entry routine for an x or y co-ordinate. If x? is true, then enters an x co-ordinate value,
;; otherwise enters a y co-ordinate value.

  let val 0
  let valid? false
  while [not valid?]
  [
    set val read-from-string user-input
      (word "Enter " (ifelse-value (x?) [ "x" ] [ "y" ]) " co-ordinate for node n" [who] of node)
    ifelse (x? and ((val < min-pxcor) or (val > max-pxcor))) or
       (not x? and ((val < min-pycor) or (val > max-pycor)))
      [ user-message "Invalid value entered - number is outside the permitted values as defined by the Settings. Please re-enter the value." ]
      [ set valid? true ]
  ]
  
  report val
end

to create-network-user-specified
; Lets the user set up the nodes in the network.

  let nodes-to-choose-from []
  let to-node nobody
  let from-node nobody
  let num-links 0
  let adj ""
  let n 0
  let done false

  ask nodes [ hide-turtle ]
  ifelse (specify-coordinates?)
    [ ; the user specifies the co-ordinates of each node
      foreach sort nodes
      [
        let x enter-coordinate true ?
        let y enter-coordinate false ?
        ask ?
        [
          setxy x y
          show-turtle
          if (output-trace?)
            [ output-print (word "Node n" ([who] of ?) " added at co-ordinates (" (precision xcor 2) "," (precision ycor 2) ").") ]
        ]        
      ]
    ]
    [ ; let the user specify where the nodes should be drawn using the mouse
      foreach sort nodes
      [ ; make sure the nodes are entered by the user in ascending order
        set done false
        ask ?
        [
          while [not done]
          [
            if mouse-down?
              [ setxy mouse-xcor mouse-ycor
                show-turtle
                set done true
              ]
          ]
          display
          while [mouse-down?] [wait 0.1]
          if (output-trace?)
            [ output-print (word "Node n" ([who] of ?) " added at co-ordinates (" (precision xcor 2) "," (precision ycor 2) ")") ]
        ]
      ]
    ]

  ; now create the links between the nodes
  foreach sort nodes
  [
    set num-links no-of-nodes
    set num-links user-one-of (word "How many links for " ? "? ") n-values (num-links + 1) [?]
    
    ; create a list of nodes to choose from
    ask ?
    [ set nodes-to-choose-from (sort other nodes) ]
    
    set n 1
    set from-node ?

    repeat num-links
    [
      ; choose the state to link to
      if-else (n = num-links)
        [ set adj ifelse-value (n = 1) ["one"] ["last"] ]
        [ set adj ifelse-value (n = 1) ["first"] ["next"] ]
      if-else (length nodes-to-choose-from = 1)
        [ set to-node first nodes-to-choose-from ]
        [ set to-node user-one-of (word "Choose the " adj " node that " from-node " links to: ") nodes-to-choose-from ]
      set nodes-to-choose-from remove to-node nodes-to-choose-from
      
      ask ?
      [
        ; create a link to the other node
         create-link-with to-node
         [ set thickness link-thickness ]
      ]
      set n n + 1
    ]
  ]
end

to setup-searcher
;; creates some new searchers

  let this-agent 0
  
  set search-completed false
  set searcher-that-found-goal nobody
  if (visited-nodes = 0) ; not initialised yet
    [ set visited-nodes []]
  create-searchers 1
  [
    set this-agent who
    set size node-size
    ifelse (link-thickness = 0)
      [ set pen-size 3 ]
      [ set pen-size link-thickness * patch-size * 2.5 ]
    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
  
  if (output-trace?)
    [ output-print (word "The searcher agent " this-agent " is starting at node " start-node-number ".") ]
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
  if (output-trace?)
    [ clear-output ]
  ask searchers [ die ] ;; kill off existing searchers
  set searchers-used 0
  ask links [ set thickness link-thickness ] ;; 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
    [
      if (output-trace?)
        [ output-print (word "Searcher agent " [who] of searcher-that-found-goal " has found the goal node n0.") ]
      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 node-size
              ifelse (link-thickness = 0)
                [ set pen-size 3 ]
                [ set pen-size link-thickness * patch-size * 2.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 (output-trace?)
                [ output-print (word "Expanding the search for searcher " [who] of searcher-agent
                                     " by hatching new searcher " who " at node n" [who] of node ".")
                  if (search-behaviour = "Hill Climbing Search")
                    [ output-print (word "Height of searcher " who " = " (precision height 2)) ]
                  if (search-behaviour = "Greedy Best First Search")
                    [ output-print (word "Path cost of searcher " who " = " (precision path-cost 2)) ]
                  if (search-behaviour = "A* Search")
                    [ output-print (word "(Path cost, estimated cost, combined cost) of searcher " who " = ("
                        (precision path-cost 2) ", " (precision estimated-cost 2) ", " (precision (path-cost + estimated-cost) 2) ")" ) ]
                  
                ]

             if goal-node node
               [ set search-completed true
                 set searcher-that-found-goal self ]
            ]
        ]
    ]
end

to generate-problem-description
;; Writes to the Output box a description of the search problem in the form of an exam question.

  clear-output
  if (start-node-number = 0)
    [ output-print "Error - cannot generate the problem description for the search problem when the start-node-number is set to 0."
      stop ]

  output-print "Problem description:"
  output-print (word "Show how the " search-behaviour " algorithm searches the network shown.")
  output-print "Show the list of active searcher agents along with the nodes they are visiting."
  output-print (word "The start node is node n" start-node-number " and the start node is the goal node (i.e. node n0).")
  output-print "Expand the nodes in the order of their node number. For example: "
  output-print "expand node n1 before every other node; expand node n2 before every "
  output-type "other node except node n1; and so on. " 
  
  ifelse (allow-revisited-nodes?)
    [ output-print "Also, allow nodes to be revisited. " ]
    [ output-print "Also, do not allow nodes to be revisited. " ]

end

to load-network-from-file [filename]
; Loads the network from a file.

  let line ""
  let len 0
  let x 0 let y 0
  let n-nodes 0
  let data []
  let from-node 0
  let to-node 0
  let n-nodes-found? false
  let xy-found? false
  
  file-open filename
  while [not file-at-end?]
  [
    set line file-read-line
    set len length line
    if (len > 0)
      [
        if (item 0 line != "#") ; ignore comments
          [
            if (len > 7) and (substring line 0 7 = "nodes: ")
              [ ; this contains the number of nodes
                set n-nodes-found? true
                set n-nodes read-from-string (substring line 7 len)
                ifelse (n-nodes = 0)
                  [ user-message "Error - invalid number of nodes; must be > 0" stop ]
                  [ init-network n-nodes ]
              ]
            if (len > 4) and (substring line 0 4 = "XY: ")
              [ ; this contains the x, y co-ordinates of a node
                set xy-found? true
                set data read-from-string (substring line 4 len)
                set to-node node item 0 data
                set x item 1 data
                set y item 2 data
                ask to-node
                [ setxy x y ]
              ]

            if (len > 3) and (substring line 0 3 = "T: ")
              [ ; this defines a link
                set data read-from-string (substring line 3 len)
                set from-node node item 0 data
                set to-node node item 1 data
                ; assume that who numbers correspond to numbers in the file
                ; (this will be true only if the first agents created were the nodes)
                
                ask from-node
                [ 
                  create-link-with to-node
                ]
              ]
          ]
      ]
  ]
  file-close

  if (n-nodes-found? = false)
    [ user-message "Error - number of nodes data (nodes:) not found in file" stop ]

  set bacon-set nodes
  set kevin-bacon-node node 0
  ask kevin-bacon-node ; reset Kevin Bacon's position
  [ set kevin-bacon-xcor xcor
    set kevin-bacon-ycor ycor ]

  if (not xy-found?)
    [ change-layout ]
end

to save-network-to-file [filename]
; Saves the network to a file.

  let n-nodes count nodes
  let from-node-who 0
  let to-node-who 0
  
  if (n-nodes = 0)
    [
      user-message "Error - no nodes in the network."
      stop
    ]

  if (file-exists? filename)
    [ file-close
      file-delete filename ] ; do not open new file in append mode
  file-open filename
  
  file-print (word "nodes: " n-nodes)

  if (specify-coordinates?)
    [ ; save the co-ordinates of the location of each node so that
      ; this remains fixed when the network is loaded back in
      ask nodes
      [
        file-print (word "XY: [ " who " " xcor " " ycor " ]")
      ]
    ]
  ask nodes
  [
    set from-node-who who
    ask my-links
    [
      set to-node-who [who] of other-end
      file-print (word "T: [ " from-node-who " " to-node-who " ]")
    ]
  ]

  file-close
end

to add-to-network

  let nodes-to-choose-from []
  let to-node nobody
  let from-node nobody
  let num-links 0
  let adj ""
  let n 0
  let done false
  let new-nodes []

  let num-nodes read-from-string user-input "How many nodes to add?"
   
  ; let the user specify where the nodes should be drawn

  create-nodes num-nodes
  [
    hide-turtle
    init-node
    set new-nodes lput self new-nodes
  ] ; create the nodes first and hide them initially so that spurious nodes do not get created temporarily in the centre
    ; before their position has been set by the user

  foreach new-nodes
  [ ; set the position of the new nodes to where the user wants them, and then show the node
    ask ?
    [
      ifelse (specify-coordinates?)
        [ ; the user specifies the co-ordinates of each node
  
          let x enter-coordinate true self
          let y enter-coordinate false self
          setxy x y
          show-turtle        
        ]
        [
          set done false
          while [not done]
          [
            if mouse-down?
              [ setxy mouse-xcor mouse-ycor
                show-turtle
                set done true
              ]
          ]
          display
          while [mouse-down?] [wait 0.1]
        ]

      if (output-trace?)
        [ output-print (word "Node n" who " added at co-ordinates (" (precision xcor 2) "," (precision 2 ycor) ").") ]
    ]
  ]

  ; now create the links for the new nodes
  set num-nodes count nodes
  foreach new-nodes
  [
    set num-links num-nodes
    set num-links user-one-of (word "How many links for " ? "? ") n-values (num-links + 1) [?]
    
    ; create a list of nodes to choose from
    ask ?
    [ set nodes-to-choose-from (sort other nodes) ]
    
    set n 1
    set from-node ?

    repeat num-links
    [
      ; choose the state to link to
      if-else (n = num-links)
        [ set adj ifelse-value (n = 1) ["one"] ["last"] ]
        [ set adj ifelse-value (n = 1) ["first"] ["next"] ]
      if-else (length nodes-to-choose-from = 1)
        [ set to-node first nodes-to-choose-from ]
        [ set to-node user-one-of (word "Choose the " adj " node that " from-node " links to: ") nodes-to-choose-from ]
      set nodes-to-choose-from remove to-node nodes-to-choose-from
      
      ask ?
      [
        ; create a link to the other node
         create-link-with to-node
         [ set thickness link-thickness ]
      ]
      set n n + 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).  Searching For Kevin Bacon NetLogo model.
;   Artificial Intelligence. Ventus Publishing Aps.
;