Map matching algorithms for intelligent transportation system

• Main Author: Hou, Xiangting
• Other Authors: Cai Wentong
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2021
• Subjects: Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/148923
• Institution: Nanyang Technological University

Map matching algorithms for route inference and vehicle localization are essential for Intelligent Transportation System (ITS) applications to reduce traffic congestion and accidents. Currently, the Global Positioning System (GPS) is widely used to obtain the absolute positions of vehicles. When the GPS has high measurement frequency, the travelling routes of vehicles can be inferred from the GPS positions. However, since the errors of GPS measurements can be large and the sampling rate can be low, these increase difficulties for route inference and vehicle localization. In this thesis, map matching algorithms for route inference and vehicle localization given GPS measurements are investigated. For route inference, an opportunistic online map matching algorithm is firstly proposed. Unlike the existing online map matching algorithms which experience an inference delay between the GPS measurement and the inferred travelling route, the opportunistic algorithm is able to generate an immediate route inference when a new GPS measurement becomes available. In addition, in case when the opportunistic strategy produces an improper traveling route, a rollback mechanism that is able to correct the already inferred route is employed. The proposed algorithm is evaluated using the real dataset containing GPS trajectories. The experimental results show that the proposed algorithm outperforms the existing algorithms in terms of inference accuracy. More importantly, the proposed algorithm can yield much shorter inference delay and requires less execution time, which are critical for many real-time ITS applications. Secondly, existing map matching algorithms usually adopt a driving cost model, which is formulated by considering travelling features and driving preferences (referred to as weights), to determine a travelling route. In general, the weights are estimated either empirically or through data-driven approaches. The empirical setting approaches determine the weights based on specific driving cost models. However, the weights need to be re-estimated empirically when the driving cost models are changed. Alternatively, the data-driven approaches determine the weights from the selected historical routes of vehicles. However, estimation bias may be introduced due to inappropriate routes selection. To decrease the estimation bias, a distribution-based weights estimation approach is proposed, where weights are estimated by inferring their distributions through Bayesian inference, considering the traces generated from the drivers in a city scale. Then, a sampling-based strategy is adopted to determine the values of the weights from their distributions. Experiments are conducted to assess the map matching accuracy by comparing it with empirical setting and data-driven approaches. The experimental results show that the proposed approach is able to achieve higher map matching accuracy than the empirical setting and data-driven approaches. For vehicle localization, approaches based on Vehicle-to-Vehicle (V2V) communication techniques are investigated to localize the target vehicle by leveraging the state information of its nearby vehicles. To determine the position of the target vehicle, most of the existing works need a large search space. This inevitably leads to large computational overheads. In addition, the measurement errors of state information can be large due to the external conditions. Therefore, the estimated position of the target vehicle may largely deviate from the real position. In this thesis, an efficient and error-tolerant target vehicle localization approach is proposed to increase the localization efficiency and accuracy even in the presence of large measurement errors. Unlike the existing approaches, a pruning-based strategy is proposed to prune the search space for the position of the target vehicle by considering the relative positions of its nearby vehicles. To determine the position of the target vehicle, a displacement-based selection strategy is also proposed to reduce the influence of the measurement errors of state information. Experiments are conducted to assess the localization accuracy and efficiency by comparing it with the state-of-the-art approaches. The experimental results show that compared with the existing approaches, the proposed approach is able to achieve higher localization efficiency and accuracy even with large measurement errors. Similarly, localization approaches based on V2V communication techniques are also investigated to localize the nearby vehicles detected by a target vehicle. Different from the localization for the target vehicle, which is a self-localization process by using the state information of the nearby vehicles, the localization for the nearby vehicles is not processed by the vehicle itself. The geometry and trajectory information of the nearby vehicles are usually considered as the state information for localization in the existing works. However, the diversity of the geometry information and insufficiency of the trajectories of the nearby vehicles may restrict the application of the existing localization approaches. In this thesis, a Bayesian-based localization approach is proposed to estimate the absolute positions of the nearby vehicles through incorporating the GPS measurements and relative positions. Different from the existing works, the proposed approach can be applied when the geometry information is diverse and the trajectories of the nearby vehicles are insufficient. The proposed approach is evaluated in terms of the localization accuracy based on a real dataset containing the trajectories of vehicles. The experimental results show that the proposed approach is able to achieve higher localization accuracy compared with the GPS measurements. In summary, the major contributions of this thesis are: (1) An online map matching algorithm that reduces inference delays; (2) A distribution-based weights estimation approach that decreases the estimation bias; (3) An efficient, V2V-based target vehicle localization approach that tolerates measurement errors; and (4) A Bayesian-based nearby vehicle localization approach that can be applied when the geometry information is diverse and the trajectories of the nearby vehicles are insufficient.