Rethinking GPS: Developing a New Generation Positioning System at Uber
Positioning and navigation using the global positioning system (GPS) have deeply penetrated our daily lives, and they are particularly critical for Uber services. To organize quick and effective picks, our GPS technologies need to know the position of the associated passengers and drivers, as well as provide navigation guidance 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 smooth operation of such a system, the location for passengers and drivers should be as accurate as possible.
After launching (literally) GPS in 1973, we began to understand our world better, experienced an exponential increase in the 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 fundamentals, that is, how GPS works, have not changed much, which leads to significant performance limitations. In our opinion, the time has come to rethink some of the initial assumptions that were true in 1973 regarding where and how we use GPS, respectively, and computing power and additional information that we can use to improve results.
GPS works well under clear skies, but its approaching position can be wildly inaccurate (with an error of 50 meters or more) where we need accuracy most of all: in densely populated and high-rise urban areas where many of our users are located. To overcome this problem, 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 performs complex probabilistic calculations on GPS data available via the Android GNSS API .
In this article, we will discuss why GPS can do poorly in an urban environment and summarize 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 standard GPS (red) versus our improved position approximation (blue) for picking from Uber HQ in San Francisco. Our approximate location was very close to the real passenger path, and GPS showed significant deviations.
A bit of GPS / GNSS background
Before discussing our approach in detail, let's briefly summarize how GPS works in order to understand why it may be inaccurate in a multi-story urban environment.
GPS is a network of more than 30 satellites controlled by the US government, located in orbit at an altitude of about 20 thousand kilometers. (Most smartphones these days can also receive signals from similar Russian GLONASS satellites .) These satellites send radio frequency signals that GPS receivers, like those in smartphones, can record. It is important that these satellites notify you when they will launch these signals.
For each satellite whose signal the receiver processes, the difference between the acquisition time and the launch time (flight time) is multiplied by the speed of light, the resulting value is calledpseudo distance . If the clock of the satellite and the receiver 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 can intuitively interpret the approximation of the location produced by the GPS receiver, the intersection of the spheres centered on the satellites and the radius of each sphere with a given pseudo-distance. In practice, the GPS receiver processes signals from a significantly 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, obstacles, etc. In addition to GPS and GLONASS, some new / future receivers may / will be able to process signals from other satellite systems. Some other Galileo launched satellite navigation systems are operated by the European Union, IRNSS in India and BeiDou are operated by China. More general termGNSS (global navigation satellite system) covers these systems. (We will use this term further.)
Image 2: In this simplified interpretation of the GPS receiver’s calculations, the spheres intersect at the center of the known satellite locations.
Why GNSS location is inaccurate in urban environments
A very strong claim lies with GNSS-based positioning, that the receiver has a line of sight to every satellite whose pseudo-distance it computes. This mechanism works well in an open area, but it does not work well in an urban environment, as shown in Figure 3 below:
Image 3: The restriction of line of sight and strong reflection can cause large GPS errors.
Buildings very often limit the direct view of satellites, so the receiver processes the signals corresponding to the reflection from other buildings. A significant inaccuracy (positive bias) in the pseudo-distance resulting from this phenomenon can lead to errors in the approximation of the position, which can reach 50 or more meters in urban canyons. Most of us who traveled on foot, or by car, or ordered Uber in large cities, experienced these problems for themselves.
Signal Strength to Rescue
Our approach to increasing the accuracy of determining the location creates a feature from each GNSS signal restriction, which creates problems for standard receivers. How? For Android phones, the LocationManager API provides not only the approximate position of the phone, but also the signal-to-noise ratio (SNR) for each visible GNSS satellite. If we compare the information about the “signal strength” with 3D maps, then we can get very valuable information about the position. Image 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 on:
Image 4: The signal strength of the satellites, combined with 3D maps, provides very valuable location information.
Plunging into details, our approach is based on placing the following assumption in a mathematical framework: if the SNR for the satellite is low, then the line of sight line may be limited or shaded; if the SNR is high, then the LOS (line of sight) is possibly clean. The “maybe” specifier is critical here: even if the receiver is in the shadow zone, strongly 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 , a phenomenon related to multipath attenuation ). Also, in most cases, the 3D map is not completely accurate, and it certainly does not transmit random restrictions to large moving objects that are not reflected on the map, like trucks. This adds uncertainty to the process.
Probabilistic shadow mapping using ray tracing
Although the intuitive assumption that the signal strength of the satellites carries useful location information sounds good, it should be concretized using probability frames. For any possible position of the receiver, we can check if the beam is blocked from this position to the satellite on our 3D map. Now, using the model to distribute SNR probability 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 a high SNR is low. The overall probability of a given position, based on the SNR of satellites, is the product of the probabilities associated with different satellites. By doing this on a grid of possible positions, we get a probabilistic surface - or a heat map of the possible positions of the receiver, based only on satellite signal strength. We call this procedureprobabilistic comparison of shadows .
Image 5: Ray tracing from one possible location to each satellite for probabilistic shadow matching. This is done for thousands of likely locations.
A probabilistic surface or heat map, from probabilistic shadow mapping, combines information from satellite SNR measurements. Be that as it may, as we see in Image 6 below, this heat map can be very complex. It can have many separate, strongly separated hot spots (local maxima) often corresponding to a given side of the street, but sometimes also to incorrect positions (for example phantoms). In order to narrow our approach and avoid phantoms, we must combine this information with even more information.
Image 6. A heat map of positions calculated 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 conventional GPS (red path, gray ellipse with uncertainty) is inaccurate.
Combining information through a partial filter
For Android phones, the information we use in addition to the signal strength of satellites is usually the standard GNSS position correction, but it can also be Android Fused position, which may include Wi-Fi based positioning. Since this location can be very inaccurate, a one-time instant combination of the standard GNSS fix and probabilistic shadow matching usually leads to poor performance. In order to take advantage of information about the strength of satellite signals, we trust GPS less in built-up areas (the gray GPS uncertainty ellipse in image 6 is the usual model that we use, and the black uncertainty ellipse for improved GPS is the result of our algorithm). Then we use the previous measurements and place restrictions on position changes over time, using a model adapted for the application (for example, a pedestrian against a car). We achieve this usingpartial filter , which approximates the probability of the distribution of receiver positions at any given time by a set of suspended particles. In other words, we assume where the phone is, using thousands of possible locations (i.e., particles).
Over time, the probabilistic weights and locations of particles progresses based on measurements and patterns of motion. Since the heat map from probabilistic shadow matching has so many local maxima and since the GNSS correction can have such large outliers, we cannot use the usual technique like the Kalman filter or the advanced Kalman filter , which is based on the tracked distribution probability of a well approximated Gaussian distributionhaving the shape of a bell. A partial filter allows us to approximate an arbitrary distribution, in exchange for greater complexity, and here our server architecture comes into play.
Image 7: An approximation of the location obtained as a weighted centroid of the hot spots provided by a partial filter often corrects very large GPS errors. The inaccuracy radius (white circle) for improved GPS is based on a cut of a set of particles, 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 servers, with very stateful services.
Image 8: The enhanced Uber GPS system consists of a partial filter service, a 3D tile map management service, a manager service, a Uber HTTP API, and cloud storage and integrates with other Uber services.
There are two types of state in the game: the state of a partial filter for each user and the 3D maps used for ray tracing, region by region. Using a partial filter requires a server affinity level. Each new request to our service should be sent 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 may contain some small amount of 3D world in RAM.
Since each server can contain only a few square kilometers of map data, not all servers can serve all users. The implementation of the backend system for our solution required the creation of a session routing layer that takes into account the 3D server map. In addition to internal tests and performance evaluation, we also launched a test on our own Android devices using the internal version of the Uber application for drivers, as illustrated in Image 9, below:
Image 9: Comparison of the red / blue dots in our internal version of the application for drivers, let Uber employees test our solution anywhere in the world.
Accurate determination of the position of the passenger and driver is a very important condition for fulfilling the Uber mission 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 range of approaches to improve position determination using 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 great potential, and we are always looking for talented and highly motivated individuals (software and algorithm engineers, data visualization engineers, and machine learning engineers) to join us and help realize this potential.
Danny Iland, Andrew Irish, Upamanyu Madhow, & Brian Sandler are members of the Uber's Sensing, Inference and Research team. Danny, Andrew, and Upamanyu were part of the original group that conducted this research at the University of California, Santa Barbara. After starting this work as a startup, they demonstrated server-side partial filtering to improve position determination in San Francisco using 3D maps created using publicly available data from air LiDAR. They joined Uber in July 2016.