Hill Climbing with Wall Following 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: Hill-Climbing-with-Wall-Following.nlogo

WHAT IS IT?

Imagine blind turtles in mountainous terrain who want to find the nearest high points. Their situation is complicated by the presence of buildings in the terrain. The blind turtles only have two senses they can use - an ability of touch (i.e. they can follow a wall via proximity detection), and an ability to sense which way is up in the terrain. This model tries to simulate where the blind turtles would head to.

The model is based on two models provided by Uri Wilensky - the Hill Climbing Example model and the Wall Following Example model, both available in the Code Examples directory of the Models Library.


WHAT IS ITS PURPOSE?

The purpose of this model is to investigate what would happen when the two behaviours of hill climbing and wall following are combined. This is also a partial answer to Exercise 5.3.1 in the Exercises for Artificial Intelligence book.


HOW TO USE IT

First press the setup button after choosing the turtle behaviour you want to be exhibited using the turtle-behaviour chooser and selecting the number of turtles you want created using the number-of-turtles slider. To run the model, press either the go button for continuous simulation, or the go once button to run the simulation for a single tick. To add some buildings into the environment, press the create-new-buildings button. The colour of the buildings is set by the colour-of-buildings slider. The number of hills (represented by light shading) is set by the number-of-hills slider.


THE INTERFACE

The buttons in the model's Interface are defined as follows:

- setup: This resets the simulation. All the turtles are re-created, all existing buildings are deleted, and a new random terrain with new buildings is generated in the environment.

- restart: This recreates the turtles and deletes any existing paths, but keeps the existing terrain and buildings.

- go: This will run the simulation continuously.

- go once: This will run the simulation one step at a time.

- create-random-buildings: This will create some more random buildings in the environment. Be careful not to press this too much, otherwise the buildings will then cover the entire environment.

The choosers and sliders in the model's Interface are defined as follows:

- colour-of-buildings: This allows the use to choose the colour of the buildings - either black or white.

- turtle-behaviour: This allows the user to set the behaviour of the turtles. Try changing this when the simulation is running and see what happens.

- number-of-turtles: This sets the number of turtles that will be created when either the setup or restart buttons are next pressed.

- number-of-hills: This sets the number of hills in the terrain that will be created when the setup button is next pressed.


THINGS TO NOTICE

Notice when the turtle behaviour is set to Both that many of the turtles end up following walls, while the rest climb to the nearest high point. Why is this? Can you add two modifications of the Both behaviour where the turtles still keep on applying both types of behaviour initially but either all end up at high points or all end up following walls?

Notice what happens when the colour of the buildings is set to white and the turtle behaviour is set to Hill Climbing. Many of the turtles end up on the edge of the buildings, slightly inside. Why is this? Why does this not happen when the building colour is set to black? In this case, the turtles seem to have an ability to partially follow the walls of some of the buildings even though they are not applying wall following behaviour. How is this possible?

Notice what happens when the number of hills is set to 1 and the colour of the buildings is set to black - most of the environment ends up black. What causes this? Why does this not happen when the colour is set to white?


THINGS TO TRY

Try changing the values of the choosers and sliders and observe what happens in the simulation as a result.

Try changing the turtle behaviour during the simulation then observe what happens.

Try increasing the number of turtles so that at least one is created on every available space. What happens as a result for the different turtle behaviours?


EXTENDING THE MODEL

Add further turtle behaviours and/or modifications of the existing ones to the model.


NETLOGO FEATURES

To simulate the hill climbing sense, the model uses NetLogo's uphill command. To simulate the touch sense (for wall following via proximity detection), the model uses the patch-right-and-ahead command. To generate the terrain, the diffuse command is used.


CREDITS AND REFERENCES

Much of the code for this model is based on code provided by Uri Wilensky. It was taken from the Hill Climbing Example model and the Wall Following Example model, both available in the Code Examples directory of the Models Library.

To refer to this model in publications, please use:

Teahan, W. J. (2010). Hill Climbing with Wall Following NetLogo model.
Exercises for Artificial Intelligence. Ventus Publishing Aps.


PROCEDURES

; The code written by Uri Wilensky (see copyright message below)
; has been modified by Bill Teahan for the following book:
;
; Teahan, W. J. (2010). Exercises for Artificial Intelligence. Ventus Publishing Aps.
; 
turtles-own
[
  peak? ;; indicates whether a turtle has reached a "peak",
        ;; that is, it can no longer go "uphill" from where it stands
  direction  ;; indicates which direction the turtle follows a wall
             ;;  1 follows right-hand wall, -1 follows left-hand wall
]

