Map matching

"I was seven meters into a lake, according to the satellites. The map insisted there was a bridge. I chose to believe the map."

A Well-Grounded AI Agent

This section assumes you are comfortable with a Gaussian noise model for a position fix (Section 25.1 covered GNSS error sources, and the probability machinery lives in Chapter 4). Map matching is a spatial constraint applied after positioning, so it composes naturally with the dead-reckoning trajectories from Chapter 24 and the RF fixes from Section 25.2.

What map matching is, and why a map is such a strong prior

Formally, you are given a sequence of noisy position observations \(z_1, \dots, z_T\) and a map represented as a graph: a set of edges (road segments, corridor centerlines, rail links) with geometry. The goal is to output, for each observation, the map location it corresponds to, and by extension the connected path through the network. The prior is strong because the map removes almost all of the state space. A GNSS fix with 8 meters of standard deviation covers roughly 200 square meters of plausible ground; within that patch there may be only one road, occupying a fraction of a percent of the area. If you trust the map, you have compressed your uncertainty by two orders of magnitude for free.

The catch is that the map is a prior, not an oracle. It can be stale (a new road, a closed lane), it can be topologically dense (a cloverleaf interchange stacks four roadways within GNSS error of each other), and the vehicle can legitimately leave it (a car in a parking lot, a pedestrian cutting across a plaza). Every good matcher is therefore a balance between trusting geometry and admitting that the observation might mean what it says.

The geometric baseline and where it snaps to the wrong road

The simplest matcher is point-to-curve snapping: for each fix, find the nearest point on the nearest edge and report that. It is one line of computational geometry and it is genuinely useful for coarse display. Its weakness is that it is memoryless. It has no notion that the previous point was on Elm Street, so at an intersection where two roads pass within a few meters it will happily flip between them fix by fix, producing a route that zig-zags across the junction like a nervous pinball. Point-to-curve also ignores heading: a fix that is geometrically closest to a cross-street can be assigned there even when your velocity vector is clearly along the main road.

Incremental (topological) matchers patch this by scoring candidate edges with a weighted sum of perpendicular distance, heading agreement, and connectivity to the previously chosen edge. They are fast and streaming-friendly, and for clean highway data they are hard to beat. But a greedy per-step decision dooms them in dense networks: one confident wrong turn onto a parallel service road, and every subsequent point is scored relative to that mistake with no mechanism to recover. What you want is a method that defers commitment, weighing whole hypotheses of the path rather than one point at a time.

The HMM formulation that won

The dominant approach, popularized by Newson and Krumm in 2009 and now the backbone of OSRM, Valhalla, and most fleet products, casts map matching as decoding a hidden Markov model. The hidden state at each timestep is which road segment the vehicle is on; the observations are the GNSS fixes. Two probabilities define the model.

The emission probability answers "how likely is this fix given that I am really on segment \(r\)?" It is a Gaussian on the great-circle distance from the fix \(z_t\) to its closest point \(x_{t,r}\) on the segment:

where \(\sigma_z\) is the positioning noise, typically estimated from the fix's own accuracy field or a fixed value near the GNSS error floor. The transition probability answers "how plausible is moving from segment \(r\) at time \(t\) to segment \(s\) at time \(t+1\)?" The insight is that on a real road network the driving distance between the two matched points should be close to the straight-line distance the receiver actually moved. Large discrepancies mean the route would require an implausible detour, so they are penalized with an exponential (equivalently, the difference is modeled as an empirically near-exponential variable):

Here \(d_{\text{route}}\) is the network shortest-path distance between the candidate points, \(d_{\text{gc}}\) is the great-circle distance between consecutive fixes, and \(\beta\) controls tolerance for detours. Decoding the single most likely state sequence is then the classic Viterbi problem: the maximum-probability path through a trellis whose columns are timesteps and whose rows are candidate segments. This is why we said map matching is a shortest-path problem in disguise. The Viterbi backpointer is exactly the mechanism that lets a late observation correct an earlier ambiguous choice.

import numpy as np

# Toy HMM map matcher. Two parallel roads (A, B) ~15 m apart.
# candidates[t] = list of (segment_id, snapped_xy) for fix z[t]
# We score emission (fix-to-segment distance) and transition
# (route distance vs. straight-line move) and run Viterbi.

sigma_z, beta = 8.0, 30.0            # GNSS noise (m), detour tolerance (m)

def emission_logp(fix, snap):
    d = np.linalg.norm(np.asarray(fix) - np.asarray(snap))
    return -0.5 * (d / sigma_z) ** 2

def transition_logp(prev_snap, cur_snap, fix_prev, fix_cur, route_dist):
    d_gc = np.linalg.norm(np.asarray(fix_cur) - np.asarray(fix_prev))
    return -abs(route_dist - d_gc) / beta

def viterbi(fixes, candidates, route):
    T = len(fixes)
    log = [{} for _ in range(T)]     # segment_id -> best log-prob
    bp  = [{} for _ in range(T)]     # segment_id -> predecessor
    for seg, snap in candidates[0]:
        log[0][seg] = emission_logp(fixes[0], snap)
        bp[0][seg] = None
    for t in range(1, T):
        for seg, snap in candidates[t]:
            best, best_prev = -np.inf, None
            for pseg, psnap in candidates[t - 1]:
                score = (log[t - 1][pseg]
                         + transition_logp(psnap, snap, fixes[t - 1],
                                           fixes[t], route[(pseg, seg)]))
                if score > best:
                    best, best_prev = score, pseg
            log[t][seg] = best + emission_logp(fixes[t], snap)
            bp[t][seg] = best_prev
    seg = max(log[T - 1], key=log[T - 1].get)   # backtrack
    path = [seg]
    for t in range(T - 1, 0, -1):
        seg = bp[t][seg]
        path.append(seg)
    return path[::-1]

The code above is the whole idea in forty lines. In practice you replace the toy route lookup with an on-demand shortest-path query over the real network (Dijkstra or contraction hierarchies), gate candidates to those within a few \(\sigma_z\) of each fix to keep the trellis small, and handle the pathological case where no route connects two candidates by assigning a floor probability. The particle-filter alternative from Chapter 10 represents the same posterior with samples instead of a discrete trellis, which is what you reach for indoors when the "map" is a set of walls that particles must not cross.

Online, offline, and the indoor case

The Viterbi decode above is offline: it needs the whole sequence before it commits. For post-hoc analytics (fleet reports, trip reconstruction, HD-map trace mining) that is exactly right and gives the best accuracy. For live navigation you need an online variant. The standard trick is a fixed-lag decoder: run Viterbi over a sliding window of the last \(k\) fixes and emit the matched segment for the oldest point in the window, accepting a few seconds of latency in exchange for the correction power of a little future context. Pure greedy online matching is available too when latency is sacred, at the accuracy cost we described for incremental matchers.

Indoors, the map is not a road graph but a floor plan, and the dominant constraint flips from "stay on the line" to "do not pass through walls." Here map matching usually rides inside a particle filter: each particle carries a pedestrian dead-reckoning state (from step detection and heading, per Chapter 24), and any particle whose proposed step crosses a wall polygon is killed. The surviving particle cloud is automatically constrained to the walkable space, and over a corridor or two it converges hard because the building geometry is so informative. This wall-constraint idea is a close cousin of the occupancy constraints used in Chapter 52, the difference being that in map matching the map is given rather than built.

What's Next

In Section 25.5, we drop the assumption that positioning and motion are separate stages and fuse GNSS fixes directly with inertial measurements, letting the filter carry velocity and heading through the tunnels and urban canyons where satellites vanish and a map alone cannot save you.