Route Planner

turtles-own[
  high
  medium
  low
  
  prob-high
  prob-medium
  prob-low
  
  ;; expected time to reach node - based on expectation of previous nodes (linked)
  ;; this will be used for calculation of immediate rewards
  expectation
  
  ;; variable to store value obtained from value iteration
  value
]

links-own[
;  prob-high ;; for node linking node A to node B, this represents the probability that the driver will take 1 time step to reach node B when the traffic level at node A is high
;  prob-medium ;; for node linking node A to node B, this represents the probability that the driver will take 1 time step to reach node B when the traffic level at node A is medium
;  prob-low ;; for node linking node A to node B, this represents the probability that the driver will take 1 time step to reach node B when the traffic level at node A is low
]

to go
  ask turtle 9[value-iteration]
  
  ask turtles[
    set label (word who ": " value)
    set color blue
  ]
  tick
end 

to value-iteration
    ifelse(who != 9)[
      set color red
      
      ;; count of possible ways to travel (out link neighbors)
      let count-n (count out-link-neighbors)
      
      ;; who of out link neighbors
      let who-n (sort ([who] of out-link-neighbors))
      
      ;; prob of main direction (for value iteration calculation)
      let main-prob (1 - ((count-n - 1) * 0.1))
      
      ;; list which stores all possible values of all actions taken in state s - used to computing max
      ;; immediate reward (R) is taken as negative of expected time to reach state/node s' (to reflect the reward function of rewarding user for reaching node early)
      let val-list []
      
      foreach who-n[
        let main-dir-node ?
        let val (main-prob * ([value] of turtle main-dir-node)) - ([expectation] of turtle main-dir-node)
        
        
        ;; iterate through other nodes
        foreach who-n[
          if(? != main-dir-node)[
            set val (val + (0.1 * ([value] of turtle ?)))
          ]
        ]
        
        set val-list lput val val-list
      ]
      
      ;; set value as max in val-list - value iteration
      set value (precision (max val-list) 2)
    ]
    [
      set value 100
    ]
    
    
    
    ;; recursively call value iteration on in link neighbors
    ask in-link-neighbors[value-iteration]
end 

to update-expectation
  ;  0
  ifelse(who = 0)[
    set expectation 0
    set color red
  ]
  ;; for all other nodes
  [
    ;; boolean to check if all neighbors has expectation updated - will not proceed to update node if boolean is false (some neighbors not updated)
    let n-expect? true
    
    foreach([who] of in-link-neighbors)[
      if(([color] of turtle ?) != red)[
        set n-expect? false
      ]
    ]
    
    ;; proceed to update expectation if all neighbors are updated
    if(n-expect? = true)[
      ;; sum of expectation of all in-link neighbors
      let sum-expectation 0
      
      foreach([who] of in-link-neighbors)[
        let n-who ([who] of (turtle ?))
        let n-expectation ([expectation] of (turtle ?))
        
        set sum-expectation (sum-expectation + n-expectation + (mean-travel-time n-who (traffic-conditions n-who n-expectation)))
      ]
      
      ;; average over all neighbors
      set sum-expectation (sum-expectation / (length ([who] of in-link-neighbors)))
      
      set expectation sum-expectation
      
      set color red
    ]
    
  ]
  
  ;; recursively call update-expectation procedure to all out link neighbors
  ask out-link-neighbors[update-expectation]
end 

to setup
  ca
  reset-ticks
  ask patches[set pcolor 69]
  
  setup-nodes
  setup-links
  
  ;; update expected time to reach all nodes
  ;; this will be used to compute the immediate reward
  ask turtle 0[update-expectation]
  
  ask turtle 9[set value 100]
  
  ask turtles[
    set label (word who ": " value)
    set color blue
  ]
end 

;; setup nodes in the network

to setup-nodes
  crt 1[setxy 3 13 set shape "rounded-rectangle" set color blue set label who set label-color black]
  crt 1[setxy 1 10 set shape "rounded-rectangle" set color blue set label who set label-color black]
  crt 1[setxy 3 10 set shape "rounded-rectangle" set color blue set label who set label-color black]
  crt 1[setxy 5 10 set shape "rounded-rectangle" set color blue set label who set label-color black]
  crt 1[setxy 2 7 set shape "rounded-rectangle" set color blue set label who set label-color black]
  crt 1[setxy 4 7 set shape "rounded-rectangle" set color blue set label who set label-color black]
  crt 1[setxy 1 4 set shape "rounded-rectangle" set color blue set label who set label-color black]
  crt 1[setxy 3 4 set shape "rounded-rectangle" set color blue set label who set label-color black]
  crt 1[setxy 5 4 set shape "rounded-rectangle" set color blue set label who set label-color black]
  crt 1[setxy 3 1 set shape "rounded-rectangle" set color blue set label who set label-color black]
end 

;; setup links between nodes

