SA*：一种多线程路径规划算法

doi:10.12082/dqxxkx.2018.180019

地球信息科学学报 ›› 2018, Vol. 20 ›› Issue (6): 753-761.doi: 10.12082/dqxxkx.2018.180019

• 2017年中国地理信息科学理论与方法学术年会优秀论文专辑 • 上一篇下一篇

SA*：一种多线程路径规划算法

孙经纬¹(), 孙广中¹, 詹石岩¹, 毛睿², 周英华^1,^*()

1. 中国科学技术大学计算机科学与技术学院,合肥 230026
2. 深圳大学计算机与软件学院,深圳 518060

收稿日期:2018-01-02 修回日期:2018-03-10 出版日期:2018-06-20 发布日期:2018-06-20
通讯作者: 周英华 E-mail:sunjw@mail.ustc.edu.cn;yinghua@ustc.edu.cn
作者简介:
作者简介：孙经纬(1992-),男,博士生,主要从事高性能计算与算法优化研究。E-mail: sunjw@mail.ustc.edu.cn
基金资助:
国家自然科学基金项目（61432016、61303047）;广东省普通高校国家级重大培育项目(2014GKXM054);广东省普及型高性能计算机重点实验室（2017B030314073）

SA*: A Multi-thread Path Routing Algorithm

SUN Jingwei¹(), SUN Guangzhong¹, ZHAN Shiyan¹, MAO Rui², ZHOU Yinghua¹()

1. School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, China
2. College of Computer Science and Software Engineering, Shenzhen University, Shenzhen 518060, China

Received:2018-01-02 Revised:2018-03-10 Online:2018-06-20 Published:2018-06-20
Supported by:
National Natural Science Foundation of China, No.61432016, 61303047;Guangdong Pre-national project, No.2014GKXM054;Guangdong Province Key Laboratory of Popular High Performance Computers, No.2017B030314073

摘要/Abstract

摘要：

路径规划问题是路网交通应用中的一个基础问题。A*算法是一个求解点到点最短路径问题的高效算法。但随着路网数据规模的增长,A*难以保证求解的实时性。利用并行计算进行加速是常用的算法性能提高手段,然而A*算法是由一系列前后依赖的迭代步骤组成,因此难以进行直接的并行化。本文提出一种分段化搜索的改进A*算法（SA*）。该算法在搜索路径前先选择若干可能在最短路径上的结点作为导航点,然后多线程并行地分别求出导航点之间的最短路径,并拼接这些路径作为原问题的一个近似解。分段搜索本身可以减少路径规划的搜索空间,借助多线程并行则可以进一步提高求解速度。实验结果表明,在真实路网数据上,利用16核的机器,SA*的性能可以达到A*算法的10-30倍。

关键词: 多线程, 并行计算, 路径规划, 启发式搜索

Abstract:

Path routing problem is a fundamental problem in many applications on road networks. The A* algorithm is an efficient method to find the point-to-point path. Road networks with Cartesian coordinates can provide Euclidean distance as a heuristic function to guide the search direction of A*, then A* can simply and intuitively outperforms the classic Dijkstra's algorithm. However, Euclidean distance is a fairly relaxed lower bound of the real distance. It limits the potential of pruning more search space of A* on road networks. Higher performance is needed to fit the real-time requirement in the application on large-scale networks. Parallel computing is an effective approach to accelerate many algorithms. However, there are strong data dependencies between iterations of A*, and each iteration has little potential parallelism because of the low-dimensional property of road network. Thus, it is difficult to efficiently exploit the availability of multiple cores with the standard A* algorithm. In this paper, we propose Segmented A* (SA*) algorithm, which is more adaptable to modern multi-core CPU platform than A*. It selects some waypoints that split the required shortest path into several segments, then it searches on each segment separately and concatenates these segments as an approximate result. SA* performs better than A* on account of two factors. One is that sequential SA* can prune more search space than A*. The other is that the searches of SA* on segments can be parallelized, so SA* can make better use of multi-core CPU. The selection of waypoints has a key impact on both calculation performance and the accuracy of path. To exploit the benefit from segmented search and meanwhile reduce the performance overhead from this selection, we consider using some low-cost heuristic strategies to select the waypoints before handling each path routing sub-problem. At first, we rapidly calculate a rough path as a guidance, then select the nodes in this rough path that uniformly split the path to several segments. We can easily guarantee that each segment has the same number of nodes. This split has more possibility to lead to a balanced search space in parallel calculating each segment. In our experiments, using 16 cores, SA* can be 30 times faster than A* on a large-scale real-world road network with a loss of path accuracy less than 10%.

