HMM Map Matching: Noisy Pings onto Roads

Background

At Grubhub my team owned the real-time location side of Pathfinder: every active courier streams a location ping roughly once a second, and nearly everything downstream — dispatch offers, arrival predictions, "your driver is 2 minutes away", and the live traffic feed itself — needs to know where that courier is on the road network, not where the phone thinks it is. Raw GPS in a dense city is systematically wrong: multipath off building facades introduces errors that are large, biased, and correlated in time. I've written up the physics of that separately in GPS Urban Canyon — and this demo doesn't imitate those errors with a random walk, it runs that project's error model, ray-traced against real Chicago buildings, ping by ping. Snapping each ping to the nearest road — the obvious fix — fails exactly when it matters, flickering between parallel streets, one-way pairs, and overpasses.

The standard cure, and the one we ran in production, is a hidden Markov model in the shape Newson and Krumm described for Bing Maps^[1]: treat the vehicle's true road position as hidden state, treat the pings as noisy observations, and let the road network's connectivity decide which explanation of the last half-minute of evidence is most plausible. The interesting engineering isn't the model — it's making it answer in microseconds, for thousands of couriers concurrently, against a metric that changes every few minutes.

The Model

States. A state is a candidate position on a specific directed edge — road segment plus direction of travel plus offset along it. Candidates for each ping come from a quadtree over the road segments (built once per map, shared with the routing engine): every segment within a few noise standard deviations of the ping, projected onto its polyline, capped at the best eight.

Emission. How well does a candidate explain the ping? Gaussian in the distance between the ping and the candidate's road position:

