STANDARDwalkthrough
Location Service and Map Matching
A user is driving along a highway with a parallel frontage road 15 meters away. Raw GPS reports their position as being on the frontage road.
This is a catastrophic failure caused by GPS error. Raw GPS has 5 to 10 meter accuracy in open sky and 50 meters or more in urban canyons where buildings reflect satellite signals (multipath interference).
“The navigation app says "turn right" onto the frontage road when the user is actually on the highway at 65 mph.”
The simplest solution, snapping to the nearest road, fails at exactly the worst moments: highway-frontage parallels, complex intersections, and multi-level interchanges. We need something smarter.
We use a Hidden Markov Model (HMM) where the hidden states are road segments and the observations are GPS readings. For each GPS point, we compute emission probabilities (how likely this GPS reading came from each nearby road segment, based on perpendicular distance) and transition probabilities (how likely the driver moved from segment A to segment B, based on road connectivity and the distance traveled).
The Viterbi algorithm finds the most likely sequence of road segments through the entire trajectory, not just the single nearest road for each point. Why HMM over simple nearest-road snapping?
Because the HMM considers the entire trajectory. If the previous 20 GPS points were all on the highway and the current point is ambiguous, the HMM assigns much higher probability to the highway because leaving the highway requires a specific exit ramp.
Simple snapping has no memory and would oscillate between highway and frontage road with every noisy GPS reading. Modern phones improve raw GPS accuracy through fused location: combining GPS satellites (5 to 10m accuracy), Wi-Fi access point triangulation (15 to 30m), cell tower triangulation (100 to 300m), accelerometer dead reckoning (drift-prone but gap-filling), and barometer (altitude for multi-level roads).
Google's Fused Location Provider on Android combines all these signals using a Kalman filter before passing the fused coordinates to the map matching HMM. Trade-off: the HMM adds 10 to 20ms of latency compared to simple nearest-road snapping at under 1ms.
For navigation turn-by-turn, this latency is invisible. For real-time multiplayer games that need 60fps location updates, the HMM cost might matter.
We accept the latency because wrong-road snapping is far more costly than a 20ms delay. What if the interviewer asks: what about tunnels where GPS is completely lost?
We switch to dead reckoning using the accelerometer and gyroscope, projecting the vehicle's last known speed and heading along the road graph until GPS signal returns.
Related concepts