A Low-Sampling-Rate Trajectory Matching Algorithm in Combination of History Trajectory and Reinforcement Learning

doi:10.11947/j.AGCS.2016.20160046

Abstract

Abstract: In order to improve the accuracy of low frequency (sampling interval greater than 1 minute) trajectory data matching algorithm, this paper proposed a novel matching algorithm termed HMDP-Q (History Markov Decision Processes Q-learning). The new algorithm is based on reinforced learning on historic trajectory. First, we extract historic trajectory data according to incremental matching algorithm as historical reference, and filter the trajectory dataset through the historic reference, the shortest trajectory and the reachability. Then we model the map matching process as the Markov decision process, and build up reward function using deflected distance between trajectory points and historic trajectories. The largest reward value of the Markov decision process was calculated by using the reinforced learning algorithm, which is the optimal matching result of trajectory and road. Finally we calibrate the algorithm by utilizing city's floating cars data to experiment. The results show that this algorithm can improve the accuracy between trajectory data and road. The matching accuracy is 89.2% within 1 minute low-frequency sampling interval, and the matching accuracy is 61.4% when the sampling frequency is 16 minutes. Compared with IVVM (Interactive Voting-based Map Matching), HMDP-Q has a higher matching accuracy and computing efficiency. Especially, when the sampling frequency is 16 minutes, HMDP-Q improves the matching accuracy by 26%.

Key words: low-sampling-rate floating car data, trajectory matching, Markov decision process, reinforcement learning

CLC Number:

P208

