reveal.js

# 18 Programming agent AI

---
						## 18.1 Modelling behaviour

Artificial Intelligence (AI) is the simulation of human intelligence in machines that are programmed to think and act like humans (or anything we consider intelligent).

In the context of ABM, AI refers to the rules and decision-making processes that govern the behaviour of individual agents within the model.

---
						## 18.1 Modelling behaviour
						
						For our model, based on the conceptual model, we will implement simple behaviour for two agent types:

- `settlements`: 
							- produce goods according to their size and a productivity term. 
							- create or destroy traders according to their current size. 
						- `traders`: 
							- take some goods from their base and deliver them to another settlement, 
							- which is chosen based on the size of other settlements and the distance between these and the base settlement.
							- Traders will then return with goods from that settlement back to the base and restart the cycle.
						
						Implementing these behavioural rules will take us from step 6 to 9.
						---
						## 18.2 Implementing path finding

Start from the most fundamental: **movement of traders between settlements**.
						
						We want a proper *path-finding algorithm* that will allow traders to navigate the pond avoiding land patches (least-cost path).

We will use the [A* (A-star) algorithm in NetLogo User Community Models](http://ccl.northwestern.edu/netlogo/models/community/Astardemo1).

Try also the simpler implementation using Euclidean distance and `links` in the [PondTrade_step07_agent AI v2_links.nlogo](https://github.com/Andros-Spica/PondTrade/blob/master/PondTrade_step07_agent%20AI%20v2_links.nlogo) file.

---
						## 18.2 Implementing path finding
						### Walking through the A* code

```NetLogo
            patches-own
            [
              isLand
              pathCost
              
              ;;; path-finding related
              parent-patch ; patch's predecessor
              f ; the value of knowledge plus heuristic cost function f()
              g ; the value of knowledge cost function g()
              h ; the value of heuristic cost function h()
            ]

...

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
            ;;; A* path finding algorithm ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
            ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
            ; modified from Meghendra Singh's Astardemo1 model in NetLogo User Community Models
            ; http://ccl.northwestern.edu/netlogo/models/community/Astardemo1
            ; modified lines/fragments are marked with ";-------------------------------*"
            ; In this version, patches have different movement cost.
            ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; the actual implementation of the A* path finding algorithm
            ; it takes the source and destination patches as inputs
            ; and reports the optimal path if one exists between them as output
            to-report find-a-path [ source-patch destination-patch]

; initialize all variables to default values
              let search-done? false
              let search-path []
              let current-patch 0
              let open [] ;-------------------------------*
              let closed [] ;-------------------------------*

;-------------------------------*
              ask patches with [ f != 0 ]
              [
                set f 0
                set h 0
                set g 0
              ]
              ;-------------------------------*

; add source patch in the open list
              set open lput source-patch open

; loop until we reach the destination or the open list becomes empty
 while [ search-done? != true]
 [
 ifelse length open != 0
 [
 ; sort the patches in open list in increasing order of their f() values
 set open sort-by [ [?1 ?2] -> [f] of ?1 < [f] of ?2 ] open

; take the first patch in the open list
                  ; as the current patch (which is currently being explored (n))
                  ; and remove it from the open list
                  set current-patch item 0 open
                  set open remove-item 0 open

; add the current patch to the closed list
                  set closed lput current-patch closed

; explore the Von Neumann (left, right, top and bottom) neighbors of the current patch
                  ask current-patch
                  [
                    ; if any of the neighbors is the destination stop the search process
                    ifelse any? neighbors4 with [ (pxcor = [ pxcor ] of destination-patch) and (pycor = [pycor] of destination-patch)] ;-------------------------------*
                    [
                      set search-done? true
                    ]
                    [
                      ; the neighbors should not already explored patches (part of the closed list)
                      ask neighbors4 with [ (not member? self closed) and (self != parent-patch) ] ;-------------------------------*
                      [
                        ; the neighbors to be explored should also not be the source or
                        ; destination patches or already a part of the open list (unexplored patches list)
                        if not member? self open and self != source-patch and self != destination-patch
                        [
                          ;set pcolor 45 ;-------------------------------*

; add the eligible patch to the open list
                          set open lput self open

; update the path finding variables of the eligible patch
                          set parent-patch current-patch
                          set g [g] of parent-patch + pathCost ;-------------------------------*
                          set h distance destination-patch
                          set f (g + h)
                        ]
                      ]
                    ]
            ;        if self != source-patch ;-------------------------------*
            ;        [
            ;          set pcolor 35
            ;        ]
                  ]
                ]
                [
                  ; if a path is not found (search is incomplete) and the open list is exhausted
                  ; display a user message and report an empty search path list.
                  user-message( "A path from the source to the destination does not exist." )
                  report []
                ]
              ]

; if a path is found (search completed) add the current patch
              ; (node adjacent to the destination) to the search path.
              set search-path lput current-patch search-path

; trace the search path from the current patch
              ; all the way to the source patch using the parent patch
              ; variable which was set during the search for every patch that was explored
              let temp first search-path
              while [ temp != source-patch ]
              [
            ;    ask temp ;-------------------------------*
            ;    [
            ;      set pcolor 85
            ;    ]
                set search-path lput [parent-patch] of temp search-path
                set temp [parent-patch] of temp
              ]

; add the destination patch to the front of the search path
              set search-path fput destination-patch search-path

; reverse the search path so that it starts from a patch adjacent to the
              ; source patch and ends at the destination patch
              set search-path reverse search-path

; report the search path
              report search-path
            end
            ```

---
						## 18.2 Implementing path finding
						### Assigning path costs 🤔

Once the algorithm is clear, we need to assign path costs to patches.

Before looking at the solution, try to write the code yourself:

- Each patch has a `pathCost` variable (already defined)
						- Land patches have a high `pathCost` (arbitrary, e.g. 1000)
						- Water patches have a low `pathCost` (the baseline, i.e. 1)

When and where should this be done?
						Do we need to do it every time we run the search?
						What value should be a parameter (slider) in the interface?

(EXTRA CHALLENGE: further differentiate the path cost in settlements, i.e. cost to "port")
						---
						## 18.2 Implementing path finding
						### Assigning path costs - Solution

```NetLogo
            to create-map

...

assign-path-cost

paint-patches

end

...

to assign-path-cost

ask patches
              [
                ifelse (isLand = false)
                [ set pathCost 1 ] ; arbitrary unit for now
                [ set pathCost relativePathCostInLand ] ; defined by parameter in relation to the cost of path in water (i.e., 1)
              ]

end
 ```
						Remember to create the `relativePathCostInLand` slider in the interface.

---
						## 18.2 Implementing path finding
						### Assigning path costs - Solution (challenge)

```NetLogo
            to create-coastal-settlements

; consider only coastal patches
              let coastalPatches patches with [(isLand = true) and (any? neighbors with [isLand = false])]

repeat numberOfSettlements
              [
                ; ask a random coastal patch without a settlement already
                ask one-of coastalPatches with [not any? settlements-here]
                [
                  sprout-settlements 1 ; creates one "turtle" of breed settlements
                  [
                    set sizeLevel 1 + random 10 ; sets a random arbitrary size level for the settlement (between 1 and 10)

; give meaningful display proportional to size
                    set shape "circle 2"
                    set size 1 + sizeLevel / 3
                  ]
                  ; replace the land path cost with the port pathCost
                  set pathCost relativePathCostInPort
                  ; exclude this patch from the pool of coastal patches
                  set coastalPatches other coastalPatches
                ]
              ]

end
 ```
						Remember to create the `relativePathCostInPort` slider in the interface.

---
						## 18.3 Testing the A* path-finding

- Uncomment the lines involving `set pcolor ...` in the `find-a-path` procedure to visualise the search process
						- reduce the simulation speed to see the search process
						- run `setup` (which now sets `pathCost`)
						- In the command center, run:

```NetLogo
            show find-a-path (patch -30 -30) (patch 30 -30)
            ```

Try various coordinates to see how the search process work with different contexts.
						
						---
						## 18.3 Testing the A* path-finding

| | | | |
 | --- | --- | --- | --- |
 | <img src="https://github.com/CoDArchLab-ABM/course-guide/blob/main/assets/screenshots/BlockB_PondTrade_step07_agent AI v2_AStar view-process0.png?raw=true" width="200"> | <img src="https://github.com/CoDArchLab-ABM/course-guide/blob/main/assets/screenshots/BlockB_PondTrade_step07_agent AI v2_AStar view-process1.png?raw=true" width="200"> | <img src="https://github.com/CoDArchLab-ABM/course-guide/blob/main/assets/screenshots/BlockB_PondTrade_step07_agent AI v2_AStar view-process2.png?raw=true" width="200"> | <img src="https://github.com/CoDArchLab-ABM/course-guide/blob/main/assets/screenshots/BlockB_PondTrade_step07_agent AI v2_AStar view-process3.png?raw=true" width="200"> |

---
						## 18.4 Finding all routes

Implement a new procedure `set-routes` that will:
						- be called during in `setup` after creating the settlements
						- will ask each settlement to find the best routes to every other settlements
						- will store the path in a new global variable `routes`

This involves:
						- creating a new global variable `routes`
						- creating a new procedure `set-routes`
						- calling `set-routes` in `setup`
						- asking each settlement to find the best routes to every other settlements
						- storing the path in a new global variable `routes`

---
## 18.4 Adapting model schedule - Solution

```NetLogo
globals [ routes ]

...

to setup

reset-timer
  clear-all

; set the random seed so we can reproduce the same experiment
  random-seed seed

create-map

create-coastal-settlements

set-routes

create-traders-per-settlement

update-display

output-print (word "Set up took " timer " seconds.")

end

...

to set-routes

set routes [] ; initialize/reset the routes as an empty list

let settlementsWithoutRoutes settlements ; helper variable to keep track of which settlement already searched for routes

ask settlements
  [
    let thisSettlement self

ask other settlementsWithoutRoutes
    [
      let optimalRoute find-a-path ([patch-here] of thisSettlement) ([patch-here] of self) ; find the optimal route to this settlement
      set routes lput optimalRoute routes ; add the optimal route to the end of the routes list

; paint route patches in shades of red depending on route frequency
      foreach optimalRoute
      [ ?1 ->
        ask ?1
        [
          ifelse (pcolor = 106 or pcolor = 54) ; if its the first route crossing the patch
          [
            set pcolor 11
          ]
          [
            set pcolor min (list (pcolor + 1) (19)) ; sets a maximum at 19 (the brightest)
          ]
        ]
      ]
    ]

set settlementsWithoutRoutes other settlementsWithoutRoutes

]

end
```

With great computation comes great responsibility! Know that you can stop NetLogo by selecting "Tools > Halt" from the menu bar.

---
## 18.5 Decision making

Having implemented path-finding, we can now focus on the decision-making process of traders when choosing their destination settlement.

<img src="https://damienhowellpt.com/wp-content/uploads/2022/07/Path-of-least-resistance.jpg" width="300">
---
## 18.5 Decision making 🤔

Before looking at the solution, try to write the code yourself (this is a hard one!):

- Create a new procedure `choose-destination` for the `trader` breed
- The procedure should:
  - calculate a "attractiveness" score for each settlement (excluding the base settlement)
  - choose the destination settlement with the best attractiveness score
- The attractiveness score should consider:
  - the size of the settlement (bigger is more attractive)
  - the distance (total path cost) from the base settlement (closer/less costly is more attractive)

---
## 18.5 Decision making - Solution

```NetLogo
traders-own [ base route destination direction lastPosition ]

...

to choose-destination ; ego = trader

let thisTrader self

; get routes connecting the base settlement
  let routesFromBase get-routes-from-settlement [base] of thisTrader

; order these routes by benefit/cost ratio
  set routesFromBase sort-by [ [?1 ?2] -> benefit-cost-of-route ?1 > benefit-cost-of-route ?2 ] routesFromBase

; print the options available
;  foreach routesFromBase
;  [
;    print "==============================================================="
;    print "route between:"
;    print [who] of get-origin-and-destination ?
;    print "has the benefit-cost ratio of:"
;    print benefit-cost-of-route ?
;  ]
;  print "-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x-x"

; select the one with higher benefit/cost ratio
  set route first routesFromBase

; mark the most effective route
  foreach route
  [ ?1 ->
    ask ?1 [ set pcolor yellow ]
  ]

; get the settlement of destination
  set destination one-of (get-origin-and-destination route) with [who != [who] of ([base] of thisTrader)]

end

...

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;; Get and set routes (helper 'to-report' procedures) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to-report get-route [ settlement1 settlement2 ] ; accepts two settlements and returns a route

; get routes connecting settlement1
  let routesFromSettlement1 filter
  [ ?1 ->
    ([one-of settlements-here] of first ?1 = settlement1) or
    ([one-of settlements-here] of last ?1 = settlement1)
  ] routes

; get the route connecting settlement2 from the previous list
  let routeFromSettlement1ToSettlement2 filter
  [ ?1 ->
    ([one-of settlements-here] of first ?1 = settlement2) or
    ([one-of settlements-here] of last ?1 = settlement2)
  ] routesFromSettlement1

report first routeFromSettlement1ToSettlement2

end

to-report get-routes-from-settlement [ aSettlement ] ; accepts a settlement and return a list of routes

report filter
  [ ?1 ->
    ([one-of settlements-here] of first ?1 = aSettlement) or
    ([one-of settlements-here] of last ?1 = aSettlement)
  ] routes

end

to-report get-origin-and-destination [ aRoute ] ; accepts a route and returns a turtle-set with two settlements

report (turtle-set ([ one-of settlements-here ] of first aRoute) ([one-of settlements-here ] of last aRoute))

end

to-report benefit-cost-of-route [ aRoute ] ; accepts a route and returns a number (the benefit/cost ratio of the route)

let cost 0

foreach aRoute ; for every patch in the given route
  [ ?1 ->
    set cost cost + [pathCost] of ?1
  ]

let originAndDestination get-origin-and-destination aRoute
  let benefit 0
  ask originAndDestination [ set benefit benefit + sizeLevel ] ; the benefit is the sum of the sizeLevel of the two settlements

report benefit / cost

end
```

`get-route` is only for debugging purposes, it is not used in the model.
---
## 18.6 Movement

Once destination is decided, the trader needs to:

- move along the selected route until it reaches the destination settlement
- return to the origin settlement following the same route in reverse

---
## 18.6 Movement 🤔

Before looking at the solution, try to write the code yourself (this is VERY hard!):
- Create a new procedure(s) for the `trader` breed
- The procedure should:
  - move the trader along the selected route towards the destination settlement (or back)
  - check if the trader is at the destination or base settlement and choose the right direction
  - check if in a patch centre (round coordinates) to move to the next patch in the route
  - move progressivelly towards the next patch in the route (not teleporting)
  - speed should be dependent on the pathCost of the patch-here

Things to consider:
- How to keep track of the direction of movement?
- How to keep track of the progress of movement?
- How to check if the trader is at the destination or base settlement?
- How to check if the trader is in a patch centre?
- How to move progressivelly one patch centre to another?
- How to make the speed dependent on the pathCost of the patch-here?

---
## 18.6 Movement - Solution

```NetLogo
to move-to-destination ; ego = trader

; update lastPosition if in a patch center
  if ((xcor = [pxcor] of patch-here) and (ycor = [pycor] of patch-here))
  [
    set lastPosition patch-here
  ]
  ; find where in the route list is the trader
  let currentPosition position lastPosition route

; set direction if in a settlement
  ifelse (currentPosition = 0) ; in the first extreme of the route list
  [
    set direction 1 ; move in the route list towards larger index numbers
  ]
  [
    if (currentPosition = (length route - 1)) ; in the last extreme of the route list
    [
      set direction -1 ; move in the route list towards smaller index numbers
    ]
  ]
  ; else the trader is in route to either the base or the destination

; move through the route following direction
  let targetPatch item (currentPosition + direction) route
  ;move-to targetPatch ; constant travel time (1 patch per tick)
  facexy ([pxcor] of targetPatch) ([pycor] of targetPatch)
  forward min (
    list
    (1 / [pathCost] of patch-here) ; the maximum distance in a tick in the current patch
    (distancexy ([pxcor] of targetPatch) ([pycor] of targetPatch)) ; the distance to the target patch
    )

end
```

---
## 18.6 Movement - Solution (continued)

```NetLogo
to go

ask traders
  [
    if (patch-here = [patch-here] of base) ; update the destination whenever in the base settlement
    [
      choose-destination
    ]
    move-to-destination
  ]

end
```

---
## 18.7 Enhancing visualisation

Colour the route patches depending on how many routes pass through them (done in `set-routes`)

```NetLogo
to setup

clear-all
  reset-ticks

; set the random seed so we can reproduce the same experiment
  random-seed seed

create-map

create-coastal-settlements

set-routes

create-traders-per-settlement

update-display

end

...

to update-display

paint-routes
  paint-active-routes

; scale the size of settlements according to their dynamic free-scaled sizeLevel
  let maxSettlementSize max [sizeLevel] of settlements

ask settlements
  [
    set hidden? not showSettlements
    set size 1 + (sizeLevel / maxSettlementSize) * 9
  ]

end

to paint-routes

; resets route patches to the terrain color
  foreach routes
  [ ?1 ->
    let aRoute ?1

foreach aRoute
    [ ??1 ->
      ask ??1 [ paint-terrain ]
    ]
  ]

; paint route patches in shades of red depending on route frequency
  foreach routes
  [ ?1 ->
    let aRoute ?1

foreach aRoute
 [ ??1 ->
 ask ??1
 [
 if (showRoutes)
 [
 ifelse (pcolor < 11 or pcolor > 19) ; if its the first route crossing the patch
 [
 set pcolor 11
 ]
 [
 set pcolor min (list (pcolor + 1) (19)) ; sets a maximum at 19 (the brightest)
 ]
 ]
 ]
 ]
 ]

end

to paint-active-routes

ask traders
  [
    foreach route
    [ ?1 ->
      ask ?1
      [
        ifelse (showActiveRoutes)
        [
          set pcolor yellow
        ]
        [
          if (not showRoutes) ; if not displaying all routes
          [
            ; resets to the patch terrain color
            paint-terrain
          ]
        ]
      ]
    ]
  ]

end
```

Remember to create the `showRoutes` and `showActiveRoutes` switches in the interface.

---
## 18.8 Testing agent behaviour

Temporary hack: replace the code in `create-traders-per-settlement`:

```NetLogo
to create-traders-per-settlement

; For now, we create only one trader to better control its behaviour
  ask one-of settlements
  [
    let thisSettlement self

hatch-traders 1
    [
      set base thisSettlement

set shape "sailboat side" ; import this shape from the library (Tools > Shape editor > import from library)
      set color [color] of base
      set size 3
    ]
  ]

; the previous code for creating traders can be commented out
; by adding ';' at the beggining of each line, or
; by selecting several lines and either selecting 'Edit > Comment' or pressing 'ctrl + ;'.
;  ask settlements
;  [
;    let thisSettlement self ; to avoid the confusion of nested agent queries
;    hatch-traders round sizeLevel ; use the sizeLevel variable as the number of traders based in the settlement
;    [
;      set base thisSettlement
;
;      ; give meaningful display related to base
;      set shape "sailboat side" ; import this shape from the library (Tools > Shape editor > import from library)
;      set color [color] of base
;      set size 3
;
;      ; place it somewhere in the pond, randomly for now (if not, the command "hatch-breed" will place them in the same patch of the settlement)
;      move-to one-of patches with [isLand = false]
;    ]
;  ]

end
```

Reduce `numberOfSettlements` (e.g. 10) and run `setup` and `run` (repeatedly) to observe the trader's behaviour.

---
### Checking the milestone File (step 7)