Map Matching

Map Matching
An Introduction

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}$