# 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
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 [
]
;; bounce off top and bottom walls
if abs pycor = max-pycor [
]
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. Non agregated data can be seen here File:Results bounce.xlsx

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
]
setxy random-xcor random-ycor
]
end

to setup-lost-area
set pcolor red
]

end

to check-borders
end

to go-random
if found = true [
stop
]
tick
if pcolor = red [
set found true
]
check-borders
forward 1
]
end
```

## 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
]
setxy random-xcor random-ycor
]
end

to setup-lost-area
set pcolor red
]

end

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

to go
if found = true [
stop
]
tick