The Mitsubishi A-Team: Map-Matching
Jeremy J. Lin, Tomoro Mochida, Riley C. W. O’Neill, Atsuro Yoshida
Academic Mentor: Dr. Shunsuke Kano
Industry Mentors: Dr. Masashi Yamazaki, Akinobu Sasada

July 14, 2023
g-RIPSJ. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

1 / 87

Introduction, Notation, Problem Summary and Statement

Table of Contents
1

Introduction, Notation, Problem Summary and Statement

2

Machine Learning Methods

3

AHP Map Matching Algorithm

4

Fuzzy Logic Map Matching Algorithm

5

Evaluation Performance

6

Preprocessing/Postprocessing

7

References

8

Misc

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

2 / 87

Introduction, Notation, Problem Summary and Statement

Map Matching
Map matching is the process of determining the correct traveling route taken by a person or
vehicle using road network data and trajectory data obtained from GPS or other positioning
sensors.

(a) Google Map

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida(b) Self-driving Car [1]Mitsubishi A

15/07

3 / 87

Introduction, Notation, Problem Summary and Statement

Road Network
Definition (Road Network)
A road network (V , E ) is a graph drawn on a plane.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

4 / 87

Introduction, Notation, Problem Summary and Statement

GPS Trajectory
Definition (GPS Trajectory)
A GPS trajectory Tr is a timeseries of points in a plane.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

5 / 87

Introduction, Notation, Problem Summary and Statement

Map Matching Problem
Here is the main problem our research project addresses:
Problem (Map Matching Problem)
Given a road network (V , E ) and a GPS trajectory Tr, match Tr to the actual route in themap.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

6 / 87

Introduction, Notation, Problem Summary and Statement

Previous Research

There is a lot of previous research in map matching algorithms:
1. Topological Map Matching Algorithm
2. Map Matching Based on Hidden Markov Model
3. Dijkstra’s Algorithm for Offline Map Matching

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

7 / 87

Introduction, Notation, Problem Summary and Statement

Datasets
State of the art trajectory registration algorithms deployed at the industrial level utilize
millions of trajectories for training and inference, leveraging the device’s sensors (IMU
(accelerometer/gyroscope), speedometer, compass, etc) for improved results.
In the absence of such an expansive dataset, we are left to scour the internet for data:
DatasetRaw GPS IMU data
Velocity
Elevation
GroundTimeseries
Truth
KCMMN [2]V
X
X
X
V
BDD100K [3]
V
V
V
X
X
OpenStreetMaps [4]
V
X
V
V
X
EnviroCar [5]
V
X
V
X
X
However, none of these have IMU, velocity, AND ground truth trajectories.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

8 / 87

Introduction, Notation, Problem Summary and Statement

Data Fusion and Processing

In the absence of a dataset with speed, direction, IMU data, AND ground truth
trajectories, we propose to train a Graph Neural Network (GNN) on the BDD100K
dataset to approximate IMU/velocity data from the raw trajectories for use on the
KCMMN dataset.
BDD100K: 5GB compressed, 47GB as uncompressed JSON’s, 3GB after removing
trajectories with missing GPS or gyroscopic data ( 2,000 of 520,000 trajectories) andresaving as CSV’s.
Data processed at Minnesota Super-computing Institute due to storage overhead.
What is a graph neural network?

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

9 / 87

Machine Learning Methods

Table of Contents
1

Introduction, Notation, Problem Summary and Statement

2

Machine Learning Methods

3

AHP Map Matching Algorithm

4

Fuzzy Logic Map Matching Algorithm

5

Evaluation Performance

6

Preprocessing/Postprocessing

7

References

8

Misc

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

10 / 87

Machine Learning Methods

What is a Neural Network?
”Universal approximator” function with layers of the form:
x k = f (W k x k−1 + b k )f : Rdk → Rdk nonlinear function; W k ∈ Rdk ×dk−1 , b k ∈ Rdk learnable
Trained to minimize some loss function over some dataset via backpropagation.
Convolutional Neural Networks (CNNs): learn a local filter of the form:Xx k+1 = b k+1 +F k+1 (x k − y k )y k

y k ∈N(x k )where F is compactly supported. For images and grid like data, F is just a matrix;
with pooling operations, this is incredibly powerful. Note this is a numericalapproximation to the integralZ(F ∗ I )(x) =J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

F (x − y )I (y )dy .

15/07

11 / 87

Machine Learning Methods

Convolutional Neural Networks

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

12 / 87

Machine Learning Methods

