Map matching when the map is wrong: Efficient vehicle tracking on- and
  off-road for map learning
  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.
