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