Comment by skzv | Hacker News Reader

Comment by skzv | Hacker News Reader

Parent Full thread

Yup! This issue, which is commonly described as the "wrong-side-of-the-street" or "wrong-city-block" error, is one of the biggest ones, and is where a lot of the innovation I mentioned is happening today.

This occurs because in "urban canyons", meaning streets with tall high-rises or sky scrapers, there is little or no line of sight to GNSS satellites (GNSS being the generic term for all satellite positioning systems, not just the American GPS). Consequently, what your phone picks up are signals reflected off of buildings, which exaggerates the distance between you and the satellites, and causes the positioning solution to be pushed away- onto the other side of the street or another city block.

One way Google/Android is tackling this is by using Google's trove of 3D building data, the same that is rendered in Google Earth when you use it in 3D. Your phone uses the building data to correct for reflections. Read on here (and note the authour!): https://android-developers.googleblog.com/2020/12/improving-...

And, the device can use various filters and smoothers to minimize sudden jumps, and normally does, but there are edge-cases (for example, an app may be requesting pure "unfiltered" GNSS location returned directly from the GNSS chipset, hence the jumps). But rest assured, we are working on this issue.

Anyway, thanks for the feedback. We're always doing our best to improve location accuracy and reliability for billions of users in all scenarios and environments, and it's no trivial feat!

I wonder how the inventors of GPS would have responded if back in the early nineties you had suggested to just add a map of all the worlds high buildings to the GPS receiver.

I think we're doing all sorts of things now that people decades ago thought were simply impossible!

seems almost impossible even now.. awesome and inspiring work. Kudos to all of you

Fun fact: when I was looking into patenting this concept in c. 2007, the prior art search revealed that it had already been patented by someone in Japan in c. 1997.

Amazing to think that ideas people had back when Selective Availability was on for the foreseeable future are just now becoming available to consumers. Congrats on getting it done!

Cool! Were you involved in GPS/localization R&D back then?

Yes, I was working for a company making standalone car navigation devices (remember those?), amongst other GPS-related things - I also worked on a lot of OEM GPS receivers. There was even a guy (not me!) who had written the firmware for a GPS receiver basically from scratch, so I got a look at everything from the very low level up to the navigation UI.

At this point the iPhone hadn’t come out yet, but building data was just starting to show up the maps we used for navigation.

Very cool. What are you up to these days?

My manager worked at Qualcomm back in the day and played a huge role in creating the first GNSS smartphone chipsets.

Likewise, I've learned a lot from him and other veterans in my org.

Cloud infrastructure - so basically I have gone right from one end of the scale spectrum (tiny GPS receivers) to the very opposite extreme :D

Trying to predict reflections by processing building geometry sounds very complicated and error-prone.

Wouldn't it be easier to query Google Maps & Waze telemetry for impossible position jumps? Then you could make geofences where Google Play Services ignores position jumps and falls back to Wifi-based location and integrating the accelerometer.

We consider and integrate all kinds of solutions, accounting for building geometry is just one of them, and we do thorough validation to ensure it's actually helping. There's always various tradeoffs being made.

Ideally, clients will be using our Fused Location Provider API [0] which fuses any (or all) of GNSS, WiFi, accel, gyro, mag... with smoothing + filtering to provide the best location possible at any time while automatically managing power compromises; in effect, using WiFi + accel, as you described, along with more signals and filtering. However, some clients still choose to use pure GPS/GNSS, for various reasons.

Part of providing the best location experience possible (while simultaneously minimizing power drain...) is providing high accuracy at every percentile. Some techniques that may improve the average or median percentile error may cause higher errors at the 90% percentile. For example, let's say we check for "impossible" GNSS position jumps, and just ignore those. What if 10% of the time, the position it's jumping to is actually closer to the true position - since suddenly we might have better line of sight - and previously we were stuck at a worse estimate? What might help in one situation might hurt more in another. It's hard to build robust systems to handle every possible scenario and condition (on all sorts of different kinds of hardware from tons of vendors, since anyone can launch an Android device). It's even harder because, as you can image, smartphone grade sensors are magnitudes worse than those you find in survey or military grade hardware.

Also, WiFi-based localization can only be as good as the estimate of WiFi access point location, which isn't always great (and it's usually worse so since WiFi signal strength localization isn't that great), so GNSS is generally higher accuracy under good conditions (and hence rectifying GNSS error wherever we can is one of our goals), and the error of accel/gyro based dead-reckoning grows quadratically/cubically (due to double integration errors), so it doesn't get you very far.

[0] https://developers.google.com/location-context/fused-locatio...

Great description of why hard problems are hard :) Thanks for the time and hard work!

Reply on news.ycombinator.com