MITSUBISHI-A project
Title:
Construction for incomplete map matching based on local and global geometries
Industrial Partner: Advanced Technology R&D Center of MITSUBISHI Electric Corp.
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, or 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, next
generation key devices, system solutions for electric power, transportation, or factory
automation and automobiles.
Industrial Mentor:
Masashi Yamazaki, Ph.D., MITSUBISHI Electric Corp.
Introduction:
One of the topics of geospatial information processing is matching between incomplete
maps to maintain geospatial information. The technology is needed for multiple mapping
systems that generate huge and/or precise maps efficiently. In general, maps generated bymultiple mapping systems are incomplete because of obstacles that hide several areas. To
generate a consistent map from the incomplete maps, suitable matching and integration
between incomplete maps should be proceeded. Figure 1 shows an example where circles
in (a) and (b) correspond to incomplete information due to the separated traffic lanes (bluelines). In Fig. 1 (c), they have been successfully merged.
One of the examples of such system is the Simultaneous Localization and Mapping(SLAM) system by multiple robots. SLAM is used for activities in spaces whose maps are notgiven, and it is currently used for cleaning robots and so on. In the case of SLAM (by multiplerobots), shapes of the environment are obtained as 3D sampling points (a so-called pointcloud). When considering to construct accurate road maps, the point clouds obtained through
SLAM are incomplete, which in turn might lead to incomplete road maps. Therefore, matching
and integration for incomplete maps are necessary to produce a complete map from SLAM
results of multiple robots.
In fact, the SLAM algorithm can collect trajectories of sensor(s) and map structures incoordinates whose origins are placed on positions of the sensor(s). Accumulated errors oflocalization cause deformations of map information. It is important to make robust algorithms
that can match and integrate incomplete maps despite of the occurrence of accumulated
errors. To build such algorithms, geometry and statistics are expected to play important roles.

Figure 1 Incomplete mapping results and their merged results(from https://www.giho.mitsubishielectric.co.jp/giho/pdf/2019/1902106.pdf)
Technical Background:The basics of matching between incomplete maps exist in a “map matching algorithm”
that estimates routes from rough trajectories by comparing them with a complete map. Usual
GPS sensors can detect their own positions, but the results are in low precision andfrequency to determine the route accurately. Map matching is an algorithm which estimatesaccurate routes from trajectories with errors and complete maps (cf. Figure 2).

Figure 2 Map matching overview (from GitHub: amillb/pgMapMatch)Map matching algorithms are made from considering not only the distance between
trajectories and roads but also graph structures. For example, the road that is far from thecurrent position can be matched as the true route when the road is connected with past andfuture routes. Therefore, several methods that use local and global geometries and/orprobabilities are proposed as map matching algorithms.
Map matching algorithms are often proposed by implementations and evaluations(bottom-up approach), and there is no best method for map matching. Matching algorithms
between incomplete maps are often made differently by different companies. In this project,
it is expected to construct a comprehensive mathematical formulation for this task based on
top-down approaches.
Expectations:
In this project, we consider how to build and evaluate matching methods between
incomplete maps based on local and/or global geometries such as order, divergence, andmetrics by beginning with traditional map matching algorithms. Especially, it is better toconsider not just the implementation, but also a comprehensive mathematical formulation toguide the implementations. For this purpose, it is expected to use topologies and so on as
new points of view for the task.
If the formulations will be made, the way to integrate matched parts also becomes ourtarget. The integration may need to consider statistics such as Bayes filtering depending on
measurement errors.
Requirements:
We assume basic knowledge of Euclidian geometry and manifold in treating geospatial
information. Additionally, knowledge of graph theory and topological geometry for global
analysis, and Riemannian and other differential geometries for local analysis would bebeneficial. Moreover, knowledge on Bayesian statistics and Bayesian filter (correspondingto map fusion), and stochastic models should be useful for the integration of matchedmaps.
Recommended Reading and References:[1] Quddus, M. A., Ochieng, W. Y., & Noland, R. B. (2007). Current map-matching algorithms fortransport applications: State-of-the art and future research directions. Transportation researchpart c: Emerging technologies, 15(5), 312-328.
[2] Chao, P., Xu, Y., Hua, W., & Zhou, X. (2020, February). A survey on map-matching algorithms.
In Australasian Database Conference (pp. 121-133). Springer, Cham.

[3] 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.
[4] Lou, Y., Zhang, C., Zheng, Y., Xie, X., Wang, W., & Huang, Y. (2009, November). Map-matching
for low-sampling-rate GPS trajectories. In Proceedings of the 17th ACM SIGSPATIAL
international conference on advances in geographic information systems (pp. 352-361)[5] Teng, W., & Wang, Y. (2019). Real-time map matching: A new algorithm integrating spatiotemporal proximity and improved weighted circle. Open Geosciences, 11(1), 288-297.