Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

New geometric approaches to the map-matching problem
T. Akamatsu, G. Gress, K. Huneycutt, S. Omura
Academic Mentor: Dr. Kano
Industry Mentor: Dr. Yamazaki

August 8, 2022
g-RIPS
1 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Mathematical assumption
The “distance" with error

Map-matching
Given GPS trajectory data and a road map, map-matching is the process ofdetermining the route on the map that corresponds to the trajectory data.

Web mapping services

Autonomous Vehicles [H]
2 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Mathematical assumption
The “distance" with error

Problem Statement

3 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Mathematical assumption
The “distance" with error

Problem Statement
Let us fix N ∈ N, N ≥ 2, but almost everywhere we consider the case N = 2.
Definition (Trajectory)
A trajectory T r is a sequence p = (p1 , p2 , . . . , pn ) of points in RN equipped witha sequence t(p) = (t1 , . . . , tn ) of positive numbers satisfying t1 < t2 < · · · < tn ,called the timestamp of p,a sequence spd(p) = (spd1 , . . . , spdn ) of positive numbers called the speed ofp (optional),a sequence u(p) = (u1 , . . . , un ) of unit vectors in RN , called the direction of p
(optional).
4 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Mathematical assumption
The “distance" with error

Problem Statement
Definition (Road Network)
A road network (also known as a map) is a directed graph G = (V, E) consists ofthe set V (resp. E) of vertices (resp. edges) with an embedding ϕ : |G| → RN of thegeometric realization |G| of G. We will identify G and the image ϕ(|G|) by ϕ as longas there is no confusion.
Definition (Local Road Network)
A local road network is a directed connected subgraph of G = (V, E).

5 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Mathematical assumption
The “distance" with error

Road Network

6 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Mathematical assumption
The “distance" with error

Local Road Network

7 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Mathematical assumption
The “distance" with error

Problem Statement
Definition (Route)
A route r on a road network G = (V, E) is a sequence of connected edges(e1 , e2 , . . . , en ) ⊂ E, i.e. the head of ei coincides with the tail of ei+1 for eachi = 1, 2, . . . , n − 1. Let R denote the set of all routes.
Definition (Candidate Routes)
For the local road network graph as H of the road network G, we define
CRH = CR B {routes on a local road network graph H},

8 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Mathematical assumption
The “distance" with error

Route

9 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Mathematical assumption
The “distance" with error

Candidate Routes

10 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Mathematical assumption
The “distance" with error

Problem Statement

Definition (Map-Matching)
Given a road network G = (V, E) and a trajectory T r, the map-matching, MRG (T r),
is the route that is the argument of the minimum of some function L : CR → R+ ,called the loss function.

11 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Mathematical assumption
The “distance" with error

Map-matching Pipeline
Road network and trajectory

Pre-processing

Candidate routes

Minimize loss function

Optimal route
12 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Mathematical assumption
The “distance" with error

Mathematical Formulation
edge
Assumption
Give the GPS error as Err : p → R≥0 and assume
that the spherically-symmetric probability measure
γ p (e.g. Gaussian measure) is given such thato
 nsupp γ p = B p; Err(p) B x ∈ RN dRN (x, p) ≤ Err(p) .

p1
supp γ p2Err(p2 )p2x

We assume that p ∈ p is truly located at x withprobability γ p (x).
Suppose that there is NO error with respect tothe speed and direction information.

p3
Exist withprobability γ p2 (x).
13 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Mathematical assumption
The “distance" with error

Definition (The “distance" with error between p ∈ p and e ∈ E)
• Define the “distance" with error dErr between p ∈ p (with errors) and e ∈ E (without
errors) as
Z
dErr (p, e) B dRN (x p , e) dγ p (x p ).
x p ∈B p;Err(p)x p3dRN (x p3 , e) B min dRN (x p3 , xe )
xe ∈e

p

=0

x p1

x p2
edge e14 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Review of mid-term presentation
Motivation
Our strategy
Summary & Future problem

Wasserstein method
Definition ((L1 -)Wasserstein distance (review of mid-term presentation))
Let (X, d) be a complete and separable metric space. For probability measures µ, ν withfinite supports, we define W1 distance between µ and ν asXX
W1 (µ, ν) B mind(x, y)π(x, y),π∈Π(µ,ν)where π ∈ Π(µ, ν) :⇔ for any x, y ∈ X,

Px∈X y∈Xy∈X π(x, y) = µ(x),Definition (Prob. meas. associated w/ p and A ∈ CR)
P• For the trajectory p, define µp B (1/n) p∈p δ p .
• ▷ Devide each A ∈ CR into m + 1 equal parts andV(A, m) denotes the set of m threshold points.
P▷ Define νA B (1/m) a∈V(A,m) δa .

