Database Reference
In-Depth Information
then maintains the current road segment (a discrete ID), a position on
that road segment, and a deviation from the road to allow for errors in
the road network. Inference for the proposed model is computed using
a particle filter which is typical for these complex, non-linear dynamic
models. The future position of an object is computed by allowing each
particle to take a random walk along the road network for a limited time.
Each road segment has a distribution over the amount of time it would
take to traverse this segment, thus the point at which the particles stop
when time runs out provides a reasonable estimate of the object's next
state. The results show substantial improvements over a basic KFM for
tracking.
A similar problem is that of map-matching [69], in which an object's
noisy position observation is aligned with a known restricted movement
surface (e.g. road network). The diculty in map-matching is the un-
certainty in an object's observed location at a given time. Additionally,
the road network may be uncertain as well (e.g. user generated maps).
Lastly, the problem typically needs to be solved in real-time so the ob-
ject can identify its true current position and continue navigating to its
destination.
A natural model for the task of map-matching is the hidden Markov
model (HMM) since it combines information about the distribution over
the current state of an object with new (noisy) observations. Newson
and Krumm [60] apply an HMM for the map-matching problem using
GPS as the observed value and individual road segments as the hidden
states. The authors defined the transitions between roads to be based on
the distance and connectivity between segments. For instance, a vehicle
is more likely to transition to a connected road segment than one that is
far away. A similar model is also introduced by Pink and Hummel [67].
In this case, the authors utilize inferred heading information about the
vehicle paired with a more accurate representation of the road network
based on smooth polynomials instead of linear segments to improve ac-
curacy. Both of these methods rely on consistent and high frequency
GPS measurements.
In practice, GPS observations are often obtained irregularly and at
low-sampling rates (i.e. 1
/
120Hz or lower). In these situations, the map-
matching problem becomes that of inferring the specific route (sequence
of roads traveled) between two GPS observations in an o
ine setting.
Several approaches have been developed specifically for this scenario.
Similar to previous works, Lou et al. [52] address the low sampling fre-
quency map-matching problem by introducing an algorithm that com-
bines a spatial and temporal analysis into an HMM-like model. The
Spatio-Temporal-matching (ST-matching) algorithm first attempts to