Transition. How plausible is moving from candidate $x_t$ to candidate $x_{t+1}$ in one second? A bounded shortest-path search runs through the network from one candidate to the other, and the score combines three terms: the Newson–Krumm discrepancy between routed distance and straight-line distance (a vehicle that isn't teleporting moves about as far along the road as it does through space), the turn probabilities of every junction the route passes, and a reference-speed prior that penalizes transitions requiring implausible speed for those roads:

Decoding. Viterbi over a trailing window of samples — the matcher we ran used the last 30–120 seconds of pings at a 1-second update rate, and that's exactly what this demo does. Each new ping re-solves the window:

The window is the point. The newest ping's match — the head of the window — is the real-time answer, and it's necessarily a guess about an ambiguous present. But the same ping keeps getting re-decoded as fresh evidence arrives, so a wrong guess at a parallel street heals within a few seconds, long before anyone acts on it. Outliers get the same mercy: when no candidate of a new ping is reachable from any candidate of the previous one — a multipath spike, a parking garage, a GPS outage — the matcher bridges the gap at a fixed penalty rather than restarting, so one bad ping can't wipe out thirty seconds of accumulated evidence. Getting that detail right matters more than any tuning constant: an early version of this demo restarted the chain on outliers, and a single spike would silently degrade the entire trailing window into nearest-edge snapping.

The Data Structures

The matcher's hot path allocates nothing and chases no pointers. Everything it consults is a flat, quantized, precomputed array, keyed by directed edge id:

Reference speeds — one Uint16 per directed edge, in cm/s. Turn probabilities — one Uint8 per (incoming edge → outgoing edge) pair, storing the negative log-probability in 1/16-nat steps, laid out in the same CSR order as the graph's adjacency so that "the edges leaving the head of edge e" and "their turn costs" are the same two offset reads. Next-edge lookup — the CSR itself: two array reads to enumerate continuations, which is what keeps the bounded transition searches tiny. Quadtree — packed node and item arrays over segment bounding boxes for candidate generation. For this demo's downtown Chicago extract the whole parameter pack is a few hundred kilobytes; the production equivalent for a metro area still fits comfortably in cache-friendly memory on every matcher node.

The reason for this shape is operational, not aesthetic. The parameter file is rebuilt offline and shipped to matcher nodes alongside the routing engine's five-minute traffic customization — reference speeds and turn behavior always coherent with the routing metric, hot-swapped by pointer flip. And because the arrays are position-independent integers, "load the new parameters" is a memcpy, not a deserialization.

Closing the Loop

Map matching is the front half of a feedback loop. Once pings are pinned to directed edges, consecutive matches yield observed traversal speeds per edge — thousands of couriers become a live probe fleet. Those observations feed the traffic model, the traffic model re-customizes the routing engine every few minutes, and the routing engine's updated metric ships back to the matchers as fresh reference speeds. That's the machinery behind Customizable Route Planning and the Pathfinder 3.0 merchant discovery design — this page is where their input data comes from.

The Noise Is Real

The usual way to demo a map matcher is to sprinkle Gaussian noise on a track and clean it back up — which quietly begs the question, because real urban GPS error is nothing like white noise. So this demo generates its errors the way the city actually does. It loads 17,240 real building footprints from OpenStreetMap for the same downtown extract, extrudes them to their tagged heights, and takes GPS satellite geometry from the same IGS precise-orbit file the GPS Urban Canyon demo uses. Then, for every second of the simulated trip, it ray-traces each satellite against the skyline from the vehicle's true position: satellites with direct line of sight contribute clean pseudoranges; blocked satellites are searched for a single-bounce facade reflection by the image method, and if one exists the receiver tracks it — eating the excess path delay as a pseudorange bias; satellites with neither are lost. A weighted-least-squares solve over whatever survives yields the exact position error a receiver would compute, HDOP included — and when fewer than four satellites survive, or the geometry collapses, there is no fix at all and the receiver coasts.

The result is the real texture of city GPS: honest 3–5 m fixes on open streets, 50–100 m biased excursions in deep canyons where every visible "satellite" is a reflection off the same glass tower, and outright outages. One production-faithful consequence falls out immediately: the receiver knows how bad its own fix is (geometry dilution plus how many reflections contaminate the solve), and the matcher consumes that per-ping accuracy estimate as its emission σ — exactly how production weights the phone's reported accuracy. In measurement, that channel alone is worth about six points of correct-road accuracy over the best fixed σ.

About the Demo

Everything below runs in a web worker on the same downtown Chicago extract as the CRP demos: ~5,300 OSM ways contracted to a directed road graph, then the full offline pipeline — packing reference speeds, quantizing turn probabilities at every junction, building the quadtree, and extruding the sky model. After that it simulates a delivery trip — a route through the graph, driven with human speed variation and stops at lights — and observes it through the ray-traced canyon model above. The matcher then consumes the stream ping by ping, exactly as it would live. Synthetic Gaussian modes (σ = 5/15/30 m) remain available as controls, both for comparison and to show how much harder structured, biased error is than white noise of the same magnitude.

Watch the three trajectories: red raw pings drifting off the road, the gold live window continually revising itself, and the purple settled trail it leaves behind. Toggle the memoryless nearest-edge baseline to see what the HMM is actually buying — the baseline flickers across parallel streets every time the bias wanders, while the matcher holds the road. Crank the noise to 30 m, or shrink the window to 30 s, and see the accuracy table respond. Click anywhere on the map to start a new trip there.

Honest idealizations: the turn priors here are derived from junction geometry and road class (production learns them from millions of matched historical traversals — the demo's are reference priors in the same packed format); the accuracy channel is fused but the phone's reported heading and speed aren't, though production uses all three; the canyon model traces single-bounce specular reflections only, with building heights from OSM tags where present and a 12 m default where not, GPS satellites only, and the skyline within 700 m of the receiver; during an outage the receiver simply repeats its last fix rather than dead-reckoning; and speeds are OSM speed limits under a fixed congestion factor rather than live traffic. The structure — quadtree candidates, packed parameter lookups, bounded next-edge searches, Viterbi over a trailing window with per-ping accuracy weighting and outlier bridging — is the real thing.