PORP: parallel optimization strategy of route planning for self-driving vehicles

doi:10.3785/j.issn.1008-973X.2022.02.014

Journal of ZheJiang University (Engineering Science)

2022, Vol. 56

Issue (2): 329-337 DOI: 10.3785/j.issn.1008-973X.2022.02.014

PORP: parallel optimization strategy of route planning for self-driving vehicles

Tian-lun DAI1(

),Bo-han LI1,*(

),Ya-lei ZANG1,Hua DAI2,Zi-qiang YU3,Gang CHEN1

1. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China
2. School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
3. School of Computer and Control Engineering, Yantai University, Yantai 264005, China

Download:

HTML

PDF(1135KB) HTML
Export: BibTeX | EndNote (RIS)

Abstract

In order to achieve the parallel optimization of route planning, and solve the problem of high response time of location-based services (LBS) caused by extensive concurrent queries during peak hours, a dual-level grid index (DLG-index) was firstly introduced, and then, based on DLG-index, a parallel optimization algorithm of route planning (PORP) was introduced. The top layer of DLG-index is a skeleton graph consisting of border nodes of the entire graph, and the bottom layer is composed of all grids partitioned by the entire graph. For a given query, the first step is to compute a global path based on the skeleton graph. Then the route planning task is divided into multiple local optimizations in grids passed by the global path. At the same time, each local optimization is maintained independently by different processors. The algorithm can optimize the planned route in real time based on varying traffic conditions. The entire optimization is implemented in several segments, which can be handled by multi-processors and achieve rapid response to massive concurrent queries. Experiments results showed that compared with CANDS algorithm, the response time of PORP was reduced by an average of 49.6% and the processing time was saved by an average of 28.5%.

Key words： parallel computing route planning continuous route planning index dynamic road network

Received: 12 July 2021 Published: 03 March 2022

CLC:

TP 311

Corresponding Authors: Bo-han LI E-mail: SX2016060@nuaa.edu.cn;bhli@nuaa.edu.cn

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Tian-lun DAI
	Bo-han LI
	Ya-lei ZANG
	Hua DAI
	Zi-qiang YU
	Gang CHEN

Cite this article:

Tian-lun DAI,Bo-han LI,Ya-lei ZANG,Hua DAI,Zi-qiang YU,Gang CHEN. PORP: parallel optimization strategy of route planning for self-driving vehicles. Journal of ZheJiang University (Engineering Science), 2022, 56(2): 329-337.

URL:

https://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2022.02.014 OR https://www.zjujournals.com/eng/Y2022/V56/I2/329

PORP：面向无人驾驶的路径规划并行优化策略

为了实现路径规划并行优化，解决基于位置的服务（LBS）在高峰时段遭遇大量路径规划的并发查询所导致的较高响应时间的问题，提出双层网格（DLG-index）索引，并基于此提出路径规划的并行算法（PORP）. 双层索引的顶层由完整路网的边界节点组成，底层由网格组成，网格由完整路网分割而来. 对于一个给定的查询，基于骨架图计算一条全局路径，然后将规划任务划分成多个局部优化任务. 每个局部优化任务对应此查询的全局路径通过的网格，同时，每个局部优化任务由不同的处理器独立维护. 算法能够基于复杂变化的路况，及时调整导航路线，整个调整过程分段实施，可以由多处理器依次协同完成，实现对海量并发查询做出快速响应. 与CANDS算法相比，PORP的响应时间平均减少了49.6%，处理时间平均减少了28.5%.

关键词： 并行计算, 路径规划, 连续路径规划, 索引, 动态路网

Fig.1 Schematic diagram of prefix path tree

Fig.2 Distributed deployment of DLG-index

Fig.3 Parallel framework of PORP

Tab.1 Road network sets

Tab.2 Index building time with different grid sizes s

Tab.3 Index maintenance time with different grid sizes s

Tab.4 Improvement ratio with different steps for slot and congestion thresholds

Fig.4 Response time with different grid sizes

Fig.5 Throughout with different response time thresholds

Fig.6 Processing time with different numbers of queries

Fig.7 Travel cost with different path lengths


[1]	GHAFOURI A, LASZKA A, DUBEY A, et al. Optimal detection of faulty traffic sensors used in route planning [C]// Proceedings of the 2nd International Workshop on Science of Smart City Operations and Platforms Engineering. New York: ACM, 2017: 1-6.

[2]	LIEBIG T, PIATKOWSKI N, BOCKERMANN C, et al Dynamic route planning with real-time traffic predictions[J]. Information Systems, 2017, 64: 258- 265 doi: 10.1016/j.is.2016.01.007

[3]	ÖZAL A, RANGANATHAN A, TATBUL N. Real-time route planning with stream processing systems: a case study for the city of lucerne [C]// Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Geo Streaming. Chicago: ACM, 2011: 21-28.

[4]	SHAO S, GUAN W, RAN B, et al Electric vehicle routing problem with charging time and variable travel time[J]. Mathematical Problems in Engineering, 2017, 2: 1- 13

