This document was written by Paul Edwards and is released
to the public domain. It can be found at:
http://freespace.virgin.net/paul.edwards3/gpsavg/peavg.txt
POST-S/A Addendum at end.
Averaging - just how useful is it?
----------------------------------
The answer to this question is not straightforward. It
depends on the following 3 factors:
A. What you are planning on using the waypoint for.
B. How much it costs you to average.
C. How many satellites you can see.
A - What you are planning on using the waypoint for
---------------------------------------------------
Ignoring 3D applications where altitude is important,
and the benefits of averaging are actually higher,
there are 4 broad categories of use for a waypoint
in practical terms. Your practical use is more
likely to be a mixture of them rather than fall
100% into one category. Accuracy is normally quoted
in RMS, but RMS is a single measure that doesn't
actually represent ANY of the 4 practical uses, it
attempts to give a single general figure to encompass
them all.
1. How far you are away from the true position "on average" (in metres).
2. The size of the search area "on average" (in square metres).
3. The worst-case scenario, as seen by the maximum distance
you can get away from the true position (in metres).
4. The worst-case scenario, as seen by the maximum search
area you may end up having to search.
Some examples of all 4 types of use are:
1. You are in a clearing and have line of sight to all objects,
so as long as you are within reasonable distance to the object,
you will spot it immediately. But its actually dark so you
have to first of all get to the location on your GPS by car,
then get out and use a torch to scan 360 degrees until you see
the object. You are interested in average distance because that
is how far you have to walk, and that is your cost that you are
trying to reduce.
2. You are in a crowded marketplace, looking for a particular
stall. Because there are stalls everywhere and people
everywhere you can only see one stall at a time. Once again
you want to reduce the distance so that you find the desired
stall sooner.
3. You are in the clearing again, dropped off by the taxi
driver, and now you have to walk to the object. You can
walk about 100 metres OK, but after that your arthritis
kicks in and it is excrutiating painful to walk further.
You don't particularly care about reducing the distance
from 90m to 80m, as your arthritis doesn't bother you at
those distances. However, 200m and you'll probably have
fainted trying to get there.
4. You are're in the market place again. The next bus
is in 10 minutes time. Then there is another 20
minutes for the one after that. After that, you
have to catch a taxi, much more expensive. But
you need to find the stall regardless. In 10
minutes you can search a circle with radius 100m.
But a circle with radius 200m is 4 times the
area, which means you will miss the last bus. You're
keen to catch the first bus. There is no advantage
to decreasing the search time below 10 minutes
because you have to wait for the bus anyway. You
are not interested in the average, just getting rid
of the extremeties, which DO cost you.
B - How much it costs you to average
------------------------------------
Nothing comes for free, or does it? Perhaps you are taking
the waypoint for your employer, and he is having to pay you
for every minute that you're standing around doing nothing.
Or perhaps you're sightseeing and you're enjoying the view
from Mrs Macquarie's Point, and time spent averaging is
totally free. In many cases, GPS receivers allow you to
average whilst entering the name of the waypoint, which
may take a minute. If you usually stand still to do this
(instead of bumping into things whilst you enter the name
whilst walking), then this minute is often free. But
usually the average beyond the one minute will not be free,
e.g. if you're in a foreign city, do you really want to
stand outside your hotel so that you can find it again
easily or is your time better spent touring?
In some situations you actually NEED a particular accuracy,
regardless of the cost, so the cost essentially becomes
irrelevant, you just have to look up the value and charge
the employer accordingly.
C - How many satellites you can see
-----------------------------------
The S/A error introduced by the different satellites
does not cause a constant error, e.g. 50 metres to
the North. Otherwise it would be easy to correct
for. Instead, the satellites all have their own
errors put out, and the result of this is that when
you average them all out, the result is not as bad
as if you just opened yourself up to one of them.
This process is known as overdetermination. Generally,
the more satellites you have, the better you reduce
the effects of S/A. Because the effects of S/A have
already been reduced, averaging has less potential for
gain. And the converse is true.
So how do you combine all these factors? Well it is
simple enough to graph long term averages on the pure
forms of the 4 uses. John Galvin has provided this
data for the first 8 minutes of averaging at various
intervals. I don't have a full set of data for any
other set of "satellite visibility" so you cannot
see the results of that, you'll have to judge for
yourself.
To deal with the cost issue, we can graph the simplest
case, where the cost is directly proportional to time,
say you are a wage-earner and taking the waypoint for
your boss to use later. Let us also assume the
"average search area" (case 2) scenario, and that the
time (and cost) are directly proportional to the
search area.
There is still a constant factor missing, that
depends on your application, so needs a judgement
call made. That is the time/cost taken to search
each unit (ie square metre). So the best that can
be done is graph the reduction in search area
against cost (time). But that graph alone is not
sufficient to make a judgement call, as even if
you're getting near-zero value for money at the
moment, it might still be cost-justified to continue
if in a little while you'll be back in the black.
So we need 3 different graphs for each usage scenario,
e.g. average search area.
1. average search area versus time, for applications
that require a particular average search area, regardless
of cost.
2. gradient of (1), ie reduction in search area per
minute (unit cost) versus time (cost), for cost-sensitive
applications.
3. reduction in search area to date per time (cost)
versus time (cost).
Graph 3 will show you what length of time gives you the
best value for money, which prevents you stopping at a
peak or trough of Graph 2. Graph 2 is useful for if you
want to stop immediately (meaning cost isn't really
proportional to time, it's more expensive for larger
times), but want to make a judgement call as to whether
the gain currently being had is worth it, ie if you're
at the best rate you can get, you'll stay on for another
minute anyway.
Graphs 2 and 3 are derived from 1, they just show the
information needed to make those decisions clearer.
So you can see we need a total of 12 graphs, 3 for each
of the 4 usage scenarios.
First, John Galvin's data:
avgtime avgsrch maxsrch
0 sec 9762.452408 113339.7668
1 sec 9760.270024 111823.6649
15sec 9701.816866 96078.86435
30sec 9595.167867 86487.03635
60sec 9281.674712 71202.35339
120sec 8433.794734 50641.68168
240sec 6818.709443 24735.88637
360sec 5700.897571 17839.41602
480sec 4931.960283 15908.32562
all in square meters
avgtime rmserror avgerror maxerror
0 sec 55.744821 49.24206883 189.9399056
1 sec 55.73858981 49.23444454 188.6652525
15sec 55.5714331 49.07659576 174.8795355
30sec 55.26514947 48.87212795 165.9206988
60sec 54.35484134 48.30882213 150.5470447
120sec 51.71998073 46.61398298 126.9635684
240sec 46.58822378 42.68752282 88.7337425
360sec 42.59873273 38.84340466 75.35557312
480sec 39.62185878 35.45462813 71.16022234
all values in meters
Before we go on, it is worth looking at one particular
set of data, that at the 4 minute mark. 4 minutes is
the period of correlation for S/A. Here are the results...
reduction caused by 4 minutes averaging (correlation period):
RMS: 16%
Usage Scenario 1 (average error): 13%
Usage Scenario 2 (average search area): 53%
Usage Scenario 3 (maximum error): 30%
Usage Scenario 4 (maximum search area): 78%
The full 12 graphs can be found at
http://freespace.virgin.net/paul.edwards3/peavg.123
Unfortunately I don't have the ability to translate
the graphs into jpegs for universal display, so it
is only of use to people with Lotus 123. However,
you can graph them yourself from the raw data, e.g.
here is the data for the average search area reduction
rate, ie Scenario 2 Graph 2 (square metres/minute)...
0 0
1 131
15 251
30 427
60 627
120 848
240 808
360 559
480 384
I think the average search area reduction is the most
interesting one to look at, because an average distance
application doesn't come up too often. If you can see
the object line of sight it doesn't normally make a
difference whether its 100 or 50 metres away. Searching
applications are considerably more expensive.
As you can see, we get into the law of diminishing returns
around the 6 minute mark, the most gain actually happens
quite early on, and in fact by the first 4 minutes the
search area has already halved!
I have graphed another set of data, this one with a better
RMS, about 36 metres. This data has been processed by me,
with raw data obtained from:
http://www.cnde.iastate.edu/staff/swormley/gps/Data/99081201.asc
for location 41.501596, -81.607336. I have calculated results
for every single second from 1 second to 32 minutes. The
C code to do this can be found in ozpd at www.kerravon.w3.to,
gpsdist.c. The resultant spreadsheet is called peavg2.123.
Interesting points to note are the peaks of position
improvement rate, occurring at (seconds):
rms = 207
avgerror = 194
maxerror = 289
avgsrch = 183
maxsrch = 231
However it is the best total reduction/time which is
what is the best value for money assuming a linear
cost. These peaks occur at.
rms = 351
avgerror = 351
maxerror = 379
avgsrch = 307
maxsrch = 337
So for average search area applications, 5 minutes 7 seconds
is the most cost-justified averaging time, assuming cost
is proportional to time. Or put another way, if you want
to earn something (reduced search space) for your time spent,
then spend just over 5 minutes there, and you'll get paid the
highest rate of any averaging time. I think this is the most
important number to remember.
After 4 minutes we see the following reductions, not as
good as John Galvin's data due to the lower starting RMS...
rms = 16%
avgerror = 15%
maxerror = 23%
avgsrch = 29%
maxsrch = 40%
For completeness, there is an earlier graph available,
peavg.gif, which uses some data points provided by David
Wilson to determine the rate of search area reduction as
a function of time. I do not know what the reason for
the dramatic changes earlier on are, but they are not
reproduced in the other graphs, and are minor in the
scheme of things (since they are short-lived) so are
probably best ignored.
One other point not covered is in the practical searching.
Most real-life searching of places will involve arriving
at the GPS location and then, if you can see the object,
going directly there, or if you can't, then having to
perform an expensive search. The real practical gain
comes when you go from an expensive search to a
line-of-sight. This difference could be very small, e.g.
just 2 metres closer may have given you line-of-sight, or
perhaps it would have made you more inclined to go in the
correct direction.
If you e.g. need to be within 50 metres to see something,
and you've only got 50% chance of being within 50m, 52% of
being within 52m, then you will have 2% less searches to do.
With more than one user of a waypoint, and more than one
waypoint, that's 2% saving for lots of people, with only
one cost of taking the original waypoint, so the benefits
may be enormous. As always, it depends on exact usage.
POST-S/A Addendum, using RMS figures from David Wilson:
time (mins), rms error, search area/const, (area reduction/const)/cost(time)
0 5.62 31.58
1 5.11 26.11 (5.47)
2 4.79 22.94 (4.32)
5 4.33 18.75 (2.57)
15 3.85 14.82 (1.12)
30 3.5 12.25 (0.64)
60 3 9 (0.38)
120 2.45 6 (0.21)
This is for applications where search area is the best model (which I
believe is the most accurate model for the majority of situations).
The SA the situation was very different. You actually got the BEST
rate of decrease at the 3 minute mark, with the best overall rate
(value for money) at the 5 minute mark.
As we can see, you get the best value for money now is at the 1 minute
mark. I suspect it is even less than that, and that the best rate
approaches 0, ie you hit the law of diminishing returns immediately.
So I don't think I'll average for any time that isn't free.
Having said that, you do halve the search area in about 8 minutes, same
as when SA was on. But back then, it was a much larger area that was
being eliminated. Still, it's good to know that you can spend just 8
minutes at a site and do more reduction in search area than the next
50 years. Certainly worth trying to find a reason to stick around!