Graph (Convolutional) Neural Networks
Graph - points + pairwise connectivity, i.e. trajectories and roads. Want a network structure that can leverage theconnectivity and extract spatial-temporal features.
PyTorch Geometric (PyG) has over 100 different forms of graph convolutional neural networks implemented, eachof which leverage different properties of the graph. Of those in PyG, we identified 3 network layer structures ofinterest:
X
1. NNConv: xik+1 = W k xik +Fk (xj0 − xi0 )xjk , where Fk : Rd0 → Rdk ×dk+1 is a neural network.
j∈N(i)H
X X
1
2. FeaStConv: xik+1 =qh (xik − xjk )Whk xjk , where qh (z) = Softmaxh (uhT z + ch ) is an attention|N(i)|h=1j∈N(i)

head.
3. GMMConv: xik+1 =HX X
1gh (xik − xjk )Whk xjk , where gk is a learnable Gaussian function.
|N(i)|h=1j∈N(i)We postulate that a naturally translation invariant network would be adventitious, at least for the first layer, e.g.:X1
xik+1 = b k +F k (xj0 − xi0 )W k [xj0 − xi0 ]|N(i)|j∈N(i)

but nothing of this form appears to be implemented yet in PyG - implementing such a layer is of tremendousinterest.
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

13 / 87

Machine Learning Methods

GNN for Feature Extraction / Modeling
1. Modeling IMU/velocity data:
3 filter layers of NNConv GNN network in PyG. Each filter consists of a 3 layer neuralnetwork.
Graph construction: 11-KNN (time) neighbors graph (this is identical to a 1D
convolution, just for proof of concept).
If successful, this will give robust approximations of the acceleration 3-vector, gyroscopic
3-vector, speed, and direction of travel.
2. Unsupervised Graph contrastive learning: (if (1.) is successful)leverage the large size of BDD100K, KCMMN, and OpenStreetMaps data to learn morerobust features for registration.
Implement SimCLR contrastive learning framework [6] on graphs - next slide.
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

14 / 87

Machine Learning Methods

Graph Learning Frameworks: Results

Implemented 3 layer NNConv GNN for modeling IMU data, each with 3-layer filter on
input graph.
Result: not good. Possible vanishing gradient problem.
Additionally, PyG DataParallel is not optimized for distributed models - actually slower touse more GPU’s.
Hence, graph neural networks were not examined further for this study.
What to do instead?

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

15 / 87

Machine Learning Methods

1D CNN’s for Modeling IMU Data

Learn local filter to estimate IMU data.
Result: not good either... possible vanishing gradients?
BDD100K data is ”questionable” - does not specify CRS for GPS points or units ofacceleration/speed. Requests for clarification have gone unanswered.
Conclusion: abandoned modeling IMU data to focus on training edge affinity function.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

16 / 87

Machine Learning Methods

