Santa Fe Trail 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: Santa-Fe-Trail.nlogo

WHAT IS IT?

This model tests out various behaviours as solutions to the Santa Fe Ant Trail problem.

The Santa Fe Ant Trail problem is an instance of the Artificial Ant problem with a specific path (the Santa Fe Trail). The Artificial Ant problem originated by Jefferson et al. (Koza, 1992; p.54) with the Genesys-Tracker System (Jefferson et al., 1991). The Santa Fe Trail was designed by Christopher Langton (Koza, 1992; p.54), which is a somewhat more difficult trail than the "John Muir Trail" originally used for the Artificial Ant problem. Indeed, there are others more difficult than the Santa Fe Trail paths, like the "Los Altos Hills" path (Koza, 1992; p. 156).

This model loads the trail from a data file, then various behaviours can be loaded into the input box and modified for testing on the Trail.


HOW IT WORKS

A single ant turtle agent is created as the ant. Its starting location is at the top left of the environment. Its actions are determined by the code in the Ant-Actions input box of the Interface. This box is editable - the user can modify the code as she or he wishes by pressing the Change box. The code is then executed by the ant each tick when the go button is pressed.

Various motor actions for the ant are provided in the model for use in defining their behaviour and are explained as follows:
- move: This moves the ant forward one step.
- turn-left: This turns the ant left by 90 degrees.
- turn-right: This turns the ant right by 90 degrees.

Various sensing and/or sensory-motor actions for the ant are provided in the model for use in defining their behaviour and are explained as follows:
- food-ahead: This reports whether there is food directly ahead of the ant.
- food-on-my-left: This reports whether there is food on the left of the ant.
- food-on-my-right: This reports whether there is food on the right of the ant.
- food-ALR: This reports the action needed to be performed by the ant if there is food nearby. If there is none, then the default action is to move ahead.
- food-direction: This reports the direction of food if there is any nearby. If there is none, then the default direction is 0 degrees (straight ahead).


HOW TO USE IT

Choose which behaviour you want to be executed by the ant using the which-behaviour chooser. This will then be loaded into the Ant-Actions input box when the Setup button is pressed. Then to run the model, press the Go button.


THE INTERFACE

The buttons in the Interface are defined as follows:

- Setup: This will clear the environment and load the Santa Fe Trail into it, and create a single ant turtle agent at the start of the trail. It will also load the code for the ant's behaviour (as specified by the which-behaviour chooser) into the Ant-Actions input box. This can then be edited by the user if they wish.

- Go: This will run the simulation.

- Restart: This will restart the simulation from the beginning without the need to press the Setup button (this is useful when you have edited the Ant-Actions Input box, since pressing Setup will re-load the original unedited behaviour).

The chooser, monitors, input box, slider and switch are defined as follows:

