“Current Sustained Speed” (Part I)

A helpful new feature in v4.0 is the addition of live (and after-action) pace data from a trail. After using the app extensively myself for running, I realized that seeing my current mile or kilometer pace is at least as useful as (if not more useful than) my speed.

The Problem

The speed values that come out of CLLocationManager tend to be a bit difficult to wrangle; they can jump all over the place, especially when the signal of the GPS isn’t great. Perhaps most nefarious is the occasional 0.0 speed value that comes out of nowhere when you are driving down the highway at 70 miles per hour. If I wanted to determine when a user has truly stopped, I needed to do better than just taking the speed value from CLLocationManager naïvely.

This problem led me to rethink what ‘speed’ value I really wanted in the first place. I experimented with thresholding filters with a running average, Kalman filters, coffee filters, and just about everything under the sun. Ultimately, I decided that just smoothing or filtering the instantaneous speed to get a more ‘accurate’ value was the wrong objective. When I used Trail Tracker myself, I wanted to know what my current pace was, but not necessarily at the precision of each individual location update (which can vary greatly), and also not at the granularity of each mile, kilometer, or other fixed distance. We wanted to get a feel for how I’m doing for the last little bit. Quantifying that ‘little bit’ is the tricky part, and that’s what we’ll address here.

A Simple Solution

@property (nonatomic) CLLocationSpeed filteredSpeed;

...

/*
  When we get a new location, update our filtered value and return the result.
 */
- (CLLocationSpeed)filteredSpeedWithUpdate:(CLLocation*)newLocation {
    // this is our tunable parameter
    // amount of importance we assign to a new value
    // alternatively, we can think of this as the 'learning rate'
    //  to take a machine learning perspective
    static const double alpha = 0.75;

    self.filteredSpeed = self.filteredSpeed * (1.0 - alpha) + newLocation.speed * alpha
    
    return self.filteredSpeed;
}

In practice this solution doesn’t get us much. We certainly smooth the speed values over time, but this approach ignores an important piece of information about the new location we are seeing: the age of that data. This function is time agnostic, so five updates spaced 3 seconds apart would yield the same result as updates spaced 3 minutes apart, which is obviously not desirable. If the GPS loses its signal for ten seconds or so, we will go right into averaging the new data with very old values once we regain a connection, and that’s no good. If we are trying to calculate a smoothed value that is still semantically useful, taking into account data from 3 minutes ago isn’t going to help.

The implications of this method are also unintuitive: by repeatedly averaging a new measurement with the old filtered measurements, any particular piece of data averaged into the filtered value theoretically maintains a presence in the filtered value forever, since we’re just repeatedly averaging (in practice, the limits of a double’s precision will cause the value to eventually get ‘pushed out,’ but assuming we have a double with an 11 bit exponent [CLLocationSpeed is defined as a 64 bit double on arm64, which according to IEEE 754 has an 11 bit exponent], we’re dealing with a scale of 22048 – 1023 / log2(10) = 10-308, on the order of a thousand updates, assuming an alpha of 0.5).

Of course the value will quickly be forgotten once it passes the thousandths place or so, but regardless, using a method that lets old information stick around for so long just felt kind of wrong.

A Better Solution

A more intuitive solution should take advantage of when an update comes in. The CLLocation class provides a timestamp when updates come in, which we can use to our advantage. In order to take advantage of this information, we need to re-think our approach to smoothing. Specifically, we will have to keep not only old speed information around that we want to smooth with, but also the timestamps. Therefore, we’ll just be hanging on to entire CLLocation objects to keep things simple.

@property (nonatomic) NSMutableArray <CLLocation*>* history;

...

/*
  When we get a new location, take an average from a particular slice of the
   history and return the average.
 */
- (CLLocationSpeed)filteredSpeedWithUpdate:(CLLocation*)newLocation {
    // lazy load the history
    if (!self.history) {
        self.history = [[NSMutableArray alloc] init];
    }

    // these are our tunable parameters
    // how far back in time we can look for data
    // larger values will give a less responsive (but smoother) output
    static const NSTimeInterval maxAge = 15.0;
    // how big we need the history to get before we can use our smoother
    static const int minimumHistorySize = 3;
    
    CLLocationSpeed filteredSpeed = 0;
    
    // we'll use this to keep our history trimmed
    int outdatedIndex = -1;

    if (self.history.count >= minimumHistorySize) {
        // so we can keep a running average without storing huge sums
        int speedCount = 0;

        for (int idx = self.history.count - 1; idx >= 0; --idx) {
            CLLocation* thisLocation = self.history[idx];
            if ([newLocation.timestamp timeIntervalSinceDate:thisLocation.timestamp] > maxAge) {
                outdatedIndex = idx;
                break;
            }

            // keep a running average
            speedCount++;
            filteredSpeed += (newLocation.speed - filteredSpeed) / speedCount;
        }
    } else {
        filteredSpeed = newLocation.speed;
    }

    // trim out locations we'll never need again
    [self.history removeObjectsInRange:NSMakeRange(0, outdatedIndex + 1)];

    // keep building our history
    [self.history addObject:newLocation];

    return filteredSpeed;
}

How do we feel about this? I’d say it’s better, but it still has some serious shortcomings:

  • The time cutoff isn’t very intelligent: the averaging still doesn’t take into account the age of the data. It only makes a binary decision on whether or not the data is ‘new enough’ based on our parameters.
  • If you are familiar with the Kalman filter, you’ll also notice that we don’t have any parameter analogous to the decay rate in the Kalman filter: any update that comes within the valid time period gets equal treatment, which isn’t optimal.
  • If we stop, we’d like to know we’ve stopped more quickly than the amount of time it takes the maxAge value to invalidate the history.

I’ll discuss how I went about addressing these issues next time. Thanks for reading!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s