Download PDF - Durham e-Theses

3.4. Results
53
example, one iteration only found a small number of people before getting stuck but
all other iterations in that set found all people then a lot of useful data would be
removed.
A third possibility would be to directly include the times for that iteration up to
the point where the robot became stuck in the averages for that set; that is, included
into the average time taken to find each number of people found up to that number.
The downside to this is that the average time taken will then drop for later numbers,
as the robot is liable to be running slowly in the run up to it becoming stuck.
A final option would be to continue the data for the incomplete iterations through
extrapolation — extending the results to estimate the times at which later people
would have been found had the robot not become stuck (for imperfect cleaning),
and the time taken to clean all cells at a particular initial Base Value (for perfect
cleaning). This has the downside that the data being used is artificial, and does not
come wholly from actual simulation results.
In the results shown below it was decided, for imperfect cleaning, to extrapolate
all data which had found 100 or more of the 500 people. Iterations which had failed
to find 100 people were discarded, with the average for that run calculated from the
other iterations.
The algorithm which is most affected by this, by some margin, is the Low Pass
Filter method.
For perfect cleaning, the majority of methods failed to complete to such a degree
that only a subset of algorithms are presented.
3.4.2
Computational complexity
The time axis on all graphs is based on the number of movements between cells
taken by the robot. It does not take into account the amount of time the algorithm
took to compute — some algorithms are more computationally intensive, but still
able to complete the task in a smaller number of movements.
While this is a difficult metric to measure (as the speed of completion is based
on many factors, including the speed of the processor and the number of concurrent