Key words: multi-thread, parallel computing, path routing, heuristic search, road network

孙经纬, 孙广中, 詹石岩, 毛睿, 周英华. SA*：一种多线程路径规划算法[J]. 地球信息科学学报, 2018, 20(6): 753-761.DOI:10.12082/dqxxkx.2018.180019

SUN Jingwei,SUN Guangzhong,ZHAN Shiyan,MAO Rui,ZHOU Yinghua. SA*: A Multi-thread Path Routing Algorithm[J]. Journal of Geo-information Science, 2018, 20(6): 753-761.DOI:10.12082/dqxxkx.2018.180019

图/表 10

图1

图2

图3

表1

表2

表3

图4

图5

图6

图7

参考文献 30

[1]	Dijkstra E W.A note on two problems in connexion with graphs[J]. Numerische mathematik, 1959,1(1):269-271. doi: 10.1007/BF01386390
[2]	Bellman R.On a routing problem[J]. Quarterly of applied mathematics, 1958:87-90.
[3]	Cherkassky B V, Goldberg A V, Radzik T.Shortest paths algorithms: Theory and experimental evaluation[J]. Mathematical programming, 1996,73(2):129-174. doi: 10.1007/BF02592101
[4]	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
[5]	Pohl I.Bi-directional and heuristic search in path problems[D]. Stanford: Stanford University, 1969.
[6]	Ikeda T, Hsu M Y, Imai H, et al.A fast algorithm for finding better routes by AI search techniques[C]. Vehicle Navigation and Information Systems Conference, 1994:291-296.
[7]	Brand S.Efficient obstacle avoidance using autonomously generated navigation meshes[D]. TU Delft, Delft University of Technology, 2009.
[8]	Brand S, Bidarra R.Parallel ripple search-scalable and efficient pathfinding for multi-core architectures[C]. International Conference on Motion in Games. Springer Berlin Heidelberg, 2011:290-303.
[9]	Pearl J.Heuristics: Intelligent search strategies for computer problem solving[M]. Boston: Addison-Wesley Longman Publishing Company, 1984.
[10]	Demetrescu C, Goldberg A V, Johnson D S.The shortest path problem: Ninth DIMACS implementation challenge[M]. American Mathematical Soc, 2009.
[11]	Camil D, Andrew G, David J. 9th dimacs implementation challenge - shortest paths[EB/OL]. , 2009-10-21
[12]	Ratner D, Pohl I.Joint and LPA*: combination of approximation and search[C]. Proceedings of the Fifth AAAI National Conference on Artificial Intelligence. AAAI Press, 1986:173-177.
[13]	Korf R E.Depth-first iterative-deepening: An optimal admissible tree search[J]. Artificial intelligence, 1985,27(1):97-109. doi: 10.1016/0004-3702(85)90084-0
[14]	Björnsson Y, Enzenberger M, Holte R C, et al.Fringe Search: Beating A* at Pathfinding on Game Maps[J]. CIG, 2005,5:125-132.
[15]	Goldberg A V, Harrelson C.Computing the shortest path: A search meets graph theory[C]. Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2005:156-165.
[16]	Andrew G, Renato W.Computing Point-to-Point Shortest Paths from External Memory[C]. Proceedings of the seventh International Workshop on Algorithm Engineering and Experiments, 2005. SIAM, 2005:26-40.
[17]	Geisberger R, Sanders P, Schultes D, et al.Contraction hierarchies: Faster and simpler hierarchical routing in road networks[C]. International Workshop on Experimental and Efficient Algorithms. Springer Berlin Heidelberg, 2008:319-333.
[18]	Arz J, Luxen D, Sanders P.Transit node routing reconsidered[C]. International Symposium on Experimental Algorithms. Springer Berlin Heidelberg, 2013:55-66.
[19]	Delling D, Goldberg A V, Nowatzyk A, et al.Phast: Hardware-accelerated shortest path trees[J]. Journal of Parallel and Distributed Computing, 2013,73(7):940-952. doi: 10.1016/j.jpdc.2012.02.007
[20]	Abraham I, Delling D, Goldberg A V, et al.A hub-based labeling algorithm for shortest paths in road networks[C]. International Symposium on Experimental Algorithms. Springer Berlin Heidelberg, 2011:230-241.
[21]	Botea A, Baier J A, Harabor D, et al.Moving target search with compressed path databases[C]. Proceedings of the Twenty-Third International Conference on International Conference on Automated Planning and Scheduling. AAAI Press, 2013:288-292.
[22]	Sankaranarayanan J, Alborzi H, Samet H.Efficient query processing on spatial networks[C]. Proceedings of the 13th annual ACM international workshop on Geographic information systems. ACM, 2005:200-209.
[23]	Sankaranarayanan J, Samet H, Alborzi H.Path oracles for spatial networks[J]. Proceedings of the VLDB Endowment, 2009,2(1):1210-1221. doi: 10.14778/1687627.1687763
[24]	Sun J, Sun G.SPLZ: An efficient algorithm for single source shortest path problem using compression method[J]. GeoInformatica, 2016,20(1):1-18. doi: 10.1007/s10707-015-0229-7
[25]	陆锋,周成虎,万庆.基于层次空间推理的交通网络行车最优路径算法[J].武汉测绘科技大学学报,2000,25(3):226-232. doi: 10.3321/j.issn:1671-8860.2000.03.008
	[ Lu F, Zhou C H, Wan Q.An optimum vehicular path algorithm for traffic network base on hierarchical spatial reasoning[J]. Journal of Wuhan Technical University of Surveying and Mapping, 2000,25(3):226-232. doi: 10.3321/j.issn:1671-8860.2000.03.008
[26]	李清泉,郑年波,徐敬海,等.一种基于道路网络层次拓扑结构的分层路径规划算法[J].中国图象图形学报,2007,12(7):1280-1285. doi: 10.3969/j.issn.1006-8961.2007.07.024
	[ Li Q Q, Zheng N B, Xu J H, et al.A hierarchical route planning algorithm based on multi-level topological structure of road network[J]. Journal of Image and Graphics, 2007,12(7):1280-1285. ] doi: 10.3969/j.issn.1006-8961.2007.07.024
[27]	高松,陆锋.一种基于路网等级启发式策略的路径搜索算法[J].地球信息科学学报,2009,11(2):151-156.
	[ Gao S, Lu F.A path finding heuristic algorithm for a road network hierarchy[J]. Journal of Geo-information Science, 2009,11(2):151-156. ]
[28]	刘康,段滢滢,张恒才.基于路网拓扑层次性表达的驾车路径规划方法[J].地球信息科学学报,2015,17(9):1039-1046. doi: 10.3724/SP.J.1047.2015.01039
	[ Liu K, Duan Y Y, Zhang He C.A driving route planning method based on road network topological hierarchy expression[J]. Journal of Geo-information Science, 2015,17(9):1039-1046. ] doi: 10.3724/SP.J.1047.2015.01039
[29]	Meyer U, Sanders P.Δ-stepping: a parallelizable shortest path algorithm[J]. Journal of Algorithms, 2003,49(1):114-152. doi: 10.1016/S0196-6774(03)00076-2
[30]	Madduri K, Bader D A, Berry J W, et al.Parallel Shortest Path Algorithms for Solving Large-Scale Instances[R]. Georgia Institute of Technology, 2006.

数据名	结点数	边数
USA	23 947 347	58 333 344
W	6 262 104	15 248 146
E	3 598 623	8 778 114
CAL	1 890 815	4 657 742
NE	1 524 453	3 897 636
NW	1 207 945	2 840 208

方法	分段	NW	NE	CAL	E	W	USA
A*	N/A	105	129	178	318	423	1524
SA*(line)	k=2	44	50	79	131	146	513
	k=4	22	35	39	64	64	200
	k=8	14	32	20	42	34	99
	k=16	11	33	13	39	24	72
SA*(path)	k=2	38	50	68	116	137	465
	k=4	15	22	27	46	52	169
	k=8	8	14	12	23	24	75
	k=16	5	11	6	15	14	47

方法	分段	NW	NE	CAL	E	W	USA
SA*(line)	k=2	6.5	6.4	6.5	4.5	5.1	1.9
	k=4	17.0	13.3	17.0	12.2	13.4	5.5
	k=8	36.5	26.2	36.5	23.1	30.1	12.5
	k=16	66.8	49.1	66.7	45.5	61.2	33.1
SA*(path)	k=2	3.2	1.4	3.1	1.7	2.5	1.8
	k=4	5.8	3.3	5.8	3.6	4.7	3.4
	k=8	7.7	5.2	8.2	5.5	6.9	5.3
	k=16	9.4	7.1	10.1	7.4	8.8	7.1

SA*：一种多线程路径规划算法

SA*: A Multi-thread Path Routing Algorithm

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 30

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	秦承志. 数字地形分析方法研究的维度——精准、高效、易用[J]. 地球信息科学学报, 2020, 22(4): 720-730.
[2]	王浩, 王含宇, 杨名宇, 许永森. Retinex图像增强在GPU平台上的实现[J]. 地球信息科学学报, 2019, 21(4): 623-629.
[3]	潘淼鑫, 林甲祥, 陈崇成, 叶晓燕. 基于C-SOM和Spark的并行空间离群挖掘方法及应用[J]. 地球信息科学学报, 2019, 21(1): 128-136.
[4]	邱强, 秦承志, 朱效民, 赵晓芳, 方金云. 全空间下并行矢量空间分析研究综述与展望[J]. 地球信息科学学报, 2017, 19(9): 1217-1227.
[5]	周恩波, 毛善君, 李梅, 孙振明. GPU加速的改进PAM聚类算法研究与应用[J]. 地球信息科学学报, 2017, 19(6): 782-791.
[6]	刘洋, 关庆锋. 景观指数的并行计算方法[J]. 地球信息科学学报, 2017, 19(4): 457-466.
[7]	江岭, 王春, 赵明伟, 杨灿灿. 面向数据传输的地理栅格数据快速压缩方法[J]. 地球信息科学学报, 2016, 18(7): 894-901.
[8]	沈占锋, 李均力, 于新菊. 基于协同计算的白洋淀湿地时序水体信息提取[J]. 地球信息科学学报, 2016, 18(5): 690-698.
[9]	李梦雅, 王军, 沈航. 洪灾应急疏散路径规划算法优化[J]. 地球信息科学学报, 2016, 18(3): 362-368.
[10]	刘康, 段滢滢, 张恒才. 基于路网拓扑层次性表达的驾车路径规划方法[J]. 地球信息科学学报, 2015, 17(9): 1039-1046.
[11]	刘扬, 付征叶, 郑逢斌. 高分辨率遥感影像目标分类与识别研究进展[J]. 地球信息科学学报, 2015, 17(9): 1080-1091.
[12]	王春, 江岭, 陈泰生, 杨灿灿. 基于Pfafstetter规则的流域编码算法并行化方法[J]. 地球信息科学学报, 2015, 17(5): 556-561.
[13]	刘军志, 朱阿兴, 秦承志, 江净超, 朱良君, 沈琳. 论地理规律对流域过程模拟并行计算的指导作用[J]. 地球信息科学学报, 2015, 17(5): 506-514.
[14]	任沂斌, 陈振杰, 程亮, 李满春, 骈宇哲. 采用动态负载均衡的LiDAR数据生成DEM并行算法[J]. 地球信息科学学报, 2015, 17(5): 531-537.
[15]	艾贝贝, 秦承志, 朱阿兴. 栅格地理计算并行算子对区域计算算法并行化的可用性分析——以多流向算法为例[J]. 地球信息科学学报, 2015, 17(5): 562-567.