- which-behaviour: This specifies the behaviour that gets loaded into the Ant-Actions input box and subsequently executed when the Go button is pressed. The behaviours are defined as follows:
"Optimum": This is the optimum behaviour for the Santa Fe Trail (it follows the trail exactly).
"Koza": This is the translation from LISP to NetLogo code of the solution mentioned in Koza's first GP book (Genetic Programming: On the Programming of Computers by the Means of Natural Selection, 1992, p. 154).
"Koza-1": This was a solution discovered using Grammatical Evolution provided by Loukas Georgiou that is based on a semantically equivalent grammar to the set of programs possible within the original Santa Fe Trail definition of Koza.
"Koza-2": This is a manual modification of "Koza-1" to remove unnecessary steps.
"Koza-3": This is a further manual modification to "Koza-2" that adds a single "move" command in order to improve performance even further.
"Koza Modified": This is modified version of "Koza" which removes unnecessary steps.
"Look ALR 1": The ant looks ahead for the trail, then left, then right (no peripheral vision); it turns in the direction of food that was first found, otherwise it moves forward.
"Look ALR 2": The ant looks ahead for the trail; then left; then right (using peripheral vision). Then it moves in the direction of food.
"Look ALR 2a": This is a modification to "Look ALR 2" for a myopic ant that does not have peripheral vision (i.e. it can only use the food-ahead command to sense food as in Koza's original definition, and so it must physically turn to the left or right in order to sense the presence of food on its left or right).
"Look ALR 2b": This is a modification to "Look ALR 2a" where the ants look right first rather than left.
"Look ALR 3": This is similar to "Look ALR 2" but uses simpler code.
"Look ALR 4": This is similar to "Look ALR 2" but uses even simpler code.
"Look ALR 5": This is another solution discovered using Grammatical Evolution provided by Loukas Georgiou that uses the minimum amount of motor steps.

- Motor Steps: This is the number of motor actions the ant performs - i.e. move, left turn or right turn.

- Sensing Steps: This is the number of sensing actions the ant performs - e.g. looking to see if there is food ahead or to its left or right.

- Total Steps: This is the sum of the Motor Steps + Sensing Steps.

- Food Eaten: This is the amount of food eaten. If the ant has managed to eat all 89 patches of food, then it completes the task.

- Ant-Actions: These are the actions the ant performs each tick of the simulation.

- Max-Steps: This is the maximum number of Motor Steps the ant is allowed to perform before the simulation is stopped.

- Show-Path?: If this is set to On, then the path the ant takes will be drawn in the environment.


THINGS TO NOTICE

Notice that the Optimum behaviour does not perform any sensing actions - there are only the motor actions needed to follow the path exactly. This is the minimum number of motor steps needed to follow the trail (hence why this is called the Optimum behaviour). However, this behaviour is too specific - it would only be useful for following the Santa Fe Ant Trail and nothing else.

Notice which of the other behaviours result in the same number of motor steps as the Optimum behaviour. How do they compare when the sensing steps are also taken into consideration?

Notice that the best solution (apart from Optimum) requiring the least number of motor steps, and not using the extra sensing operators food-on-my-left and food-on-my-right, is "Koza-3". It takes 365 steps. It works better compared to the other Look ALR type solutions because it takes advantage of a quirk of the Santa Fe Trail whereby if you had to turn in order to find the trail, then you can move forward two steps rather than one and you won't lose the trail. i.e. This solution would fail on a different trail where there was a rapid change in direction.

Notice that the Optimum solution requires 165 steps without any sensing operations being performed. For solutions that are constrained as in Koza's original problem to physically turn left or right in order to check if there is food on your left or right, then when there is a gap in the trail where there is no food, there is a penalty involved in looking both ways and turning back again to the original heading. As there are 55 patches on the trail which have no food, then this results in a cost of 55 x 4 motor steps as the agent has to turn left, then right, then right, then left. i.e. This imposes a cost of 220 steps at least, so a minimum is 165 + 220 steps, or 385 steps.

In addition, there is the cost of turning which will add an extra 2 steps compared to the optimum for each right turn if the agent's inclination is to turn left first, and vice versa if the other way around. i.e. For left-turns-before-right-turns agents, there are 11 right turns, so added cost is 22; for right-turns-before-left-turns agents, there are 10 left turns, so added cost is 20.

This explains why some solutions discovered by evolutionary algorithms require 405 and 407 steps (385 + 20 and 385 + 22). The solutions that are less (377 motor steps for "Koza-2" and 365 motor steps for "Koza-3") take advantage of a quirk in the trail that allows an ant to move 2 steps rather than 1 after a turn. By moving 2 step forward, the ant jumps over some of the gaps in the trail, therefore avoiding the extra 4 steps needed that the other ants need to take.


THINGS TO TRY

Try out all the different behaviours to see which one is "best" (i.e. uses the minimum number of total steps (motor + sensing). Compare this with the Optimum behaviour.

Try writing your own behaviours or modify an existing one using the Change button in the Ant-Actions input box. (For example, remove the last 'move' command from Koza's behaviour to see what happens). Make sure that you press the Setup button first before doing this to clear any existing paths. How well do your behaviours perform? Are they successful in getting to the end of the Trail?


EXTENDING THE MODEL

Try writing an evolutionary algorithm (via a Genetic Algorithm, Genetic Programming or Grammatical Evolution, for example) to evolve the behaviour of the ant to see what code is evolved as a result.


NETLOGO FEATURES

Note the use of the run command to run the commands in the Ant-Actions code.


RELATED MODELS

See the Follow Trail model.


CREDITS AND REFERENCES

This model was created by William John Teahan and Loukas Georgiou.

To refer to this model in publications, please use:

Santa Fe Trail NetLogo model.
Teahan, W. J. (2010). Exercises for Artificial Intelligence. Ventus Publishing Aps

Further references:

JEFFERSON, D., COLLINS, R., COOPER, C., DYER, M, FLOWERS, M., KORF, R., TAYLOR, C., WANG, A. (1991) Evolution as a Theme in Artificial Life: The Genesys/Tracker System. In Langton, Christopher, et al. (editors), Artificial Life II. Addison-Wesley.

KOZA, J.R. (1992) Genetic Programming: On the Programming of Computers by the Means of Natural Selection. Cambridge, MA: MIT Press.

LANGDON, W.B., POLI, R. (1998) Better Trained Ants for Genetic Programming. Technical report, University of Birmingham, School of Computer Science (CSRP-98-12), April 1998.


PROCEDURES

; Santa Fe Trail model.
; 
; The ant turtle agents try to follow the Santa Fe Ant Trail devised by John Koza.
;
; This model is based on the original Santa Fe Trail model written by Loukas Georgiou.
;
; Copyright 2010 William John Teahan and Loukas Georgiou. All Rights Reserved.

globals
[
  food-amount         ;; The number of pieces of food in the trail
  steps               ;; The number of motor steps the ant performed (i.e. move, right-turn or left-turn)
  sensing-steps       ;; The number of additional sensing steps the ant performed (i.e. food-ahead)
  food-eaten          ;; The number of pieces of food found and eaten by the ant 
  init-actions?       ;; Actions have been initialised (checked and modified in the first loop of "go")
  actions             ;; The Ant-actions to be executed in "go"
  food-colour         ;; The patch colour of food on the trail
  eaten-food-colour   ;; The patch colour of food that has been "eaten"
  trail-colour        ;; The patch colour of the trail where there is no food
  background-colour   ;; The patch colour of everything off the trail
]

;;;;;;;;;;;;;;;;;;;;;;;;
;;; Setup procedures ;;;
;;;;;;;;;;;;;;;;;;;;;;;;

to setup

  clear-all  

  set food-colour 54 ; green
  set eaten-food-colour 52 ; dark green
  set trail-colour 34 ; brown
  set background-colour 68 ; light green background

  setup-global-settings
  setup-santa-fe-trail
  execute-behaviour
  
  crt 1
  [
    set size 1.5
    set color black
    setxy 0 0
    facexy 1 0
    ifelse Show-Path?
      [ pen-down ]
      [ pen-up ] 
  ]
  
end

to setup-global-settings
; This initialises the global variables and settings.

  set-default-shape turtles "bug"
  set food-amount 89
  set steps 0
  set sensing-steps 0
  set food-eaten 0 
  set Ant-Actions " "
  set init-actions? false
  set actions ""

end


to setup-santa-fe-trail
; This procedure sets up the Sante Fe Trail in the environment by
; reading it in from a file.

  ask patches
  [
    set pcolor background-colour
  ]

  let data ""
  let char ""
  let x -1
  let y -1  
  
  file-open "Santa-Fe-Trail.dat"
 
  while [not file-at-end?]
  [
    set data file-read-line
    set y y + 1
    set x 0
    
    while [x < 32]
    [    
      set char item x data      
      if char = "1" [ask patch x (y * -1) [add-food]] 
      if char = "0" [ask patch x (y * -1) [add-gap]]
      set x x + 1      
    ]    
  ]  
  file-close 
end

to add-food
  set pcolor food-colour
end

to add-gap
  set pcolor trail-colour
end

to execute-behaviour
; This performs the actions as defined 

  let act ""
  set Ant-Actions ""
  if (which-behaviour = "Koza")
    [ file-open "Santa-Fe-Trail-Program-Koza.ctr" ]
  if (which-behaviour = "Koza-1")
    [ file-open "Santa-Fe-Trail-Program-Koza-1.ctr" ]
  if (which-behaviour = "Koza-2")
    [ file-open "Santa-Fe-Trail-Program-Koza-2.ctr" ]
  if (which-behaviour = "Koza-3")
    [ file-open "Santa-Fe-Trail-Program-Koza-3.ctr" ]
  if (which-behaviour = "Koza Modified")
    [ file-open "Santa-Fe-Trail-Program-Koza-Modified.ctr" ]
  if (which-behaviour = "Optimum")
    [ file-open "Santa-Fe-Trail-Program-Optimum.ctr" ]
  if (which-behaviour = "Look ALR 1")
    [ file-open "Santa-Fe-Trail-Program-Look-ALR-1.ctr" ]
  if (which-behaviour = "Look ALR 2")
    [ file-open "Santa-Fe-Trail-Program-Look-ALR-2.ctr" ]
  if (which-behaviour = "Look ALR 2a")
    [ file-open "Santa-Fe-Trail-Program-Look-ALR-2a.ctr" ]
  if (which-behaviour = "Look ALR 2b")
    [ file-open "Santa-Fe-Trail-Program-Look-ALR-2b.ctr" ]
  if (which-behaviour = "Look ALR 3")
    [ file-open "Santa-Fe-Trail-Program-Look-ALR-3.ctr" ]
  if (which-behaviour = "Look ALR 4")
    [ file-open "Santa-Fe-Trail-Program-Look-ALR-4.ctr" ]
  while [not file-at-end?] [
    set act word act word file-read-line "\n"
  ]  
  file-close
  set Ant-Actions act

end


;;;;;;;;;;;;;;;;;;;;
;;; Go procedure ;;;
;;;;;;;;;;;;;;;;;;;;

to go

  if steps >= max-steps [stop]
  if food-eaten >= food-amount [stop]
  
  if not init-actions? [
    let act Ant-Actions
    set act remove " " act
    if empty? act [stop]
    set actions (word "ask turtle 0 [\n " Ant-Actions " \n]") 
  ]
  
  set init-actions? true
    
  run actions 

  tick
end

;;;;;;;;;;;;;;;;;;;;;;;;
;;; ANT OPERATIONS ;;;
;;;;;;;;;;;;;;;;;;;;;;;;

to move
; The ant performs the motor step of moving forward.

  if steps < max-steps and food-eaten < food-amount
  [
    fd 1
    if (pcolor = food-colour)
    [
      set pcolor eaten-food-colour
      set food-eaten food-eaten + 1
    ]
    set steps steps + 1   
  ]
end

to turn-left
; The ant performs the motor step of turning left.

  if steps < max-steps and food-eaten < food-amount
  [
    lt 90
    set steps steps + 1
  ]
end

to turn-right
; The ant performs the motor step of turning right.

  if steps < max-steps and food-eaten < food-amount
  [
    rt 90
    set steps steps + 1
  ]
end
to-report food? [ patch-agent ]
; Returns true if the patch is "food".

  report ([pcolor] of patch-agent = food-colour)
end

to-report food-ahead
; The ant performs the sensing step of checking if there is any food
; directly ahead.

  set sensing-steps sensing-steps + 1
  report food? patch-ahead 1
end

to-report food-on-my-left
; The ant performs the sensing step of checking if there is any food
; on it's left side.

  set sensing-steps sensing-steps + 1
  report food? patch-left-and-ahead 90 1
end

to-report food-on-my-right
; The ant performs the sensing step of checking if there is any food
; on it's right side.

  set sensing-steps sensing-steps + 1
  report food? patch-right-and-ahead 90 1
end

to-report food-ALR
; The ant performs the sensing step of checking if there is any food
; nearby. This reporter returns the action needed to head towards it.
; If there is no food nearby, it defaults to an "ahead" action.
; (ALR stands for "Ahead, Left or Right").

  set sensing-steps sensing-steps + 1
  if (food? patch-ahead 1)
    [ report "ahead" ]
  if (food? patch-left-and-ahead 90 1)
    [ report "turn-left" ]
  if (food? patch-right-and-ahead 90 1)
    [ report "turn-right" ]
  report "ahead"
end

to-report food-direction
; The ant performs the sensing step of checking if there is any food
; nearby. This reporter returns the direction of the food.
; If there is no food nearby, it defaults to the current heading.

  set sensing-steps sensing-steps + 1
  if (food? patch-ahead 1)
    [ report 0 ]
  if (food? patch-left-and-ahead 90 1)
    [ set steps steps + 1 ; the ant will make a left turn
      report (- 90) ]
  if (food? patch-right-and-ahead 90 1)
    [ set steps steps + 1 ; the ant will make a right turn
      report 90 ]
  report 0
end

to restart
; Clears any paths drawn and restarts the turtle back at the start.

  ask turtle 0
  [
    setxy 0 0
    facexy 1 0
  ]
  clear-drawing
  set food-amount 89
  set food-eaten 0
  set steps 0
  set sensing-steps 0
  set init-actions? false
  
  ask patches with [pcolor = eaten-food-colour]
  [ set pcolor food-colour ]
end
;
; Copyright 2010 by William John Teahan and Loukas Georgiou. 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).  Santa Fe Trail NetLogo model.
; Exercises for Artificial Intelligence. Ventus Publishing Aps.
;