GCN Deep Search Method for Optimal Path of Dynamic Road Network

doi:10.3778/j.issn.1673-9418.2105035

Abstract

Abstract: The optimal path search and planning in the road network has received widespread attention as an important part of location-based services (LBS). Positioning technologies such as radio frequency identification (RFID) have brought a lot of traffic data, which has become the foundation and challenge of research. Travel scenarios in cities are very sensitive to the dynamic changes of the road network. At the same time, the traffic situation in the city is complex and changeable, and the real road network and the trajectories of moving objects contain rich temporal and spatial semantic information. These are difficulties faced by the optimal route search in the road network. In response to these challenges, after analyzing the deficiencies of existing algorithms, a machine learning model GCN-Search based on graph convolutional networks for deep search is proposed, with reference to the heuristic idea of A* algorithm. Firstly, the model uses the spatio-temporal graph convolutional network to aggregate the spatio-temporal information of adjacent areas and past periods to model the recent dynamic changes of the road network on which urban travel depends. Secondly, the model expands the search depth, defines the depth evaluation value of the node, and uses a neural network to replace the artificially designed evaluation function to search for nodes that are conducive to the overall optimal path until the final path is generated. Comparative experiments on the RFID dataset provided by a traffic management bureau show that the GCN-Search algorithm can effectively use the temporal and spatial semantic information of RFID data, and can improve the accuracy of the optimal route search for short-term travel on the dynamic road network.

Key words: graph convolution, optimal path, A* algorithm, radio frequency identification (RFID), spatio-temporal graph convolution

摘要： 路网中的最优路径搜索与规划作为位置服务中重要部分受到广泛关注，射频识别技术（RFID）等技术带来的大量交通数据成为了研究的基础与挑战。城市中出行场景对路网动态变化非常敏感，同时城市复杂多变的交通情况、真实路网与移动对象轨迹丰富的时空语义信息，都是动态路网中的最优路径搜索面临的难题。针对这些挑战，在分析现有算法不足的基础上，参考A*算法启发式思想，提出一种基于图卷积网络进行深度搜索的机器学习模型GCN-Search。模型首先通过时空图卷积网络，聚合相邻区域与过往时段的时空信息，对城市出行所依赖的路网近期动态变化进行建模；其次扩展路径搜索的深度，定义节点的深度估价值，并使用神经网络替代人工设计的估价函数，搜索利于路径整体最优的节点，直到生成最终路径。在某交管局提供的RFID数据集上进行的对比实验表明，GCN-Search算法可以有效利用RFID数据中的时空语义信息，提升动态路网出行的最优路径搜索的准确率。

关键词: 图卷积, 最优路径, A*算法, 射频识别技术（RFID）, 时空图卷积

