Map matching when the map is wrong: Efficient vehicle tracking on- and off-road for map learning
This addresses the issue of unreliable vehicle tracking for applications like navigation and map updates, though it is incremental as it builds on existing HMM and Kalman methods.
The paper tackles the problem of vehicle tracking when the road map is inaccurate, by developing an algorithm that efficiently combines map matching and free-space tracking to handle both on- and off-road movement. The result is a method that avoids misleading trajectories and can detect map errors, such as missing roads or incorrect directions, for map learning applications.
Given a sequence of possibly sparse and noisy GPS traces and a map of the road network, map matching algorithms can infer the most accurate trajectory on the road network. However, if the road network is wrong (for example due to missing or incorrectly mapped roads, missing parking lots, misdirected turn restrictions or misdirected one-way streets) standard map matching algorithms fail to reconstruct the correct trajectory. In this paper, an algorithm to tracking vehicles able to move both on and off the known road network is formulated. It efficiently unifies existing hidden Markov model (HMM) approaches for map matching and standard free-space tracking methods (e.g. Kalman smoothing) in a principled way. The algorithm is a form of interacting multiple model (IMM) filter subject to an additional assumption on the type of model interaction permitted, termed here as semi-interacting multiple model (sIMM) filter. A forward filter (suitable for real-time tracking) and backward MAP sampling step (suitable for MAP trajectory inference and map matching) are described. The framework set out here is agnostic to the specific tracking models used, and makes clear how to replace these components with others of a similar type. In addition to avoiding generating misleading map matching trajectories, this algorithm can be applied to learn map features by detecting unmapped or incorrectly mapped roads and parking lots, incorrectly mapped turn restrictions and road directions.