Rethinking GPS: Developing a new generation positioning system in Uber
Location and navigation using global positioning system (GPS) have deeply penetrated our daily lives, and they are particularly critical for Uber services. To organize fast and efficient selection, our GPS technologies need to know the situation of the passengers and drivers compared, as well as provide a navigation guide from the current position of the driver to the place where you need to pick up the passenger, and then to the desired destination. For the smoothest operation of such a system, determining the location for passengers and drivers should be as accurate as possible.
launching (literally) GPS in 1973 , we began to understand our world better, experienced the exponential growth of computing power available to us, and developed powerful algorithms for modeling uncertainties from areas like robotics. Despite the fact that our lives have become increasingly dependent on GPS, the fundamental fundamentals, that is, how GPS works, have not changed much, which leads to significant performance limitations. In our opinion, it's time to rethink some of the initial assumptions that were true in 197? as to where and how we use GPS, respectively, and the processing power and additional information that we can use to improve the results.
The GPS works well under a clear sky, but its approaching position can be wildly inaccurate (with an error of 50 meters or more) where accuracy is most needed for us: in densely populated and high-rise urban areas, where many of our users are located. To overcome these problems, we developed an upgrade for GPS software on Android, which significantly improved the accuracy of the position in the urban environment through a client-server architecture that uses 3D maps and conducts complex probabilistic calculations on GPS data available through Android GNSS API .
In this article, we'll discuss why GPS can do poorly in the urban environment and sum up how we fixed it using advanced signal processing algorithms deployed on a scale on our server infrastructure.
Image 1: The GIF above shows a comparison of the standard GPS (red) against our improved approach position (blue) for selection from Uber HQ in San Francisco. Our approximate location was very close to the present route to the passenger, and the GPS showed significant deviations.
A bit of background GPS /GNSS
Before a detailed discussion of our approach, let's briefly summarize how GPS works, in order to understand why it may be inaccurate in a multi-storey urban environment.
GPS is a network of more than 30 satellites controlled by the US government, orbiting the earth at an altitude of about 2?000 kilometers. (Most smartphones these days can also receive the signal of similar Russian satellites " GLONASS ") These satellites send radio frequency signals that GPS receivers, like those in smartphones, can record. It is important that these satellites notify about the time when they will launch these signals.
For each satellite whose signal the receiver processes, the difference between the acquisition time and the launch time (the flight time) is multiplied by the speed of light, the resulting value is called pseudo-distance . If the satellite and receiver clock are synchronized, and the signal moves along the line of sight, then this value will be equal to the real distance to the satellite. However, the clock is not synchronized, so the receiver needs to solve an equation of four unknowns, its own 3D coordinates on the sphere, and the deviation of the clock. Thus, we need at least four satellites (four equations) to obtain these four unknowns.
If we ignore the deviation of the clock, we intuitively can interpret the approximation of the location produced by the GPS receiver, the intersection of spheres with the center on the satellites and the radius of each sphere by a given pseudo-distance. In practice, the GPS receiver processes signals from a much larger number of satellites (up to 20 GPS and GLONASS satellites visible in the open field), and obtaining more than the minimum number of equations provides additional resistance to noise, obstructions, etc. In addition to GPS and GLONASS, some new /future receivers can /can process signals from other satellite systems. Some other launching satellite systems Galileo , administered by the European Union, IRNSS in India and BeiDou , controlled by China. The more general term is GNSS (Global Navigation Satellite System) covers these systems. (We will use this term further.)
Image 2: In this simplified interpretation of GPS receiver calculations, the spheres intersect at the center of known satellite locations.
Why GNSS location is inaccurate in the urban environment
A very strong statement is behind positioning based on GNSS, that the receiver has a line of sight to each satellite, whose pseudo-distance it calculates. This mechanism works well in open terrain, but in an urban environment it works poorly, as shown in image 3 below:
Image 3: Line-of-sight limitation and strong reflection can cause large GPS errors.
Buildings very often limit the direct view of satellites, so the receiver processes signals corresponding to reflection from other buildings. A significant inaccuracy (positive bias) in the pseudo-datum resulting from this phenomenon can lead to inaccuracies in the position approximation, which can reach 50 or more meters in urban canyons. Most of us who traveled on foot, or by car, or ordered Uber in big cities experienced these problems on themselves.
The strength of satellite signals to save
Our approach to increasing location accuracy creates a feature from every GNSS signal limitation that creates problems for standard receivers. How? For Android phones, the LocationManager API provides not only an approximate phone position, but also a signal-to-noise (SNR) indicator for each visible GNSS satellite. If we compare information about the "signal strength" with 3D maps, then we will be able to obtain very valuable information about the position. Picture 4 below shows a simplified version of how SNR satellites and 3D maps can be used to guess which side of the street we are at:
Image 4: The strength of the satellite signal, in combination with 3D maps, provides very valuable location information.
Diving into detail, our approach is based on placing the following assumption in the mathematical framework: if the SNR for the satellite is low, then the line of sight line path is perhaps limited or shaded; If SNR is high, then LOS (line of sight) is probably clean. The specifier "possibly" is critical here: even if the receiver is in the shadow zone, highly reflected signals can still reach it, and even if it is in a clean area, the received signal may be weak (due to destructive interference between the LOS and the reflected paths , the phenomenon related to the multipath attenuation ). Also in most cases, the 3D map is not completely accurate, and definitely does not transmit random constraints by large moving objects not reflected on the map, like trucks. This adds uncertainty to the process.
Probabilistic comparison of shadows using ray tracing
Despite the fact that the intuitive assumption that the signal strength of satellites carries useful information about the location sounds good, it should be specified using the probabilistic framework. For any possible position of the receiver, we can check whether the beam from this position is blocked to the satellite on our 3D map. Now, using the model for SNR probability distribution under LOS and shadow conditions, we determine the most probable SNR value for this satellite. For example, if the position is shaded, then the probability of high SNR is small. The total probability of a given position, based on SNR satellites, is a product of probabilities related to different satellites. By doing this on a grid of possible positions, we get a probabilistic surface - or a heat map of possible positions of the receiver, based only on the signal strength of the satellites. We call this procedure probabilistic comparison of shadows .
Figure 5: Tracing rays from one possible location to each satellite for probabilistic shadow mapping. This is done for thousands of possible locations.
A probabilistic surface or heat map, from probabilistic shadow mapping, combines information from SNR measurements of satellites. However, as we see in Figure 6 below, this heat map can be very difficult. It can have many isolated, strongly separated hot spots (local maxima) that often correspond to the specified side of the street, but sometimes also to incorrect positions (for example, phantoms). In order to narrow our position approach and avoid focusing on phantoms, we must connect this information with even more of it.
Image 6. The position heat map computed using satellite signal strengths can have many hot spots. In the above example, our improved position approximation (blue path, black ellipse with uncertainty) follows the actual path (yellow path), while the usual GPS (red path, gray ellipse with uncertainty) is inaccurate.
Combination of information through a partial filter
For Android phones, the information we use in addition to the signal strength of satellites, this is usually the standard correction of the GNSS position, but it can also be Android Fused position, which can include Wi-Fi-based positioning. Since this location may be very inaccurate, a one-time instantaneous combination of a standard GNSS correction with probabilistic shadow matching usually leads to poor performance. In order to take advantage of information about the strength of satellite signals, we trust the GPS less in the built-up areas (the gray ellipse of GPS uncertainty in image 6 is the usual model we use, and the black uncertainty ellipse for improved GPS is the result of our algorithm). Then we use the previous measurements and impose restrictions on position changes over time, using a model adapted for the application (for example, pedestrian versus the car). We achieve this using partial filter , which approximates the probabilities of distribution of receiver positions at any given time by a set of suspended particles. In other words, we assume where the phone is located, using thousands of possible locations (ie, particles).
Over time, probabilistic weights and particle locations progress through measurements and motion patterns. Since the heat map from the probabilistic shadow mapping has so many local maxima and since the GNSS correction can have such large emissions, we can not use the conventional technique like Kalman filter or extended Kalman filter , which is based on the tracked probability of the distribution of the well-approximated Gaussian distribution of , having the form of a bell. A partial filter allows us to approximate an arbitrary distribution, in exchange for a greater complexity, and here our server architecture comes into play.
Figure 7: Location approximation obtained as a weighted centroid of hot spots provided by a partial filter often corrects very large GPS errors. The inaccuracy radius (white circle) for improved GPS is based on the cutoff of the particle set, and is often a more realistic measurement than the small inaccuracy radius (black circle) usually returned by pure GPS even when position errors are large.
From signal processing to large-scale software
The combination of a partial filter and ray tracing adds complexity to the backend ecosystem of the servers, with the receipt of very stateful services.
Image 8: The advanced Uber GPS system consists of a partial filter service, a 3D tile management service, a manager service, a Uber HTTP API, and a cloud storage and integrates with other Uber services.
In the game there are two types of status: the state of the partial filter for each user and 3D maps used for ray tracing, regionally. Using a partial filter requires a server-side affinity level. Each new request to our service should be forwarded to the same backend server for processing, in order to update the correct partial filter. Additionally, due to the large size of 3D maps, each backend server can contain some small amount of 3D world in RAM.
Since each server can only contain a few square kilometers of these cards, not all servers are capable of serving all users. Implementation of the backend system for our solution required the creation of a routing layer of sessions, which takes into account the 3D server map. In addition to internal tests and performance evaluation, we also ran a test on our own Android devices using the internal version of the Uber for drivers application, as illustrated in Image 9 below:
Image 9: Comparing the red /blue dot in our internal version of the driver application, has allowed Uber employees to test our solution anywhere in the world.
Accurate determination of the position of the passenger and the driver is a very important condition for the execution of the mission of Uber to provide transport with the same reliability as the delivery of water everywhere and for everyone. To achieve our mission, our Sensing, Intelligence and Research teams are working on a variety of approaches to improve positioning with the creative use of sensors and computing on mobile devices, combined with the processing power of our server infrastructure. The combination of advanced signal processing, machine learning algorithms and software on a scale has enormous potential, and we are always looking for talented and highly motivated individuals (software engineers and algorithms,in data visualization and machine learning engineers), to join us and help in realizing this potential.
Danny Iland, Andrew Irish, Upamanyu Madhow, & Brian Sandler are members of Uber's Sensing, Inference and Research team. Danny, Andrew, and Upamanyu were part of the original group that led this research at the University of California, Santa Barbara. After launching this work as a startup, they demonstrated server-side partial filtering to improve positioning in San Francisco using 3D maps created using public data from air LiDAR. They joined the Uber in July 2016.