P

x∈X π(x, y) = ν(y).

A

B

Compare W1 (µp , νA ) with W1 (µp , νB ).
15 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Review of mid-term presentation
Motivation
Our strategy
Summary & Future problem

Wasserstein Distance: Proof of Concept

16 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Review of mid-term presentation
Motivation
Our strategy
Summary & Future problem

Motivation
Location only.

A▷ W1 (µp , νA ) < W1 (µp , νB ).
We should select the route B.
Introduce probability measures µεp,A , νεA and νεBthat include speed and direction information.
▷ Compare W1 (µεp,A , νεA ) with W1 (µεp,B , νεB ).

B▷ The effect of location is still strong.
Normalization.

• Each p ∈ p is located on thevertical or parallel bisectors.
• spd(p), Err(p) are the same ateach p, respectively.
17 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Review of mid-term presentation
Motivation
Our strategy
Summary & Future problem

Motivation
Location only.

A▷ W1 (µp , νA ) < W1 (µp , νB ).
We should select the route B.
Introduce probability measures µεp,A , νεA and νεBthat include speed and direction information.
▷ Compare W1 (µεp,A , νεA ) with W1 (µεp,B , νεB ).

B▷ The effect of location is still strong.
Normalization.

• Each p ∈ p is located on thevertical or parallel bisectors.
• spd(p), Err(p) are the same ateach p, respectively.
17 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Review of mid-term presentation
Motivation
Our strategy
Summary & Future problem

Motivation
Location only.

A▷ W1 (µp , νA ) < W1 (µp , νB ).
We should select the route B.
Introduce probability measures µεp,A , νεA and νεBthat include speed and direction information.
▷ Compare W1 (µεp,A , νεA ) with W1 (µεp,B , νεB ).

B▷ The effect of location is still strong.
Normalization.

• Each p ∈ p is located on thevertical or parallel bisectors.
• spd(p), Err(p) are the same ateach p, respectively.
17 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Review of mid-term presentation
Motivation
Our strategy
Summary & Future problem

Motivation
Location only.

A▷ W1 (µp , νA ) < W1 (µp , νB ).
We should select the route B.
Introduce probability measures µεp,A , νεA and νεBthat include speed and direction information.
▷ Compare W1 (µεp,A , νεA ) with W1 (µεp,B , νεB ).

B▷ The effect of location is still strong.
Normalization.

• Each p ∈ p is located on thevertical or parallel bisectors.
• spd(p), Err(p) are the same ateach p, respectively.
17 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Review of mid-term presentation
Motivation
Our strategy
Summary & Future problem

Motivation
Location only.

A▷ W1 (µp , νA ) < W1 (µp , νB ).
We should select the route B.
Introduce probability measures µεp,A , νεA and νεBthat include speed and direction information.
▷ Compare W1 (µεp,A , νεA ) with W1 (µεp,B , νεB ).

B• Each p ∈ p is located on thevertical or parallel bisectors.
• spd(p), Err(p) are the same ateach p, respectively.

▷ The effect of location is still strong.
Normalization.
W1 (µεp,A , νεA )W1 (µεp,B , νεB )▷ Comparewith.
W1 (µp , νA )W1 (µp , νB )17 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Review of mid-term presentation
Motivation
Our strategy
Summary & Future problem

Motivation
Location only.

A▷ W1 (µp , νA ) < W1 (µp , νB ).
We should select the route B.
Introduce probability measures µεp,A , νεA and νεBthat include speed and direction information.
▷ Compare W1 (µεp,A , νεA ) with W1 (µεp,B , νεB ).

B• Each p ∈ p is located on thevertical or parallel bisectors.
• spd(p), Err(p) are the same ateach p, respectively.

▷ The effect of location is still strong.
Normalization.
W1 (µεp,A , νεA ) W1 (µεp,B , νεB )▷>.
W1 (µp , νA )W1 (µp , νB )▷ We can select the route B.
17 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Review of mid-term presentation
Motivation
Our strategy
Summary & Future problem

Our strategy: Perturb µp and each ν only by ε according to speed and direction.
• Let 0 < ε ≪ 1. For each p ∈ p, A ∈ CR, a ∈ V(A, m) and x ∈ V(A, m), define(x = p),(1 − ε)/nεµp,A (x) B 
ε · our weight including S &D (x ∈ V(A, m)),

supp µp

supp µεp,A18 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Review of mid-term presentation
Motivation
Our strategy
Summary & Future problem