FEI Ke, QIN Xiaolin, CHI Heyu, LI Tang. GCN Deep Search Method for Optimal Path of Dynamic Road Network[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(1): 116-126.

费珂, 秦小麟, 迟贺宇, 李瑭. 面向动态路网的最优路径GCN深度搜索方法[J]. 计算机科学与探索, 2023, 17(1): 116-126.

References

[1] BASIRI A, LOHAN E S, SILVA P F E, et al. Overview of positioning technologies from fitness-to-purpose point of view[C]//Proceedings of the 2014 International Conference on Localization and GNSS, Helsinki, Jun 24-26, 2014. Piscata-way: IEEE, 2014: 1-7.
[2] BAO J, ZHENG Y, MOKBEL M F. Location-based and preference-aware recommendation using sparse geo-social net-working data[C]//Proceedings of the 20th International Con-ference on Advances in Geographic Information Systems, Redondo Beach, Nov 7-9, 2012. New York: ACM, 2012: 199-208.
[3] SU K H, LI J, FU H B. Smart city and the applications[C]//Proceedings of the 2011 International Conference on Elec-tronics, Communications and Control, Ningbo, Sep 9-11, 2011. Piscataway: IEEE, 2011: 1028-1031.
[4] QURESHI K N, ABDULLAH A H. A survey on intelligent transportation systems[J]. Middle-East Journal of Scientific Research, 2013, 15(5): 629-642.
[5] GIANNOTTI F, NANNI M, PINELLI F, et al. Trajectory pattern mining[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, Aug 12-15, 2007. New York: ACM, 2007: 330-339.
[6] 刘新宇, 谭力铭, 杨春曦, 等. 未知环境下的蚁群-聚类自适应动态路径规划[J]. 计算机科学与探索, 2019, 13(5): 846-857.
LIU X Y, TAN L M, YANG C X, et al. Self-adjustable dyna-mic path planning of unknown environment based on ant colony-clustering algorithm[J]. Journal of Frontiers of Com-puter Science and Technology, 2019, 13(5): 846-857.
[7] MIKOLOV T, KOMBRINK S, BURGET L, et al. Extensions of recurrent neural network language model[C]//Proceedings of the 2011 IEEE International Conference on Acoustics, Speech, and Signal Processing, Prague, May 22-27, 2011. Piscataway: IEEE, 2011: 5528-5531.
[8] 赵婷婷, 孔乐, 韩雅杰, 等. 模型化强化学习研究综述[J]. 计算机科学与探索, 2020, 14(6): 918-927.
ZHAO T T, KONG L, HAN Y J, et al. Review of model-based reinforcement learning[J]. Journal of Frontiers of Com-puter Science and Technology, 2020, 14(6): 918-927.
[9] SCARSELLI F, GORI M, TSOI A C, et al. The graph neural network model[J]. IEEE Transactions on Neural Networks, 2008, 20(1): 61-80.
[10] YAN S J, XIONG Y J, LIN D H. Spatial temporal graph convolutional networks for skeleton-based action recognition[C]//Proceedings of the 32nd AAAI Conference on Artifi-cial Intelligence, the 30th Innovative Applications of Artifi-cial Intelligence, and the 8th AAAI Symposium on Educa-tional Advances in Artificial Intelligence, New Orleans, Feb 2-7, 2018. Menlo Park: AAAI, 2018: 7444-7452.
[11] CHAUDHARY A, MITTAL H, ARORA A. Anomaly detec-tion using graph neural networks[C]//Proceedings of the 2019 International Conference on Machine Learning, Big Data, Cloud and Parallel Computing, Faridabad, Feb 14-16, 2019. Piscataway: IEEE, 2019: 346-350.
[12] WANG F S, LIU P Y. Temporal management of RFID data[C]//Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Aug 30-Sep 2, 2005. New York: ACM, 2005: 1128-1139.
[13] JEFFERY S R, GAROFALAKIS M N, FRANKLIN M J. Adaptive cleaning for RFID data streams[C]//Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Sep 12-15, 2006. New York: ACM, 2006: 163-174.
[14] XU H, DING J, LI P, et al. An improved SMURF scheme for cleaning RFID data[J]. International Journal of Grid and Utility Computing, 2018, 9(2): 170-178.
[15] 刘云恒, 刘耀宗, 张宏. 一种不确定RFID数据流清洗策略[J]. 计算机科学, 2016, 43(S2): 482-485.
LIU Y H, LIU Y Z, ZHANG H. Uncertain RFID data stream cleaning strategy[J]. Computer Science, 2016, 43(S2): 482-485.
[16] BIRANT D, KUT A. ST-DBSCAN: an algorithm for clus-tering spatial-temporal data[J]. Data & Knowledge Enginee-ring, 2007, 60(1): 208-221.
[17] CAI M, WANG S, SHEN X, et al. A scheme for anomalous RFID trajectory detection based on improved clustering algo-rithm under digital-twin-driven[C]//Proceedings of the 16th EAI International Conference on Mobile and Ubiquitous Sys-tems: Computing, Networking and Services, Houston, Nov 12-14, 2019. New York: ACM, 2019: 126-134.
[18] ZHANG J B, ZHENG Y, QI D K. Deep spatio-temporal residual networks for citywide crowd flows prediction[C]//Proceedings of the 31st AAAI Conference on Artificial Intel-ligence, San Francisco, Feb 4-9, 2017. Menlo Park: AAAI, 2017: 1655-1661.
[19] QIAO S L, SUN R C, FAN G P, et al. Short-term traffic flow forecast based on parallel long short-term memory neural network[C]//Proceedings of the 2017 8th IEEE International Conference on Software Engineering and Service Sciences, Beijing, Nov 24-26, 2017. Piscataway: IEEE, 2017: 253-257.
[20] 徐冰冰, 岑科廷, 黄俊杰, 等. 图卷积神经网络综述[J]. 计算机学报, 2020, 43(5): 755-780.
XU B B, CEN K T, HUANG J J, et al. A survey on graph convolutional neural network[J]. Chinese Journal of Com-puters, 2020, 43(5): 755-780.
[21] YU B, YIN H T, ZHU Z X. Spatio-temporal graph convo-lutional networks: a deep learning framework for traffic forecasting[C]//Proceedings of the 27th International Joint Conference on Artificial Intelligence, Stockholm, Jul 13-19, 2018. San Francisco: Morgan Kaufmann, 2018: 3634-3640.
[22] WANG J Y, WU N, ZHAO W X, et al. Empowering A* search algorithms with neural networks for personalized route recom-mendation[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Anchorage, Aug 4-8, 2019. New York: ACM, 2019: 539-547.
[23] NANNICINI G, DELLING D, LIBERTI L, et al. Bidirec-tional A* search for time-dependent fast paths[C]//LNCS 5038: Proceedings of the 7th International Conference on Experi-mental Algorithms, Provincetown, May 30-Jun 1, 2008. Berlin, Heidelberg: Springer, 2008: 334-346.
[24] DEMIRYUREK U, BANAEI-KASHANI F, SHAHABI C. A case for time-dependent shortest path computation in spa-tial networks[C]//Proceedings of the 18th SIGSPATIAL Inter-national Conference on Advances in Geographic Information Systems, San Jose, Nov 3-5, 2010. New York: ACM, 2010: 474-477.
[25] LI X J, MA Y D, FENG X W. Self-adaptive autowave pulse-coupled neural network for shortest-path problem[J]. Neuro-computing, 2013, 115: 63-71.
[26] PANOV A I, YAKOVLEV K S, SUVOROV R. Grid path planning with deep reinforcement learning: preliminary results[J]. Procedia Computer Science, 2018, 123: 347-353.
[27] SUDHOLT D, THYSSEN C. Running time analysis of ant colony optimization for shortest path problems[J]. Journal of Discrete Algorithms, 2012, 10: 165-180.
[28] DAUPHIN Y N, FAN A, AULI M, et al. Language model-ing with gated convolutional networks[C]//Proceedings of the 34th International Conference on Machine Learning, Syd-ney, Aug 6-11, 2017. New York: ACM, 2017: 933-941.
[29] MONTI F, BOSCAINI D, MASCI J, et al. Geometric deep learning on graphs and manifolds using mixture model CNNS[C]//Proceedings of the 30th IEEE Conference on Computer Vision and Pattern Recognition, Honolulu, Jul 21-27, 2017. Piscataway: IEEE, 2017: 5115-5124.