Rethinking GPS: Engineering Next-Gen Location at Uber
ubere.ng
ubere.ng
...
> if the SNR for a satellite is low, then the line-of-sight path is probably blocked or shadowed; if the SNR is high, then the LOS is probably clear. The qualifier “probably” is crucial here: even when the receiver is in a shadowed area, strong reflected signals can still reach it, and even if it is in a clear area, the received signal can be weak (because of destructive interference between LOS and reflected paths, a phenomenon referred to as multipath fading).
...
They use something called "probabilistic shadow mapping", which, as drewda mentioned, is work done at UCSB. That team moved over to Uber.
Very interesting.
'Demo: ShadowMaps, the urban phone tracking system', 2014 [1]
'ShadowMaps Takes Top Prizes in UCSB’s New Venture Competition', 2014 [2]
'How Uber moves the ‘blue dot’ to improve GPS accuracy in big cities', 2018 [3]
[1] https://dl.acm.org/citation.cfm?id=2641755 [2] https://www.noozhawk.com/article/shadowmaps_takes_top_prizes... [3] https://www.theverge.com/2018/4/19/17252680/uber-gps-blind-s...
https://www.linkedin.com/in/upamanyu-madhow-7a124512/
> On leave (2016-17) from UCSB at Uber
Pretty cool when fairly technical research has immediate real-world applications.
As an alternative, phones might start using the dual frequency L1+L5 technology which Broadcom announced last year to detect the reflected signals without relying on an external service with knowledge of the local topology.
https://www.broadcom.com/products/wireless/gnss-gps-socs/bcm...
Here is a working implementation to do GNSS shadowing with GPS, Galileo, and Glonass using OpenstreetMap 3D Export of buildings and terraing.
https://github.com/xaedes/GNSS-Shadowing
It is written in C++ and has a working python binding. But the interface is extremely polished. The ideas behind it are simple though: Satellite trajectories are computed using SGP4 from publicly available TLE files. The current ones will be downloaded from cmake. Some coordinate system transformations later a simple software shadow rasterization (in layered 2D map) algorithm is performed with 3D data pulled in from .obj files that are generated from OpenStreetMap. Dilution of Precision values are calculated from visible satellites for each rasterization point. The shadow information can also be used to do shadow matching.
Maybe someone has a use for this^^
https://tia.ucsb.edu/about-tia/success-stories/shadowmaps/
Then it went dark. So Uber deserves credit for funding the continuing development of this tech, but it isn't open when the pre-acquired company could have provided exactly what you want. I really wish there were different (but still financially rewarding) avenues for technology like this to go down, other than being swallowed whole by BigCorp and disappearing from the world.
Edit: It's mentioned at the footnote of the article: "constructed from publicly available aerial LiDAR data". That poses an additional problem - Aerial lidar data globally is very hard to come by - it does not exist for most places in the world and it's also out of date. Shameless plug: At tensorflight.com we built deep learning models for 2.5D map of buildings based on satellite imagery.
Furthermore, the article does not mention a 3d model of the world from Lidar data either - it specifically mentions just San Francisco
Just look at the raw GPS measurements and look for signs of trouble (high uncertainty, coordinates "teleporting" users around unnaturally, etc.). Maybe you only need it on certain particular streets within a city.
There are commercial LIDAR drone services you can hire, so worst case they just pay some of those people to give them 3D models for the specific areas where they have the worst problems and the highest traffic, and they get a huge improvement.
These acquisitions came around the time Uber was pivoting into a logistics company. It wouldn't be too surprising if they had a pretty rich 3d map dataset of a few test cities. Especially if they had deployed autonomous cars in them.
[1] https://www.denverpost.com/2015/06/29/uber-buys-boulder-bing...
[2] https://www.theverge.com/2015/3/3/8145035/ubers-first-confir...
Doing something latency-sensitive in software better than the firmware, over a cellular network, seems like a very lofty goal.
When you limit the scope like that, I think most of my concerns go away. Very cool work here.
From the article: "We therefore use past measurements and constrain the location evolution over time using a motion model adapted to the application (e.g., pedestrian vs. vehicular motion)." … "Over time, the probability weights and particle locations evolve based on the measurements and the motion model."
Presumably this means something along the lines of throwing out hypothesized locations based on impossible movements. If they were very sure that a car was at a particular location 5 seconds ago and now it is at another location 100 meters away, then that's believable because cars can travel at that speed (~40 mph or ~65 km/h). But if dealing with a pedestrian, it indicates low probability of the latest measurement being correct.
I'm just guessing on the specifics of what the motion model does. But it seems like they're trying to use history in more cases than just when someone is sitting still.
Because nothing has ever been built by a company that had marginal, if any, improvements over what was there before?
Not saying that’s the case here, but I’m skeptical of your argument why OP shouldn’t be skeptical, to put it nicely.
If only there was some kind of mechanism like differential GPS that can be used to correct the GPS signal in some generic way. I understand this is what AGPS is supposed to do but it doesn't seem to work in downtown Chicago.
Here's a peek into average building heights in downtown Chicago. Anywhere red, yellow, or orange we expect to have poor sky visibility. GLONASS being more popular has made Chicago slightly less challenging, before you could have trouble even seeing enough satellites to get a fix.
If you're interested in working on that kind of thing please apply to the positions at the bottom of the blog post.
This statement is so absurd that at first I was not even going to respond to it.
That didn't stop one company from doing so... cough cough Google. (https://www.wired.com/2014/04/threatlevel_0401_streetview/)
Also, I have no idea why Uber left out the fact that they are indeed using both the driver and the users WiFi location data.
Notice that they highlighted that they only use Android users....
Would be interesting to see if the accuracy of Uber services deteriorate if the privacy settings on Android were to tightened up....
Here is a useful link for WiFi access point/ cell tower location database [Big, Beautiful Data: Mapbox Visualizes Skyhook Wi-Fi Access Point Location](https://www.skyhookwireless.com/blog/company/mapbox-visualiz...)
I helped launch this project back when Mozilla needed an inexpensive location solution for Firefox OS devices. It is still used for testing the Firefox Nightly channel, though the Firefox Release channel uses Google's location service.
https://location.services.mozilla.com/
Here is a zoomable world map of all the network locations:
Each of the three location methods, UTDOA, GPS, and WiFI are good at different things. They can all get 50m accuracy or better--when they work.
GPS is great outdoors and rural, but has problems with indoors and urban canyons because of sky view, attenuation and multipath. It also needs ephemeris data periodically (ie AGPS) and 5 sat fixes, which can mean 30s to first locate. Obviously WiFi is good if you can get it; it's like a street sign. UTDOA has 5s fix times and works wherever you have a cell signal, indoors or out, and also has the feature it doesn't depend on handset software; it's network based. So you really want all three, plus maybe other weaker methods like CGI, ECID, or CGITA for hybrid locations. They're all good in different cases.
So carriers ARE using two of the three methods as you point out.
But UTDOA is network based (towers), not handset, so it's expensive and carriers hated it. So much in fact, that they colluded to keep it out of the LTE standard [0] and avoid that expense and IP issues.
Skyhook, already dealing with Google [1] was bought by TruePosition, which then vanished into Skyhook since UTDOA was out of the picture. I'm pretty sure there's no UTDOA left in deployment.
So you have 2 out of three handset methods but you're lacking the third. Which means despite new FCC indoor 50m location rules[2], if you're dying indoors with no WiFi, you better not call 911 and expect a good location [3].
This was my point about business. We have the tech on the shelf to make 50m indoor reliably, we just won't.
0. https://finance.yahoo.com/news/trueposition-ericsson-settle-...
1. https://searchengineland.com/skyhook-wireless-sues-google-yo...
2. https://www.fcc.gov/document/proposes-new-indoor-requirement...
3. https://www.iafc.org/on-scene/on-scene-article/concerns-rema...
> For Android phones, the information we use in addition to satellite signal strengths is usually just the standard GNSS position fix, but can also be Android Fused locations, which may include WiFi-based positioning. Since this location can be very inaccurate, single time instant (one-shot) fusion of GNSS fix with shadow matching likelihoods typically leads to poor performance.
I was thinking the same thing you were. I wonder why they found that it worked poorly for them.
The nice thing about standard GPS is that it's passive. You listen to the some signals, do some local calculation, and you know your position. Then, optionally, you can send that position data to a third party.
Uber's approach changes that. You might not know exactly where you are, but send Uber your info and they'll figure it out.
IMO this is not the way we want things to go: various services, all with their own location-determining tech, all done out of the user's sight or control. (Uber's reputation for privacy reinforces this.)
Let's work on improving the accuracy with which a device can determine its own location. Apparently there's progress there: https://www.theverge.com/circuitbreaker/2017/9/25/16362296/g...
Once it's determined on-device, users should be able to determine the granularity at which we share our location.
I have been in a few situations where 2d was not sufficient to specify the location. For example, multiple levels in the airport. Another example is bridge crossings, where one road is much higher than the other.
Another problem with 2d is that I always have to "orient" myself to verify the GPS is indeed working well. It would be easier with AR or street view.
I put in my actual street address when booking an Uber and the app keeps “helpfully” putting the blue dot on the other side of the street.
Then the driver needs to cut across 4 lanes of traffic to get to me.
I report it to Uber, it gets fixed for a couple of weeks then breaks again.
The actual area of interest surrounding the user is probably at most 1 km^2, but that’s still 1M points or about 4MB (which can be compressed, and easily quantized with say 16-bit float instead) which I really wouldn’t want some app downloading on demand. It’d be interesting to know how many map tiles they need for a good solution though. 256x256 meters with 16-bit floats is just 128 KB. That seems within the realm of acceptable, especially if it reduces the error in pickup.
I don't remember any instance (out of 20-30 I've taken with friends) where the driver arrived exactly at my position. It's an usual sight where people run across the intersection to catch their waiting cab. Most drivers usually call you immediately on arrival to establish the relation the exact position. And they usually only speak some strange local cabbie dialect.
The cabbie can only view coordinate on the map, they don’t have some kind of radar to look at things relatively.
Why not use HDOP, VDOP? It's a better inidication of how off you really are (likely within CEP). Pretty much every new drone AHRS uses DOP values vs snr...
I mean I have never really looked into it but how bad is plain old GPS anyways?
- https://spectrum.ieee.org/tech-talk/semiconductors/design/su...
Collecting location data every second is (mostly) useless and creates a lot of excess nonsense (even Google only keeps it like, what, every five minutes?), but at some point I'm looking to figure out some fun ways to visualize the GPS and speed data table I have just endlessly growing. It'd be interesting to see like... a heatmap of where I go, or a heatmap of my average speed on given areas of a road, or whatever.
Regarding accuracy, I've found if I let my foot off the brake and move up a foot, the GPS receiver's velocity will tick upwards briefly, it seems to be pretty freaking accurate, at least in the less urban environments I drive in. But given the 4 meter accuracy GPS allegedly has, I didn't expect it even could be as precise as sometimes it is. Not sure what the receiver I'm using does in the background, may have it's own accelerometer and the like.
Their idea of winning SV fame, got a lady killed and will add government regulation places it isn’t needed.
Getting a good PR firm at work really opened my eyes to just how manipulated everything is.
I hate my life.
Instead you’ve taken an attitude that guarantees your continued misery.
I don't get to work on it. I'm tired of that.
Sometimes it's much easier to get to do interesting things at a small place than at a big place. Being one of the "biggest tech companies" means you have a lot of keeping-the-lights-on to do.
ubere.ng
To me, that reads as some company called Ubere from a country code I'm not familiar with. Took a minute to read it as Uber Engineering.