Our strategy: Perturb µp and each ν only by ε according to speed and direction.
• Let 0 < ε ≪ 1. For each p ∈ p, A ∈ CR, a ∈ V(A, m) and x ∈ V(A, m), define(1 − ε)/m (x ∈ V(A, m)),ενA (x) B 
ε/n(x ∈ p).

supp νA

supp νεA
18 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Review of mid-term presentation
Motivation
Our strategy
Summary & Future problem

Summary & Future problem
Summary
Quantify the distance between p ∈ p and each A ∈ CR by making µp and νAε-pertubation according to speed and direction information.
Conclude that the route A with the smallest W1 (µεp,A , νεA )/W1 (µp , νA ) is thetrue route.

Future problem (from a theoretical point of view)
Is this method also effective when CR is dense?
Formulation of µp with (γ p ) p∈p .
19 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results“Electric” Method“Harmonic oscillator” method“Electric” Method : Review of Mid-presentation
Route Ap1

p2
p3

Route B

p4
Figure: Connecting traj.

Figure: Moving topts. and giving charges.

“closer” route.

Considering not only trajectory points, but also the entire polyline.
20 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results“Electric” Method“Harmonic oscillator” method“Electric” Method : Problems
Problems:
× Not taking into account speed and direction information.
R
R
× Divergence problem : polyline route r−2
RR
Even if polyline route (r2 + ε)−1 , affects of intersection point is too large.
p2 p4 p6

p7
p1 p3 p5

p8
p9
p10

• • •

• • •

• • • ••••• • • ••••
21 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results“Electric” Method“Harmonic oscillator” method“Electric” Method : Strategy to Solve the Problems
Strategy:
Replace “maximizing inverse square” to “minimizing square”;
1: “electric” method
A∈CR r 2
max

min r2 : “harmonic oscillator” method

A∈CR

22 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results“Electric” Method“Harmonic oscillator” method“Harmonic Oscillator” Method : General Setting
m :mass,
k :spring constant,v(t) :verocity of mass point,kx(t) :displacement from naturallength of springk

Lagrangian
x(t)
m

v(t)

