PNT Roundup: Uber turns on shadow matching

The technological underpinning for stock markets’ techno-darlings doesn’t always work perfectly. That problem produces lost revenue and lost value. So Uber, for one, has done something about it, partly based on research developed by Paul Groves at University College London and featured in the February 2012 cover story of GPS World.

Smartphones finding each other in the urban landscape constitute Uber’s business basis. When driver and rider can’t find each other, because they’re on opposite sides of the street or even opposite sides of the block, a ride can’t happen. In the GPS world, we call this multipath, reflected signals, shadowing or simply urban canyon. In Uber parlance it is “wasted supply.”

To eradicate it, Uber acquired Shadow Maps in 2016 and has integrated the company’s technology into the Uber app. Beta testing now goes on in 15 cities; early results indicate that positioning accuracy has improved twofold.

The Shadow Maps process, derived from Groves’ shadow-matching concept, directs the Uber algorithm to examine a 3D rendering of the cityscape and perform a probabilistic estimate of user location based on — simultaneously — which satellites are in direct line-of-sight and which aren’t, in conjunction with predicted satellite location, or almanac.

The process uses ray tracing, color-coding satellite signals by strength to predict likely locations. Each probability calculation takes 20–100 milliseconds, and can run every four seconds for riders and more frequently for drivers, according to Uber engineers and former Shadow Maps principals Andrew Irish and Danny Iland.

“You just want to have a better, tighter estimate to account for how much faster cars move,” Irish said.

Prior Work. Paul Groves has researched this area for nearly a decade at the Space Geodesy and Navigation Laboratory, University College London, where he is an associate professor. Lei Wang won ION’s Parkinson Award for his Ph.D. thesis on shadow matching and now works at Apple. Marek Ziebart is a professor and vice-dean, research, UCL.

“There are many different approaches to 3D-mapping-aided GNSS and several different research groups around the world working on them,” said Groves. “At UCL, we have been integrating shadow matching with 3D-mapping-aided GNSS ranging algorithms. We now have a real-time demo system running on an Android smartphone, albeit limited to Central London. By making full use of the new Android ‘raw measurements’ capability, we get around a factor of 5 accuracy improvement over conventional single-epoch GNSS in dense urban areas.”

“It’s great to see people actually making use of our research rather than it just languishing in research papers. The more widely that shadow matching and other 3D-mapping-aided GNSS techniques are used, the better.”
In February 2012, Groves and his co-authors presciently wrote:

“A practical shadow-matching algorithm must be implementable in real time on a mobile device. Three models may be considered.

• A network-based solution, whereby GNSS measurements are transmitted to a server, which stores the building boundary data, computes a solution and then sends it to the user.
• A handset-based solution, where the shadow-matching algorithm is run on the handset, which also stores the building boundary data.
• A hybrid model, whereby the shadow-matching algorithm runs on the handset, but the building boundary data is streamed from a server as and when required.

“Using stored or streamed building boundaries, fewer than 50 comparison and addition operations are required to calculate an overall shadow-matching score for one candidate position with two GNSS constellations. Therefore, shadow matching may be performed in real time on a mobile device with several hundred candidate positions, where necessary.”

The magazine article was based on a presentation at the European Navigation Conference 2011 in London. The authors will present their latest research, reflecting significant progress over the last seven years, at ION GNSS+ 2018 in Miami, Sept. 24-28.