[5]	TAHA A E M. Facilitating safe vehicle routing in smart cities [C]// 2017 IEEE International Conference on Communications. Paris: IEEE, 2017: 1-5.

[6]	DANIEL T. Multi-modal route planning in road and transit networks [D]. Freiburg: University of Karlsruhe, 2018.

[7]	TONG Y X, ZENG Y X, ZHOU Z M, et al A unified approach to route planning for shared mobility[J]. Proceedings of the VLDB Endowment, 2018, 11 (11): 1633- 1646 doi: 10.14778/3236187.3236211

[8]	DEMIRYUREK U, BANAEI-KASHANI F, SHAHABI C, et al. Online computation of fastest path in time-dependent spatial networks [C]// International Symposium on Spatial and Temporal Databases. Berlin: Springer, 2011: 92-111.

[9]	WANG H N, LI G L, HU H Q, et al R3: a real-time route recommendation system[J]. Proceedings of the VLDB Endowment, 2014, 7 (13): 1549- 1552 doi: 10.14778/2733004.2733027

[10]	MALVIYA N, MADDEN S, BHATTACHARYA A. A continuous query system for dynamic route planning [C]// 2011 IEEE 27th International Conference on Data Engineering. Hannover: IEEE, 2011: 792-803.

[11]	XU J J, GUO L M, DING Z M, et al. Traffic aware route planning in dynamic road networks [C]// International Conference on Database Systems for Advanced Applications. Berlin: Springer, 2012: 576-591.

[12]	ZHANG D X, YANG D Y, WANG Y, et al Distributed shortest path query processing on dynamic road networks[J]. The VLDB Journal, 2017, 26 (3): 399- 419 doi: 10.1007/s00778-017-0457-6

[13]	WANG S Z, CAO J N, YU P. Deep learning for spatio-temporal data mining: a survey [EB/OL]. [2021-07-01]. https://ieeexplore.ieee.org/document/9204396.

[14]	WANG Y S, YUAN Y, MA Y L, et al Time-dependent graphs: definitions, applications, and algorithms[J]. Data Science and Engineering, 2019, 4: 352- 366 doi: 10.1007/s41019-019-00105-0

[15]	HART P E, NILSSON N J, RAPHAEL B A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4 (2): 100- 107 doi: 10.1109/TSSC.1968.300136

[16]	刘晓倩, 张辉, 王英健基于改进RRT的路径规划算法[J]. 自动化技术与应用, 2019, 38 (5): 96- 100 LIU Xiao-qian, ZHANG Hui, WANG Ying-jian Improved path planning algorithm of RRT[J]. Techniques of Automation and Applications, 2019, 38 (5): 96- 100 doi: 10.3969/j.issn.1003-7241.2019.05.022

[17]	刘军, 冯硕, 任建华移动机器人路径动态规划有向D算法[J]. 浙江大学学报:工学版, 2020, 54 (2): 291- 300 LIU Jun, FENG Shuo, REN Jian-hua Directed D algorithm for dynamic path planning of mobile robots[J]. Journal of ZheJiang University: Engineering Science, 2020, 54 (2): 291- 300

[18]	OUYANG D, YUAN L, QIN L, et al Efficient shortest path index maintenance on dynamic road networks with theoretical guarantees[J]. Proceedings of the VLDB Endowment, 2020, 13 (5): 602- 615 doi: 10.14778/3377369.3377371

[19]	WU S W, LI D M, ZHANG G L, et al. Density-based dynamic revision path planning in urban area via VANET [C]// International Conference on Machine Learning and Intelligent Communications. Shanghai: Springer, 2016: 129-138.

[20]	DAI T L, ZHENG W C, SUN J, et al Continuous route planning over a dynamic graph in real-time[J]. Procedia Computer Science, 2020, 174: 111- 114 doi: 10.1016/j.procs.2020.06.065

[21]	HOLZER M, SCHULZ F, WAGNER D Engineering multilevel overlay graphs for shortest-path queries[J]. Journal of Experimental Algorithmics, 2009, 13: 156- 170

[22]	WANG S Z, HAO M, CHEN H, et al. Multi-task adversarial spatial-temporal networks for crowd flow prediction [C]// Proceedings of the 29th ACM International Conference on Information and Knowledge Management. 2020: 1555-1564.

[23]	WANG S Z, CAO J N, CHEN H, et al SeqST-GAN: Seq2Seq generative adversarial nets for multi-step urban crowd flow prediction[J]. ACM Transactions on Spatial Algorithms and Systems, 2020, 6 (4): 1- 24

[24]	REZAEI M, NOORI H, RAZLIGHI M M, et al ReFOCUS+: multi-layers real-time intelligent route guidance system with congestion detection and avoidance[J]. IEEE Transactions on Intelligent Transportation Systems, 2019, 22 (1): 1- 14

[25]	XIE J Y, SONG Z Y, LI Y P, et al A survey on machine learning-based mobile big data analysis: challenges and applications[J]. Wireless Communications and Mobile Computing, 2018, 8738613

