One of the main features a successful transportation system needs to provide an accurate and efficient service is a good reliable map for navigation. GPS (Global Positioning System) are satellite-based systems that integrate with mapping technology to provide nearly accurate location while navigating. However, GPS cannot see through tall buildings. Uber decided to fix this issue by integrating 3D maps, probability, and algorithms.
GPS inaccuracy is well known in inner cities, when you need focused accuracy for specific turns and find out you missed one because it was 20 meters before or after the turn you took. Many canceled rides are a result of drivers and riders not meeting at the pick-up location due to GPS issues; Uber has named this problem "wasted supply." GPS reliant navigation systems are still incomplete, and Uber has decided to solve this issue.
GPS
Global positioning systems started in the 1970's when satellites became more abundant in the sky. They were initially used by the military and government agencies that could launch their satellites into orbit. The cost of tracking was enormous at first, but as time flew by and technology increased in both accuracy and efficiency as well as lowered in cost, more and more satellites were sent up into space, to clutter the skies.
Today there are thousands of satellites orbiting the earth and giving GPS more accuracy at a lower cost. With the onset of mobile phones and navigational mapping apps, an increase in need of accuracy grew with the increase in the number of users.
GPS can pinpoint up to 100 meters in the city, which is due to the phenomenon known as "shadowing," where buildings block the direct line of vision that GPS has. Buildings and glass have a tendency to distort and refract signals. Which is why some GPS signals do not work well in cities.
Uber's ShadowMaps team
Uber bought out ShadowMaps in 2016, and the company's founders and chief designer Dr. Andrew Irish and Dr. Danny Iland developed the idea while studying for their Ph.D.'s in UC Santa Barbara. The code has been tested in a pilot in 15 cities around the world.
Iland explained to the press that "I usually say when someone asks me what I do, that I move the blue dot." The importance of the "blue dot" is where the map pinpoints a location. Iland and Irish are trying to move the blue location dot to the exact point on the map that the driver and the rider are positioned. Cities with extreme high lines such as LA and NYC pose extreme issues for accurate GPS.
Iland explained, "So this obviously presents problems for us because we might think that a driver is on a different road than they actually are, and that can cause ETAs to be totally off."
** ShadowMaps Solution**
The way around the problem is by integrating occlusion modelling into the GPS system, where the system has access to a 3D model of the city. The new rendering algorithm then makes an estimated :guess" as to where you really are located. Through the collaborative use of over 30 satellites at any given moment above a city, will generate a high probability of accuracy for such a "guess."
Iland explains "Pretend there are only three satellites. 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 a line of sight."
Red Blue
ShadowMaps uses the old raw GPS data colored in red and superimposes the new SM data in blue. As Island states, "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."
There are issues with their model, and this includes the use of ray tracing, where a satellite signal is color-coded by strength, used to illustrate likely locations and cut through the noise. This produces an issue termed multi-path fading, which is when the satellites signals bounce off of buildings that intersect with each other, strengthening some of the signals that aren't in direct line of sight. This complicates the algorithm and can lead to erroneous conclusions about the location of the driver and rider.
Irish adds "So if you kind of ray trace over a grid 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. You just want to have a better tighter estimate to account for how much faster cars move."
Iland explains that "Each probability calculation takes between 20 and 100 milliseconds, and can run every four seconds for riders and more frequently for drivers."
Outcomes of theory in practice
The Shadowmaps team has not invented this concept, they are expanding on it, as shadow mapping is a known science that has been and is still being researched around the world.
Associate Professor at University College London, Paul Groves explains that "Their (Iland and Irish)approach is not unique. 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."
Groves continues to explain how the more scientists work on the subject from different approaches; the more improvements will be reached by all, "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."
My take: Uber has one advantage on many other research teams, they have a global source of data readily available and a system, that can integrate the new technology immediately. Once the shadow-map tech is upgraded to the Uber mapping system, their accuracy should be better then Waze. Saying this, I remember that Waze is Google, and I wouldn't put it past them to have such a system being developed in parallel. It really doesn't matter who wins the accuracy war, so long as we drivers and riders have access to an accurate system that will save a lot of time and wasted driving to wrong locations.