The big problem with GPS, amazing though it is, comes down to accuracy. It just never seems to be quite accurate enough. Uber engineers now think they have a software way of making it quite a bit more accurate and it's remarkably clever.

Uber really needs more accuracy from GPS than the usual tens of meters because its pickups depend on knowing where you are and you knowing where the car that is trying to pick you up is. Even if the error is small by general standards, it can still place you on the wrong side of the road or round the corner of a building. This miss-location can cause pickups to be missed completely with loss of revenue.

The problem is made worse because the majority of Uber pickups occur in big cities and the tall buildings block direct line of sight communication with the GPS satellite. Instead the receiver is likely to pick up reflections off buildings which degrade positioning to 50 meters or worse.

What can you do about it?

Short of putting up more satellites  there doesn't seem much that can be done - but hardware is not the only solution. There is often more signal in the data than simple processing gets out. Not that the GPS positioning algorithm is simple. You need contact with four satellites to get enough information to solve the equations to get the receiver's position. However, as well as the data coded onto the carrier frequency, there is also the strength of that carrier. Most phones provide, as part of their standard API, a signal-to-noise ratio (SNR) for each satellite in view. Now suppose that on one side of the street tall buildings block direct access to one satellite, but on the other side of the street it has a clear line of access.

Taking this simple idea further, we can suppose that if we have a 3D map or model of the approximate location we can compute the current "shadows" caused by the buildings on the satellite positions as they are at that particular time. This shadow map can then be used to work out where the GPS receiver is according to the current SNR data. This can't be 100% accurate because the 3D map cannot be perfect and there are other sources of GPS reflections and shadows such as moving vehicles.

The researchers have managed to implement a system that makes use of algorithms from a wide range of areas. First, ray tracing is used to compute the shadow map for each of the satellites that are in view. From this a probability of location, a "heat map", can be computed using the actual SNR data. This map isn't enough on its own to pin down a location, but combined with a time series of probable locations it can. In principle you could use a Kalman filter to do the job - this takes the current location, direction of travel and creates a probability estimate for the new location. This is then refined by the additional information i the heat map. However, a Kalman filter has assumptions that the errors are normal and a better. but more complicated approach. is to use a particle filter where a set of locations are proposed based on the initial probabilities and are slowly weeded out as the motion data is added to give new positions. As the motion data accumulates, it becomes clear that most of the particles have a low probability of being the correct location. Particle filters were very popular in AI before deep neural networks took the spotlight, but they are still use by robots to keeping track of where they are.

All of this makes for a lot of computation. It is all done on the server; the phone simply uploads the satellite data and gets back improved co-ordinates. As the computation is on-going, the user has to connect to the same service for the tracking to work.

The GPS shadow map could be used more generally to improve GPS accuracy in other situations.

The question really is how much more data is there in the signal and what other environmental states can be used to fix position even more accurately. Presumably using tricks of the sort that sat navs use to locate a vehicle's position on the nearest road (see Roads API For A Smooth Accurate Track), could be used with pedestrians if we know where the sidewalks are - exactly. Once you have a rough location then correlations with even more local features, like the GPS shadow map, can make the position more accurate.

More Information

Rethinking GPS: Engineering Next-Gen Location at Uber

By Danny Iland, Andrew Irish, Upamanyu Madhow and Brian Sandler

Related Articles 

Software Gives Centimeter Positioning With Phone GPS

Roads API For A Smooth Accurate Track

Getting Started with Google Earth       

Getting started with Google Maps JavaScript       

GPS Always Overestimates Distances

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info