## Why do you need Mad Location Manager?

Are you tired of «extra» kilometers duу to an inaccuracy of GPS-data in taxi applications?

Are there regular sharp «jumps» in the Applications for Courier tracking?

Do you need precise tracking in an on-demand service?

##### The solution is Mad Location Manager

## What are the features of Mad Location Manager?

It reduces the errors in route tracking

It eliminates additional distance when the object is motionless

It decreases the noise from Low-class smartphones

It excludes sharp «jumps» to the points remote from a real route

It filters errors duу to the short-term loss of GPS-signal

#### In addition, it solves the other tasks related to the delivery and tracking of the objects moving on the map

## How does it work?

#### To implement the system we need data from the following three sensors:

##### Magnetometer

Shows where the North is

##### Accelerometer

Is used for acceleration measurement and angle determination

##### Gyroscope

Allows us to get the current position of the object through the integration of gyroscope readings given the initial object position

#### The simplest and the most convenient are virtual Android sensors

#### We have an acceleration vector in the “absolute” coordinate system and we can implement Kalman filter

##### Virtual Android sensors

We can use a LINEAR_ACCELERATION sensor for linear accelerations (excluding gravity force) and ROTATION_VECTOR sensor for device orientation

##### Kalman filter

We determine the state vector of the system, the transition matrix, the control vector, and other components of the Kalman filter. Then define the covariance noise matrix of the process and measurement noise. In this form, it is relatively easy to implement the filter

#### To make the long story short…

## Filter parameters

#### Now we have to determine the types of matrixes

System state vector

State-transition model

Control-input mode

Control Vector

Observation model

#### Perform several operations with matrices

The observation model maps the true state space into the observed space. In our case, it equals to identity matrix as we can get everything from a GPS receiver (speed and coordinates) and don’t need to convert it. If the receiver can’t get information about speed then an observation model changes to this:

pic. 1The second one shows the better result with a short-term loss of the GPS signal because the state vector is not affected by the last speed received from a receiver.

pic.2 Covariance noise measurement matrixIf a receiver doesn’t provide information about speed. Otherwise:

pic. 3These values could be received in different ways. You can parse NMEA message and use HDOP value. Also, you can use Location class getAccuracy() method. We should know the direction to get speed to in our coordinate system. For this, we can use either course component from NMEA message or getBearing() method from Location class.

pic. 4 Process noise covariance matrixOver time the positioning error due to the integration of accelerometer readings will increase. Therefore, we have to take GPS-coordinate as the result instead of accelerometer reading. Dt is the period between 2 update steps (obtaining of GPS-coordinates) in Kalman filter.

#### To make Kalman filter work, we have to bring all the data to the single coordinate system.

## GeoHash

#### The algorithm for converting two coordinates of the form 42.8795949 (longitude), 74.5998444 (latitude) into one string

In this project, it is used to solve 2 problems. First, it is necessary to somehow merge the nearby points to reduce the flow of redundant information. To do this, you can select a radius and merge all the points that fall into the circle with this radius. But how to choose the radius and center of this circle? Calculating the distance in spherical coordinates is a costly operation, so a GeoHash function is used to “join” fast coordinates. This function produces a hash as a string, the length of which is determined by the user and affects the encoding accuracy. The longer the hash length is, the smaller the region is and the greater accuracy of the coordinates is in one region. The maximum possible length of a GeoHash string is 12 characters. A very good result for our task shows hash with 7 and 8 precision.

#### Another application of this function

Another way to use this function is “jumps” filtering. We will assume that if the GPS receiver has given out more than 3 (user-defined count) coordinates with one hash, then this point is correct and it should be taken into account. If less — then, probably, this is some random value that does not need to be taken into account.

Examples above illustrate that GeoHash filter allows to significantly reduce the number of processing coordinates. It may be crucial if coordinates are planned to be processed by the server or to save the routes in the database.

#### Result, conclusion and further improvements

As a result, we wrote an Android module and a C library that implements all of the above filters. Visually routes became smoothed and calculation error was reduced.

Green line shows GPS data with significant nose. Red one - filtered data (firstly, by Kalman filter, than by filter based on GeoHash)

Two algorithms were used to calculate the distance. One of them is the Vincenti algorithm. It is used inside of the distanceBetween() method of the Location class. The second method: https://en.wikipedia.org/wiki/Great-circle_distance (section with the haversine formula). Tests show that the results are almost the same, while the second option requires fewer resources. Yet, there are high chances that at greater distances the error will be greater. Within the city, both algorithms will operate the same way.

## Use and develop

The solution if licensed by MIT. Therefore, do not Forget about the copyrights and authorship