At Rover, we have started taking advantage of the benefits of having a native app to create features like GPS tracked walks. These Rover Cards are great for owners to see the route taken on a dog walk, or verify that a sitter visited your pet during the day. One feature of these Rover Cards is to display the distance that a sitter has walked with your dog. As you can imagine, calculating distance from a bunch of location data points comes with many challenges.

The biggest challenge we faced is how to display the actual distance a sitter has traveled. Mobile device GPS points can have varying degrees of accuracy, depending on the GPS signal strength in rural areas, how many tall, steel, concrete buildings are warping the signal in a more urban setting, or other factors.

Originally, we decided to sort all of our “steps” or data points on their accuracy value and filter out the bottom 25% of those steps (the least accurate). That way, we’re left with steps that are (hopefully) accurate enough for a - relatively - correct distance calculation. This initial attempt didn’t really work as well as we’d hoped. Distances were still all over the map, because, in the real world, you can’t really make assumptions about how accurate someone’s mobile GPS “steps” might be.

After getting multiple user reports about how inconsistent these distance calculations were (yay, feedback), we spent some time researching various methods of improving our calculations. The team consensus landed on using Kalman filtering method. Kalman filtering is an algorithm that uses measurements observed over time, containing statistical noise and other inaccuracies, and produces estimates of unknown variables that tend to be more accurate than those based on a single measurement alone. So instead of just measuring the distance between two lat/long points, we now can take into consideration the accuracy of those points and the (assumed) average speed that a person is walking, as well.

Here, we see a map of raw data points from an actual walk:

Raw Points

Calculating the expected distance of that walk on an actual map, we get 1.08 miles walked:

Calculated Distance

Here is the algorithm that we are using:

if (step.accuracy < 1) step.accuracy = 1;

long elapsedTime = step.time.getTime() - timeStamp;
if (elapsedTime > 0) {
    // time has moved on, so the uncertainty in the current position increases
    // 3f denotes a speed of 3 meters per second.
    // We're assuming that people will be traveling that fast on average
    variance += elapsedTime * 3f * 3f / 1000;
    timeStamp = step.time.getTime();
}

// Kalman gain matrix
// K = Covariance * Inverse(Covariance + MeasurementVariance)
// Because K is dimensionless, it doesn't matter that variance has different units to lat and lng
float K = variance / (variance + step.accuracy * step.accuracy);

// apply K
lat += K * (step.location.latitude - lat);
step.location.latitude = lat;
lng += K * (step.location.longitude - lng);
step.location.longitude = lng;
// new Covariance  matrix is (IdentityMatrix - K) * Covariance
variance = (1 - K) * variance;

A step here is a data point containing a lat/long location coordinate, an accuracy value, and a timestamp of when that point was recorded.

After plugging in the raw data points into our algorithm, we get a distance of 1.0376421374353721 miles. We’re only off by 0.05 miles! With a few simple lines of math, we’re able to vastly improve the accuracy of our walk distance calculations. And now, you can do it too!

Scout

If you want to come up with creative solutions to interesting problems like this, we’re hiring!