# 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.

## Contents

# 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

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.

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. Non agregated data can be seen here File:Results bounce.xlsx

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

## 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