Estimating speed from position updates with uncertain time intervals

Question

I have 2 alternative methods to solve a problem, and I was just wondering what people who know the math better than I think, and if there is a better method to use for this type of problem.

The problem: I have a list of lat/lon positions and a value for the time interval between position updates and wish to find the SOG (Speed Over Ground). However there is some uncertainty in the exact value for each time interval - as the data is retrieved over the internet, even though in a program it would (for example) be set to request an update every 60 seconds. The data comes from an ocean racing yacht simulator, so SOG will also change with varying conditions and also with changes in course (relative to wind).

One approach is to weight new updates proportional to the length of time that interval and multiply into our current best SOG estimate. Something like this (T in seconds):

$$\text{speed} = \text{distance} / \Delta T$$ $$d = 1 - e^{-\Delta T}$$ $$\text{sog} = d * \text{speed} + (1 - d) * \text{sog}$$

And this works ok, especially if the speed is relatively consistent.

Prior to seeing this method, the one I had come up with to estimate SOG is this:
Maintain a list of the $N$ most previous {timestamp, lat, lon} tuples.
On each update, compute the harmonic mean of all possible sub intervals from $0, N-1$:

$$ S = N(N+1)/2 $$

$$ \text{sog estimate} = S / \sum_{i=0,j=i+1}^{N-1} \text{time}_{ij} / \text{distance}_{ij} $$

Then keep a list of the $M$ most previous estimates and again take the harmonic mean. $N$ & $M$ should not be too large. And obviously if there are not yet $N$ tuples to sum sub-intervals over, just use however many are available. Since the updates occur each 60 seconds, a value of 10-15 seems appropriate for both $N$ & $M$. One possible improvement I can think of is to weight each sub interval similar to method 1. This second method seems to be more accurate than the first, although can sometimes take longer to converge on a reasonably accurate estimate - usually approximately N updates are required before it becomes accurate for any practical use.
It also seems to handle changes in 'real' SOG better, ie slight accelerations.

Given that SOG is rarely consistent over say more than 15 or 20 minutes, ie from an increase in wind strength, or change of angle to one with higher/lower boatspeed etc, and also that direction can change (again, with a change in speed), what would be the best algorithm to compute the SOG from uncertain time intervals and change in position. Also, is there a possible way to estimate the error in estimation? Even possibly correct for this error term once computed? I should mention all the data I have available: heading, lattitude and longitude, and I keep a timestamp from the beginning of each update request.

I would like to be able to compute this speed as accurately as possible.

Thanks in advance for any assistance, and forgive my poor use of MathJaX.

Edit: I get Math processing errors from MathJaX that works fine on math.stackexchange? Notice a lot of them in either questions to?? So reposted plain text math.

Answer 1

Because you trust the GPS positions (and therefore the distances computed from them) but the times have errors, regress the times against the cumulative distances.

To account for acceleration and deceleration, consider a model of the form

$$\text{Time} = t = \beta_0 + \beta_1 X + \beta_2 X^2 + \varepsilon$$

where $X$ is distance and $\varepsilon$ represents the time errors. After fitting this you can estimate $\widehat{dt/dX} = \hat{\beta}_1 + 2 \hat{\beta}_2 X$, whence

$$\text{Speed estimate} = \widehat{dX/dt} = 1/\widehat{dt/dX} = \frac{1}{\hat{\beta}_1 + 2 \hat{\beta}_2 X}.$$

This will likely work best for times near the middle of your dataset. Thus, for instance, you could maintain a circular buffer of $k$ observations which at any moment would span times $t_1, t_2, \ldots, t_k$ and use them to estimate speeds near the mean position $\frac{1}{k}\sum_{i=1}^{k}X_k$.

As an example I generated distances according to the formula $X(t) = 15 + i - i^2/25$ for times $t=1, 2, \ldots, 10$. This represents a period of uniform deceleration from a unit speed. Note that it is not the same as the postulated model: the variation in time is given by the quadratic formula. I then varied those times by independent standard normal variates. Compared to the nominal sampling interval this is a huge error: you can't even be sure that two successive times are actually in the right order. This is a fairly severe test of the method.

Here is a plot of a typical realization, with the red dots showing the true values, the blue ones showing the observed values (i.e., the true values with time jittering), and the ordinary least squares fit of the time. I used $k=10$.

Note that the time measurements are so awful, the boat seems to reverse its course several times, especially near times 2 and 4.

Unlike many of the realizations I looked at, this fit doesn't look terribly good in the center: the line departs from the red dots. Be that as it may, let's look at how the estimated and actual speeds varied during this period:

(Note that you can estimate a speed at any time, not just a measured time, because the fitted coefficients give a formula for the speed.)

In this plot of speed versus position (not time), the blue curve is the estimate and the red curve is the actual speed. Obviously they are not very close near the ends, but for the middle times the estimate is excellent. (The middle times are around positions 19-20, as the first plot indicates.) Note that you would run into severe difficulties estimating speeds directly from the sequence of positions, because (due to the errors in the times) the boat seems to be jumping around forwards and backwards. If you treat the backwards jumps as true reversals you would grossly overestimate the speeds, but if you treat them as negative speeds you would run into severe problems when averaging. The moral here is that it's best to fit a model of position versus time and only then attempt to estimate speeds; don't attempt to estimate speeds directly.

The larger $k$ is, the more accurate you can expect to be. Use the machinery of OLS to estimate the prediction error of the time for any desired position; from that you can propagate the error to the speed estimate.

The speed estimates might jump around a little due to the addition of new values and dropping of old values as you go along. You could get fancier and use weighted regression, decreasing the weights smoothly to zero near the extreme positions. In doing so, a plot of estimated speeds versus position would be a little smoother. (This technique is akin to the recently popularized "Geographically Weighted Regression" of Fotheringham, Charlton, and Brunsdon.)