You might have noticed a problem when you try to use your smartphone to navigate a big city: your GPS location is usually super inaccurate. Sometimes it’s only by a few feet, but if you’re in a particularly dense part of the city where satellite signals are blocked by high-rise buildings, the discrepancy can be orders of magnitude greater. For most people, it’s just one of the many modern-day nuisances of urban life. But for companies that rely on two people with smartphones finding each other in a labyrinth of steel and concrete — like Uber — GPS inaccuracy is a source of never-ending pain and frustration.
Like ships passing in the night, a driver can be on one corner looking for a rider who’s actually on the other side of the block. This can often lead to canceled rides — Uber calls it “wasted supply” — which is money out of a driver’s pocket and Uber’s as well. This gets exponentially more problematic when you have several riders in one car, a la UberPool. And when you start thinking about driverless cars wandering aimlessly through our urban canyons, desperately searching for riders with unreliable GPS coordinates… talk about your dystopias.
Recently, I sat down with two Uber engineers who may have a solution for all this chaos. Andrew Irish and Danny Iland were both PhD students at UC Santa Barbara when their startup Shadow Maps was acquired by Uber in 2016. Since then, they’ve been working on integrating their technology into Uber’s app. They recently began beta testing in 15 cities across the globe, and based on early results, they are now getting GPS signals that are twice as accurate as before.
“I usually say, when someone asks me what I do, that I move the blue dot,” Iland jokes. That’s important because as I open Uber’s app while sitting at my 14th-floor desk at The Verge’s office in lower Manhattan, I see my blue dot hovering outside a hotel that’s over 200 feet away. What Irish and Iland are doing is trying to move that blue dot back across the street so it’s as accurate as possible when an Uber driver comes looking for me.
The Global Positioning System project was launched in the early 1970s as a way to overcome the limitations of previous navigation systems. It was originally designed for things that fly, like planes. So one of the core assumptions was that all satellites would have a direct line of sight, meaning the signal would always travel in a straight line. But now, those assumptions have changed, thanks to the ubiquity of smartphones and the rise of location-based services like Uber.
:format(webp)/cdn.vox-cdn.com/uploads/chorus_asset/file/10681507/urban_multipath.jpeg)
All at once, satellites went from tracking airplanes to tracking the smartphones of individuals walking through dense cities. Not only did these satellites lose their line-of-sight advantage, they had to contend with a forest of tall buildings acting as mirrors to refract and distort the signals. This phenomenon, commonly referred to as “shadowing,” can create a location error of up to 100 meters or more, especially in high-value markets like New York City and San Francisco. That can wreak havoc on the most sensitive aspect of Uber’s business: the pickup.
“So this obviously presents problems for us because we might think that a driver is on a different road than they actually are,” Iland says. “And that can cause ETAs to be totally off.”
To fix the problem, Iland and Irish used a process called occlusion modeling, by which Uber’s algorithm looks at a full 3D rendering of the city and does a probabilistic estimate of where you are based, which satellites you can see, and which you can’t. There are around 30 satellites in the US’s GPS constellation, as well as a constellation of Russian GLONASS satellites. (China and the European Union are in the process of launching their own GPS satellites.) Using public data from the satellites available to software developers, Uber is able to use a process of elimination to get a more accurate read on where you are when you’re trying to hail a ride.
“Pretend there are only three satellites,” Iland says. “So, if I can see satellites C and D with high signal strength, but I can’t see satellite B, then I’m probably on the left side of the street where satellite B is blocked by a building. If I can see B and C, but I can’t see D, then I’m probably on the right side of the street. And so we’re using the satellite visibility information as part of the algorithm, instead of just assuming that all satellites are line of sight.”
He adds, “It’s basically like negative information. You can make assumptions based off of what you don’t see, in addition to what you do see.”
Irish and Iland use ray tracing, in which satellite signals are color-coded by strength, to better illustrate likely locations and cut through the noise. One confusing effect is multipath fading, in which satellites signals that bounce off of buildings that intersect with each other, strengthening certain signals that aren’t otherwise in direct line of sight. This can complicate the ShadowMaps’ algorithm and draw erroneous conclusions about the most likely location of both driver and rider.
“So if you kind of ray trace over a grid,” Irish says, “and you score these locations over the grid based off of how well they agree with the satellite signal strength and the 3D building models, a lot of these noisy effects that we were describing before average out.” Each probability calculation takes between 20 and 100 milliseconds, and can run every four seconds for riders and more frequently for drivers, Iland says. “You just want to have a better tighter estimate to account for how much faster cars move,” Irish adds.
Later, we go for a stroll on the west side of Manhattan so they can show me how much better the modified version of Uber’s app is at finding our GPS location. Sitting in a conference room in Uber’s New York City office, my head is spinning with technical jargon. But out in the fresh air, it’s easier to see how the ShadowMaps team’s simple corrections make a world of difference. We walk next to a park, where there is a wide-open view of the sky and, as a result, a more accurate GPS reading. We turn down a street, our view of the sky narrows, and suddenly our blue dot jumps to the other side of the block. Then Iland shows his version of the app: our actual position and the blue dot are more or less in sync.
ShadowMaps isn’t necessarily a unique approach to the problem of GPS accuracy. Paul Groves, an associate professor at University College London, leads research into robust positioning and navigation within the Space Geodesy and Navigation Laboratory. He praised the ShadowMaps team for bringing GPS improvements to a wider audience, but he stopped short of offering them full credit for their work.
“Their approach is not unique,” Groves says. “It is partially based on work that we have published in the open literature. There are also several other researchers working on similar approaches. We now have a demo system running on an Android smartphone in real-time, albeit restricted to central London.”
A lot of it comes down to a preference in methodology, Groves said. “The more people using these approach, the better in my mind. It gives you better performance. If people are actually making use of our research, rather than leaving and forgetting about it, than we’re making a contribution to the world, rather than just generating piles of paper.”
Iland, Irish, and their team began working on integrating occlusion modeling into the Uber app over a year ago. In February 2018, they began beta testing the corrective algorithm in 15 cities in which Uber operates. (Some of those pilot cities were shut down, though, after Uber sold its Southeast Asia business to rival Grab.) The early results show a twofold improvement in GPS accuracy and thousands fewer cancellations each month. They are now waiting for the green light to take their project global.
Improving GPS accuracy has nothing to do with giving Uber more or less permission to track your location. Last year, the company pulled a heavily criticized feature from its app that allowed it to track riders for up to five minutes after a trip in an effort to fix its poor reputation for customer privacy. On the contrary, Iland and Irish say they are simply using publicly available data on satellite locations to make the whole process of hailing a car on your phone more seamless.
“How often do you have to manually type in your address versus how often do we predict it accurately without you having to do anything?” Iland asks. “So that’s making it a more magical experience. When you open the app, we already know what is the correct address and all you have to do is hit request.”