[26]	LI J L, LUO G Y, CHENG N, et al An end-to-end load balancer based on deep learning for vehicular network traffic control[J]. IEEE Internet of Things Journal, 2018, 6 (1): 953- 966

[27]	JEFFREY L A, VICTOR J B A cooperative multi-agenttransportation management and route guidance system[J]. Transportation Research Part C: Emerging Technologies, 2002, 10 (5/6): 433- 454

[28]	WANG M, SHAN H G, LU R X, et al Real-time path planning based on hybrid-vanet-enhanced transportation system[J]. IEEE Transactions on Vehicular Technology, 2015, 64 (5): 1664- 1678 doi: 10.1109/TVT.2014.2335201

[29]	李博涵, 张潮, 李东静, 等支持室内障碍空间的DSP-Topk查询优化算法研究[J]. 计算机研究与发展, 2017, 54 (3): 557 LI Bo-han, ZHANG Chao, LI Dong-jing, et al A DSP-Topk query optimization algorithm supporting indoor obstacle space[J]. Journal of Computer Research and Development, 2017, 54 (3): 557 doi: 10.7544/issn1000-1239.2017.20150895

[30]	YU Z Q, YU X H, KOUDAS N, et al. Distributed processing of k shortest path queries over dynamic road networks [C]// Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. Portland: ACM, 2020: 665-679.

[31]	YUAN J, ZHENG Y, XIE X, et al. Driving with knowledge from the physical world [C]// Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego: ACM, 2011: 316-324.

[1]	Xi-yun YANG,Ya-xin LIU,Wen-bing MA,Guo-tong XING,Feng GAO. Bidding strategy of wind farm participation in frequency regulation market considering wind power uncertainty[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(4): 736-744.

[2]	He-xiang LIN,Lian-peng QIAO,Ye YUAN,Guo-ren WANG. Keyword search algorithm of large graph based on GPU[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(2): 271-279.

[3]	Si-han DONG,Jun-chang XIN,Kun HAO,Zhong-ming YAO,Jin-yi CHEN. A join query optimization algorithm in multi-blockchain environment[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(2): 313-321.

[4]	Chu-hang YANG,Shao-hui JIA,Ye-cheng MA,Jing-wei ZHU,Yong LIU,Gao-rong HAN. Three-dimensional numerical engineering simulation of oxy-fuel high alumina glass furnace[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(2): 410-418.

[5]	Juan-juan REN,Kuan LIU,Wei-hua WANG,Ying ZHANG,Ke-xin YANG,Ming-ming LIU. Evaluation of cracking condition for CRTS Ⅲ prefabricated slab track based on interval analytic hierarchy process[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(12): 2267-2274.

[6]	Qi-zhen KANG,Jing-jing LI,Yu-chao LI,Shi-yuan YAO,Yun-min CHEN. Permeability of sodium polyacrylate modified calcium bentonite in acid-base salt solution[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(10): 1877-1884.

[7]	Jun-ming WANG,Xing-ya ZHAO,Ling-hong CHEN,Li-xia HAN,Xiang GAO,Ke-fa CEN. Ammonia effect on optical properties of secondary organic aerosols[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(9): 1812-1818.

[8]	Fei WANG,Guo-fang GONG,Li-wen DUAN,Yong-feng QIN. XGBoost based intelligent determination system design of tunnel boring machine operation parameters[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(4): 633-641.

[9]	Bing YANG,Wen-bo MO,Jin-liang YAO. 3D palmprint recognition by using local features and deep learning[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(3): 540-545.

[10]	Li LONG,Shan-suo ZHENG,Yan ZHOU,Jin-chuan HE,Hong-li MENG,Yong-long CAI. Parallel study of seismic reliability analysis of water supply pipe network based on quasi-Monte Carlo method[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(2): 241-247.

[11]	Ai-min ZHOU,Cai-xia ZHOU,Jin-yan OUYANG,Shu-tao ZHANG. Model of synthetic evaluation on interface stylistic beauty based on moderately standardized of index[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(12): 2273-2285.

[12]	Liang CAI,Hong-cen ZHOU,Heng BAI,Zhen-gong CAI,Ke-ting YIN,Yi-jun BEI. Application load forecasting method based on multi-layer bidirectional LSTM and improved PSO algorithm[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(12): 2414-2422.

[13]	DING Qiang, TAO Wei-ming. Improved Tau-H strategy for four-dimensional cooperative route planning of multi-UAVs[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(7): 1398-1405.

[14]	LI Ying, YAN Guo-feng, WANG Yu, HUANG Yu-xin, DU Jian-xiang, XIE Li-juan, HE Sai-ling. Classification of tobacco aroma based on Terahertz time domain spectroscopy[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(3): 537-542.

[15]	ZHOU Jia-li, CHEN Yi-jun, WU Min. Image acquisition and preprocessing method based on FPGA monitor[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(2): 398-405.

Viewed

Full text

Abstract

Cited

Shared

Discussed