GNNs for Learnable Edge Affinity Function
Suitable for Dijkstra’s algorithm, Fuzzy inference, etc.
Define S(e) = {i : e ∈ KNN(pi )}, D(p, e) = argminq∈e |q − p|, |D|(p, e) = minq∈e |q − p|.
Train f (e) = f (V [S(e)], [F [S(e)]; |D|(V [S(e)]; D(V [S(e)], e)], e) as a neural network.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

17 / 87

Machine Learning Methods

Edge Affinity Model Architecture
1. Point-wise feature encoder: 3 layer neural net. Input: signed distance to edge,
projection’s signed distance to each node.
2. Feature Aggregation (pooling): to be discussed
3. Decoder (classifier): 2 layer neural net

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

18 / 87

Machine Learning Methods

Feature Aggregation for Machine Learning (aka Pooling)

As the set of points corresponding to each edge under the inverse KNN adjacency vary in
cardinality, we need some means of aggregating the point-wise features into a single vector of
fixed size for machine learning.
We try the following as an initial implementation:n
X
Summation:f (xi ) - intuitively, if an edge has more nearby trajectory points, it’s more
i=1

likely in the ground truth trajectory.
n
1X
Averaging:f (xi ) - erases information on number of points, but more regularity.
ni=1

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

19 / 87

Machine Learning Methods

Results of Summation/Average pooling

Not good. Model tends to vote all trajectory, all non-trajectory, or 50-50 split.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

20 / 87

Machine Learning Methods

New Pooling Operations for Point-Based Networks
We Introduce a novel new pooling operation for data of varying cardinality (e.g. pointclouds):
Extract k features with maximal l 1 norm and k features with minimal l 1 norm:
Itop = Kargmaxi ∥x[i]∥1 ;Ibot = Kargmini ∥x[i]∥1V = (x[Itop ], x[bot ])Set m = 2k. Extract:2
Dot products: Ai j = Vi · Vj : i < j ( m 2−m values)2
l 1 Distances: Dij = ∥Vi − Vj ∥1 ( m 2−m values)
l 1 magnitudes: Mi = ∥Vi ∥1 (m values) Vectors: V (m ∗ n (feat dim) values)
Total: 4k 2 + 2kn values output.
Q: What to do if there’s not k points in the edge set?
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

21 / 87

Machine Learning Methods

Padding

If there are fewer than k points at an edge... Let’s repeat the maximum/minimum value forthe respective max/min index set.
This introduces 0’s into the extracted distances, i.e. we tell the model not many points are
there, which can be incorporated into the decision making process. This is analogous to thepositional encodings used for transformers.
If there are fewer than 2k points: redundancies are still had, but in different places. Is this abad thing? Unclear.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

22 / 87

Machine Learning Methods

Loss Formulation(x
Define the y -switch operator for ease of notation: (x)y =
1−x

:y =1
:y =0

Binary Cross Entropy: BCE (x, y ) = −y log(xy ) − (1 − y ) log(1 − xy )Reweighted BCE: αy BCE (f (x), y ) for α ∈ (0, 1)
Focal loss: FL(x, y ) = −αy (1 − xy )γ log(xy )J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

23 / 87

Machine Learning Methods

Results & Discussion
High training accuracy (95% overall, 84% of trajectory edges correctly identified)
Low positive testing accuracy (82% overall, 10% of trajectory edges identified. )Q: Is this overfitting? Or is it differences in training/testing distributions? Or both?
∼ The train/test split was done by trajectory... quite possible that these vary in distribution.
∼ Overfitting - more work needs to be done to determine where excess in model is.
∼ The pooling operation results in a very large output dimension - how to best mitigate this?
Attempts to mitigate overfitting so far have resulted in lower training AND testing accuracy...
interesting.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

24 / 87

Machine Learning Methods

Training Results

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

25 / 87

Machine Learning Methods

Training Results: Enlarged to Show Texture

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

26 / 87

Machine Learning Methods

Training Results: The Good

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

27 / 87

Machine Learning Methods

Training Results: The Bad

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

28 / 87

Machine Learning Methods

Testing Results

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

29 / 87

Machine Learning Methods

Testing Results

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

30 / 87

Machine Learning Methods

Takeaways & Directions for Future Work
The model has potential... but can it outperform hand-crafted feature extraction?
Possible Model / Training improvements:
1. Modifications to training: learning rate decay, adaptive weighting, longer training time.
2. Data is very clean - add obvious measures to mitigate common-sense mistakes?
3. Input feature engineering: absolute values instead of signed distances? When/what tonormalize?
4. Pool sooner? Too many layers for an easy problem?
Data Improvements:
1. GET MORE DATA - reduce susceptibility to differences in projection
2. GET DATA WITH IMU/VELOCITY DATA
Also: apply Dijkstra’s algorithm to results for evaluation: quite possible it works even for
testing da
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

31 / 87

AHP Map Matching Algorithm

Table of Contents
1

Introduction, Notation, Problem Summary and Statement

2

Machine Learning Methods

3

AHP Map Matching Algorithm

4

Fuzzy Logic Map Matching Algorithm

5

Evaluation Performance

6

Preprocessing/Postprocessing

7

References

8

Misc

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

32 / 87

AHP Map Matching Algorithm

What is AHP?

The Analytic Hierarchy Process (AHP) is a method of decision making that combinesmathematical analysis with human judgment. It uses hierarchical classification to handle
complex or abstract information.
AHP has not been widely applied to map matching, so our algorithm is a relatively new
method.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

33 / 87

AHP Map Matching Algorithm

Flowchart of AHP Map Matching Algorithm
Input

Initial Map Matching (IMM)

True

Junction Condition (JC)Subsequent Map
Matching (SMM)

The correct edge isthe previously selected edge

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

False

Mitsubishi A

15/07

34 / 87

AHP Map Matching Algorithm

Initial Map Matching (IMM)

The purpose of initial map matching is to specify the correct edge that matches the first
trajectory point p0 .
The initial map matching uses:
Distance data, which is the data of the distance between the point p0 and each candidate
edge.
Direction data, which is the data of the angle difference between the heading of the firstpoint p0 and the direction of each candidate edge.
Using AHP, we assign a weight to each candidate edge and finally select the highest weightedge as the correct edge for p0 .

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

35 / 87

AHP Map Matching Algorithm

Junction Condition (JC)

After IMM, SMM, and also JC itself, we always check the junction condition (JC) for the next
trajectory point, say pt . The junction condition verifies whether the point still matches thepreviously selected edge. It is based on
How far the point is from the next junction point.
How small the angle difference between the direction of pt and that of pt−1 is.
If the point is considered to have not yet crossed the junction, the previously selected edge istaken as the correct edge for that point. Otherwise, we proceed to the subsequent map
matching.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

36 / 87

AHP Map Matching Algorithm

Subsequent Map Matching (SMM)
The subsequent map matching (SMM) is performed on a point that fails to meet the junction
condition. It detects the matching of that point based on
Distance data (same as IMM).
Direction data (same as IMM).
Turn restriction data, which reflects if the vehicle on the previously selected edge canlegally turn onto each candidate edge.
Using these data we choose the correct edge for the point.
We go back to the junction condition and repeat this process until we reach the last trajectory
point.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

37 / 87

AHP Map Matching Algorithm

Implementation Result

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

38 / 87

AHP Map Matching Algorithm

Implementation Result

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

38 / 87

AHP Map Matching Algorithm

Implementation Result

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

38 / 87

AHP Map Matching Algorithm

Implementation Result: Example of MismatchingSome jumps

Some branches

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

39 / 87

AHP Map Matching Algorithm

Summary

Advantages
1. Simple and easy to understand.
2. Relatively fast.
3. Considerably good accuracy.

Disadvantages
1. Sensitive to measurement errors.
2. Large variation in accuracy depending on trajectory data.

Future work
1. Postprocessing for detecting and fixing mismatching.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

40 / 87

Fuzzy Logic Map Matching Algorithm

Table of Contents
1

Introduction, Notation, Problem Summary and Statement

2

Machine Learning Methods

3

AHP Map Matching Algorithm

4

Fuzzy Logic Map Matching Algorithm

5

Evaluation Performance

6

Preprocessing/Postprocessing

7

References

8

Misc

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

41 / 87

Fuzzy Logic Map Matching Algorithm

Fuzzy Inference System

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

42 / 87

Fuzzy Logic Map Matching Algorithm

Fuzzy Logic Map Matching algorithm
Fuzzy logic Map Matching (FLMM) algorithm consists of two main step :Finding the correct link the vehicle is traveling on which can be divided. This step canfurther be divided into two sub-step:Finding initial correct link (IMP step)Finding a correct link when the vehicle crosses an intersection (SMP 2)

tracking vehicle around the link and detecting whether the object crossed the intersection(SMP 1). [7]

Number of Input
Number of RuleJ. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

IMP
4
6

Mitsubishi A

SMP 1
6
12

SMP 2
6
10

15/07

43 / 87

Fuzzy Logic Map Matching Algorithm

Initial Map Matching Process
Input :
1. Speed of the vehicle, v (m/s)
2. Horizontal dilution of Precission (HDOP)
3. Perpendicular Distance, PD (m)4. Heading error, HE = |θ − θ′ |Algorithm:
1. Find all candidate links inside the error bound2. select edges with the highest FIS 1 output
3. repeat until an edges is selected consecutively
Figure: IMP implementation

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

44 / 87

Fuzzy Logic Map Matching Algorithm

SMP 1
Additional input :1. Speed of the vehicle, v (m/s)
2. Perpendicular Distance, PD (m)3. ∆d = d − d2
4. Heading Increment, HI = |θ′ − θ|
5. α and β.

SMP 1 step :1. Calculate FIS 2 score from current trajectory point and theprevious matched point and edges.
2. If FIS 2 is greater than a certain cutoff then conclude that thecurrent edges still in the trajectory, and calculate theprojection point.
3. Else, indicate that current trajectory is entering a junction,and begin SMP 2 step.
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

Figure: FIS2 diagram

15/07

45 / 87

Fuzzy Logic Map Matching Algorithm

SMP 2
Input
1. Speed of the vehicle, v (m/s)
2. Horizontal dilution of Precission (HDOP)
3. Perpendicular Distance, PD (m)4. Heading error, HE = |θ − θ′ |5. Link Connectivity
6. Distance error, difference between distance travelledfrom last position(A) and shortest path from thelast matched position(M) to the current position(B) around the links (e.g ϵ = AB − (MO + ON))SMP 2 step :1. Find all candidate link inside the error bound2. Select the edge with the highest FIS 3 output

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

46 / 87

Fuzzy Logic Map Matching Algorithm

Map Matching Flow Chart

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

47 / 87

Fuzzy Logic Map Matching Algorithm

FLMM Result

Figure: map matching process in KCMMN data set

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

48 / 87

Fuzzy Logic Map Matching Algorithm

FLMM Results
Advantage
1. Intuitive and easy to add or remove input variable
2. Less sensitive to input errors
3. Relatively good result and less sensitive tomeasurement errors

Disadvantage
1. Algorithm is slower than other method we tried.
2. Rules and parameter value in our implementations
are too simple

Figure: Before

Future Works
1. Incorporate data driven algorithm to tune FLMM
parameter (see Figure)
2. Adding new rules to the system (e.g :deciding
whether map is urban versus suburban)
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

Figure: After
15/07

49 / 87

Evaluation Performance

Table of Contents
1

Introduction, Notation, Problem Summary and Statement

2

Machine Learning Methods

3

AHP Map Matching Algorithm

4

Fuzzy Logic Map Matching Algorithm

5

Evaluation Performance

6

Preprocessing/Postprocessing

7

References

8

Misc

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

50 / 87

Evaluation Performance

Evaluationd0
Ground Truth
Prediction

d−

d+
Err =

d− +d+d0

d0 = length of ground truthd− = length of prediction route erroneously subtracted
d+ = length of prediction route erroneously added
Figure: Error Formula by Newson and Krumm [8]J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

51 / 87

Evaluation Performance

Results
AHP and Fuzzy incorporated other variable such as speed and bearing direction, which
are not available in the test dataset.
Parameter tuning needs to be done to achieve better performance.

Figure: FMM Average Error 14.7%
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Figure: AHP Average Error 19.2%

Figure: Fuzzy Average Error 20.2%

Mitsubishi A

15/07

52 / 87

Preprocessing/Postprocessing

Table of Contents
1

Introduction, Notation, Problem Summary and Statement

2

Machine Learning Methods

3

AHP Map Matching Algorithm

4

Fuzzy Logic Map Matching Algorithm

5

Evaluation Performance

6

Preprocessing/Postprocessing

7

References

8

Misc

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

53 / 87

Preprocessing/Postprocessing

Preprocessing

Due to time constraints, we could not conduct experiment in preprocessing of mitigating staypoints and eliminating outliers, though we have already implemented it.
We expect conducting preprocessing reduces the error rate and computation time.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

54 / 87

Preprocessing/Postprocessing

The DBSCAN Clustering Algorithm”Density-Based Spatial Clustering of Applications with Noise” (DBSCAN) is a clustering
algorithm based on metric information. This algorithm classifies the points into the 3categories:
1. Core points;
2. Reachable points;
3. Unreachable points.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

55 / 87

Preprocessing/Postprocessing

Mitigating Stay Points by DBSCAN

Figure: Before averaging eachcluster. The red points are theunreachable points detected by
DBSCAN, and each non-red color
represents one cluster.

Figure: After averaging each cluster.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

56 / 87

Preprocessing/Postprocessing

Eliminating Outliers by DBSCAN

Figure: The orange points were classified as unreachable points by DBSCAN
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

57 / 87

Preprocessing/Postprocessing

Postprocessing

As we have seen, the routes the fuzzy logic MM and AHP find may have a lot of ”jumps” andundesired ”branches”.
In order to deal with these problems, it may be promising to conduct postprocessing such as:
1. Interpolating the jumps;
2. Cutting off the branches.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

58 / 87

Preprocessing/Postprocessing

Interpolating Jumps
We propose filling the jumps simply by the shortest paths:

Figure: Jumps
Figure: Filling Jump by Shorted Paths
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

59 / 87

Preprocessing/Postprocessing

Cutting off Branches

We propose a procedure to cut off the branches as follows:
1. Find the shortest path from the start point to the end point;
2. Subtract the edges in the shortest path from the set of the edges in the predicted routeby the map matching algorithm;
3. Remove all connected components of the shape of a linear graph.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

60 / 87

Preprocessing/Postprocessing

Cutting off Branches

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

61 / 87

Preprocessing/Postprocessing

Cutting off Branches
1. Find the shortest path from the start point to the end point.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

62 / 87

Preprocessing/Postprocessing

Cutting off Branches
2. Subtract the edges in the shortest path from the set of the edges in the predicted route by
the map matching algorithm.
3. Remove all connected components of the shape of a linear graph.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

63 / 87References

Table of Contents
1

Introduction, Notation, Problem Summary and Statement

2

Machine Learning Methods

3

AHP Map Matching Algorithm

4

Fuzzy Logic Map Matching Algorithm

5

Evaluation Performance

6

Preprocessing/Postprocessing

7

References

8

Misc

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

64 / 87References

Acknowledgements

We would like to extend our sincere gratitude and thanks to Mitsubishi, Tohoku University, the
AIMR, the UCLA IPAM, Suito Sensei & G-RIPS staff, and the G-RIPS 2022 Mitsubishi A
team for making this work possible.
We would also like to thank our academic and industrial mentors: Dr. Shunsuke Kano,
Dr. Masashi Yamazaki, and Akinobu Sasada.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

65 / 87References

References I[1][Online]. Available: https://hmc.unist.ac.kr/research/autonomous-driving/.

[2]

M. Kubička, A. Cela, P. Moulin, H. Mounier, and S.-I. Niculescu, “Dataset for testing
and training of map-matching algorithms,” in 2015 IEEE Intelligent Vehicles Symposium(IV), IEEE, 2015, pp. 1088–1093.

[3]

F. Yu, H. Chen, X. Wang, et al., “Bdd100k: A diverse driving dataset for heterogeneous
multitask learning,” in Proceedings of the IEEE/CVF conference on computer vision andpattern recognition, 2020, pp. 2636–2645.

[4]

OpenStreetMap, Public GPS Trajectories, https://www.openstreetmap.org/traces,
2023.

[5]

EnviroCar, Envirocar data, https://envirocar.org/analysis.html?lng=en, 2023.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

66 / 87References

References II[6]

T. Chen, S. Kornblith, M. Norouzi, and G. Hinton, “A simple framework for contrastive
learning of visual representations,” in International conference on machine learning,
PMLR, 2020, pp. 1597–1607.

[7]

M. A. Quddus, R. B. Noland, and W. Y. Ochieng, “A high accuracy fuzzy logic based
map matching algorithm for road transport,” Journal of Intelligent Transportation
Systems, vol. 10, no. 3, pp. 103–115, 2006.

[8]

P. Newson and J. Krumm, “Hidden Markov map matching through noise andsparseness,” in Proceedings of the 17th ACM SIGSPATIAL International Conference on
Advances in Geographic Information Systems - GIS ’09, Seattle, Washington: ACM Press,
2009, p. 336, isbn: 978-1-60558-649-6. doi: 10.1145/1653771.1653818. [Online].
Available: http://portal.acm.org/citation.cfm?doid=1653771.1653818 (visitedon 06/30/2022).

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

67 / 87References

Thank You!
Questions?
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

68 / 87

Misc

Table of Contents
1

Introduction, Notation, Problem Summary and Statement

2

Machine Learning Methods

3

AHP Map Matching Algorithm

4

Fuzzy Logic Map Matching Algorithm

5

Evaluation Performance

6

Preprocessing/Postprocessing

7

References

8

Misc

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

69 / 87

Misc

Miscellaneous Page

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

70 / 87

Misc

Flow of our algorithm
Input

Yes

Initial Map Matching (IMM)

Check whether the next
point is close to a junction

Map Matching at
a Junction (MMJ)

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. YoshidaNo

The correct edge isthe previously matched edge

Mitsubishi A

15/07

71 / 87

Misc

Flow of our algorithm
Input

Yes

Initial Map Matching (IMM)

Check whether the next
point is close to a junction

Map Matching at
a Junction (MMJ)

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. YoshidaNo

The correct edge isthe previously matched edge

Mitsubishi A

15/07

71 / 87

Misc

Initial Map Matching

The purpose of Initial Map Matching is to specify the correct edge that matches the first
trajectory point p0 .
Initial Map Matching takes the following steps:
1. Identify candidate edges. They are the edges that have the possibility of matching p0 .
2. Assign a weight to each candidate edge. Weights are computed by using two factors:
distance and direction.
3. Take the highest weight edge as the correct edge for p0 .

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

72 / 87

Misc

Initial Map Matching

The purpose of Initial Map Matching is to specify the correct edge that matches the first
trajectory point p0 .
Initial Map Matching takes the following steps:
1. Identify candidate edges. They are the edges that have the possibility of matching p0 .
2. Assign a weight to each candidate edge. Weights are computed by using two factors:
distance and direction.
3. Take the highest weight edge as the correct edge for p0 .

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

72 / 87

Misc

Initial Map Matching

The purpose of Initial Map Matching is to specify the correct edge that matches the first
trajectory point p0 .
Initial Map Matching takes the following steps:
1. Identify candidate edges. They are the edges that have the possibility of matching p0 .
2. Assign a weight to each candidate edge. Weights are computed by using two factors:
distance and direction.
3. Take the highest weight edge as the correct edge for p0 .

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

72 / 87

Misc

Initial Map Matching

The purpose of Initial Map Matching is to specify the correct edge that matches the first
trajectory point p0 .
Initial Map Matching takes the following steps:
1. Identify candidate edges. They are the edges that have the possibility of matching p0 .
2. Assign a weight to each candidate edge. Weights are computed by using two factors:
distance and direction.
3. Take the highest weight edge as the correct edge for p0 .

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

72 / 87

Misc

Initial Map Matching: Step 2
Let e1 , . . . , en be candidate edges obtained in Step 1.
First, we define the pairwise comparison matrix A = [αij ] for distance using hierarchicalclassification as follows:
αij
1
2
3
4
5
6
7
8
9
1/αji

range
0 ≤ dj − di ≤ 1
1 < dj − di ≤ 3
3 < dj − di ≤ 5
5 < dj − di ≤ 7
7 < dj − di ≤ 9
9 < dj − di ≤ 11
11 < dj − di ≤ 13
13 < dj − di ≤ 15
15 < dj − didj − di < 0

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. YoshidaHere,
di := dist(p0 , ei ) = inf d(p0 , x),x∈ei

dj := dist(p0 , ej ).
p

p

d

d
e

Mitsubishi A

e
15/07

73 / 87

Misc

Initial Map Matching: Step 2
Based on the matrix A, we compute weights w1dist , . . . , wndist for distance.

e1
..
.

α11
..
.

A
···
..
.

α1n
..
.

en

αn1 · · ·αnngeometric mean√n α
11 · · · α1n =: g1
..
.
√
n α
n1 · · · αnn =: gn
P
S := ni=1 gi

weightw1dist := g1 /S..
.
wndist := gn /S

The same procedure is performed for the direction data and then we get weights
w1dir , . . . , wndir for direction.
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

74 / 87

Misc

Initial Map Matching: Step 2
Based on the matrix A, we compute weights w1dist , . . . , wndist for distance.

e1
..
.

α11
..
.

A
···
..
.

α1n
..
.

en

αn1 · · ·αnngeometric mean√n α
11 · · · α1n =: g1
..
.
√
n α
n1 · · · αnn =: gn
P
S := ni=1 gi

weightw1dist := g1 /S..
.
wndist := gn /S

The same procedure is performed for the direction data and then we get weights
w1dir , . . . , wndir for direction.
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

74 / 87

Misc

Initial Map Matching: Step 2
Based on the matrix A, we compute weights w1dist , . . . , wndist for distance.

e1
..
.

α11
..
.

A
···
..
.

α1n
..
.

en

αn1 · · ·αnngeometric mean√n α
11 · · · α1n =: g1
..
.
√
n α
n1 · · · αnn =: gn
P
S := ni=1 gi

weightw1dist := g1 /S..
.
wndist := gn /S

The same procedure is performed for the direction data and then we get weights
w1dir , . . . , wndir for direction.
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

74 / 87

Misc

Initial Map Matching: Step 2
Based on the matrix A, we compute weights w1dist , . . . , wndist for distance.

e1
..
.

α11
..
.

A
···
..
.

α1n
..
.

en

αn1 · · ·αnngeometric mean√n α
11 · · · α1n =: g1
..
.
√
n α
n1 · · · αnn =: gn
P
S := ni=1 gi

weightw1dist := g1 /S..
.
wndist := gn /S

The same procedure is performed for the direction data and then we get weights
w1dir , . . . , wndir for direction.
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

74 / 87

Misc

Initial Map Matching: Step 2
Finally we define the total weight TW(ei ) for each candidate edge ei byTW(e i ) := c dist widist + c dir widir ,where c dist and c dir are coefficients reflecting the relative importance of distance anddirection, given byc distc dir

urban
0.0806
0.372

suburban
0.438
0.464

rural
0.556
0.434

The highest edge is taken as the correct edge that matches p0 .
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

75 / 87

Misc

Exmple of AHP-based map matching
Example
1 2 0.25
A = 0.5 1 0.2  .
4 5 1

p0
e1

e3
e2

Say,
d1 = dist(p0 , e1 ) = 10,
d2 = dist(p0 , e2 ) = 12,
d3 = dist(p0 , e3 ) = 3.
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

76 / 87

Misc

IMP Algorithm
Algorithm IMP Algorithm
Count = 0
if Count ≤ 3 thenrepeatFind candidate edges
Perform FIS-1 for all candidate edge
Pick candidate edge with highest FIS-1 output
if previous selected edge = current selected edge thenCount = Count + 1
end ifuntil Count = 3
end ifProceed with SMP 1
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

77 / 87

Misc

SMP-1 Algorithm
Algorithm SMP-1 Algorithm
Stay = TRUE
if Stay = TRUE thenrepeatoutput = FIS-2(current trajectory, previous edge)
if output ≥ 60 thencurrent edge = previous edge
else
Stay = FALSE
end ifuntil Stay = FALSE
end ifProceed with SMP 2
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

78 / 87

Misc

SMP-2 Algorithm

Algorithm SMP-2 Algorithm
Find candidate edges
Perform FIS-3 for all candidate edge
Pick candidate edge with highest FIS-3 output
Proceed with SMP 1

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

79 / 87

Misc

FIS Example
Denote PQ and ∆φ are the two primary input and
Z as an output that measure the likelihood of P
matched to Q
PQ = 18 ∆φ = 12
FIS have these following rules:
1. R1 : If PQ is short and ∆φ is small then thepossibility of matching P on link AB (Z) is high.
2. R2 : If PQ is long and ∆φ is large then thepossibility of matching P on link AB (Z) is low.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

80 / 87

Misc

Rule 1
Calculating the strength of Rule 1 (ω1 )
Short

1

Small

1

0.8

0.5

0

20

0

20

Figure: Membership Figure: Membership
Function of PQ
function of ∆φω1 = min(0.8, 0.5) = 0.5

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

81 / 87

Misc

Defuzzification Stage

Takagi-Sugeno-Kang Fuzzy Inference System :Output =

ω1
ω2
Z1 +
Z2
ω1 + ω2
ω1 + ω2

Where : Z1 and Z2 is an output of function based on therule. e.g:(
50, if possibility of matching is highZ=
10, if possibility of matching is low

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

82 / 87

Misc

FIS 1
Input :
1. Speed of the vehicle, v (m/s)
2. Horizontal dilution of Precission (HDOP)
3. Perpendicular Distance, PD (m)4. Heading error, HE = |θ − θ′ |Rule :
1. If v is high and HE is small then L1 is average
2. If v is high and HE is Large then L1 is low
3. If HDOP is good and PD is short then L1 is average
4. If HDOP is good and PD is long then L1 is low
5. If HE is small and PD is short then L1 is average
6. If HE is large and PD is long then L1 is low

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

Figure: FIS1 diagram

15/07

83 / 87

Misc

FIS 2
Additional input :1. ∆d = d − d2
2. HI = |θ′ − θ|
3. α and β.

Rule :
1. If α < 90 and β < 90 then L2 is high
2. If ∆d > 0 and (α ≥ 90 or β ≥ 90) then L2 is low*
3. If HI is small and α < 90 then L2 is low
4. If HI is small and ∆d ≥ 0 and (α or β ≥ 90) then L2 is low*
5. If HI is large and α < 90 and β < 90 then L2 is low
6. If HDOP is good and v is zero then L2 is high
7. If HDOP is good and ∆d < 0 then L2 is average
8. If HDOP is good and ∆d ≥ 0 then L2 is low
9. If v is high and HI is small then L2 is average
10. If HDOP is good and v is high and HI is 180o then L2 is high
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

Figure: FIS2 diagram

15/07

84 / 87

Misc

FIS 3
Additional input :1. Link Connectivity
2. Distance error, difference between distance travelledfrom last position(A) and shortest path from thelast matched position(M) to the current position(B) around the links (e.g ϵ = AB − (MO + ON))

IMP rule plus some additional rules:
1. If connectivity is low then L3 is low
2. If connectivity is high then L3 is high
3. If distance error is low then L3 is high
4. If distance error is high then L3 is low

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

85 / 87

Misc

Improvement to DBSCAN proprecessing
The DBSCAN algorithm has the 2parameters:
1. The eps parameter decides thesearch radius;
2. The min pts parameter decides
the threshold for a point to beclassified into a core point.
We developed a method to determine
the appropriate eps corresponding
each data instance. We expect thismethod is more robust than one in
the previous research, where the eps
is fixed based on specific dataset.
J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

86 / 87

Misc

Improvement to DBSCAN proprecessing

Futhermore, we propose ”2-steps DBSCAN preprocessing”:
1. The first DBSCAN with a relatively small eps mitigates stay points;
2. The second DBSCAN with s relatively big eps mitigates outliers.

J. J. Lin, T. Mochida, R. C. W. O’Neill, A. Yoshida

Mitsubishi A

15/07

87 / 87