MITSUBISHI-A project
Title:
Construction of metrics for map matching between travel trajectories and map graphs
Industrial Partner:
MITSUBISHI Electric Corp., Advanced Technology R&D Center.
Mitsubishi Electric, founded in 1921, is an electronical and electric equipment manufacturer,
developing products and solutions in a wide range of fields, including home appliances,industrial equipment, and space technologies. Advanced Technology R&D Center wasestablished to support the business of Mitsubishi Electric Group through the development ofa broad scope of projects covering both basic and new advanced technologies. The main
research themes include power electronics, mechatronics, satellite communications, nextgeneration key devices, system solutions for electric power, transportation, factory
automation, and automobiles.
Industry Mentor:
Masashi YAMAZAKI, Ph.D., MITSUBISHI Electric Corp.
Akinobu SASADA, MITSUBISHI Electric Corp.
Introduction:
Recently, maps utilized for navigation systems have become more precise because ofdevelopments of ADAS (Advanced Driver-Assistance Systems) and ADS (Automated DrivingSystems.) Previsouly, maps for navigation systems were stored in roadway units. Currently,maps for ADAS/ADS, called HD maps (High-Definition maps), are stored in lane units, andthe network structure of maps has become huge and very complicated (cf. Figure 1.)
If we would like to specify our position in an HD map, we need to localize our position withless than several meter accuracies. However, GPS (Global Positioning System) may havean error of several meters because of multipath errors from buildings and so on, and it ishard to localize our position in HD map in some scenes by GPS. For this reason, we need touse an expensive high-precision positioning system or inertial navigation system to localize
our position.
On the other hand, map-matching algorithms achieve such localizations in HD maps in amuch less expensive way. Map matching enables us to find the correct travel route from an
HD map even if the GPS has errors that are greater than the precision of an HD map. Suchmatching is obtained by using optimization techniques for consistency between travel routes
and candidate routes. The formulations use knowledge of mathematics like geometry orprobability theory.

Figure 1 An image of a High Definition map (from https://www.here.com/learn/blog/hereintroduces-hd-live-map-to-show-the-path-to-highly-automated-driving)Technical Background:
Map matching in this project is defined as finding the correct travel route from map andtrajectory data (cf. Figure 2). It means extracting connected sub(di)graphs as the candidates
from the map represented as (di)graphs and selecting only one route by using time series
data like position, direction, and speed.
To build a map-matching algorithm for several scenes, we need to treat not each point of
the trajectory but the trajectory itself. If we can get enough high-precision GPS data for mapmatching, map matching can be proceeded by just using the nearest neighbor search
between each point of the trajectory and map. Otherwise, such map-matching algorithms
cause failures to find the correct travel route. For this reason, previous works consider somekind of loss functions or distances between the map and trajectory itself and get the correct
travel route by minimizing the loss functions.
The potential for developments in map-matching algorithms directly corresponds to thedifficulty in the modification of loss functions. For the simplest case of map matching, it treatsonly undirected graphs as maps and 2-dimensional position series as trajectories. If we would
like to treat additional information like one-way traffic, azimuth, or speed, we need to modify
the definition of the loss function to include this information. One of our aims is to define a
new loss function that can be modified easily based on mathematics.

Figure 2 Map matching overview (from GitHub: amillb/pgMapMatch)
Expectations:
In this project, we formulate a new map-matching algorithm based on an analysis ofprevious studies about hidden Markov models and so on. In a project held last year, newmap-matching algorithms were developed based on physics or optimal transport. In thisyear’s project, it is expected to expand these methods to additional data and scenes ordevelop new methods that differ from these methods.
As the result, it is expected that students perform simulations and compare the results withprevious studies, including quantitative evaluations of the processing time and precision.
Special Requirements:
We assume basic knowledge of elementary geometry, probability, statistics, and graphtheory in treating geospatial information. Additionally, it is useful (but not required to haveexperience with graph theory (like Dijkstra’s algorithm), Bayesian statistics (like the Kalmanfilter), optimization theory, or optimal transport (like the Wasserstein distance.) In order todo simulations of this problem, students are expected to have some programming
experience (especially Python). Moreover, it will be helpful to have some knowledge ofnearest neighbor search algorithms (like k-d tree.)Recommended Reading and References:
This current survey for map-matching algorithms is good for the introduction.
[1] Chao, P., Xu, Y., Hua, W., & Zhou, X. (2020, February). A survey on map-matchingalgorithms. In Australasian Database Conference (pp. 121-133). Springer, Cham.
It is also useful to know traditional and heuristic map matching by[2] Quddus, M. A., Ochieng, W. Y., & Noland, R. B. (2007). Current map-matching algorithms
for transport applications: State-of-the art and future research directions. Transportation
research part c: Emerging technologies, 15(5), 312-328.
Some famous algorithms use hidden Markov model. It is introduced by[3] Newson, Paul, and John Krumm. "Hidden Markov map matching through noise andsparseness." Proceedings of the 17th ACM SIGSPATIAL international conference on
advances in geographic information systems. 2009,
One of the implementations is open to the public. The article is[4] Yang, C., & Gidofalvi, G. (2018). Fast map matching, an algorithm integrating hidden
Markov model with precomputation. International Journal of Geographical Information
Science, 32(3), 547-570,
and the source code is located at “https://github.com/cyang-kth/fmm.”
In other case, particle filter, which is a kind of Bayesian filter, is utilized.
[5] Wang, Xuemei, and Wenbo Ni. "An improved particle filter and its application to an
INS/GPS integrated navigation system in a serious noisy scenario." Measurement
Science and Technology 27.9 (2016): 095005.
Another case defines a kind of scoring function for map-matching.
[6] Sharath, M. N., Nagendra R. Velaga, and Mohammed A. Quddus. "A dynamic twodimensional (D2D) weight-based map-matching algorithm." Transportation Research Part C:Emerging Technologies 98 (2019): 409-432.
The final report of g-RIPS-Sendai 2022 Mitsubishi-A project should be useful.
[7] Akamatsu, T., Gress, G., Huneycutt, K., & Omura, S. (2022). g-RIPS Sendai 2022
Mitsubishi-A group final report.
https://www.racmas.tohoku.ac.jp/g-rips/pdf/MITSUBISHI-A_FinalReport.pdf