历史数据和强化学习相结合的低频轨迹数据匹配算法

doi:10.11947/j.AGCS.2016.20160046

测绘学报 ›› 2016, Vol. 45 ›› Issue (11): 1328-1334.doi: 10.11947/j.AGCS.2016.20160046

历史数据和强化学习相结合的低频轨迹数据匹配算法

孙文彬, 熊婷

中国矿业大学(北京)地球科学与测绘工程学院, 北京 100083

收稿日期:2016-02-01 修回日期:2016-10-01 出版日期:2016-11-20 发布日期:2016-12-03
通讯作者: 熊婷 E-mail:391074727@qq.com
作者简介:孙文彬(1977-),男,博士,副教授,研究方向为全球离散格网理论、智能计算、并行计算。E-mail:swb1996@126.com
基金资助:
国家自然科学基金（41671383）

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

SUN Wenbin, XIONG Ting

College of Geosciences and Surveying Engineering, China University of Mining and Technology(Beijing), Beijing 100083, China

Received:2016-02-01 Revised:2016-10-01 Online:2016-11-20 Published:2016-12-03
Supported by:
The National Natural Science Foundation of China (No.41671383)

摘要/Abstract

摘要： 针对低频（采样间隔大于1 min）轨迹数据匹配算法精度不高的问题，提出了一种基于强化学习和历史轨迹的匹配算法HMDP-Q，首先通过增量匹配算法提取历史路径作为历史参考经验库；根据历史参考经验库、最短路径和可达性筛选候选路径集；再将地图匹配过程建模成马尔科夫决策过程，利用轨迹点偏离道路距离和历史轨迹构建回报函数；然后借助强化学习算法求解马尔科夫决策过程的最大回报值，即轨迹与道路的最优匹配结果；最后应用某市浮动车轨迹数据进行试验。结果表明：本文算法能有效提高轨迹数据与道路匹配精度；本算法在1 min低频采样间隔下轨迹匹配准确率达到了89.2%；采样频率为16 min时，该算法匹配精度也能达到61.4%；与IVVM算法相比，HMDP-Q算法匹配精度和求解效率均优于IVVM算法，16 min采样频率时本文算法轨迹匹配精度提高了26%。

关键词: 低频浮动车数据, 轨迹匹配, 马尔科夫决策过程, 强化学习

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

中图分类号:

P208

孙文彬, 熊婷. 历史数据和强化学习相结合的低频轨迹数据匹配算法[J]. 测绘学报, 2016, 45(11): 1328-1334.

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.

参考文献

[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.

历史数据和强化学习相结合的低频轨迹数据匹配算法

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	郑晔, 郭仁忠, 马丁, 赵志刚, 李晓明. 面向地理路网的交通信号智能协同控制方法[J]. 测绘学报, 2021, 50(9): 1203-1210.
[2]	叶浩宇, 涂伟, 叶贺辉, 麦可, 赵天鸿, 李清泉. 基于深度强化学习的电动出租车运营优化[J]. 测绘学报, 2020, 49(12): 1630-1639.