Reducing GPS data error on Android with Kalman filter and accelerometer

Prehistory

One day I got a cool task to improve the accuracy of positioning and distance calculating based on GPS data on Android devices. After some research, I found that different GPS-receivers produce different errors. The accuracy of the GPS point can be influenced by buildings, big trees, various weather conditions and by the satellites configuration. GPS gives nice values to detect one-time position, but its accuracy is not enough when using a stream of GPS data to calculate distance and cost of taxi-services. The received data is not suitable due to the error accumulation. The error accumulation may lead to 400% of overpricing and to customers dissatisfaction as the result.

Therefore, at first, the problem should be solved on Android devices. Most drivers use Android smartphones because of their low price. The next step is to implement some online service for that.

A brief search has shown that one of the most reliable methods to increase positioning and distance calculating accuracy is to create vector map of the roads and to project GPS coordinates to the nearest road like it’s implemented here. In addition, some graph-based checks should be implemented. This method might be suitable if there was a map of road coordinates. Yet the collection of such information for the map is very difficult and resource-consuming, therefore, we cannot use this method. We could use google map roads API, but that service has a limitation — maximum 2500 requests per day. Also, some phones don’t support google play (yes, they do exist).

Formulation of the problem
Since we do not have a reliable database with road coordinates, we need to get better GPS coordinates programmatically. It means that we have to implement an algorithm to solve the following issues:

1. The false increase of distance when a car is not moving.
2. Sharp “jumps” to a point remote from real route for significant distance (about 500 meters)
3. Short-term loss of GPS signal

Herewith, the algorithm should not consume whole battery within 3 minutes as well as all available RAM. What is more, it should not accumulate coordinates, but process only several previous and current coordinates instead.

The next research has shown that the most common solution for the issues of positioning and noise is the Kalman filter. There are a lot of articles about it on the web, so I will not explain how it works. Our goal is to provide the pragmatic solution, without a ton of theory.

So, here is a question: what can provide information about object position except for GPS? We could use wi-fi points, but there are not many free wi-fi points in our city. We could also use GSM towers, but again, it is necessary to collect information and create a map of such objects (wi-fi and gsm towers). In addition, those sources do not provide precise results. To get more accurate results we need information about the motion characteristics like velocity and direction. The first google request returned that modern smartphones have a bunch of sensors such as an accelerometer, magnetometer, and gyroscope. It means that theoretically, we have one more source of position data. Besides, we need to know what do those sensors do and how to use them.

Read the rest here: https://blog.maddevs.io/reduce-gps-data-error-on-android-with-kalman-filter-and-accelerometer-43594faed19c