Download PDF - Durham e-Theses

34 Chapter 3. Search and Rescue as a Weighted Cleaning Problem
Here, (i0 , j 0 ) is a cell whose position is not based on the position (i, j), and k is the
p
distance between the two cells (i, j) and (i0 , j 0 ), such that k = (i − i0 )2 + (j − j 0 )2 ;
this would require — for a map of size w × h, where w ≥ h — w2 h2 comparisons,
as each cell would need to be compared wh times.
Comparing this to the number of calculations required in the same situation
from the recursive, neighbour based Equation 3.1, each cell is compared against
its eight neighbours and itself, requiring 9 comparisons. This is repeated as the
information disperses across the board. Taking a non-optimised case of updating
all cells in every iteration until a stable state is reached, each iteration requires 9wh
comparisons. The map will stabilise once — in the worst case — a highly valued
cell in one corner has diffused to the opposite corner. Travelling using diagonals
and perpendiculars, it will reach there in at most w iterations (where w ≥ h). This
means that the total number of comparisons will not exceed 9w2 h — which even in
its worse case will be faster unless h < 9. The same would be true for any diffusion
method which could not be calculated recursively.
The Navigation Map produced by Equation 3.4 is shown in Fig 3.5.
The speed of calculation can be improved by limiting the size of the area over
which the calculation has taken place. If (i0 , j 0 ) is limited such that k ≤ R (where
R is a constant ‘radius’ value) then the number of calculations is reduced to πR2 wh
comparisons. While this would greatly reduce the amount of time required to calculate the navigation values, it would be at the expense of the amount of data available
to the robot at any given point — limiting the range over which it could detect high
base values, and thus preventing it from being able to seek out the highest base
values on the map.
It should be noted here that the Navigation Map produced by Equation 3.4 is not
entirely appropriate for a hill climbing algorithm. As has been mentioned, for each
of the methods mentioned here there will be a pay off between at the one extreme
guiding the robot to a high valued cell regardless of distance and at the other to
a close cell regardless of value. The results of Equation 3.4 give a navigation map
which is too close to the second of these extremes. Short distances will skew the
navigation values calculated, and in the extreme (when comparing against a cell’s