Kadt02: /* Second method - bouncing */

2023-01-23T18:49:29Z

‎Second method - bouncing

Kadt02 at 18:48, 23 January 2023

2023-01-23T18:48:54Z

Kadt02 at 18:46, 23 January 2023

2023-01-23T18:46:35Z

Kadt02: Created page with "This page presents the work 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..."

2023-01-23T18:41:34Z

Created page with "This page presents the work 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..."

New page

This page presents the work 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

[[File:randomwalk_UI.png]]

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

{| class="wikitable"
|+ align="top" | '''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.

{| class="wikitable"
|+ align="top" | '''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

[[File:bounce_UI.png]]

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.

{| class="wikitable"
|+ align="top" | '''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]]

@@ Line 64: / Line 64: @@
 [[File:bounce_UI.png]]
-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]]
+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]]
 {| class="wikitable"

← Older revision		Revision as of 18:46, 23 January 2023
Line 1:		Line 1:
−	This page presents the ~~work~~ of ~~Comparison~~ of strategies for finding a lost person in the forest made by Tomas Kadane	+	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=		=Problem definition=

Finding strategies comparison - Revision history

Kadt02: /* Second method - bouncing */

Kadt02 at 18:48, 23 January 2023

Kadt02 at 18:46, 23 January 2023

Kadt02: Created page with "This page presents the work 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..."