to setup
  clear-all
  ;; make a landscape with hills and valleys
  ask n-of number-of-hills patches [ set pcolor 120 ]
  ;; slightly smooth out the landscape
  repeat 20 [ diffuse pcolor 1 ]

  create-random-buildings
  create-new-turtles
end

to go
  ;; stop when all turtles are on peak
  if all? turtles [peak?]
    [ stop ]
  ask turtles [
    if (turtle-behaviour = "Hill climbing")
      [ go-hill-climbing ]
    if (turtle-behaviour = "Wall following")
      [ go-wall-following ]
    if (turtle-behaviour = "Both")
      [ go-hill-climbing-and-wall-following ]      
  ]

  tick
end

to go-hill-climbing
  ;; the turtle agent applies hill climbing behaviour

  walk-uphill
end

to go-wall-following
  ;; the turtle agent applies wall following behaviour

  walk-by-following-walls
end

to go-hill-climbing-and-wall-following
  ;; the turtle agent applies both hill climbing and wall following behaviour

  ifelse (any? (patch-set patch-here neighbors) with [pcolor = building-colour]) ; any walls nearby?
    [ walk-by-following-walls ]
    [ walk-uphill ]
end

to restart
  ;; Restarts the simulation by kill off existing turtles and creating new ones.
  
  ask turtles [ die ]
  clear-drawing
  create-new-turtles
end

to walk-uphill  ;; turtle procedure
  ;; walk uphill if possible

  ;; remember where we started
  let old-patch patch-here
  ;; to use UPHILL, the turtles specify a patch variable
  uphill pcolor
  ;; are we still where we started? if so, we didn't
  ;; move, so we must be on a peak
  if old-patch = patch-here [ set peak? true ]
end

to walk-by-following-walls  ;; turtle procedure
  ;; turn right if necessary
  if not wall? (90 * direction) 1 and wall? (135 * direction) (sqrt 2)
     [ rt 90 * direction ]
  
  ;; wall straight ahead: turn left if necessary (sometimes more than once)
  while [wall? 0 1] [ lt 90 * direction ]

  ;; move forward
  fd 1
end

to-report wall? [angle dist]
  ;; note that angle may be positive or negative.  if angle is
  ;; positive, the turtle looks right.  if angle is negative,
  ;; the turtle looks left.
  report [pcolor] of patch-right-and-ahead angle dist = building-colour
end

to-report building-colour
  ;; returns the colour of the walls.
  
  ifelse (colour-of-buildings = "white")
    [ report white ]
    [ report black ]
end

to create-new-turtles
  ;; Creates new turtles by sprouting them at random patches.

  ;; put some turtles on patch centers in the landscape
  let max-turtles count patches with [pcolor != building-colour]
  if (number-of-turtles > max-turtles)
    [ set number-of-turtles max-turtles ]
  ask n-of number-of-turtles patches with [pcolor != building-colour]
  [
    ; print "Got here"
    sprout 1
    [
      set peak? false
      set color red
      set size 1.5
      pen-down

      ifelse random 2 = 0
        [ set direction 1 ]
        [ set direction -1 ]
    ]
  ]
end

to create-random-buildings
  ;; Creates a new set of random buildings.
  ;; make some random walls for the turtles to follow.
  ;; the details aren't important.

  ask patches
  [ if random-float 1.0 < 0.01 [ set pcolor building-colour ] ]
  ask patches with [pcolor = building-colour]
  [ ask patches in-radius random-float 4 [ set pcolor building-colour ] ]
  ask patches with [count neighbors4 with [pcolor = building-colour] = 4]
  [ set pcolor building-colour ]
  ask patches with [pcolor = building-colour] ; kill off the turtles that landed inside buildings
  [ ask turtles-here [ die ]]
end

; This model is Copyright 2010 William John Teahan.

; *** NetLogo 4.0.4 Code Example Copyright Notice ***
;
; (C) 2007 Uri Wilensky.  This code may be freely copied, distributed,
; altered, or otherwise used by anyone for any legal purpose.
;
; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
; A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT
; OWNERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
; LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
; DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
; THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
; (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
; OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
;
; *** End of NetLogo 4.0.4 Code Example Copyright Notice ***