Map Matching

The most widely adopted probabilistic framework for map matching. An HMM models the sequence of raw GPS points as noisy observations and the true road segments as hidden states. The algorithm uses the Viterbi algorithm to find the most likely sequence of road links by balancing two probabilities: emission probability (how close a GPS point is to a candidate road) and transition probability (how likely it is to travel between two candidate roads given the distance and speed). This approach naturally handles measurement noise and sparse data.

A deterministic approach that processes each GPS point sequentially as it arrives, making it suitable for real-time applications. The algorithm maintains a current matched position and, for each new point, evaluates candidate road segments based on proximity and heading consistency. It applies heuristics like staying on the same road unless a turn is clearly indicated. While computationally lightweight and ideal for turn-by-turn navigation, it is more susceptible to errors from outlier points and urban canyon multipath effects than global batch methods.

These methods construct a candidate graph where nodes represent potential matches for each GPS point and edges represent feasible paths between them. Each edge is assigned a weight combining multiple factors:

• Spatial proximity: Euclidean distance from the raw point to the road centerline
• Topological consistency: Penalty for impossible maneuvers like illegal U-turns
• Temporal coherence: Difference between measured speed and the road's free-flow speed A shortest-path algorithm like Dijkstra's or A* then finds the minimum-weight path through this graph, yielding the matched route.

Recursive Bayesian estimation techniques that treat the vehicle's true position as a dynamic state to be estimated. A Kalman filter assumes Gaussian noise and linear motion models, providing an optimal estimate for well-behaved trajectories. For complex, multi-modal distributions (e.g., at intersections), a particle filter maintains multiple hypotheses (particles) weighted by their likelihood given the GPS observation. These methods excel at smoothing noisy trajectories and providing uncertainty estimates alongside the matched position, critical for safety-sensitive autonomous driving applications.

A geometric curve-matching approach that measures the similarity between the raw GPS trajectory and candidate road paths. The Fréchet distance is often described as the minimum leash length required for a person and a dog to walk along two curves without backtracking. In map matching, it provides a robust, parameter-free metric to compare the shape of the driven path against the shape of road network polylines. This method is particularly effective for low-sampling-rate data where traditional point-to-segment matching fails due to large gaps between consecutive GPS fixes.

Emerging methods that leverage sequence-to-sequence models and graph neural networks to learn map matching directly from data. A Recurrent Neural Network (RNN) or Transformer can process a sequence of GPS coordinates and output a corresponding sequence of road segment IDs, implicitly learning complex urban mobility patterns. These models can incorporate rich contextual features like road class, historical traffic patterns, and driver behavior profiles that are difficult to encode in hand-crafted probabilistic models, often achieving state-of-the-art accuracy on challenging sparse datasets.

The dominant probabilistic framework for map matching. An HMM models the true road segment as a hidden state and the noisy GPS point as an observable emission. The Viterbi algorithm then finds the most likely sequence of road segments.

• Emission Probability: Models how likely a GPS point is given a specific road, typically using a Gaussian distribution over the point-to-segment distance.
• Transition Probability: Models the likelihood of moving from one road segment to another, often based on the difference between the great-circle distance and the network route distance.
• Key Advantage: Naturally handles GPS noise and provides a globally optimal path, not just a greedy local match.

A dynamic programming algorithm used to decode the most likely sequence of hidden states in an HMM. In map matching, it efficiently finds the optimal path through the road network graph given a sequence of noisy observations.

• Constructs a trellis of candidate road segments for each GPS point.
• Iteratively computes the maximum probability path to each state, pruning suboptimal branches.
• Complexity: O(T * N²) where T is the number of GPS points and N is the number of candidate road segments per point.
• Essential for real-time applications when combined with efficient candidate pruning.

A sequential Monte Carlo method that represents the vehicle's position as a set of weighted hypotheses, or particles, distributed across the road network. Unlike HMMs, particle filters handle non-Gaussian noise and multimodal distributions naturally.

• Prediction Step: Particles propagate along road segments based on a motion model and estimated speed.
• Update Step: Particle weights are adjusted based on the likelihood of the new GPS observation.
• Resampling: Low-weight particles are discarded and replaced to prevent degeneracy.
• Particularly effective in dense urban canyons where GPS multipath errors create complex noise profiles.

A measure of similarity between two curves that respects the ordering of points along the curves. In map matching, it is used to evaluate the geometric accuracy of a matched trajectory against the raw GPS trace.

• Often described as the dog-leash distance: the minimum leash length needed for a person and dog to traverse their respective paths.
• Unlike Hausdorff distance, it preserves the temporal sequence of points.
• Weak Fréchet Distance: A computationally cheaper variant that allows backtracking, useful for quick quality checks.
• Used as an offline evaluation metric to benchmark map matching algorithm performance.

A dead-reckoning navigation technique that uses accelerometers and gyroscopes to continuously calculate position, orientation, and velocity without external references. When fused with GPS via a Kalman filter, INS provides high-frequency trajectory data that dramatically improves map matching accuracy in signal-denied environments.

• IMU Data: Provides acceleration and angular velocity at 100+ Hz, bridging gaps between 1 Hz GPS fixes.
• Sensor Fusion: Tightly coupled GPS/INS integration corrects INS drift and smooths GPS noise.
• Critical for autonomous vehicles navigating tunnels, parking garages, and dense urban corridors where GPS is intermittent.