to setup-links
  crt-links 0 1
  crt-links 0 3
  crt-links 1 2
  crt-links 1 4
  crt-links 2 4
  crt-links 2 5
  crt-links 3 2
  crt-links 3 5
  crt-links 3 8
  crt-links 4 5
  crt-links 4 6
  crt-links 4 8
  crt-links 4 9
  crt-links 5 6
  crt-links 5 7
  crt-links 6 9
  crt-links 7 9
  crt-links 8 7
end 

;; procedure to create links from turtle to turtle - used in setup-links procedure

to crt-links[from-turtle to-turtle]
  ask turtle from-turtle[create-link-to turtle to-turtle]
end 

;; procedure to report mean travel time along an edge with source node (as input) given certain traffic conditions (input)

to-report mean-travel-time[node traffic]
  let prob 0

  if(node = 0)[
    if(traffic = "high")[
      set prob n0-high-prob
    ]
    if(traffic = "medium")[
      set prob n0-medium-prob
    ]
    if(traffic = "low")[
      set prob n0-low-prob
    ]
  ]
  if(node = 1)[
    if(traffic = "high")[
      set prob n1-high-prob
    ]
    if(traffic = "medium")[
      set prob n1-medium-prob
    ]
    if(traffic = "low")[
      set prob n1-low-prob
    ]
  ]
  if(node = 2)[
    if(traffic = "high")[
      set prob n2-high-prob
    ]
    if(traffic = "medium")[
      set prob n2-medium-prob
    ]
    if(traffic = "low")[
      set prob n2-low-prob
    ]
  ]
  if(node = 3)[
    if(traffic = "high")[
      set prob n3-high-prob
    ]
    if(traffic = "medium")[
      set prob n3-medium-prob
    ]
    if(traffic = "low")[
      set prob n3-low-prob
    ]
  ]
  if(node = 4)[
    if(traffic = "high")[
      set prob n4-high-prob
    ]
    if(traffic = "medium")[
      set prob n4-medium-prob
    ]
    if(traffic = "low")[
      set prob n4-low-prob
    ]
  ]
  if(node = 5)[
    if(traffic = "high")[
      set prob n5-high-prob
    ]
    if(traffic = "medium")[
      set prob n5-medium-prob
    ]
    if(traffic = "low")[
      set prob n5-low-prob
    ]
  ]
  if(node = 6)[
    if(traffic = "high")[
      set prob n6-high-prob
    ]
    if(traffic = "medium")[
      set prob n6-medium-prob
    ]
    if(traffic = "low")[
      set prob n6-low-prob
    ]
  ]
  if(node = 7)[
    if(traffic = "high")[
      set prob n7-high-prob
    ]
    if(traffic = "medium")[
      set prob n7-medium-prob
    ]
    if(traffic = "low")[
      set prob n7-low-prob
    ]
  ]
  if(node = 8)[
    if(traffic = "high")[
      set prob n8-high-prob
    ]
    if(traffic = "medium")[
      set prob n8-medium-prob
    ]
    if(traffic = "low")[
      set prob n8-low-prob
    ]
  ]
  if(node = 9)[
    if(traffic = "high")[
      set prob n9-high-prob
    ]
    if(traffic = "medium")[
      set prob n9-medium-prob
    ]
    if(traffic = "low")[
      set prob n9-low-prob
    ]
  ]
  
  report ((prob * 1.0) + ((1.0 - prob) * 2.0))
end 

;; procedure to retrieve traffic conditions at a node at time step

to-report traffic-conditions[node timestep]
  ;; string to retrieve traffic
  let report-list ""
  
  if(node = 0)[
    set report-list n0-traffic-level
  ]
  if(node = 1)[
    set report-list n1-traffic-level
  ]
  if(node = 2)[
    set report-list n2-traffic-level
  ]
  if(node = 3)[
    set report-list n3-traffic-level
  ]
  if(node = 4)[
    set report-list n4-traffic-level
  ]
  if(node = 5)[
    set report-list n5-traffic-level
  ]
  if(node = 6)[
    set report-list n6-traffic-level
  ]
  if(node = 7)[
    set report-list n7-traffic-level
  ]
  if(node = 8)[
    set report-list n8-traffic-level
  ]
  if(node = 9)[
    set report-list n9-traffic-level
  ]
  
  ;; convert to list format
  set report-list (read-from-string report-list)
  
  ;; retrieve item in report-list based on timestep
  ifelse(timestep <= 10)[
    ;; 0 to 10
    report item 0 report-list
  ]
  [
    ifelse(timestep <= 15)[
      ;; 11 - 15
      report item 1 report-list
    ]
    [
      ifelse(timestep <= 30)[
        ;; 16 - 30
        report item 2 report-list
      ]
      [
        ifelse(timestep <= 100)[
          ;; 31 - 100
          report item 3 report-list
        ]
        [
          ;; nothing
          report 0
        ]
      ]
    ]
  ]
end