1
1
L(t) = mv(t)2 + kx(t)22
2
ActionZ
)
Z (
1
1
2
2
Act =
mv(t) + kx(t) dt
L(t) dt =2
2
23 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results“Electric” Method“Harmonic oscillator” method“Harmonic Oscillator” Method : Settings in Map-matching Problem
p ∈ RN : trajectory point,v p = spd p u p ∈ RN : speed at p,e1

p Err p

e1

vp
e2
B

Err(p) ∈ R : error of p,

B ∈ CR,e∈B

S (p, e) : score of edge e
B ⟨v, ⃗e⟩RN exp (−dErr (p, e))Connect trajectory point to the highest score edge by “spring”.
Define “Lagrangian” of this system.
24 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results“Electric” Method“Harmonic oscillator” method“Harmonic Oscillator” Method : Settings in Map-matching Problem
v s : spring direction component of v p
x p = dErr p (p, e) : “displacement” of p
xp mp
vs

e1
kp
vp

1
m p = 1+Err(p) : “mass” of p,k p = exp (−Err(p)) : “spring constant” w.r.t. p,
M(p) = m p

2
vs: “momentum” of p,log(1+|v p |)P(p) = k p x2p : “potential” of p,
L := M(p) + P(p) : “Lagrangian”.
25 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results“Electric” Method“Harmonic oscillator” method“Harmonic Oscillator” Method : Settings in Map-matching Problem
p = (pi )0≤i≤n : traj. points,
vp = (vi = spdi ui )0≤i≤n : velocity,p0

Err : p → R : error,
p1

B ∈ CR : route.

lp

pn−1

pn

lp : [0, 1] → RN : polyline,
vlp : [0, 1] → RN : velocity,

B

Errlp : [0, 1] → R : error,

L(t) := M(lp (t)) + P(lp (t)),Z
L(t) dt : “action” of p on B.

Actp (B) :=[0,1]

26 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results“Electric” Method“Harmonic oscillator” method“Harmonic Oscillator” Method : Settings in Map-matching Problem
Route A
p1

p2
p3

p4

Route B
Calculate Actp (A) and Actp (B).
Choose the route that minimize action.
27 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results“Electric” Method“Harmonic oscillator” method“Harmonic Oscillator” Method : Strength/Weakness and Future
ProblemStrength/weakness:✓ No divergence problem,✓ Taking into account speed and direction naturally,
× Insufficient consideration of the entire route.
Future problems:
Consider more appropriate way to define mass and spring constant.
Connect to all edge of a route with appropriate weight to consider thewhole route.
28 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results“Electric” Method“Harmonic oscillator” method“Electric Method" and "Harmonic Oscillator": Proof of Concept

29 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Implementing metric-based methods

30 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Implementing metric-based methods
Why are we defining each of the metric-based functions here, instead of in a
separate Class? Because metric_mm is designed to accommodate any
distance-based loss function, allowing for simple and customizable simulator
creations.

31 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Sendai Map Revisited

Now we revisit the Sendai map case.

32 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Map-matching Pipeline
Road network and trajectory

Pre-processing

Candidate routes

Minimize loss function

Optimal route33 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Sendai Map Revisited

34 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Map-matching Pipeline
Road network and trajectory

Pre-processing

Candidate routes

Minimize loss function

Optimal route35 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Sendai Map Revisited

Obtaining Candidate Routes (Dijsktra’s Algorithm)
CPU times: user 45.8 s, sys: 49.7 ms, total: 45.9 s
Wall time: 45.9 s
Preprocessing Candidate Routes
CPU times: user 12.7 s, sys: 103 ms, total:
Wall time: 12.8 s

12.8 s36 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Map-matching Pipeline
Road network and trajectory

Pre-processing

Candidate routes

Minimize loss function

Optimal route37 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Sendai Map Revisited
Least Squares Runtime
CPU times: user 1.53 s, sys:
Wall time: 1.55 s

29.9 ms, total:

1.56 sInverse Squares Runtime
CPU times: user 14.2 s, sys:
Wall time: 10.2 s

392 ms, total:

14.6 s

Wasserstein Runtime(Computation times vary wildly based on parameters- anywherefrom 20 seconds, to 20 minutes, to 2.5 hours)
38 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Sendai Map Revisited
Unfortunately, due to FMM relying on outdated libraries, we could not produce animage demonstrating FMM’s performance on the new trip data. Our preliminary
findings demonstrated that FMM still performed poorly on the dataset. For thesake of comparison, recall FMM’s results on the older GPS dataset:

39 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Sendai Map: Least Squares (Harmonic Oscillator) Result

40 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Sendai Map: Inverse Squares (Electrical Method) Result

41 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Sendai Map: Wasserstein Method Result

42 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Computational Complexity (Preprocessing)

43 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Computational Complexity (Metric Calculations)

The following scatter plots demonstrates how computation grows as a function of
input nodes.

44 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Computational Complexity (Metric Calculations)45 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Computational Complexity (Metric Calculations)46 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Computational Complexity
This suggests that simple distance methods (like inverse squares and leastsquares) have a computational complexity of O(n). Due to processing power, we
could not obtain enough data to infer the computational complexity of theWasserstein method. Because it relies on linear programming, we hypothesizethat the growth rate is a polynomial of degree > 1.
Some aspects of these algorithms can be improved upon– simple parallelization
techniques offer a noticeable increase. However, other aspects are inherent to themethod and are difficult to improve.

47 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Preliminary Numerical Results

Due to limits in processing power, we were unable to test our algorithms against allof the data in the dataset. However, we demonstrate a few cases here.

48 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Preliminary Numerical Results

49 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Future Work (Implementation)
While a naive Dijkstra method generates a good set of candidate routes, it
has many shortcomings. It is still relatively slow, it is conditional on the given
parameters, and it cannot handle stranger routes (traversing an edge morethan once). Each of these individually can be addressed; or it may be moresuitable to find an alternative candidate route generation method.
Investigate Wasserstein method inconsistencies more thoroughly
Incomplete road networks
Implement IMU-based map matching approaches

50 / 51

Introduction to map-matching
Wasserstein method“Physical” method
Numerical Results

Implementation
Sendai Revisited
Computational Complexity
Preliminary Numerical Results
Future Work

Thank You! And References
High-assurance Mobility Control Lab.
https://hmc.unist.ac.kr/research/autonomous-driving/
M. Kubic̆ka, A. Cela, P. Moulin, H. Mountier and S. I. Niculescu, Dataset for testing and training of
map-matching algorithms, In 2015 IEEE Intelligent Vehicles Symposium (IV), 1088–1093 (2015).
F. Santambrogio, Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling,
Progress in Nonlinear Differential Equations and their Applications, Birkhäuser/Springer, Cham. (2015).
F. Yu, H. Chen, X. Wang, W. Xian, Y. Chen, F. Liu, V. Madhavan and T. Darrell, BDD100K: A Diverse Driving
Dataset for Heterogeneous Multitask Learning, In Proceedings of the IEEE/CVF conference on computer
vision and pattern recognition, 2636–2645 (2020).
C. Yang and G. Gidófalvi, Fast map matching, an algorithm for integrating a hidden Markov model withprecomputation, International Journal of Geographical Information Science. Taylor & Francis, 32(3),547–570 (2018).

51 / 51