Rethinking GPS: Engineering next-gen location at Uber (2018)(uber.com)

263 pointsby bmeasevor 4 Jahren62 comments

Rethinking GPS: Engineering next-gen location at Uber (2018)

https://www.uber.com/en-SE/blog/rethinking-gps/

68 comments

skzvvor 4 Jahren

Google explores these techniques as well. They're critical to improving accuracy in urban areas where you don't have line of sight to satellites (this is why your GNSS (AKA GPS) location is terrible whenever you're in a city). Here's [0] a cool gif visualizing the principle of GNSS ray tracing taken from one of Google's blog posts [1]. Here's an article with more information about Google's techniques [2].

[0] https://1.bp.blogspot.com/-FskvGHx-IOc/X8qtZi1GUNI/AAAAAAAAP...

[1] https://android-developers.googleblog.com/2020/12/improving-...

[2] https://insidegnss.com/end-game-for-urban-gnss-googles-use-o...

ehsankiavor 4 Jahren

That seems much more useful, since it applies to all Android apps, whereas Uber's solution would be limited to their app only.

sieabahvor 4 Jahren

Almost like they wrote a blog article about it so others could learn from it.

If it were available to all android apps I don't know why Uber would go out of their way to reimplement it. So it must not be available to all apps and exclusive to Google maps and Waze

mpalmervor 4 Jahren

Uber's post is actually two years older than the Google one.

poopervor 4 Jahren

> April 19, 2018 / Global

Yes, original post needs a (2018) in the title.

ilakshvor 4 Jahren

I think it says that FLP (Fused Location Provider) is not built in to Android.

yincrashvor 4 Jahren

FLP is an SDK available on Android devices with Google Play Services (https://developer.android.com/training/location/request-upda...). According to the blog post, it should theoretically be rolled out to any phone with Android 8 or later.

The Uber blog post is from 2018, and Google's implementation came in 2020.

ilakshvor 4 Jahren

I tried to enter "now" and the stupid phone decided I was going for "not".

bobsmoothvor 4 Jahren

What a brilliant use of all that satellite imagery.

KMnO4vor 4 Jahren

Cool, so it looks like they take the “raw” GPS location (after the GPS module does processing to spit out a lat/long) and applies statistical methods with a model of the actual 3D geometry. Seems like a smart way to improve the accuracy from “userspace”.

This reminds me of the Comma.ai project, Laika [0]. Since they have access to the raw GPS module data (Ie the actual timings of each received satellite transmitting), they can do things such as correcting for troposphere/ionosphere delays by looking up the relevant astro data as recorded by NASA and others.

[0]: https://github.com/commaai/laika

skzvvor 4 Jahren

You may be interested in knowing that Android has exposed raw GNSS measurements through public APIs [0,1] so anybody can build their own raw processing engines using techniques like the ones described in the article

[0] https://developer.android.com/guide/topics/sensors/gnss

[1] https://developer.android.com/reference/android/location/Gns...

myself248vor 4 Jahren

Is anyone actually doing that? I see a build of RTKLIB but it's not actually using the Android GNSS API, it's just using your Android phone as a processor to handle data coming from an external Ublox receiver. Aww.

londons_explorevor 4 Jahren

The android API exposes basically the same data that would come down the serial link from a 90's era GPS receiver plugged into a PC.

That's the position estimate, information about satellite orbits, signal strengths and pseudoranges.

The data doesn't include the raw baseband information necessary to, for example, do carrier phase locking or to do a fully software implementation of GPS decoding.

skzvvor 4 Jahren

It actually exposes carrier information to do carrier-wave positioning as well [0, 1]

There's also an API to specify an antenna pattern [2]

[0] https://developer.android.com/reference/android/location/Gns...()

[1] https://developer.android.com/reference/android/location/Gns...()

[2] https://developer.android.com/reference/android/location/Gns...

sandworm101vor 4 Jahren

This should probably be called "use-specific gps optimization". These are ideas that improve accuracy for specific use cases (cars on roads) but may introduce errors for other users (people in buildings). We see this with googles driver-focused navigation whereby it always pulls you to a road, even though you may be well off the road.

Ive seen this come up in courts. A gps record will say that a person is traveling on highway X instead of parrallel street Y based on speed or direction of travel. When someone is doing something unussual (high speed in wrong direction) mapping software optimizations may go haywire. This is fine, so long as we all understand the difference between the underlying GPS track and a software-optimized track that incorporates logic beyond simple gps position.

Take the unussual situation of a large traffic accident. We dont want the EMT position to be reported as being on the sidewalk just because they are walking. Or after an earthquake. We dont want trapped survivor positions to change based on expected interfearance from tall buildings, buildings which might not be there anymore.

tuananhvor 4 Jahren

"2018" post.

AlotOfReadingvor 4 Jahren

I didn't even notice the date, thanks. The article presents it as if it was invented at Uber, but there's an identical family of techniques also called "shadow-matching" that have been known in the literature for like a decade. Many companies improve the raw GNSS fix with things like map-matching nowadays, but it was much less common even 5 years ago so this would have been fairly innovative back then.

g9yuayonvor 4 Jahren

Uber acquired a startup around 2015. It was that startup that was using shadow-matching and particle filtering to address the problems mentioned in the blog. The startup was founded by a bunch of UCLA PhDs who studied the problems, so I guess they had something innovative.

c_o_n_v_e_xvor 4 Jahren

L5 GPS will address the multipath-in-urban-canyon problem that Uber worked on.

dataflowvor 4 Jahren

If you're curious which phones support L5, check out the table linked on this page (SCROLL DOWN to "GPSTest Database" for the up-to-date table, since the first one is out of date): https://barbeau.medium.com/9be4bbb83a7b

ciupicrivor 4 Jahren

Also E5 Galileo [1]. It's such a shame that so few smartphones have support for dual frequency GPS and Galileo.

[1]: https://gssc.esa.int/navipedia/index.php/Galileo_Signal_Plan

sorenjanvor 4 Jahren

Is it really so few? Snapdragon got support for dual frequency in Snapdragon 855 released in 2018. Use the GPSTest app to see if your phone supports it.

https://github.com/barbeau/gpstest

Avamandervor 4 Jahren

iPhones got it just very recently. So at least half of tge market couldn't have it until recently.

ciupicrivor 4 Jahren

Here are a couple of phones that don't have dual frequency:

- Samsung Galaxy A53 5G (https://www.gsmarena.com/samsung_galaxy_a53_5g-11268.php)

- Samsung Galaxy S10 (https://www.gsmarena.com/samsung_galaxy_s10_5g-9588.php)

- Samsung Galaxy S20 (https://www.gsmarena.com/samsung_galaxy_s20-10081.php)

- Nokia G60 (https://www.gsmarena.com/nokia_g60-11826.php)

- Google Pixel 5 (https://www.gsmarena.com/google_pixel_5-10386.php)

- Sony Xperia 10 IV (https://www.gsmarena.com/sony_xperia_10_iv-11522.php)

- Apple iPhone 13 Pro (https://www.gsmarena.com/apple_iphone_13_pro-11102.php)

If you want to have this feature you have to start looking at the high end models which are of course expensive. Last time I've checked only Chinese brands like Huawei, Xiaomi or Realme seem to offer it at a more affordable price range.

londons_explorevor 4 Jahren

I suspect the main barrier is patents/licensing/product differentiation rather than the actual difficulty of adding one more PLL, mixer and ADC.

Besides, nearly every phone could receive GPS L5 with the radios in the cell modem if they had a suitable firmware update.

sorenjanvor 4 Jahren

According to this list[0] some Samsung Galaxy S20 does support it, as does the Pixel 5 (and 4 and 6). Google also lists both models as having L5 support[1].

Of course the best way of knowing if your phone supports it is to test it yourself.

[0] https://docs.google.com/spreadsheets/d/1jXtRCoEnnFNWj6_oFlVW...

[1] https://developer.android.com/guide/topics/sensors/gnss.html...

GekkePrutservor 4 Jahren

It's not a perfect fix though. Even dual band multi network receivers will "jump around" a bit in deep canyons.

Example: https://hikingguy.com/hiking-gear/garmin-gpsmap-66sr-review-...

capablewebvor 4 Jahren

Parent is talking about "urban canyons" which is just fancy wording for cities, while you're talking about actual canyons.

relaxingvor 4 Jahren

It’s the same problem.

capablewebvor 4 Jahren

Except the population density being different, I guess yeah.

azinman2vor 4 Jahren

I don’t know much about L5. How does it do so?

LeoPantheravor 4 Jahren

To oversimplify: It's on a different frequency and so will be subject to different forms of error. You can average the results of L1 and L5 to get a more accurate position.

skzvvor 4 Jahren

Not just that. It's a higher frequency so the correlation peaks are more narrow and hence more easily distinguishable than L1 frequency

CamperBob2vor 4 Jahren

That's not how it works at all. L5 at 1176 MHz has a different ionospheric delay than L1 at 1575 MHz. Since the timing data is identical, you can calculate and remove the ionospheric delay if you can receive both signals at once.

Correlation peak width is an SNR property (and to a lesser extent dependent on receiver LO phase noise), not something that really corresponds to the RF band in use. Whichever signal is stronger (taking antenna gain into account) is the one that will yield better-quality baseband data.

skzvvor 4 Jahren

L5 is useful in many ways, but L5 really does produce more narrow correlation peaks than L1 as well [0]

[0] https://insidegnss-com.exactdn.com/wp-content/uploads/2021/0...

CamperBob2vor 4 Jahren

Yes, that's an SNR advantage due to processing gain. Works out to more or less 10 * log10(RF signal bandwidth / baseband data bandwidth) dB.

They could have done something similar at L1, but that ship has pretty much sailed.

skzvvor 4 Jahren

I see, thanks for explaining

fshvor 4 Jahren

L5 has a 10 times higher modulation ("chipping") rate than L1/2 which does lead to a narrower correlation peak width. However, it doesn't solve the multipath problem near tall buildings.

skzvvor 4 Jahren

It has a shorter wavelength so the correlation peaks are more narrow and hence more easily distinguishable. See this illustration [0] taken from this article [1]

[0] https://insidegnss-com.exactdn.com/wp-content/uploads/2021/0...

[1] https://insidegnss.com/end-game-for-urban-gnss-googles-use-o...

FutureZeitgeistvor 4 Jahren

p1eskvor 4 Jahren

What happened to the next gen gps technology, I thought it was supposed to be out by now. Centimeter level precision, much better urban (blocked by buildings) accuracy, etc?

HatchedLake721vor 4 Jahren

GPS already has centimeter level precision. iPhone 14 will support the new L5 GPS signal

capablewebvor 4 Jahren

What others said + it depends on your location, different GPS satellites serve different continents (usually), so GPS might work better/worse in Europe compared to South Africa (as an example).

p1eskvor 4 Jahren

Wait, so with the new iphone I will be able to see my location on a map with this accuracy? So basically if a map resolves down to one foot I will have the location pinpointed to a foot from where I am? Currently it’s like 20 feet accuracy.

tuukkahvor 4 Jahren

Yes, GPS already has 1 ft accuracy in good conditions - with L5 GPS this should happen more often.

tuukkahvor 4 Jahren

It's not a single technology but multiple gradual improvements. E.g. since yesterday even iPhones have dual-frequency L5 GPS which improves accuracy in some situations: https://news.ycombinator.com/item?id=32790478

londons_explorevor 4 Jahren

Urban canyons will be properly solved by using small phased array antennas for GPS reception. Then one can detect which signals are coming from the wrong direction and therefore must be reflections.

Phased array antennas also allow GPS-based compasses which should be far better than magnetic compasses which can be rather inaccurate.

Such phased array antennas are already coming into use for more throughput for 5G and WiFi use, and antenna sharing is feasible although not currently done commonly.

[deleted]vor 4 Jahren

lalith_cvor 4 Jahren

https://news.ycombinator.com/item?id=16887276 Old HN thread

dangvor 4 Jahren

Thanks! Macroexpanded:

Rethinking GPS: Engineering Next-Gen Location at Uber - https://news.ycombinator.com/item?id=16887276 - April 2018 (102 comments)

Rethinking GPS: Engineering Next-Gen Location at Uber - https://news.ycombinator.com/item?id=17331841 - June 2018 (18 comments)

erulemanvor 4 Jahren

Needs (2018) in the title.

voz_vor 4 Jahren

Surprised I don't see Miles (https://www.linkedin.com/in/miles-detrixhe-32a979122/) on here - I remember the initial prototypes for this were his.

[deleted]vor 4 Jahren

praveen9920vor 4 Jahren

Most of the Uber cabs work in urban settings where there are bunch of Wi-Fi enabled. Could they use the Wi-Fi to pinpoint the location instead of relying on GPS? Probably they can setup some relay nodes on their own for coverage.

[deleted]vor 4 Jahren

datwelkvor 4 Jahren

No mention of iOS in the video or article. Anyone knows if Uber does something similar on iOS, and if Apple has done any similar efforts in system-level APIs like Google has?

zadwangvor 4 Jahren

Are there open data for this type of research? If someone would like to improve their algorithms.

diebeforei485vor 4 Jahren

I'm curious if they'll make use of the L5 GPS band now that popular phones are getting it.

neilfrndesvor 4 Jahren

(2018)

edfletcher_t137vor 4 Jahren

Their internal app has ads for other Uber services? Oof.

gruezvor 4 Jahren

The article says "internal version of the Uber rider app", which makes me think it's some sort of internal/beta/debug build of the app that everyone else gets. In that case it makes sense that many of the features would stay the same, including stuff like ads.

maronatovor 4 Jahren

The “internal” app is essentially the same as the regular app. The difference is that it may receive beta features, there’s an easy “report bug” button and a side panel with diagnostics info, feature flags and other debugging tools.

sidcoolvor 4 Jahren

This is an old article. Please label it likewise.

chamod12vor 4 Jahren

agluszakvor 4 Jahren

(1)

faangiqvor 4 Jahren

How about make your drivers use semi decent phones that don’t lag GPS?

jhatemyjobvor 4 Jahren

Was just in an Uber in Miami and the driver was telling me how the service stopped working for 3 hours a week ago. It seemed to be local to the area around Miami only, though. Anyone know if this is true?