> Our approach to improving location accuracy makes a feature out of the very blockage of GNSS signals that causes trouble for standard receivers. How? For Android phones, the LocationManager API provides not just the phone’s position estimate, but also the signal-to-noise ratio (SNR) for each GNSS satellite in view.
...
> 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.
This was originally created at UC Santa Barbara: https://tia.ucsb.edu/about-tia/success-stories/shadowmaps/ I've seen talks at academic conferences about the techniques over the years, but there's just been silence from Uber. Great to see they can talk about their work more publicly now.
Yes but depending on what Uber do with the technology it might be of no use to anyone else. The technology also depends on contacting servers which have information about the local 3D topology which implies that it is unlikely to be useful globally without someone wanting to be paid for the service.
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.
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.
Hi, this is a bit of a random one, but I have product that relies on GPS accuracy, and would love to hear if you guys have any ideas on how I can improve this, as well as my current implementation. Mind if I drop you an email? Cheers.
Uber gets a lot of criticism here for their business practices but from a technical standpoint this is a tremendous achievement in improving urban location accuracy. I hope they'll consider offering it as a separate API someday since it would obviously be valuable for many use cases beyond transportation.
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.
I wanted to come in to say this as well. I am not a fan of the previous practices Uber has had and I hope they have changed some of their ways but I have always appreciated their willingness to publish their findings from an engineering perspective to the world.
The calculations look pretty complex. I think doing it on mobile devices would impact battery life, which is why Uber built a server farm instead of just adding it to their Android app.
I am curious where did the Uber get the 3d map of 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.
The don't need it for the world, just rich industrialised cities, this makes the amount of data much lower. Also, I'd guess "publicly available" doesn't mean public domain, but available for purchase by the public or (and its common in developed cities) generated by the government (for flooding, mapping uses etc)
Furthermore, the article does not mention a 3d model of the world from Lidar data either - it specifically mentions just San Francisco
It's also easy for them to make a very specific, narrow list of locations where the data is needed.
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.
There are a few internal sources Uber could be getting its mapping data from[1][2]
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.
Google has 3D imagery available for a whole bunch of cities on Google Maps. (Though I don't think they have an API for that data yet.) For places where 3D data isn't available, you can always fall back to regular GPS.
Google is also using 2D imagery to generate 3d structures in rural areas, as demonstrated in this fascinating essay[1]. Details like roof shape, building height, and even bay windows are included.
I'm skeptical of this approach because it seems to me that they have not defined-well the expectation of what the GPS radio hides from them. A lot of information can get lost depending on what simplifications are taken in firmware. What I mean by this is that I would be surprised if GPS radios prioritized accurate signal reports per transponder (and/or refresh-rate of reporting that signal) over battery life when a sufficient level of accuracy is reached, which means Uber could be working with bad data. If it was a professional GNSS receiver, that's one thing, but for a GNSS chip in a cell phone, power consumption really matters the most.
Doing something latency-sensitive in software better than the firmware, over a cellular network, seems like a very lofty goal.
I would guess people internally were skeptical about it too, but as they demonstrated, they have an app that lets their employees see the difference due to this change: Presumably they wouldn't have deployed it (at likely significant resource costs for processing) if it didn't average vastly better.
Upon rereading, it seems to me that they're mostly looking to do this type of increased accuracy when an Uber is parked somewhere waiting for their rider, and you want to be able to show the rider exactly where he is parked, rather than something that is meant to be used while in motion or anything like that.
When you limit the scope like that, I think most of my concerns go away. Very cool work here.
Your concerns about bad data from dodgy hardware seem real, but it seems like their system is meant to be used while in motion.
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.
This isn't just some theoretical approach to solving the problem that's never been tried in the real world. The article suggests this is something they already built, tested, and deployed at scale. What's left to be skeptical of?
I don't really see the problem. The position fix is done in firmware as per normal, and then the server-side just looks at the SNR for each PRN and decides whether or not to adjust that position. The SRNs will probably not match across two different GPS chips, but multipath vs. shadow vs. clear sky should have enough relative difference for the server to tell the cases apart.
SNR in a processing gain system (i.e., the GPS signal) is somewhat of a manufactured value and may be taken or defined in different ways, but it is known each time you take an observation for each satellite. In fact you may have more than one signal for a given satellite due to multipath. SNR is one way to decide which of those signals to report.
As someone who has worked extensively with this team, it's nice to see their hard work coming to light. They are some of the most humble, intelligent people I've ever met.
Just want to tip my hat to the whole team behind this post—it is a masterpiece of technical writing. The post clearly underwent many revisions, sought input from across disciplines and even brought in a designer for the accompanying images. It goes into incredibly interesting detail and then zooms out into broad strokes so a relative layman can understand the challenges and innovations. Bravo.
Thank you! Having a designer replace our stick figure and clip art satellite reflection and LOS/NLOS images definitely helped. Some of the images were originally created for the company all-hands meeting, so it wasn't all from scratch for the blog post.
First time I’m genuinely impressed by an Uber engineering post... probably because it’s the first time they aren’t reinventing a feature of PostgreSQL on top of MySQL and golang.
This is interesting. GPSes work poorly in downtown Chicago, so hopefully this will help improve things.
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.
Uber clearly is willing to spend millions of dollars to get better GPS accuracy. It may only be a matter of time until corporations start launching their own constellations similar to QZSS. Japan has 3 or 4 QZSS satellites that are in a geosynchronous orbit that keeps them (mostly) directly over Japan. Since the satellites are almost straight up, there's less multipath error from the signal bouncing around between buildings.
Yes, Chicago is one of the toughest cities for GPS in the US.
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.
Would more GPS receivers help to build a better consensus? If you’re in an Uber, there are at least two smartphones, often more. The devices could collaborate over a local ad-hoc network, or via the Uber backend, to build a better estimate.
Wi-Fi geolocation is very accurate (in urban areas) because there are many Wi-Fi access points which which to triangulate and their range is pretty short. I'm surprised the article didn't mention Wi-Fi at all.
> 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.
Yes, and likewise, there is also UTDOA with cell signals, bluetooth, audio, RF, and even magnetic environments. There is a ton of improvement to be had using weighted, hybrid locations. But as usual, business and IP limitations will dominate over technical ones, so gathering all of these location methods into one system will be basically impossible for humanity.
>But as usual, business and IP limitations will dominate over technical ones, so gathering all of these location methods into one system will be basically impossible for humanity
This statement is so absurd that at first I was not even going to respond to it.
Mozilla hosts a free location service using Wi-Fi, cell, and Bluetooth network positions collected (opt-in) by Firefox Android users. The cell tower location data is available for download and is also shared with the OpenCellid project. The Wi-Fi and Bluetooth location data, unfortunately, is not available for download because it is considered personal data in some jurisdictions.
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.
Yes, Googles does GPS+WiFi, and CGI if they're desperate, but you didn't really address my claim.
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.
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.)
Another way to solve the same core problem, but approaching it from a different angle would be an ability to choose the Uber pick-up location using 3d or something like dropping the mascot in google street view or augmented reality view on top of the camera.
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 was initially surprised they don’t just do this on device. A height map of the city the user is in (say San Francisco) at only one float per square meter though is still fairly large. With a land mass of 121 sq km for San Francisco, that’s 121 million floats or about 500 MB.
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.
The range of heights is quite constrained to architecture. So 16 bit integers in meters would save half the data over floats. Then your bitmap of heights could have compression applied. A whole flat roof or road would be very compressible. Trees would be the worst.
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.
Maps allowed in China are intentionally inaccurate for national security purposes, so they are often a few hundred feet off. Accordingly, Didi is not very usable for people who can’t Chinese.
Even if the maps are distorted, the raw GPS coordinates should still be accurate. Wouldn't the cabbie at least be able to see the rider's coordinates and thus their position relative to his?
I thought of snr as a trigger, and sensitive to design-- it accounts for antenna setup, thus different for every phone.
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...
the various DOP values assume there are no local obstructions. This method attempts to take in to account the local environment and determine which satellites may be obstructed. DOPs can't help with that.
Yeah, exactly. DOP can provide an artificially rosy picture of the satellite geometry and visibility when you have clean reflections that looks like LOS satellites.
Bits of me are impressed, and bits of me think "but the icon for a uber X car on my phone takes up about 30 yards of the street anyways, so i don't mind the accuracy"
I mean I have never really looked into it but how bad is plain old GPS anyways?
This year, much more accurate GPS chips are expected from Broadcom and other manufacturers that also process L5 signals from newer GPS satellites. About 30cm accuracy is to be expected. Ueber's work is nice for short term, but whether it is still needed?
Well, at least I know why my location app gives me nearest locations that are 100 meters away. I hope Uber will open this up as an API for getting more accurate readings but it probably is biased in placing you on a road which isn't as useful for what I'm doing.
It’s a shame iOS just doesn’t seem to provide this level of data using public APIs as far as I can tell. I’d love to be proven wrong, or for Apple to be a bit more transparent regarding how they perform similar enhancements to location data.
I’m a loyal iPhone customer who likes the fact that Apple doesn’t give out API access willy nilly to apps and instead operates on a default-deny model. I’ll deal with the slightly inaccurate Uber dot.
What sorts of attacks or privacy leaks are possible from the APIs used by Uber to build this on Android? Information about each individual satellite seems like nearly useless data as an attacker, unless I'm a state actor trying to figure out whether you are inside or outside a building when aiming my drones.
I can’t think of any attacks now, and there may be none, but you can see the consequences of Google’s high level approach to APIs in the fact that Facebook snarfed up entire call histories for Android users but not iOS users.
I've been logging the position and speed of my car every second for nearly a year now with a GPS receiver, so this was super interesting to me. Still on my todo list is doing something with all that data.
I have a computer running in my car that I use mostly to play music, and it also has a little GPS receiver and a display which shows the song title/artist, or speed and coordinates on my dashboard. (I intend to get into connecting to the car's CAN and the like at some point, but I have very little free time to play with it.) I use the same piece of software to control my home automation devices and interact with a couple APIs, as much as possible is designed to operate without depending on the Internet. It's less sophisticated than either the average in-car entertainment system or the average smartphone, but it does what I want, not what other companies want, so I'm kinda fond of it.
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.
Too bad you can’t have an antenna array on top the vehicle. You could use that to get a azimuth and elevation bearing on the signals, using that to compensate for single reflections.
Is it legal to improve the accuracy of GPS? I was under the impression that high accuracy GPS was reserved specifically for the military, so improving the accuracy could be considered hacking. I guess an eventual response could be that the responsible organizations may deteriorate the civilian GPS signal to compensate. Otoh, the fact that this "hack" only works in cities at low altitudes could make it a non-issue.
It's fine, considering one can already get sub-centimeter accuracy with off the shelf equipment and post-processing (rtklib comes to mind), this is just another method to get better accuracy within the confines of more common user configurations (ie. Your phone).
they hire a deliveroo task rabbit to run behind every uber txting constantly to the customer where they are - bonus, can use local landmarks as way finders ;-)
Definitely. I don’t think it’s necessarily pessimist to know that when you see headlines about companies it’s almost always directly related to someone manipulating stock prices on way or the other.
Getting a good PR firm at work really opened my eyes to just how manipulated everything is.
It would be nice if Uber could even get basic GPS right first. Most drivers don't even use their app anymore for directions. They switch over to google maps.
Please don't conflate gps with navigation. They are entirely separate problems. I urge you to look into problems and familiarize yourself with the challenges therein before commenting.
While that is correct. I don't know what they do to mangle the GPS coordinates because that is barely functional. And even the drivers complain about it. I've taken multiple Uber pools in the last couple days where the drivers flat out called the person three blocks away because the precision is that terrible
You have an interesting response. Others in your position might use this as inspiration to work hard, get hired by a company that might sponsor a work visa, study about career advancement and aim to find a way into an Uber like company one day.
Instead you’ve taken an attitude that guarantees your continued misery.
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.
> Our approach to improving location accuracy makes a feature out of the very blockage of GNSS signals that causes trouble for standard receivers. How? For Android phones, the LocationManager API provides not just the phone’s position estimate, but also the signal-to-noise ratio (SNR) for each GNSS satellite in view.
...
> 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.
This was originally created at UC Santa Barbara: https://tia.ucsb.edu/about-tia/success-stories/shadowmaps/ I've seen talks at academic conferences about the techniques over the years, but there's just been silence from Uber. Great to see they can talk about their work more publicly now.
Some additional references:
'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...
Apparently the research was led by Dr. Upamanyu Madhow. I wonder what he's up to these days:
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.
Yes but depending on what Uber do with the technology it might be of no use to anyone else. The technology also depends on contacting servers which have information about the local 3D topology which implies that it is unlikely to be useful globally without someone wanting to be paid for the service.
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...
https://news.ycombinator.com/item?id=15308771
Google and Apple have that urban topology info too. That’s 99% of phone mapping API users covered.
Cool! I had a similar topic for my master thesis where I predict GNSS Shadowing and HDOP Maps to plan HDOP optimal routes.
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^^
Edit: It should mean: "the interface isN'T extremely polished". Not the opposite. Messed up my last edit and didn't see the mistake until now, sry^^
Hey, this is excellent work! Feel free to email me at iland at uber.com if you are interested in working on GNSS Shadowing at Uber.
Hi, this is a bit of a random one, but I have product that relies on GPS accuracy, and would love to hear if you guys have any ideas on how I can improve this, as well as my current implementation. Mind if I drop you an email? Cheers.
Uber gets a lot of criticism here for their business practices but from a technical standpoint this is a tremendous achievement in improving urban location accuracy. I hope they'll consider offering it as a separate API someday since it would obviously be valuable for many use cases beyond transportation.
Yes and no - this was originally developed at UC Santa Barbara, and Uber acquired the company that resulted:
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.
I wanted to come in to say this as well. I am not a fan of the previous practices Uber has had and I hope they have changed some of their ways but I have always appreciated their willingness to publish their findings from an engineering perspective to the world.
It seems like it would be better if android would just do this for you
It also seems like the sort of thing android will eventually do for you, once it's developed & proven out. This isn't exactly old hat.
Unless you know.. patents.
The calculations look pretty complex. I think doing it on mobile devices would impact battery life, which is why Uber built a server farm instead of just adding it to their Android app.
Google has servers, so in a way Android could still 'do it for you'.
Don't they already do it? I thought the android location service queried google's wifi database to help figure out where you are.
Yeah, it does use wifi to help determine location. Doesn't use the technique described here yet though, obviously.
I am curious where did the Uber get the 3d map of 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.
The don't need it for the world, just rich industrialised cities, this makes the amount of data much lower. Also, I'd guess "publicly available" doesn't mean public domain, but available for purchase by the public or (and its common in developed cities) generated by the government (for flooding, mapping uses etc)
Furthermore, the article does not mention a 3d model of the world from Lidar data either - it specifically mentions just San Francisco
It's also easy for them to make a very specific, narrow list of locations where the data is needed.
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.
There are a few internal sources Uber could be getting its mapping data from[1][2]
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...
Google has 3D imagery available for a whole bunch of cities on Google Maps. (Though I don't think they have an API for that data yet.) For places where 3D data isn't available, you can always fall back to regular GPS.
Google is also using 2D imagery to generate 3d structures in rural areas, as demonstrated in this fascinating essay[1]. Details like roof shape, building height, and even bay windows are included.
[1] https://www.justinobeirne.com/google-maps-moat
I'm skeptical of this approach because it seems to me that they have not defined-well the expectation of what the GPS radio hides from them. A lot of information can get lost depending on what simplifications are taken in firmware. What I mean by this is that I would be surprised if GPS radios prioritized accurate signal reports per transponder (and/or refresh-rate of reporting that signal) over battery life when a sufficient level of accuracy is reached, which means Uber could be working with bad data. If it was a professional GNSS receiver, that's one thing, but for a GNSS chip in a cell phone, power consumption really matters the most.
Doing something latency-sensitive in software better than the firmware, over a cellular network, seems like a very lofty goal.
I would guess people internally were skeptical about it too, but as they demonstrated, they have an app that lets their employees see the difference due to this change: Presumably they wouldn't have deployed it (at likely significant resource costs for processing) if it didn't average vastly better.
Upon rereading, it seems to me that they're mostly looking to do this type of increased accuracy when an Uber is parked somewhere waiting for their rider, and you want to be able to show the rider exactly where he is parked, rather than something that is meant to be used while in motion or anything like that.
When you limit the scope like that, I think most of my concerns go away. Very cool work here.
Also applies in figuring out the spot to pick up the rider, most people don't move much when requesting a car.
Your concerns about bad data from dodgy hardware seem real, but it seems like their system is meant to be used while in motion.
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.
This isn't just some theoretical approach to solving the problem that's never been tried in the real world. The article suggests this is something they already built, tested, and deployed at scale. What's left to be skeptical of?
> The article suggests this is something they already built, tested, and deployed at scale.
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.
I don't really see the problem. The position fix is done in firmware as per normal, and then the server-side just looks at the SNR for each PRN and decides whether or not to adjust that position. The SRNs will probably not match across two different GPS chips, but multipath vs. shadow vs. clear sky should have enough relative difference for the server to tell the cases apart.
SNR in a processing gain system (i.e., the GPS signal) is somewhat of a manufactured value and may be taken or defined in different ways, but it is known each time you take an observation for each satellite. In fact you may have more than one signal for a given satellite due to multipath. SNR is one way to decide which of those signals to report.
As someone who has worked extensively with this team, it's nice to see their hard work coming to light. They are some of the most humble, intelligent people I've ever met.
This is an engineering tour de force from Uber. A fascinating read. I take my hat off to the team behind this.
Thank you for the kind words.
Just want to tip my hat to the whole team behind this post—it is a masterpiece of technical writing. The post clearly underwent many revisions, sought input from across disciplines and even brought in a designer for the accompanying images. It goes into incredibly interesting detail and then zooms out into broad strokes so a relative layman can understand the challenges and innovations. Bravo.
Thank you! Having a designer replace our stick figure and clip art satellite reflection and LOS/NLOS images definitely helped. Some of the images were originally created for the company all-hands meeting, so it wasn't all from scratch for the blog post.
First time I’m genuinely impressed by an Uber engineering post... probably because it’s the first time they aren’t reinventing a feature of PostgreSQL on top of MySQL and golang.
This is interesting. GPSes work poorly in downtown Chicago, so hopefully this will help improve things.
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.
Uber clearly is willing to spend millions of dollars to get better GPS accuracy. It may only be a matter of time until corporations start launching their own constellations similar to QZSS. Japan has 3 or 4 QZSS satellites that are in a geosynchronous orbit that keeps them (mostly) directly over Japan. Since the satellites are almost straight up, there's less multipath error from the signal bouncing around between buildings.
Yes, Chicago is one of the toughest cities for GPS in the US.
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.
https://imgur.com/a/3bjiiRw
It gets even harder streets with like Lower Wacker Drive that are one deck below street level. There is almost no line of sight to any sats.
Would more GPS receivers help to build a better consensus? If you’re in an Uber, there are at least two smartphones, often more. The devices could collaborate over a local ad-hoc network, or via the Uber backend, to build a better estimate.
Yes, using measurements from multiple receivers could definitely help :)
If you're interested in working on that kind of thing please apply to the positions at the bottom of the blog post.
https://www.uber.com/careers/list/14345/
Wi-Fi geolocation is very accurate (in urban areas) because there are many Wi-Fi access points which which to triangulate and their range is pretty short. I'm surprised the article didn't mention Wi-Fi at all.
They mentioned it off-hand once:
> 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.
Yes, and likewise, there is also UTDOA with cell signals, bluetooth, audio, RF, and even magnetic environments. There is a ton of improvement to be had using weighted, hybrid locations. But as usual, business and IP limitations will dominate over technical ones, so gathering all of these location methods into one system will be basically impossible for humanity.
>But as usual, business and IP limitations will dominate over technical ones, so gathering all of these location methods into one system will be basically impossible for humanity
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...)
Mozilla hosts a free location service using Wi-Fi, cell, and Bluetooth network positions collected (opt-in) by Firefox Android users. The cell tower location data is available for download and is also shared with the OpenCellid project. The Wi-Fi and Bluetooth location data, unfortunately, is not available for download because it is considered personal data in some jurisdictions.
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:
https://location.services.mozilla.com/map#2/15.0/10.0
Yes, Googles does GPS+WiFi, and CGI if they're desperate, but you didn't really address my claim.
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...
Neat! However...
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.
Another way to solve the same core problem, but approaching it from a different angle would be an ability to choose the Uber pick-up location using 3d or something like dropping the mascot in google street view or augmented reality view on top of the camera.
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.
While that would improve the location for users that do elect to select their location, I just don't see it having widespread use.
In that situation the dude calls you and asks what number pillar you're at.
This is a good write up but the actual implementation is... questionable.
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.
I was initially surprised they don’t just do this on device. A height map of the city the user is in (say San Francisco) at only one float per square meter though is still fairly large. With a land mass of 121 sq km for San Francisco, that’s 121 million floats or about 500 MB.
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.
The range of heights is quite constrained to architecture. So 16 bit integers in meters would save half the data over floats. Then your bitmap of heights could have compression applied. A whole flat roof or road would be very compressible. Trees would be the worst.
Picking up by Didi in China is even more frustrating than we're used to with Uber. I wonder whether their peculiar attitude to geo-data is the reason for that: https://en.wikipedia.org/wiki/Restrictions_on_geographic_dat...
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.
Maps allowed in China are intentionally inaccurate for national security purposes, so they are often a few hundred feet off. Accordingly, Didi is not very usable for people who can’t Chinese.
Even if the maps are distorted, the raw GPS coordinates should still be accurate. Wouldn't the cabbie at least be able to see the rider's coordinates and thus their position relative to his?
Yes, it is the map that is wrong, not the GPS, which is (still mostly) American anyways.
The cabbie can only view coordinate on the map, they don’t have some kind of radar to look at things relatively.
I thought of snr as a trigger, and sensitive to design-- it accounts for antenna setup, thus different for every phone.
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...
the various DOP values assume there are no local obstructions. This method attempts to take in to account the local environment and determine which satellites may be obstructed. DOPs can't help with that.
Yeah, exactly. DOP can provide an artificially rosy picture of the satellite geometry and visibility when you have clean reflections that looks like LOS satellites.
Bits of me are impressed, and bits of me think "but the icon for a uber X car on my phone takes up about 30 yards of the street anyways, so i don't mind the accuracy"
I mean I have never really looked into it but how bad is plain old GPS anyways?
That is nothing really new. There are also patents around this, like this one: https://patents.google.com/patent/US8912953B2/
This year, much more accurate GPS chips are expected from Broadcom and other manufacturers that also process L5 signals from newer GPS satellites. About 30cm accuracy is to be expected. Ueber's work is nice for short term, but whether it is still needed?
- https://spectrum.ieee.org/tech-talk/semiconductors/design/su...
Well, at least I know why my location app gives me nearest locations that are 100 meters away. I hope Uber will open this up as an API for getting more accurate readings but it probably is biased in placing you on a road which isn't as useful for what I'm doing.
First time I've seen a Nigerian domain name used for a US tech company. Cool idea.
It’s a shame iOS just doesn’t seem to provide this level of data using public APIs as far as I can tell. I’d love to be proven wrong, or for Apple to be a bit more transparent regarding how they perform similar enhancements to location data.
I’m a loyal iPhone customer who likes the fact that Apple doesn’t give out API access willy nilly to apps and instead operates on a default-deny model. I’ll deal with the slightly inaccurate Uber dot.
What sorts of attacks or privacy leaks are possible from the APIs used by Uber to build this on Android? Information about each individual satellite seems like nearly useless data as an attacker, unless I'm a state actor trying to figure out whether you are inside or outside a building when aiming my drones.
I can’t think of any attacks now, and there may be none, but you can see the consequences of Google’s high level approach to APIs in the fact that Facebook snarfed up entire call histories for Android users but not iOS users.
I've been logging the position and speed of my car every second for nearly a year now with a GPS receiver, so this was super interesting to me. Still on my todo list is doing something with all that data.
can you tell us more?
I have a computer running in my car that I use mostly to play music, and it also has a little GPS receiver and a display which shows the song title/artist, or speed and coordinates on my dashboard. (I intend to get into connecting to the car's CAN and the like at some point, but I have very little free time to play with it.) I use the same piece of software to control my home automation devices and interact with a couple APIs, as much as possible is designed to operate without depending on the Internet. It's less sophisticated than either the average in-car entertainment system or the average smartphone, but it does what I want, not what other companies want, so I'm kinda fond of it.
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.
Thank you.
Related: Lots of amateur radio operators do this as well: https://aprs.fi/
Too bad you can’t have an antenna array on top the vehicle. You could use that to get a azimuth and elevation bearing on the signals, using that to compensate for single reflections.
Is it legal to improve the accuracy of GPS? I was under the impression that high accuracy GPS was reserved specifically for the military, so improving the accuracy could be considered hacking. I guess an eventual response could be that the responsible organizations may deteriorate the civilian GPS signal to compensate. Otoh, the fact that this "hack" only works in cities at low altitudes could make it a non-issue.
It's fine, considering one can already get sub-centimeter accuracy with off the shelf equipment and post-processing (rtklib comes to mind), this is just another method to get better accuracy within the confines of more common user configurations (ie. Your phone).
they hire a deliveroo task rabbit to run behind every uber txting constantly to the customer where they are - bonus, can use local landmarks as way finders ;-)
This is why I come to Hacker News.
Uber seems like a company that doesn’t really understand its place. Just do what you do.
Their idea of winning SV fame, got a lady killed and will add government regulation places it isn’t needed.
A possible distraction from the unpopular headlines? I hate thinking this way, but I am growing ever more skeptical...
Definitely. I don’t think it’s necessarily pessimist to know that when you see headlines about companies it’s almost always directly related to someone manipulating stock prices on way or the other.
Getting a good PR firm at work really opened my eyes to just how manipulated everything is.
It would be nice if Uber could even get basic GPS right first. Most drivers don't even use their app anymore for directions. They switch over to google maps.
Please don't conflate gps with navigation. They are entirely separate problems. I urge you to look into problems and familiarize yourself with the challenges therein before commenting.
While that is correct. I don't know what they do to mangle the GPS coordinates because that is barely functional. And even the drivers complain about it. I've taken multiple Uber pools in the last couple days where the drivers flat out called the person three blocks away because the precision is that terrible
oh good another article where I get to read about people doing more interesting things than I will ever get to do.
I hate my life.
You have an interesting response. Others in your position might use this as inspiration to work hard, get hired by a company that might sponsor a work visa, study about career advancement and aim to find a way into an Uber like company one day.
Instead you’ve taken an attitude that guarantees your continued misery.
I've spent years working for 2 of the biggest tech companies on the planet. Tons of cool stuff going on.
I don't get to work on it. I'm tired of that.
Kool. Then you are much better off than I assumed. Find a mentor or career coach to help you get to where you want to be.
Note that this didn't originate inside Uber.
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.
Join a startup in SV? Interesting work and still good pay...
On the plus side, you didn't just read a timely article from Uber on Lidar.
Sorry if this is off-topic, but I hate the trend of needing to "read" the TLD.
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.To be fair, it's a link shortener. The actual domain is about as normal as it can be (eng.uber.com)