Map Matching @ Uber

Summary

In this informative talk, engineer Karan from the Maps team dives into the intricacies of map matching, a critical process for converting raw GPS data into accurate positions on a road network. He explains the necessity of map matching due to the noisy and sparse nature of GPS signals, especially in urban environments. Karan introduces fundamental concepts like graph representation of road networks, distance computations, and the application of hidden Markov models to solve map matching problems. The talk concludes with insights into how Uber implements map matching in real-time for driver positioning and post-trip analysis, highlighting the efficiency of their stateless Java service.

Takeaways

• 🗺️ The script introduces the concept of map matching, which is the process of aligning raw GPS data to actual road segments.
• 🛣️ It explains that the physical road network is represented as a graph in map matching systems, with intersections as vertices and streets as edges.
• 📏 The speaker discusses two types of distance computations: Great Circle (haversine) distance and shortest path distance, with the former setting a lower bound for the shortest path algorithms.
• 📍 Map matching is necessary because raw GPS signals can be noisy and sparse, and it helps in producing accurate positions on the road network.
• 🚗 The input for map matching includes raw latitudes and longitudes, speed, and direction of the vehicle, while the output guarantees positions on actual roads with additional metadata.
• 🔍 The talk highlights two main use cases for map matching: online, for real-time driver positioning, and offline, for post-trip analysis and fare computation.
• 🤖 The map matching system at Uber uses a hidden Markov model to solve the problem, considering a sequence of GPS signals and finding the most probable road segments.
• 🔢 The process involves candidate selection, where for each GPS signal, the closest road segments are identified, and then projecting the GPS signal onto these segments.
• 📊 Emission probabilities are calculated based on the Great Circle distance between the GPS signal and its projection on the road segment, favoring closer signals.
• 🔄 Transition probabilities represent the likelihood of moving from one road segment to another, considering feasible routes and the shortest path distances.
• 🚀 The Viterbi algorithm is used to find the most probable sequence of road segments corresponding to the GPS signals, which is the solution to the map matching problem.

Q & A

What is the primary role of Karan in the Maps team?

Karan is an engineer on the Maps team, working on the core routing engine and the map matching engine.

What is the fundamental concept of representing the physical road network in the software system?

The physical road network is represented as a graph, where intersections are vertices and streets between intersections are edges.

What are the two types of distance computations mentioned in the script?

The two types of distance computations are the Great Circle distance (or haversine distance) and the shortest path distance.

Why is the Great Circle distance considered the lower bound for shortest path algorithms?

The Great Circle distance represents the shortest path between two points on the Earth's surface, and no algorithm can find a shorter path than this, as it accounts for the Earth's curvature.

What is map matching and why is it necessary?

Map matching is the process of taking raw GPS signals and matching them to corresponding road segments. It is necessary because GPS signals are noisy and do not inherently know which street they are on, making accurate positioning on actual streets essential.

What are the main inputs and outputs of a map matching system?

The main inputs are raw GPS signals, including latitude, longitude, speed, and course of the vehicle. The outputs are positions on a road network, including latitude, longitude, road segment ID, road name, and vehicle heading.

Why are GPS signals considered noisy and sparse?

GPS signals can be noisy due to factors like urban canyons where high-rise buildings interfere with the signal. They can be sparse when there are few signals over a large physical distance, making accurate positioning difficult.

What are the two main use cases for map matching mentioned in the script?

The two main use cases are online map matching, which provides real-time driver positioning for dispatch decisions, and offline map matching, which processes the entire trip's GPS data at the end of the trip for fare computation.

How does the simple solution of matching GPS signals to the closest road segment fail in practice?

The simple solution fails because GPS data is noisy, and matching to the closest segment can result in incorrect matches and impossible routes. A more advanced algorithm is needed to consider multiple data points and make a globally optimal decision.

What is a hidden Markov model and how is it used in map matching?

A hidden Markov model is a probabilistic graphical model that represents a sequence of events where the system is assumed to be a Markov process with unobserved (hidden) states. In map matching, it is used to find the most probable sequence of road segments that corresponds to a series of GPS observations.

Can you explain the candidate selection step in the context of map matching using hidden Markov models?

The candidate selection step involves identifying the road segments that could have theoretically produced each GPS observation. This is done by performing a K nearest neighbor lookup using a geospatial index for each GPS signal within a specific search radius.

What is the purpose of computing emission and transition probabilities in a hidden Markov model for map matching?

Emission probabilities represent the likelihood of observing a GPS signal while on a particular road segment. Transition probabilities represent the likelihood of moving from one road segment to another. Both are crucial for determining the most probable sequence of road segments using the Viterbi algorithm.

How does the Viterbi algorithm contribute to solving the map matching problem?

The Viterbi algorithm is a dynamic programming algorithm used to find the most probable sequence of hidden states (road segments) given a sequence of observations (GPS signals) in a hidden Markov model.

What are the performance numbers for map matching at Uber?

The performance numbers for map matching at Uber are not specified in the script, but it mentions that the system is implemented as a stateless Java service, implying efficiency and scalability.