search

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