Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2022, Vol. 56 Issue (2): 329-337    DOI: 10.3785/j.issn.1008-973X.2022.02.014
计算机与控制工程     
PORP：面向无人驾驶的路径规划并行优化策略
戴天伦1(),李博涵1,*(),臧亚磊1,戴华2,于自强3,陈钢1
1. 南京航空航天大学 计算机科学与技术学院，江苏 南京 211106
2. 南京邮电大学 计算机学院，江苏 南京 210023
3. 烟台大学 计算机与控制工程学院，山东 烟台 264005
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
 全文: PDF(1135 KB)   HTML
摘要：

为了实现路径规划并行优化，解决基于位置的服务（LBS）在高峰时段遭遇大量路径规划的并发查询所导致的较高响应时间的问题，提出双层网格（DLG-index）索引，并基于此提出路径规划的并行算法（PORP）. 双层索引的顶层由完整路网的边界节点组成，底层由网格组成，网格由完整路网分割而来. 对于一个给定的查询，基于骨架图计算一条全局路径，然后将规划任务划分成多个局部优化任务. 每个局部优化任务对应此查询的全局路径通过的网格，同时，每个局部优化任务由不同的处理器独立维护. 算法能够基于复杂变化的路况，及时调整导航路线，整个调整过程分段实施，可以由多处理器依次协同完成，实现对海量并发查询做出快速响应. 与CANDS算法相比，PORP的响应时间平均减少了49.6%，处理时间平均减少了28.5%.
关键词： 并行计算;  路径规划;  连续路径规划;  索引;  动态路网    
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
收稿日期: 2021-07-12 出版日期: 2022-03-03
CLC:  TP 311  
基金资助: 国家自然科学基金资助项目(61672284，61728204)；高安全系统的软件开发与验证技术工业和信息化部重点实验室资助项目（NJ2018014）；中国学位与研究生教育学会资助项目(B-2017Y0904-162)；华为创新DBIRP项目(CCF-HUAWEI DBIR2020001A)
通讯作者: 李博涵     E-mail: SX2016060@nuaa.edu.cn;bhli@nuaa.edu.cn
作者简介: 戴天伦（1998—），男，硕士生，从事时空数据库的研究. orcid.org/0000-0001-9763-5050. E-mail: SX2016060@nuaa.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
戴天伦
李博涵
臧亚磊
戴华
于自强
陈钢

引用本文:

戴天伦,李博涵,臧亚磊,戴华,于自强,陈钢. PORP：面向无人驾驶的路径规划并行优化策略[J]. 浙江大学学报(工学版), 2022, 56(2): 329-337.

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.

链接本文:

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

图 1  前缀路径树示意图
图 2  DLG-index分布式部署
图 3  PORP并行框架
图 名称 顶点数 边数
BJ Beijing 188229 436648
NY New York 264346 733846
FLA Florida 1070376 2712798
表 1  道路网络集
图 z=60 z=100 z=140
DLG CANDS DLG CANDS DLG CANDS
BJ 27.42 8.81 39.42 19.31 48.92 36.63
NY 29.34 10.84 49.53 21.33 61.94 37.31
FLA 31.42 11.22 54.54 23.54 67.73 42.72
表 2  不同网格尺寸对索引构建时间的影响
图 z=60 z=100 z=140
DLG CANDS DLG CANDS DLG CANDS
BJ 3.76 14.43 3.76 15.43 3.66 16.43
NY 3.57 16.49 4.57 18.49 4.57 19.49
FLA 4.48 20.35 6.48 22.35 5.48 21.35
表 3  不同网格尺寸对索引维护时间的影响
设置 ${\lambda}$(BJ) $\lambda$(NY) $ \lambda $(FLA)
$ \eta $=5, $ \gamma $=1.1 1.223 1.314 1.274
$ \eta $=7, $ \gamma $=1.2 1.323 1.427 1.327
$ \eta $=9, $ \gamma $=1.3 1.374 1.322 1.482
$ \eta $=11, $ \gamma $=1.4 1.526 1.302 1.423
$ \eta $=13, $ \gamma $=1.5 1.402 1.212 1.323
表 4  不同slot步数与拥挤度阈值对改进比例的影响
图 4  不同网格尺寸对响应时间的影响
图 5  不同响应时间阈值对吞吐量的影响
图 6  不同查询数对处理时间的影响
图 7  不同路径长度对旅行代价的影响
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] 林鹤翔,乔连鹏,袁野,王国仁. 基于GPU的大图数据上的关键字检索算法[J]. 浙江大学学报(工学版), 2022, 56(2): 271-279.
[2] 董思含,信俊昌,郝琨,姚钟铭,陈金义. 多区块链环境下的连接查询优化算法[J]. 浙江大学学报(工学版), 2022, 56(2): 313-321.
[3] 吴敬理,伊国栋,裘乐淼,张树有. 高温混合障碍空间中的移动机器人路径规划[J]. 浙江大学学报(工学版), 2021, 55(10): 1806-1814.
[4] 刘洁,董献洲,韩维,王昕炜,刘纯,贾珺. 采用牛顿迭代保辛伪谱算法的舰载机甲板路径规划[J]. 浙江大学学报(工学版), 2020, 54(9): 1827-1838.
[5] 龙立,郑山锁,周炎,贺金川,孟宏立,蔡永龙. 基于拟蒙特卡罗方法的供水管网抗震可靠性分析并行化研究[J]. 浙江大学学报(工学版), 2020, 54(2): 241-247.
[6] 刘军,冯硕,任建华. 移动机器人路径动态规划有向D*算法[J]. 浙江大学学报(工学版), 2020, 54(2): 291-300.
[7] 周佳立, 陈以军, 武敏. 基于FPGA监听的图像采集与预处理方法[J]. 浙江大学学报(工学版), 2018, 52(2): 398-405.
[8] 高德东, 李强, 雷勇, 徐飞, 白辉全. 基于几何逼近法的斜尖柔性穿刺针运动学研究[J]. 浙江大学学报(工学版), 2017, 51(4): 706-713.
[9] 季长清,余胜,王宝凤,陶帅,汪祖民,王润方. 移动云计算环境下的双色反近邻查询算法[J]. 浙江大学学报(工学版), 2016, 50(7): 1330-1337.
[10] 蔡青林,陈岭,梅寒蕾,孙建伶. 基于两级过滤的时间序列近似查询[J]. 浙江大学学报(工学版), 2016, 50(7): 1290-1297.
[11] 卢帅兵,庞建民,单征,岳峰. 基于QEMU的跨平台静态二进制翻译系统[J]. 浙江大学学报(工学版), 2016, 50(1): 158-165.
[12] 胡德超, 池龙哲, 杨琼, 王敏. 水库坝区冲刷漏斗的形成机理[J]. 浙江大学学报(工学版), 2015, 49(2): 257-264.
[13] 王骕,胡浩基,于慧敏,DAMPER R I. 基于数字水印的人脸与声纹融合识别算法[J]. 浙江大学学报(工学版), 2015, 49(1): 6-14.
[14] 金苍宏,吴明晖,应晶. 一种基于上下文索引的文本匹配框架[J]. J4, 2013, 47(9): 1537-1546.
[15] 陈楠,寿黎但,陈刚,陈珂,胡天磊. 面向动态环境的移动对象自适应索引方法[J]. J4, 2013, 47(3): 442-448.