Loading Web-Font TeX/Caligraphic/Regular
Map Matching
An Introduction
Prof. David Bernstein
James Madison University
Computer Science Department
bernstdh@jmu.edu
The Map-Matching Problem
The Situation:
A person/vehicle is moving along a finite set of streets
\overline{\mathcal{N}}
We are provided with an estimate of this person's location at a finite number of points in time denoted
\{0, 1, ..., T \}
The person's actual location at time
t
is denoted by
\overline{P}^{t}
and the estimate is denoted by
P^{t}
The Problem:
Find the street in
\overline{\mathcal{N}}
that contains
\overline{P}^{t}
The Map-Matching Problem (cont.)
A Complication:
We do not know the street system,
\overline{\mathcal{N}}
exactly
We have a
network (or graph)
representation
\mathcal{N}
and a set of piecewise linear curves (one curve associated with each arc/link)
The Actual Problem(s):
Match the estimated location
P^{t}
with a curve,
A
in the "map"
Then determine the street
\overline{\mathcal{A}} \in \overline{\mathcal{N}}
that corresponds to the actual location
\overline{P}^{t}
A secondary concern is to determine the position on the curve
A
that best corresponds to
\overline{P}^{t}
The Map-Matching Problem (cont.)
Point-to-Point Matching
The Idea:
Match
P
t
to the "closest" breakpoint in the piecewise linear curve
A Difficulty:
Point-to-Curve Matching
The Idea:
Identify the arc that is closest to
P^{t}
One Approach:
Point-to-Curve Matching (cont.)
One Difficulty:
Point-to-Curve Matching (cont.)
Another Difficulty:
Curve-to-Curve Matching
The Idea:
Find the arc that is closest to the piecewise linear curve,
P
defined by the points
P^{0}, P^{1}, ..., P^{m}
A Difficulty:
Curve-to-Curve Matching (cont.)
Another Approach:
Use the "total" distance
A Difficulty:
Curve-to-Curve Matching (cont.)
Another Approach:
"Correct" for differences in length
A Difficulty:
Using Topological Information
Getting Started
Using Topology (cont.)
Using Connectivity/Topology
There's Always More to Learn
MATHJAX CALIGRAPHIC