Finding strategies comparison

This page presents the multi-agent simulation of comparison of strategies for finding a lost person in the forest made by Tomas Kadane.

Problem definition

This problem came to my mind because I have once lost my dog in a forest. I was thinking what would be the best strategy to find the dog. However it is pretty complex problem to simulate forest and all types of strategies, so this work is simplified by multiple factors (against the reality and work assignment). I'm comparing two strategies with variable number of searchers in square pane with fixed boundaries.

Method

For the simulation I have used NetLogo 6.3.0. I'm implementing two basic searching strategies. First one is based on random walk and the second is based on the walking to the edge of the forest and then bouncing in the opposite direction.

Searched person is represented by single red colored patch (representing area where the searched person can be seen). And the searchers are so called turtles beginning at random position. When any of the turtle enters the red area, the simulation stops and number of ticks is recorded. Both methods have been done 30 times for 1, 2 and 3 searchers.

First method - random walk

In the fist method I implemented random walk. Each step (represented by one tick) one step ahead is made and then the heading is changed by random angle using this formula:

set heading (heading + (angle / 2) - (random angle))

If the searchers hits the border of the forest, he will turn "backwards" as described in this code:

to check-borders
  if (xcor < min-pxcor) [set heading (heading + 180)]
  if (xcor > max-pxcor) [set heading (heading + 180)]
  if (ycor < min-pycor) [set heading (heading + 180)]
  if (ycor > max-pycor) [set heading (heading + 180)]
end

After measuring 30 times for each angle and 1, 2 and 3 searchers I created table of average steps (ticks) needed to find the searched person. Not agregated data can be found in File:Results random walk.xlsx

Averages for random walk depending on the angle

Searchers	45 angle	90 angle	180 angle	360 angle
1	1033	583	633	1301
2	398	304	403	658
3	290	219	130	371

To see how steps needed vary I used standart deviation.

Standart deviations for random walk depending on the angle

Searchers	45 angle	90 angle	180 angle	360 angle
1	885	543	662	1793
2	377	236	356	869
3	366	237	128	472

Second method - bouncing

In the second method searchers and searchers are spawned on the random position. Setup is same as in the first method. However the moving method differs. Searchers are moving in direct way and when they hit border they bounce in oposite direction as described in this code:

to check-bounce
  ;; bounce off left and right walls
  if abs pxcor = max-pxcor [
    set heading (- heading)
  ]
  ;; bounce off top and bottom walls
  if abs pycor = max-pycor [
    set heading (180 - heading)
  ]
end

The method of recording steps needed to find the lost person was same as in the first method, however the angle is not variable now. To see how the data vary I have used standart deviation again.

Averages and standart deviations for bouncing method

Searchers	Average	St. dev.
1	566	624
2	192	161
3	180	141

Results

To evaluate random walk method. We can see that if we are searching alone, the 90 angle seems the most efective, however 180 angle seems not bad at all too. If we are searching as two people - 90 angle is the most suitable. When there are three searchers the 180 angle seems the best.

When we want to compare our two methods, For one searcher bounce method is better even then the most effective angle in random walk method. For two searchers it is the same, bounce method is more effective again, even then the 90 angle method. For three searchers is the random walk with the 180 angle most effective.

However if we want to evaluate the standart deviation, basicly it is always better with the bounce method. So it seems like safer choice if we don't want to risk really long journey to find the dog.

Conclussion

Although we can see in the tables, that there are differences in both strategies we mustn't forget, that we are using only 30 observation for all the variants. The number should be more significant to say that certainly. However we can see significant difference in standart deviation and thus we can see that using random element in our searching strategy can pay off but also can be pretty bad.

Code

Random walk method

globals [
  found
]

to setup
  clear-all
  reset-ticks
  set found false 

  setup-searchers
  setup-lost-area
end

to setup-searchers
  create-turtles searchers [
    pen-up
  ]
  ask turtles [
    setxy random-xcor random-ycor
  ]
end

to setup-lost-area
  ask patch random-xcor random-ycor [
    set pcolor red
  ]

end

to check-borders
  if (xcor < min-pxcor) [set heading (heading + 180)]
  if (xcor > max-pxcor) [set heading (heading + 180)]
  if (ycor < min-pycor) [set heading (heading + 180)]
  if (ycor > max-pycor) [set heading (heading + 180)]
end

to go-random
  if found = true [
    stop
  ]
  tick
  ask turtles [
    if pcolor = red [
      set found true
    ]
    check-borders
    set heading (heading + (angle / 2) - (random angle))
    forward 1
  ]
end

File:Sp random walk.nlogo

Bounce method

globals [
  found
]

to setup
  clear-all
  reset-ticks
  set found false

  setup-searchers
  setup-lost-area
end

to setup-searchers
  create-turtles searchers [
    pen-up
  ]
  ask turtles [
    setxy random-xcor random-ycor
  ]
end

to setup-lost-area
  ask patch random-xcor random-ycor [
    set pcolor red
  ]

end

to check-bounce
  ;; bounce off left and right walls
  if abs pxcor = max-pxcor [
    set heading (- heading)
  ]
  ;; bounce off top and bottom walls
  if abs pycor = max-pycor [
    set heading (180 - heading)
  ]
end

to go
  if found = true [
    stop
  ]
  tick
  ask turtles [
    if pcolor = red [
      set found true
    ]
    check-bounce
    forward 1
  ]
end

File:Sp bounce.nlogo