SUN Wenbin, XIONG Ting. A Low-Sampling-Rate Trajectory Matching Algorithm in Combination of History Trajectory and Reinforcement Learning[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(11): 1328-1334.

References

[1] ZHENG Kai, ZHENG Yu, XIE Xing, et al. Reducing Uncertainty of Low-Sampling-Rate Trajectories[C]//Proceedings of the IEEE 28th International Conference on Data Engineering. Washington, DC, USA: IEEE, 2012: 1144-1155.
[2] 王美玲, 程林. 浮动车地图匹配算法研究[J]. 测绘学报, 2012, 41(1): 133-138. DOI: 10.13485/j.cnki.11-2089.2014.0030. WANG Meiling, CHENG Lin. Study on Map-matching Algorithm for Floating Car[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(1): 133-138. DOI: 10.13485/j.cnki.11-2089.2014.0030.
[3] 李珂, 杨杨, 邱雪松. 城市汽车导航中一种改进的D-S证据理论地图匹配算法[J]. 测绘学报, 2014, 43(2): 208-213, 220. DOI: 10.13485/j.cnki.11-2089.2014.0030. LI Ke, YANG Yang, QIU Xuesong. An Improved Map Matching Algorithm Based on D-S Evidence Theory in City Vehicle Navigation[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(2): 208-213, 220. DOI: 10.13485/j.cnki.11-2089.2014.0030.
[4] 唐炉亮, 常晓猛, 李清泉. 出租车经验知识建模与路径规划算法[J]. 测绘学报, 2010, 39(4): 404-409. TANG Luliang, CHANG Xiaomeng, LI Qingquan. The Knowledge Modeling and Route Planning Based on Taxi' Experience[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(4): 404-409.
[5] 李清泉, 黄练. 基于GPS轨迹数据的地图匹配算法[J]. 测绘学报, 2010, 39(2): 207-212. LI Qingquan, HUANG Lian. A Map Matching Algorithm for GPS Tracking Data[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(2): 207-212.
[6] 唐进君, 刘芳. 基于路径预测的不确定性推理组合地图匹配算法[J]. 测绘学报, 2010, 39(5): 546-550. TANG Jinjun, LIU Fang. A Driver Route Prediction Based Map-matching Algorithm Integrating Uncertain Reasoning[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(5): 546-550.
[7] 曾喆, 李清泉, 邹海翔, 等. 曲率积分约束的GPS浮动车地图匹配方法[J]. 测绘学报, 2015, 44(10): 1167-1176. DOI:10.11947/j.AGCS.2015.20140352. ZENG Zhe, LI Qingquan, ZOU Haixiang, et al. Curvature Integration Constrained Map Matching Method for GPS Floating Car Data[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(10): 1167-1176. DOI:10.11947/j.AGCS.2015.20140352.
[8] 唐进君, 曹凯. 一种自适应轨迹曲线地图匹配算法[J]. 测绘学报, 2008, 37(3): 308-315. DOI: 10.3321/j.issn:1001-1595.2008.03.008. TANG Jinjun, CAO Kai. An Adaptive Trajectory Curves Map-matching Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(3): 308-315. DOI: 10.3321/j.issn:1001-1595.2008.03.008.
[9] DAI Jian, DING Zhiming, XU Jiajie. Context-Based Moving Object Trajectory Uncertainty Reduction and Ranking in Road Network[J]. Journal of Computer Science and Technology, 2016, 31(1): 167-184.
[10] SCHULZE G, HORN C, KERN R. Map-Matching Cell Phone Trajectories of Low Spatial and Temporal Accuracy[C]//Proceedings of the IEEE 18th International Conference on Intelligent Transportation Systems. Washington, DC, USA: IEEE, 2015: 180-187.
[11] CHEN Ling, TANG Yanlin, LV Mingqi, et al. Partition-Based Range Query for Uncertain Trajectories in Road Networks[J]. GeoInformatica, 2015, 19(1): 61-84.
[12] DING Zhiming, YANG Bin, GüTING R H, et al. Network-Matched Trajectory-Based Moving-Object Database: Models and Applications[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(4): 1918-1928.
[13] CHIANG M F, ZHU Wenyuan, PENG W C, et al. Distant-Time Location Prediction in Low-Sampling-Rate Trajectories[C]//Proceedings of the IEEE 14th International Conference on Mobile Data Management. Washington, DC: IEEE, 2013: 350-359.
[14] LI Yang, HUANG Qixing, KERBER M, et al. Large-scale Joint Map Matching of GPS Traces[C]//Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2013: 1320-1321.
[15] CHIANG M F, LIN Y H, PENG W C, et al. Inferring Distant-Time Location in Low-Sampling-Rate Trajectories[C]//Proceedings of the 19th ACM SIGKDD international Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2013: 1234-1241.
[16] LOU Yin, ZHANG Chengyang, ZHENG Yu, et al. Map-Matching for Low-Sampling-Rate GPS Trajectories[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York, USA: ACM, 2009: 352-361.
[17] YUAN Jing, ZHENG Yu, ZHANG Chengyang, et al. An Interactive-Voting Based Map Matching Algorithm[C]//Proceedings of the 2010 Eleventh International Conference on Mobile Data Management. Washington, DC, USA: IEEE, 2010: 43-52.
[18] YANG Jian, MENG Liqiu. Feature Selection in Conditional Random Fields for Map Matching of GPS Trajectories[M]//GARTNER G, HUANG Haosheng. Progress in Location-Based Services 2014. Switzerland: Springer International Publishing, 2015: 121-135.
[19] NEWSON P, KRUMM J. Hidden Markov Map Matching through Noise and Sparseness[C]//Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York, USA: ACM, 2009: 336-343.
[20] HUNTER T, ABBEEL P, BAYEN A. The Path Inference Filter: Model-Based Low-Latency Map Matching of Probe Vehicle Data[J]. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(2): 507-529.
[21] ZHENG Yu, ZHANG Lizhu, XIE Xing, et al. Mining Interesting Locations and Travel Sequences from GPS Trajectories[C]//Proceedings of the 18th International Conference on World Wide Web. New York, USA: ACM, 2009: 791-800.
[22] BRAKATSOULAS S, PFOSER D, SALAS R, et al. On Map-Matching Vehicle Tracking Data[C]//Proceedings of the 31st International Conference on Very Large Data Bases. New York, USA: ACM, 2005: 853-864.